[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Proper tail recursion
- From: "John D. Ramsdell" <ramsdell@...>
- Date: Thu, 26 Jul 2001 11:57:38 -0400
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
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
In the following example, the computation specified in loop.lua is
bash-2.01$ cat loop.lua
#! /usr/bin/env lua
if abs(a) < 1 then
return loop(a * 0.9)
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:
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.