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)


lutter@cise.ufl.edu (David C. Lutterkort) writes:

 > 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
 > ;)

A tail call is one where a function returns the value of calling
another function.

Tail recursion is when a sequence of tail calls ends up back in the
original function.

If the last thing a function does is call itself then it's tail
recursive and it's required to execute in finite space.

If the last thing a function does is call another function, & the last
thing that function does is call the 1st fcn, then this is a pair of
tail recursive funtions & their execution is required to occur in
finite space.

Etc.

This is really a requirement on the evaluator.  If, when the last
thing a fcn does is return the value of calling another function, the
evaluator effectively short circuits the call instead of calling
itself again, then the requirement that tail recursion occur in finite
space will be met.

See SICP for details.  For example, section 5.4.2, pages 556-558 (in
the 2nd edition).  Also section 1.2.1.

-- 
Harvey J. Stein
BFM Financial Research
hjstein@bfr.co.il