Tail Recursion
"Proper" Tail Recursion as found in Scheme is a feature that some miss in CL. It means carefully written recursive function calls can execute in constant space.

Most high-performance CL compilers can already do significant tail call elimination (see their respective manuals). In a thread on c.l.l., a vague idea of pseudostandardising across implementations was raised. To do this, some stuff would need to be defined.

What would constitute a "tail context" in CL?

It's all very well saying do tail "elimination where possible", but you'd need a list of where, like in Scheme R5RS section 3.5, which defines where tail contexts are in terms of a subset of rules of the scheme grammar. The Scheme ones are pretty common-sense I guess, but in CL may not be just "intuitively obvious" to everyone. Or maybe they would. The CMUCL manual section 5.5 about tail recursion in CMUCL talks about "tail recursive positions" - but AFAICS it does not exhaustively define what all the "tail recursive positions" / "tail contexts" might be in CL.

The CMUCL user manual explains in what situations tail-call elimination has to be suppressed for other features' sake, at least in CMUCL. Various dynamic binding issues mainly. These caveats are almost certainly not "intuitively obvious" to someone freshly arriving in CL from Scheme.

The major concern would be that an implementation with a feature of :tail-whatever and providing a known declaration of (optimise (tail-whatever 3)) to turn it on, would at minimum comply with a particular list of valid tail contexts, provided the programmer bore in mind the list of known caveats.

So you could just #- and bomb out if you knew you were writing code that pretty much depended on it - if a fellow with your source wanted to just risk it on a non-compliant implementation, they'd have to make a conscious decision to overrule your #-


So, we need:

A specification of tail contexts for all forms in CL

TODO :-)

A list of caveats

See e.g. CMUCL User Manual, 5.5

A *features* entry

:x-tail-rec or whatever.

A definition of a new declaration

e.g. from Joe Marshall in c.l.l. thread.

(declaim (optimize (dynamic-space 3))) = Tail call elimination where possible

(declaim (optimize (dynamic-space 2))) = Tail call elimination (when possible) for self-calls and locally defined (i.e. FLET or LABELS) functions only, no elimination on non-self calls.

(declaim (optimize (dynamic-space 1))) = Tail call elimination (when possible) for self-calls only.

(declaim (optimize (dynamic-space 0))) = No tail call elimination anywhere.


programming tips