Re: CL Implementations and Tail-Call Elimination

Duane Rettig <duane@xxxxxxxxx> wrote:
| In fact, given any random group of Common Lispers, you'll find that
| tail-merging can generate a lot of heated debate - on one hand, there
| is the stack-space-efficiency issue, where the implementation wants to
| use the system's stack space(s) but they are limited resources. On
| another hand there are those who would rather see debugability, and
| when frames are taken off of the stack due to tail-merging, it is a
| lot harder to see the path from one function to its apparent (but
| indirect) progeny. On a third hand, there is the conversation that is
| usually dominated when Schemers are involved about "proper" tail
| recursion (which I think is more properly called "space efficient tail
| calling") - this issue (of whether this style is right or wrong, or
| needed or unnecessary) tends to dominate conversations sometimes, but
| that tends to leave the more subtle "stack-space vs debuggable frames"
| conversation on the back burner.
| > It's unfortunate that there is no straightforward way to support such
| > a programming style in an otherwise excellent multi-paradigm language.
| Such a programming style would have to allow for the multi-paradigms
| in all directions in order to be effective, including the ones I've
| mentioned above - are CLers also willing to discuss the possibility of
| defining CPS (which is usually implied when the "space-efficient tail
| call" is discussed)?

I am, although, as I done in my own code sometimes, a little
bit of CL macrology can make your CPS-conversion *appear* to be
more like the conventional tail-call optimization, using the same
"trampoline/loop" style often used to compile "true" Scheme-like
tail calls into non-tail-guaranteed languages such as C. This
implies the moral equivalent of John Thingstad's earlier suggestion
about a DECLAIM TAIL-MERGE func1 func2 ...), that is, a group of
functions have to know they're using the same tail-call mechanism,
and have to make all tail calls using a specific macro, but given
that minimal requirement the code ends up looking fairly natural.
Here's a quick sketch of one version:

(defmacro tail-call (form)
`(locally (declare (special *current-tail-marker*))
(setf (car *current-tail-marker*)
(lambda () ,form))

(defmacro with-tail-calls-enabled (&body forms)
`(let ((*current-tail-marker* (list (lambda () (progn ,@forms)))))
(declare (special *current-tail-marker*))
(tail-call-trampoline-loop *current-tail-marker*)))

(defun tail-call-trampoline-loop (marker)
(declare (special *current-tail-marker*))
(loop while (eq marker *current-tail-marker*)
do (setf marker (funcall (car marker)))
finally (return marker)))

Trivial examples:

> (with-tail-calls-enabled (+ 17 5))

> (with-tail-calls-enabled (tail-call (* 5 12)))

> (labels ((fact/accum (x accum)
(if (plusp x)
(tail-call (fact/accum (1- x) (* x accum)))
(fact/accum 50 1)))

> (defun odds (x accum)
(format t "odds: ~d~%" x)
(tail-call (evens (1- x) (1+ accum))))

> (defun evens (x accum)
(format t "evens: ~d~%" x)
((not (plusp x))
(1+ accum))
((oddp x)
(tail-call (odds x (1+ accum))))
(tail-call (evens (/ x 2) (1+ accum))))))

> (with-tail-calls-enabled (evens 37 0))
evens: 37
odds: 37
evens: 36
evens: 18
evens: 9
odds: 9
evens: 8
evens: 4
evens: 2
evens: 1
odds: 1
evens: 0
> (with-tail-calls-enabled (evens 238764523837653235834 0))
evens: 238764523837653235834
evens: 119382261918826617917
odds: 119382261918826617917
evens: 119382261918826617916
evens: 59691130959413308958
...[trimmed for brevity]...
odds: 25
evens: 24
evens: 12
evens: 6
evens: 3
odds: 3
evens: 2
evens: 1
odds: 1
evens: 0

Exercise for the reader: Tweak the above to handle
multiple values in the final non-tail-call return. [Easy.]

Exercise for the reader#2: Minimize the consing of
the multiple values version. [Somewhat harder.]


Rob Warnock <rpw3@xxxxxxxx>
627 26th Avenue <URL:>
San Mateo, CA 94403 (650)572-2607