<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META http-equiv=Content-Type content="text/html; charset=iso-8859-1"> <META content="MSHTML 6.00.6000.16788" name=GENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=#ffffff> <DIV><FONT face="Courier New" size=2></FONT> </DIV> <BLOCKQUOTE style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px"> <DIV style="FONT: 10pt arial">----- Original Message ----- </DIV> <DIV style="BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: black"><B>From:</B> <A title=jcoglan@googlemail.com href="mailto:jcoglan@googlemail.com">James Coglan</A> </DIV> <DIV style="FONT: 10pt arial"><B>To:</B> <A title=eli@barzilay.org href="mailto:eli@barzilay.org">Eli Barzilay</A> </DIV> <DIV style="FONT: 10pt arial"><B>Cc:</B> <A title=plt-scheme@list.cs.brown.edu href="mailto:plt-scheme@list.cs.brown.edu">PLT Scheme ML</A> </DIV> <DIV style="FONT: 10pt arial"><B>Sent:</B> Sunday, January 18, 2009 4:07 PM</DIV> <DIV style="FONT: 10pt arial"><B>Subject:</B> Re: [plt-scheme] Lazy evaluation and tail calls</DIV> <DIV><BR></DIV><BR><BR> <DIV class=gmail_quote>2009/1/18 Eli Barzilay <SPAN dir=ltr><<A href="mailto:eli@barzilay.org">eli@barzilay.org</A>></SPAN><BR> <BLOCKQUOTE class=gmail_quote style="PADDING-LEFT: 1ex; MARGIN: 0pt 0pt 0pt 0.8ex; BORDER-LEFT: rgb(204,204,204) 1px solid"> <DIV class=Ih2E3d>On Jan 17, James Coglan wrote:<BR>><BR>> Right now, I've got a very bare bones Scheme and I'm more interested<BR>> in algorithms for optimising stuff rather than tools in a specific<BR>> language.<BR><BR></DIV>The `lazy' promises that Jos mentioned are not just tools: they are<BR>essentially a way to implement delayed evaluation in a way that is<BR>still safe for space.  You describe how your evaluator is holding an<BR>expression with the appropriate bindings -- and this is essentially a<BR>promise value.  The promises that are implemented in PLT's<BR>scheme/promise library are therefore very relevant, and a solution (to<BR>some degree) to your problem is what that code is doing.</BLOCKQUOTE></DIV> <DIV><BR><BR>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.<BR><BR><BR>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.</DIV></BLOCKQUOTE> <DIV><FONT face="Courier New" size=2>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)</FONT></DIV> <DIV><FONT face="Courier New" size=2></FONT> </DIV> <DIV><FONT face="Courier New" size=2>Using lazy Scheme, you can write a laymans implementation of `equal-fringe?' and have it operate without any superfluous generation of the parts of the fringes that are not relevant. That is the inequality should be detected before the remainder of the two fringes have been formed that follow two inequal elements. Just an example, but a good one, I think.</FONT></DIV> <DIV><FONT face="Courier New" size=2></FONT> </DIV> <DIV><FONT face="Courier New" size=2>Another nice example of how laziness can go wrong is described in SRFI 40 (by Phil Bewig). It is called the times3 problem. It has been adequately been solved in srfi 45 (Andre van Tonder) and used in srfi 41 (Phil Bewig)</FONT></DIV> <DIV><FONT face="Courier New" size=2>Jos</FONT></DIV> <BLOCKQUOTE style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px"> <DIV><BR></DIV> <P> <HR> <P></P>_________________________________________________<BR>  For list-related administrative tasks:<BR>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme<BR></BLOCKQUOTE></BODY></HTML>