Program Execution as a Living Tree

Dated: 

early 1963

In the first half of 1963, Dijkstra described the execution of a program as a living “tree” that can grow “branches” and “twigs”. As the tree gets older — that is, as the execution of the program progresses — branches and twigs can fall off the tree, and others can grow in their place. Dijkstra used the metaphor of the living tree to unify three seemingly disparate topics: dynamic memory management, subroutine invocations, and multiprogramming.

The tree contains local parts which resemble “contexts” of program execution. A subroutine invocation, for example, corresponds to a local part of the tree which we call a subtree. That subtree is connected via its root to the larger, encompassing, tree; that is, to its surrounding “environment” that invoked the subroutine. When the surrounding environment (Context A) invokes the subroutine, a new and local environment (Context B) is created. Dijkstra stressed the importance of formulating the contexts independently of each other (— that is, of working modularly).

The underlying “total tree” resembles the complete memory of the bare computing machine. Working modularly with subtrees allows the programmer to step away from the machine and to focus on his programming problem. One way to do the latter effectively, is to allow the programmer to dynamically allocate data whenever he feels this is necessary. Programming freedom was dear to Dijkstra.

Mathematically, Dijkstra defined his twigs and branches in terms of “vectors”, “base vectors”, and other concepts borrowed from algebra. A vector corresponds to a number of consecutive physical memory locations (— that is, to a dynamically allocated array). Each vector has a “length”, a “begin address”, and a “type”. The type characterizes the kind of elements that are stored in the vector. Each vector “leans” on a “base” in a “base vector”. The base encodes the length, the begin address, and the type of the leaning vector.

Twigs and branches are homogenous vectors. A twig is a vector of elements of elementary type (i.e. the elements are not bases). A branch is a base vector  (i.e. a vector of bases). Each element in a branch thus refers to another vector, which leans on the branch.

Each vector in Context B either leans on another vector in Context B or on an “implicit base” that is only explicit in the surrounding environment (Context A). More generally, twigs and branches in Context B rely on some formal names that only have concrete names in Context A. Contexts are thus not “self contained”; they depend on the specification of a number of parameters that are only known in the surrounding context.

To enhance the collaboration between a context, on the one hand, and twigs and branches, on the other hand, Dijkstra introduced a new type of vector: the “parameter vector”. The parameter vector is heterogeneous. Its first element contains the implicit base (e.g. of Context B), its second element contains the value of the program counter (e.g. upon subroutine invocation), its third element contains a value (e.g. of the first parameter of the to-be-invoked subroutine), and so on. A parameter vector is also called a “parameter branch”, as opposed to a regular branch.

Towards the end of his exposition, Dijkstra discussed how twigs, branches, and parameter branches can be mapped onto the bare machine, and, specifically, onto the fast core storage and the slow drum storage of his computer.

Having sketched some parts of Dijkstra's living tree metaphor here, I refer to his Dutch text (EWD 41) for further details.

Tags: