szergling <senatorZergling@gmail.com> wrote:
+---------------
| rpw3@rpw3.org (Rob Warnock) wrote:
| > (defmacro tail-call (form)
| > `(locally (declare (special *current-tail-marker*))
| > (setf (car *current-tail-marker*)
| > (lambda () ,form))
| > *current-tail-marker*))
| >
| > (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)))
|
| I cannot quite understand these, but they are really good!!!
...
| I find the (eq marker *current-tail-marker*) thing quite
| confusing, so to understand it, I've rewritten a more
| readable version. Have I missed anything subtle?
+---------------
Well, yes, one thing. My method allows for multiple tail-calling
contexts to be dynamically active at the same time, yet *not* sharing
the same value for *CURRENT-TAIL-MARKER*, while still being able to
share common subroutines and chains of tail-calling functions. The
innermost TAIL-CALL-TRAMPOLINE-LOOP will only keep going while *its*
specific value of *CURRENT-TAIL-MARKER* is returned to it. Any other
return value -- including a marker from some outer context -- is just
treated as a value to be returned from the WITH-TAIL-CALLS-ENABLED block.
Not shown in my previous example, but supported by the above structure,
is the ability for an inner procedure to make a tail call directly
into an outer TAIL-CALL-TRAMPOLINE-LOOP context, provided that the
marker value he returns is returned up through the dynamic call chain
to the instance of TAIL-CALL-TRAMPOLINE-LOOP with the matching marker.
Something like this [not tested, not even examined too closely for typos,
but the intent sholud be clear]:
(defun foo (args...)
...blah, blah, blah...
(tail-call (bar args...)))
(defun bar (args...)
(let ((*outer-marker* *current-tail-marker*))
(declare (special *outer-marker* *current-tail-marker*))
(with-tail-calls-enabled ; NOTE: Binds new *CURRENT-TAIL-MARKER*
...blah, blah, blah...
(tail-call (baz args...)))))
(defun baz (args...)
(cond
(event1 (tail-call (gorp args...)))
(event2 (tail-call (quux args...)))
(event4 (tail-call (bletch args...)))
(t (tail-call (apply #'baz (modify-somehow args...))))))
(defun bletch (args...)
(declare (special *outer-marker*))
(if ...some-condition...
(tail-call (gorp args...)) ; Call #1
(let ((*current-tail-marker* *outer-marker*))
(tail-call (quux args...))))) ; Call #2
(print
(with-tail-calls-enabled
...blah, blah, blah...
(tail-call (foo args...))))
FOO gets called in the tail-call context established by the top-level
block, and in turn calls BAR. BAR establishes an inner tail-call context,
and call BAZ. As long as all of BAZ, GORP, QUUZ, & BLETCH keep tail-
calling each other [which BLETCH will do if if SOME-CONDITION is true,
noted as "Call #1" above]], the inner context will be used. If any of
them returns a non-marker, that value will propagate upwards and become
the value of the top-level WITH-TAIL-CALLS-ENABLED, and get PRINTed.
But if BLETCH is called with SOME-CONDITION false, it will tail-call
QUXX in the TAIL-CALL-TRAMPOLINE-LOOP context that was set up by the
top-level call to WITH-TAIL-CALLS-ENABLED, which might do something else.
Why is this important? I'm not sure it really is, except that
(1) it seemed to be so to me at the time, and (2) it provides
hooks that might be useful when working with threads [that is,
allowing saving & restoring of tall-calling contexts].
+---------------
| (*tail-call-marker* was renamed to *tail-call*).
| I thought this way is much clearer.
+---------------
Unh? Not to me.
+---------------
| I also tried to record any tail-calls for debugging purposes:
| tail-calls and stack-frame debugging are orthogonal issues!
+---------------
Actually, they're quite closely related, and you can see from
reading the history of discussion of tail calls in CL.
+---------------
| Afterall, nobody complains about goto not leaving a trail
| behind, do they?
+---------------
Uh... Yes, if it blows up the system. How does your TRAMPOLINE
behave after the trillionth tail call? [Such as with a state
machine that uses tail calls for state transitions and runs
continuously for months at a time...] Oops! It doesn't, since
the debugging variable *CALL-STACK* would have long since eaten
up all the memory in the system.
The whole point of tail calls is to the get *semantics* of a chain
of GOTOs [which don't push things on stacks] while being able to
write the code *as if* subroutines were being called. That's why
one of Steele's papers was called "Lambda: The Ultimate GOTO".
-Rob
-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607