loops/tail recusion

Subject: loops/tail recusion
From: Dave Love <d.love@xxxxxxxx>
Date: 17 Jun 1997 15:48:01 +0100
>>>>> "David" == David Megginson <dmeggins@xxxxxxxxxx> writes:

 David> W. Eliot Kimber writes:
 >> While we're on the subject, can someone provide (or point me to) a
 >> brief tutorial on the distinction between a simple define, "let"
 >> procedures, and "lambda" procedures?  I seem to be being
 >> particularly dim about these--probably too many years of procedural
 >> programming to see the obvious in a scheme context.

In addition to the explanations given it _might_ help to see the
expansions of the relevant Scheme `derived expression types' in the
R4RS: <URL:ftp://ftp.swiss.ai.mit.edu/archive/users/jaffer/
public_html/r4rs_9.html>.  At least if you understand them you've
reached a certain enlightenment...

 David> (remember that tail-recursion is better than iteration in
 David> Scheme).

Presumably a thinko, but tail recursion _is_ iteration in Scheme.
(Tail-recursive functions are commonly called `iterative', and Scheme
essentially _requires_ them to be implemented like a loop, whereas
that optimization is a quality of implementation issue in your C or
Fortran compiler.)

 David>   In other words, the best equivalent for

 David>   for (x = 0; x < 100; x++) {
 David>     foo(x);
 David>   }

 David> in Scheme is

 David>   (let loop-function ((x 0))
 David>     (cond ((< x 100)
 David>            (foo x)
 David>            (loop-function (+ x 1)))))

[It should only be better than an equivalent `letrec' construction in
terms of perspicuity, though that's a good reason to use it.]
However, the C loop (if it is useful) has no direct equivalent in
DSSSL because (presumably) it relies on sequenced side-effects as you
can see in the Scheme -- juxtaposed expressions in the body of the
cond clause.

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


Current Thread