RE: (dsssl) Loop and Data content

Subject: RE: (dsssl) Loop and Data content
From: "T. Kurt Bond" <tkb@xxxxxxxxxxx>
Date: Sun, 13 Apr 2003 00:41:14 -0400
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
T. Kurt Bond, tkb@xxxxxxxxxxx

 DSSSList info and archive:

Current Thread