Special Iteration Constructs are Useful only as Syntactic Sugar

Michael Harrison has been trying to wrap his head around the reasons for why Scheme emphasizes recursion and discourage looping constructs like loop and while. SICP actually digs into this very topic in section 1.2:

“One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ‘looping constructs’ such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.”

(I thought it was cool that his thoughts on recursion ended up being tied together with my ramblings on syntactic sugar in this second section of SICP.)

So one reason why you see looping contructs being the “default” in other languages is that they aren’t always optimized for handling recursion. Lisp programmers in general are more concerned with aesthetics and with being concise… and because SICP embraces the “right way” approach, I expect to see code that looks more like mathematical proofs than the typical code-munging “get ‘r done” style you’re liable to run into in the real world.

Meanwhile, in “real” Lisp programs, I don’t expect to see so much compulsive recursion. I don’t even expect to see people writing macros to develop their own custom looping contructs. What I do expect to see is people using “the mighty loop” instead. (You can see in my last little project how the lisp hacker eliminated almost all of my gratuitous recursion– and how he used loop in a nifty read macro to take care of things like “roll 2d6” and “roll 1d6.”)

At any rate, in the same way that it is cool that you can roll-your-own OOP system in Lisp with closures and lambda… I think it is important for programmers to be able to conceptualize iterative processes in terms of recursion. To think deep thoughts, you need to be free from the crutches of less concise ways of imagining things. This is just the sort of thing that “average people” in math classes everywhere whine about: “when am I going to use this stuff?” But how much real thinking do they do, anyways?! They avoid it like the plague!

Seriously though, which kind of world do you want to live in? One in which the mathematics that determines who gets what land is the exclusive domain on the Egyptian priesthood? Or one in which someone like Euclid has expressed the underlying principles of that mathematics… thereby opening the door to make it possible for lesser men to discover and conceptualize things he never imagined. Do you want to spend the rest of your career merely implementing the ideas of others? Or would you like to have the option of doing creative work in spite of the fact that you’re not necessarily a genius?

My hunch is that SICP is The Elements of our generation.  That’s why they’re boiling things down as far as they can go– to an almost “elemental” level….  They are training us to think pure thoughts so that we can connect them to yield deeper insights than we would otherwise be able to obtain without such seemingly pedantic formalizations….  A side benefit is that they don’t need to spend hardly any time explaining language syntax, but the real point is to teach us a way of viewing programing languages not in terms of “how do I make a GUI” and “how do I talk to a database….”  (Anybody can pick up that sort of stuff from a quick google.)  They’re teaching us a more mathematized way of understanding and discussing programming languages so that we can think about them instead of just thinking in them.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: