Andr� Thieme  <address.good.until.2009.may.11@justmail.de> wrote:
+---------------
| Jon Harrop schrieb:
| > William D Clinger wrote:
| >> This all started when Jon Harrop incorrectly stated that
| >> "Trampolines...only handle a few special cases of tail
| >> calls."
| > 
| > I wrote that specifically in the context of Clojure, where it is true.
| 
| It�s very possible that you are right with this.
| I would really like to see an example, so that I can try to avoide these
| issues. If it is true that only some few special cases of tail calls
| can be done in a stack-safe way with trampolines it means that the great
| majority of the cases will run into problems with the stack.
| And if that is the case it should be easy to post one (or two) small
| examples, as a proof-of-concept.
| Could you please post some code, be it in Clojure or some other lang,
| that demonstrates this?
| I would need a concrete example.
+---------------

I don't have an example at hand that will definitely fail for you
[I use CMUCL, which agressively optimizes tail calls even between
functions across separately-compiled files], but if Clojure *does*
have a problem with proper TCO you might be able to construct an
example by, say, defining three identical functions which tail call
each other in a circle, or, if necessary to defeat some optimization,
call one of the other two pseudo-randomly, something like this:

    (defun f1 (x y)
      (let ((x1 (1- x))
	    (y1 (1+ y)))
	(if (zerop x)
	  y
	  (if (zerop (random 2))
	   (f2 x1 y1)
	   (f3 x1 y1)))))

and the same, mutatis mutandis, for F2 & F3.

I was unable to get this to fail with CMUCL even with
(F1 MOST-POSITIVE-FIXNUM 0) [M-P-F is 536870911 there,
*way* larger than any reasonable stack size], even when
compiling each function separately in its own file.
But Clojure's MMV...


-Rob

p.s. You might also try explicitly allocating something in
each function, e.g.:

    (defun f1 (x y z)
      (declare (ignorable z))
      (let ((x1 (1- x))
	    (y1 (1+ y))
	    (z1 (make-array 10)))
	(if (zerop x)
	  y
	  (if (zerop (random 2))
	   (f2 x1 y1 z1)
	   (f3 x1 y1 z1)))))

Though, again, this *didn't* cause CMUCL to break, but it *did*
slow things down a lot and force me to (SETF *GC-VERBOSE* NIL)!!  ;-}

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