Sunday, March 27, 2005

Last night I dreamt of trees...

of data, trees of reality.

To begin, yesterday I spent a good part of the day working on my latest project which combines learning Python and brushing up on some basic data structures, such as Binary Trees. Maybe "brushing up" isn't a good way to describe my intentions. I am not satisfied with knowing that I can code up a Binary Tree whenever I care to. What I am looking for is a visceral, deep, intuitive understanding.
I coded up an AVL Tree which is a balanced Binary Tree. In order to test the tree, I had to come up with some specific values to insert and then determine the resulting tree. This work was done, not on a computer, but with pen and paper. After several hours of sketching trees, I was suddenly struck with the limitation of the Binary Tree. As the tree is traversed from root to leaf, branches of the tree are eliminated from consideration. All that matters are the options that lay ahead. This is what makes Binary Trees so powerful for searching, but not so great for modeling activities. In real life, branches that connect nodes of existence come and go, seemingly at random. Nodes are connected and removed due to past-events and probablities. We seem to have the ability to skip around the tree of reality, to teleport amongst its various nodes.
But reality is a Binary Tree. Consider the effect of time on reality.
Time delimits and defines reality. Choices are made, paths are taken. We don't have to concern ourselves with options on paths we are not on. Reality is a Binary Tree, could you imagine otherwise? The choices we make resolve to a path, which in turn resolves to a line. The time-line.
I looked at the smallest of Binary Trees, three nodes, one of which was the parent with its two children, and saw infinite possibilities. I looked at a main branch of a large tree and, even with all of its sub-trees to consider, all that came to mind was the removal of possibility, the refinement of the real.
So I went to sleep last night and I dreamt of trees. Elements of life, connected by branches now seen.

Wednesday, March 02, 2005

Temporal Anamolies

My favorite StarTrek NG plots involve "temporal anamolies" in which the time-line is disrupted and the crew of the Enterprise is plunged into the grips of an alternate reality. In real life, temporal anamolies do exist, in multi-threaded software applications.
The most fundamental building-block of computer algorithms is the sequential execution of code. Code is always executed sequentially for each "unit of execution" in a computer progam. A unit of execution in a computer program is known as a thread.
A thread is a time-line in code, a unit of reality if you will. Maybe this is why programming with multiple threads seems so odd to me.
Operations on threads involve things like putting threads to sleep, which is equivalent to suspending time. Threads are "blocked" which is like having time run into a log-jam. A use for "blocking" is to make a thread wait so that it may "join" with another thread (time-line).
Note that other forms of reality such as state and data (which is like matter), are accessible by all threads in a program. Therefore a protocol has to exist between threads to ensure that time-lines don't corrupt matter. For example, you would not want to go back in time and marry your parent (sorry for the visual).
Multi-threaded programs have thier own set of common problems. One is "dead-lock" when time-lines attempt to resolve conflicts over matter access and effectively block each other out. The other problem is known as a "race-condition" which is where one time-line is dependent on the actions of another time-line.
I blogged about object-orientation in Hammer Of The Gods where I made the case that every "thing" can be classified as an object. None of the OO languages I use, effectively model threads. Instances of objects have scoped life-times. Objects are just "matter" that exist on the time-line. Threads are the time-line. Threads transcend objects.
I have two dark visions regarding threads. One vision is of a thread, endlessly spinning through time, its time-line eternal. All context and state of interest long-since extinguished. This happens, which is why the Windows Task Manager is a handy tool. The seconds it takes to launch the tool and shut-down the errant task are many eternities to a lost thread.
The other vision is nightmare involving the use of garbage-collected or reference-count-based memory management. I see a thread, drifting through an empty, irrelevant universe, holding reference to an irrelevant object. Partners in the void. Neither able to release one another from futility. Neither able to redeem the others existence.