[plt-scheme] Lazy evaluation and tail calls

From: Eli Barzilay (eli at barzilay.org)
Date: Sun Jan 18 12:20:36 EST 2009

On Jan 18, James Coglan wrote:
> 2009/1/18 Eli Barzilay <eli at barzilay.org>
> > The `lazy' promises that Jos mentioned are not just tools: they
> > are essentially a way to implement delayed evaluation in a way
> > that is still safe for space.  You describe how your evaluator is
> > holding an expression with the appropriate bindings -- and this is
> > essentially a promise value.  The promises that are implemented in
> > PLT's scheme/promise library are therefore very relevant, and a
> > solution (to some degree) to your problem is what that code is
> > doing.
> Sorry for the misunderstanding: I just meant to emphasise that I was
> more after a language-neutral discussion of algorithms for the
> problem I was trying to solve.

Right: the problem that those kind of promises solve is unrelated to
the language.  Take it as a datatype and an algorithm that force
promises in a particular way that allows more tail calls.  (And I'm
using "promises" here in a generic sense, unrelated to whatever you
see from a particular implementation.)

By the way, the language itself that you're using to implement this
has a role in this too.  For example, say that you have this code:

  (let* ([x (foo)]
         [y (bar x)])
    (baz y))

When you get to evaluate the body form, you have `x' and `y' bound in
the environment, but `x' is no longer needed.  A good language
implementation will dump the reference to `x' from the environment.
This looks like a kind of a semi-sophisticated optimization that you
can worry about later -- but especially in the case of a lazy language
not doing so can lead to memory leaks (that are very hard to find).

          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!

Posted on the users mailing list.