<div class="gmail_quote">2009/1/18 Eli Barzilay <<a href="mailto:eli@barzilay.org">eli@barzilay.org</a>> <blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> <div class="Ih2E3d">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. </div>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.</blockquote></div> 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.