Proper tail recursion

["John D. Ramsdell" <ramsdell@...>]

I generally do not find learning a new scripting language pleasant,
because the designs of most languages usually suggest to me that the
authors have not learned the lessons of past efforts of language
design and inflict needless confusion on their users.  My introduction
to lua was pleasant, as some fine choices were made in its design:
tables as objects, first class functions, and real garbage collection.
In many ways, lua is similar to Scheme except that tables replace
pairs as the basic gluing data structure, and the syntax is far easier
for non-specialists.

Still, lua has some ugly warts, such as the lack of real lexical
scoping as evidenced by need for upvalues.  This particular wart makes
implementing mutually recursive local functions very ugly, but this
subject has been fully discussed on this list, so I will not pursue
the topic here except to say that small Scheme implementations that
implement true lexical scoping have been available for a long time.
The issue I would like to discuss is proper tail recursion.

A properly tail recursive implementation of a programming language
allows the execution of an iterative computation in constant space,
even if the iterative computation is described by a syntactically
recursive procedure.  With a properly tail recursive implementation,
iteration can be expressed using the ordinary procedure call
mechanics, so that special iteration constructs are useful only as
abbreviations.

In the following example, the computation specified in loop.lua is
fundamentally iterative.

     bash-2.01$ cat loop.lua
     #! /usr/bin/env lua
     function loop(a)
       if abs(a) < 1 then
         return a
       else
         return loop(a * 0.9)
       end
     end

     print(loop(3))

     print(loop(3e30))
     bash-2.01$

If you run this program in version 4.0 of the lua interpreter, you
find the interpreter runs out of stack space.  The lua interpreter is
keeping stack frames that will never be used.  Translating this
example into Scheme and running it in a system that correctly
implements the language will never result in a stack overflow.

The Scheme standard (R5RS) specifies that Scheme implementations must
be properly tail recursive here:

http://www.swiss.ai.mit.edu/ftpdir/scheme-reports/r5rs-html/r5rs_5.html#IDX52

The rational from R5RS is:

     Intuitively, no space is needed for an active tail call because
     the continuation that is used in the tail call has the same
     semantics as the continuation passed to the procedure containing
     the call. Although an improper implementation might use a new
     continuation in the call, a return to this new continuation would
     be followed immediately by a return to the continuation passed to
     the procedure. A properly tail-recursive implementation returns
     to that continuation directly.

>From this discussion, one can see one of the benefits of a properly
tail recursive implementation of lua: stack frames are removed from
the stack earlier, and so the heap objects to which they refer can be
collected sooner if they are garbage.

There is another benefit that is very important.  If programmers are
allowed to assume that all lua implementations are properly tail
recursive, a new style of programming is available which relies on the
fact that implementations have this property.  For example, to
implement a program that behaves much like a finite state machine, one
can write a function for each state.  A transition in implemented by
tail call to the next state.  The tail recursiveness of the
implementation ensures that only stack frames needed to produce the
correct answer are retained, so the stack size does not limit the size
of the finite state machine.

Properly tail recursive implementations of programming languages have
served the functional programming community well.  Standard ML,
OCaml, Haskell, and Scheme programmers have a long tradition making
use of this property of an implementation.  I hope the lua community
works toward joining in this fine tradition.  Good luck.

John