To Iterate is Human, to Recurse, DivineJames O. Coplien, Bell LabsC++ Report 10(7), July/August 1998, pp. 43  51
IntroductionAlexander's process for applying patterns can be thought of as iterative or recursive, but the recursive perspective yields more insights into the geometric fruits of a pattern language. Each pattern works with finer structure than the one before it, preserving the overall structure of the whole. The result is fractal in nature. Alexander's later work, to be described in the forthcoming Nature of Order, more consciously aspires to this fractal nature. This month's title comes from another one of those clever quotes that are thrown around our industry, variously attributed to L. Peter Deutsch and Robert Heller. Indeed, mathematicians and computer scientists have always been intrigued with the "divinity," or at least the beauty of recursion. Strangely enough, recursion ties directly into our discussion on spatial metaphors for software. In the past two issues of the Column Without a Name, we've sought beauty in the structure of the code itself, and in the structure of distributed objects. Sometimes the structure of largely spatial programs could easily be divined in the code, particularly for distributed programs. Beauty, symmetry, and geometry are often less forthcoming in procedural code. But as we showed in the March 1998 article [Coplien1998b], using techniques like program visualization, we can find beauty by unrolling time into space. This process seems tightly linked to algorithmic and structural recursion in programs.
Beauty in TextA typical reaction to my columns of the past two months has been, "You certainly don't mean there's beauty in the text itself!" While people liked the program visualization of Jerding et al., and liked what it might portend for patterns, they felt the textual geometries were too base and too simple. If software is literaturea stretch for many readers in itselfisn't the beauty in the semantics rather than in the form? When we read a poem, do we look at the indentation, or do we look for the deep meaning intended by the poet? Richard Gabriel recently gave a talk at Warren Wilson College showing that Alexander's structural properties can be used to gauge the beauty in, of all things, English language poetry. Poetry has written structure on the page and phonetic structure as it is spoken. He has found most of Alexander's structural properties in some of the great poems of English literatureand he has found, with corroboration from poet colleagues, that the presence of strong centers and properties that map directly onto geometry correspond to beautiful poetry. And he notes that "[t]here are now poets in the land who are looking for centers, Gradients, Contrast, Deep Interlock and Ambiguity, etc., using the Alexandrian terminology."
Maybe we should take this geometryoftext thing
seriously. After all, the textual beauty of the code fits
some developers' intuitions about the overall quality of
the systems they are building. Consider this excerpt from a
letter from Peter Shillan (
I like to make my software "look" good. That is, if my object model has lines which cross over, I tend to take marks off and look for another way of laying it out or doing it a bit better so I can eliminate such things as much as possible. I like my class hierarchies to have a nice shape because I find from my own experience that if they don't, I've usually made a wrong decision about where to put certain properties  i.e. wrongly subclassing. Let's attack this issue by investigating the way we think about programming and how we capture those thoughts as programs.
Time and SpaceMost introductory computer science curricula teach programmers that there are two kinds of memory: instructions (or control) and data. This dichotomy is fundamental to the Von Neumann computation model and underlies almost all contemporary programming languages. Data is about structure; instructions (control) are about time. The program counter visits instruction after instruction in turn. The locality of visitation (or lack thereof) sometimes leads to a spatial structure in its own right. Functions are locales of control. So are loopschunks of time folded onto each other and expressed in compact form. The previous Column Without a Name offered visualizations of the runtime behavior of an objectoriented program, a way of viewing time in a purely spatial way. Programming languages do what they can to organize linear time into linear space, but control structure still has a time element that clouds our thinking in ways that data structure doesn't. Can we go even further? There are programming paradigms that do this and there are programming languages, like Miranda [Turner1985], that let one express structures in that paradigm. Consider the Von Neumann expression of the natural numbers:
int i = 1; vector<unsigned int> nats; for (;;) { nats.push_back(i); i++; } where time follows the lefttoright spatial progression of the code, and then loops through again. In Miranda, the analogous code would be:
or, more compactly,nats = [1, 2, 3..]
Time has completely disappeared; all we have is the spatial depiction of (the first part of) an infinite series. Spatially, the enumeration extends from left to right as an infinitely long line. This isn't just a notation trick, but it's fundamental to the Miranda computational model. For example, consider the C++ code:nats = [1 ..]
Try drawing a picture of this program. Does your picture capture what the Fibonacci series looks like in space? If it does, does it correspond in any way to the structure of the C++ source code?void main() { vector<unsigned int> fibs; fibs.push_back(1); fibs.push_back(1); for (int i = 3; ; ) { fibs.push_back( fibs[i1] + fibs[i2]); i++; } } In Miranda, the code would use list comprehension: fib = [a(a,b) < (1,1),(b,a+b)..]
And in Haskell, one might write it this way
( fib = 1:1:[ a+b  (a,b) < zip fib (tail fib) ] Try drawing these. Depicted this way, the series has structure: you can actually "draw" the structure of the Fibonacci series. The picture depicts not only the structure of the series, but the structure of the code as well, both in Miranda: and in Haskell [Haskell]. Of course, the advantage of the Miranda and Haskell code over the C++ code is that they're computable: I can ask for
and get an answer. The transliterated C++ equivalent never finishes computing the infinite series.fib 10 Through recursive constructs, Miranda can represent infinite series in finite space. The time element of computation is rendered completely in space. If geometry is important to beauty, and beauty is important to programming, then functional and applicative languages might point the way to more natural and perhaps more powerful programming environments. Might this be applicable only to degenerate mathematical problems? No, graphical animation systems, parsers, and a host of other systems have been rendered in functional languages, but it would be too ambitious to lay the groundwork here in this column. To understand recursion, you first have to understand recursion.
Removing TimeWe've focused time and again on the problematic element of time in Von Neumann programming, because it introduces structure that isn't purely spatial in nature. For example, consider the simple definition: square(x) = x × x Even though it's mathematical, we think of this statement programatically: define the function square(x) to be the process of getting the value of x, then seeing that we're going to multiply by another value, which is x again, so get its value again, and then do the multiplication. This is reminiscent of a process that would be built by a sequential machine, with states, and a clock to sequence the machine through its statesa very basic Von Neumann machine. It would be nicer if we good just get the value of x, give it to square, and have the whole thing over with in an instant without any steps or "clock ticks." This becomes an important concern for managing the environments in functional programming languages [Turner1979]. A language like C++ has multiple contexts called scopes, and names are bound to values in C++ through function calls, using a stack, in a way that's familiar to all procedural programmers. In a Lisp program, contexts are lists of name/value pairs rather than a stack structure. In pure applicative programming languages, there are no side effects or assignment, so the question of rebinding takes on a whole different meaning. What we want to do is just "wire the program together"identifiers are just convenient aliases for values, they aren't bound by assignment, but by their logical dependency on each other. There is a process for removing identifiers from expressions like x × x so they become pure combinatorial logic. These "chunks of logic" can be carried around as values in their own righthigher order functions. The syntax for removing an identifier x from an expression is [x]expression. So instead of writing square(x) = x × x we can write square = [x](x × x) This is a trivial example. Consider something more complicated, like factorial in SASL: def fac n = n = 0 > 1; n × fac (n + 1) It's more difficult to factor x out of fac than out of square. To help with the factoring, we can define the following constants, called combinators:
S f g x = f x (g x) Given these constants, and a few builtin higherorder functions like times, cond, and minus, we can redefine factorial as:
def fac = S (S (S (K cond) (S (S (K eq) (K 0)) I)) (K 1)) (S (S (K times) I) (S (K fac) (S (S (K minus) I) (K 1)))) To pretty it up a bit, we can define the additional combinators: B f g x = f (g x) which leaves:
def fac = S (C (B cond (eq 0)) 1) (S times (B fac (C minus 1))) There's not a single occurrence of x in the expression; it is purely combinatorial logic. Dataflow machines run applicative code in a natural way. A kind of machine called an SK reduction machine runs code that's closely related to the combinators above. The "object code" for factorial looks something like this [Turner1979]: This is a pure data flow machine which doesn't follow the normal flow of a program counter through time. Time has been unfolded into space. This program is a "picture" of factorial.
What does this have to do with C++ and objects, you
ask? With objects, not much: objectoriented programs
aren't very geometric; they do computation largely by side
effects. As for C++, consider this code from [Coplien1992], where all the instances
are functor objects with
where time has been unfolded into space by emulating the functional paradigm. (DoesValue* apply(Value *object, Value *arg) { return (*object)(arg); } Value* apply(Value *object, Value *arg1, Value *arg2) { return (*object)(arg1, arg2); } LPF *lpf = new LPF(w1); HPF *hpf = new HPF(w2); AMPLIFIER *amplifier = new Amplifier; Value *inputValue, *three = new Value(3); apply( printer, apply( amplifier, apply( apply(lpf, hpf), inputValue ), three ) ); apply look like one
of the combinators?) To take the geometry away and write it
another syntactically valid C++ form, we can invoke:
Well, not much geometry there.amplifier( (*((*lpf)(hpf)))(inputValue), three)>print();
Functional ObjectsFunctional programming lets us define functions in terms of other functions, much as we do in procedural programming. But there is an interesting twist in functional programming, because we can factor out the functions explicitly as parameters. For example, consider a function power that raises its second argument to the power of its first argument. We can apply the function power to the values 2 and 3: power 3 2 and get a value of 8. But what does the expression: power 3 mean? This yields a "value" which is a higherorder function that we can call "raise to the third power." Think of it in terms of a simple regrouping of the original expression: (power 3) 2 We can even bind other names to this function, like this: def cube x = power 3 x or, better, like this: def cube = power 3 And now we can say cube 2 to get 8. This kind of factoring is called currying, after Haskell B. Curry (does that first name sound familiar?) It is a similar process to removing x as a formal parameter, but it is more powerful, giving us truly higher order functions. This technique is central to the thinking process behind functional languages. And you might say: So what? The reason this is important is that it conjures up a geometric representation of functions. Think of power as a box that takes two inputs. We can hardwire one of its inputs to take the value 3, package that up as another box, which we present as another function: This geometric representations suggests there may be something patternish about this aspect of functional programming, too.
James Noble has noted that we do this in objectoriented
programming, too.
Think of a
SignpostsHave fun at PLoP, August 1114, at Allerton Park in Illinois.
References
