This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

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


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

> > 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 ?).
> 
> Guile's interpreter does do this correctly, by making the eval
> function handle tail-position function application directly.  So this
> function shouldn't allocate any new frames.

I am confused now. I guess the above example is to mean 
(define (fact n)
  (if (<= n 1)
      1
      (* n (fact (- n 1)))))
           ^            ^ (Was that meant in the orig. post ?)

I thought that the recursive call to fact is _not_ in tail position
(because the multiplication has to be carried out on the returned
value). Or are you saying that guile's eval can do a CPS transform to put
the call in tail position ??? That would be quite something ;)

Cheers,
David