Hi all.
This is a continuation of the same idea that tail calling is not exactly
functions but more like goto with parameters. I will refer to a block of
code that is the target of a goto with parameters a ``tail block''
to distinguish it from ``function''.
In this prototype implementation, for pragmatic reasons, we make tail blocks
compatible with functions. A tail block can be invoked from ordinary code as
an ordinary function call. It distinguishes whether it was called in this
ordinary way, or whether it was called from another tail block through the tail
dispatch loop.
The tail call mechanism is hidden behind a function called TAIL-CALL,
whose interface and semantics are similar to FUNCALL. The difference
is that when TAIL-CALL is invoked from a tail block, it causes that
tail block to terminate before the call takes place.
The basic idea is that when a tail block (that is implemented as a function)
calls another tail block, it is being permanently exited (goto semantics,
the tail call does not return). Therefore the underlying function which
implements the tail block can simply be terminated. We don't worry about
low-level details like how our target virtual machine handles stack frames; we
leave that kind of thing to M. Homme Grenouille to worry about. We like to
reason about problems at a higher level of abstraction.
In Lisp, the abandoning an evaluation frame is done by performing a, non-local
control transfer to some exit point that is dynamically outside of that
activation. We must perform this abandonment first, and afterward bring into
effect the tail call. This is done by transferring the information about the
call we want to the exit point, which then calls the function. When functions
mutually recurse, they do so by bailing out dynamically to a dispatching loop
which calls the next function in the chain.
It would be inconvenient to have to use TAIL-CALL everywhere in a tail block.
We can hide the tail call mechanism behind lexical functions, so that a tail
block can use ordinary function call syntax to call its siblings (other tail
blocks involved in the cross-module loop). A tail block defining is provided
which can set up these lexical functions, when given a list of sibling names.
Only higher-order functional arguments have to be treated with TAIL-CALL
insteadof FUNCALL. (FUNCALL will work too, but it will not terminate the
tail block and so the call won't be a tail call).
Here is a working prototype:
(defvar *tail-escape* nil)
(defun tail-call (fun args)
(let ((escape *tail-escape*)
(next-call (cons fun args)))
(if escape
(funcall escape next-call)
(tagbody
:repeat
(let ((*tail-escape* (lambda (next)
(setf next-call next)
(go :repeat))))
(return-from tail-call
(apply (car next-call) (cdr next-call))))))))
(defmacro deftail (name lambda-list &body body)
(let ((escape (gensym "ESCAPE-"))
(other-tails)
(decls))
(loop for f = (first body)
while (and (consp f)
(case (first f)
(:other-tails (setf other-tails
(append other-tails (rest f)))
t)
(declare (setf decls (append decls (rest f)))
t)))
do (pop body))
`(defun ,name (,@lambda-list &aux (,escape *tail-escape*))
,@decls
(flet (,@(loop for other in other-tails
collecting `(,other (&rest args)
(return-from ,name
(let ((*tail-escape* ,escape))
(tail-call #',other args)))))
(tail-call (fun args)
(let ((*tail-escape* ,escape))
(tail-call fun args))))
(let ((*tail-escape* nil))
,@body)))))
A very simple test case illustrates the syntax: DEFTAIL instead of DEFUN, and
an optional (:OTHER-TAILS ...) at the beginning (may be mixed among
declarations).
(deftail even (num)
(:other-tails odd)
(if (zerop num) t (odd (1- num))))
(deftail odd (num)
(:other-tails even)
(if (zerop num) nil (even (1- num))))
This is still a GOTO-like abstraction, because tail calls are tail calls even
if they are not in a tail position. They never return, just like in TAILPROG.