[plt-scheme] Lazy evaluation and tail calls

2009/1/18 Eli Barzilay <eli at barzilay.org>

> On Jan 17, James Coglan wrote:
> >
> > Right now, I've got a very bare bones Scheme and I'm more interested
> > in algorithms for optimising stuff rather than tools in a specific
> > language.
>
> 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. I imagine at some point I will want to implement
delay/force in my Scheme, but for now I want a way to make Scheme
transparently lazy. This is mostly because I'm reading "To Mock a
Mockingbird" and doing some lambda calculus, which requires normal order
evaluation in order to be directly expressed in Scheme.


Joe, Jos: sadly I'm not equipped to provide any formal reasoning at this
stage -- Scheme and SICP are really my first foray into any formal study of
computer science. All I can tell is that it looks like you'd need to somehow
evaluate the promises from the inside out iteratively and have the result
propagate into the binding of the next outer promise before evaluating it,
so you'd be able to evaluate the promises in the some order as you would in
call-by-value. This would involve every promise storing references to any
promises that need its value, which would use extra storage space, and you'd
need to flatten the tree of promise dependencies without using recursion in
the host language. I'll let you know if I figure something out.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090118/cdf700d3/attachment.html>