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

[Bernard URBAN <Bernard.Urban@meteo.fr>]

>>>>> "Jim" == Jim Blandy <jimb@red-bean.com> writes:

    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.

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 ?).

    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.

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

--

B. Urban