Introduction

Alexander'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 Text

A 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 literature--a stretch for many readers in itself--isn'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 literature--and 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 geometry-of-text 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 (peters@totem.co.uk):

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.

When I write my code, I hate having large functions liking them to be small and elegant. I also think that public member variables, as well as violating encapsulation, make the object "look" bad - i.e. it spills out making a nasty mess.

Maybe it's just me, but I find aesthetically pleasing software is not only nice to look at but does make a better system. I think programmers do have a bit of the 'artist' in them but not necessarily literary - just creativity. Most of the people I was at Uni. with couldn't write essays for toffee. [Shillan1998]

Let's attack this issue by investigating the way we think about programming and how we capture those thoughts as programs.

Time and Space

Most 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 loops--chunks of time folded onto each other and expressed in compact form.

The previous Column Without a Name offered visualizations of the run-time behavior of an object-oriented 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 left-to-right spatial progression of the code, and then loops through again. In Miranda, the analogous code would be:

nats = [1, 2, 3..]

nats = [1 ..]

void main() {
	vector<unsigned int> fibs;
	fibs.push_back(1);
	fibs.push_back(1);
	for (int i = 3; ; ) {
		fibs.push_back(
			fibs[i-1] + fibs[i-2]);
		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 (zip is a built-in function that makes a pair out of the first elements of each of its two arguments, another pair out of the second elements, another pair out of the next, and so forth):

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

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 Time

We'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 states--a 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 right--higher 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)
K x y = x
I x = x

Given these constants, and a few built-in higher-order 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)
C f g x = f x g

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: object-oriented 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 operator() defined:

Value*
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
	)
);

amplifier(
	(*((*lpf)(hpf)))(inputValue),
	three)->print();

Functional Objects

Functional 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 higher-order 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 hard-wire 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 pattern-ish about this aspect of functional programming, too.

James Noble has noted that we do this in object-oriented programming, too. Think of a Pen object in a drawing program. We tie it to functions and values that control its drawing parameters just once (perhaps at instantiation) instead of supplying such information on every invocation of the draw method. Iterators, too, are a form of currying. They take one principle argument--a collection of some sort--which we can fix, and then use the iterator in its "curried" form to walk the collection. Curiously enough, iterators are also seem to have something to do with transforming time into space: the sequenced visitation of collection elements is reified in an object. A Facade is also a form of currying, and, depending on how it's used, an Adaptor, too. All of these are coding constructs that seem to drive at the geometric foundations that we've been finding in great patterns.

Signposts

Have fun at PLoP, August 11-14, at Allerton Park in Illinois.

References

• [Coplien1992] Coplien, James. Advanced C++ Programming Styles and Idioms. Reading, MA: Addison-Wesley, ©1992, 178.