[plt-scheme] Lazy evaluation and tail calls

From: James Coglan (jcoglan at googlemail.com)
Date: Sun Jan 18 14:53:24 EST 2009

> Exactly, you are on the right track, I think. As I earlier wrote in a
> private email, you should, I think, first find out about self lifting
> promises as referred to by Eli (and very well and very generally implemented
> in PLT (Thanks Eli)). Then, there is a way to transform a tail recursive
> procedure into a space safe reference to an element of a stream. An
> interesting idea, thanks. In fact PLT's lazy scheme (thanks again Eli) does
> that (or at least comes very close)

I've managed to rig together a system whereby, when a new promise is formed,
it inspects the symbols it contains to find out if they point to other
promises. That way a tree of dependencies/dependents is built up. When you
force a promise, I iteratively flatten the dependency tree and use that to
eval the promises in the same order as you'd get in eager mode. Each promise
sends its value to those that depend on it, allowing you to invert the call
order and keep the stack flat.

Unfortunately, while this runs with a flat stack, it's extremely slow and
probably eats memory as I need two-way references between lots of promises.
Still, I'm only using lazy mode for lambda calculus right now, not sliging
lots of data around with it so maybe this optimisation isn't worth it.

Anyway, obviously I need to get beyond the first chapter of SICP so I
actually have some idea of what I'm dealing with! Thanks for all the advice
so far.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090118/34b2f4b2/attachment.html>

Posted on the users mailing list.