Tail Recursion is Looping

Lately, my thoughts and interests have swung towards functional programming languages.

As a way of reacquainting myself with the genre, I was reading through that venerable introductory programming text — The Structure and Interpretation of Computer Programs, when I came across this little snippet of code (It's exercsie 1.5 if you want to find it in the book):

  (define (p) (p))

At first glance the code snippet above seems a little weird. It seems To define the function p as itself. A little examination and thought however, will show that the two uses of (p) in the line have different meanings depending on their position. The first '(p)' in define special form, is used to specify the name and formal parameters of the function. The second occurance of '(p)', is part of the definition of the function p, where p calls itself. In other words, p calls itself recursively. So this definition is perfectly okay. (As it must be, or it wouldn't have made it into the text of SICP.)

The 'naive' C equivalent of this Scheme function would be:

void p() {
  p();
};

Both these functions are effectively infinite recursions. But they are not equivalent!

Calling the C function will cause the program to crash (with a segmentation fault on my Mac,) as the program quickly runs out of stack space. The Scheme function on the other hand will not crash. The code will run forever, until interrupted (with a Crtl-C, on my MIT-Scheme implementation.)

Proper Tail Recursion

Why this difference?

Because the Scheme specification requires implementations of the language to be properly tail recursive (I checked R6RS, and R5RS but I think all versions of the Scheme specification require suport for proper tail recursion.) As the specification says:

A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls.

A simple way of identifying a tail call is when it is the last statement in a function is recursive call to the function itself. But what does the phrase 'an unbounded number of active tail calls' mean?

Essentially, the specification is saying that a confirming Scheme implementation must allow the call stack to be infinitely deep when the recursive call is at the end of the function (i.e. it is a tail call).

This is why the Scheme code above does not crash. (It does not, terminate either, and hence is not mathematically speaking, a valid algorithm. But that's another discussion.) In effect the Scheme function above is equivalent to the following C code throgh the magic of tail call optimization.

while (1);

i.e. a simple loop.

How do Scheme interpreters do tail call optimization? I'll have to defer that didiscussion to a future post.