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] |
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