Re: Tail recursion and hobbit (was: finite state machines in guile)

[Doug Evans <devans@cygnus.com>]

   Date: Mon, 5 Oct 1998 08:15:05 GMT
   From: Bernard URBAN <Bernard.Urban@meteo.fr>

       Jim> Bernard, tell me if I've got this right:

       Jim> Hobbit does turn some tail calls into jumps, if it is able to
       Jim> figure out how.  However, tail calls to other top-level
       Jim> functions, and some tail calls within a single top-level
       Jim> function, are not optimized, and allocate additional stack
       Jim> space.

It would be nice to know what tail-calls (tail-recursion) Hobbit doesn't
turn into loops that Scheme requires an implementation to turn into loops.

   Exactly. For instance, the following is not tail call optimized:

   (define (fact n)
     (if (<= n 1)
	 1
	 (* n fact (- n 1))))

   even if equivalent to the original factorial. But guile's interpreter may
   also fail to optimize this (I have no way to verify this, any hint ?).

Out of curiousity, is there any Scheme implementation that optimizes this?
This isn't really a tail-call [at least according to the definition
I've been using.]  A tail call to `*', yes.  :-)
[And for the sake of clarity, I'm not refering to things Scheme is
required to "optimize" [turn into a loop].]

       Jim> I don't see how Hobbit could do better, given that it has
       Jim> decided to match the SCM calling conventions.  It has the
       Jim> same problems GCC does: if it could know the nature of the
       Jim> callee ahead of time, it could use a better calling
       Jim> convention, but failing that, it can't do tail calls.

I'm not clear what you mean by "calling convention" here.
Certainly there are examples where GCC doesn't need to know anything
of the callee (modulo maybe the prototype) in order to optimize
a tail call.

   Actually, this kind of information is available, but not used by
   Hobbit.