RE: (dsssl) Loop and Data content

["T. Kurt Bond" <tkb@xxxxxxxxxxx>]

Javier Farreres de la Morena writes:

> Scheme works on recursion, not on iteration, but on a special kind
> of recursion, final recursion.
> 
> Final recursion is that in which the recursive call is the last one to be
> executed. It is usually implemented with an accumulator.

The term used in R5RS Scheme is "tail recursive", but it is explained
in terms of "tail calls", and a tail call is defined by a list of
specific syntactic contexts, and tail calls need not involve recursion
(that is, calling the same procedure).  A Scheme implementation must
be able to support an *unbounded* number of tail calls.  A informal
definition of tail call is a procedure call that in a syntatic
position where the value of the tail call would immediately be
returned by the enclosing procedure: for instance, the last expression
in a procedure body.  For instance, given the two functions 

    (define (f n) (h n) (+ n 1))
    (define (g m) (j m) (f (+ m 1)))

The call to f in g is a tail call, as is the call to + in f, but the
call to + in g and the calls to h and j are *not* tail calls.  (In a
stack-based implementation the calls to h and j will require pushing a
return address on the stack, while the call to f will not, since value
returned by f can be immediately returned to g's caller.)

I don't remember the wording in the DSSSL spec, but I suspect that
since it is based on Scheme that this more strict version, which need
not involve recursion, is intended.

Those who wish more detail can look at 

    http://www.swiss.ai.mit.edu/cgi-bin/info2www?(r5rs)Proper%20tail%20recursion
-- 
T. Kurt Bond, tkb@xxxxxxxxxxx


 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist