Duane Rettig  <duane@franz.com> 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))
	 *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)))

Trivial examples:

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

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

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

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

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

    EVENS
    > (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
    12
    > (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
    146
    >

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

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