<div class="gmail_quote"><br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div bgcolor="#ffffff"><div class="Ih2E3d">
<div><font size="2" face="Courier New">There is an important difference between
normal order and lazy order. But let's assume you really mean lazy order.</font></div><div><font size="2" face="Courier New"></font> </div>
</div><div class="Ih2E3d"><div><font size="2" face="Courier New">In normal order ((lambda (x) (cons x x))
(begin (write 'foo) 'foo)) writes `foo' twice, in lazy order once only. You
might check for that.</font></div></div></div></blockquote><br><br><span style="font-family: arial,helvetica,sans-serif;">At the moment, it's lazy. In the above expression, x would be assigned the expression "</span><font size="2" face="Courier New"><span style="font-family: arial,helvetica,sans-serif;">(begin (write 'foo) 'foo)" (rather than the value of the expression), in the appropriate binding. My bound expressions are memoized so the expression is only evalled once, though if you take out the memoization you get normal order behaviour.<br>
<br>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. (Also I've just started learning Scheme, and while my current implementation is in Ruby I imagine it will flesh out so I can do more stuff in Scheme directly.) My runtime just lets you start it up in lazy or eager mode; there's no provision in the language itself for delaying execution.<br style="font-family: arial,helvetica,sans-serif;">
<br style="font-family: arial,helvetica,sans-serif;"><span style="font-family: arial,helvetica,sans-serif;">To try to figure this out I've logged the call stack in lazy and eager mode to watch what happens when I run the following code. Turns out lazy mode does tail-recurse, but when (= y 0) is finally true, we eval "acc", which is bound to the expression "(* y acc)", which expands to (* 1 (* 2 (* 3 (* 4 1)))), which is not tail recursive. So I suppose the next question would be: is it possible in principle to construct an interpreter than can expand any given lazily bound expression in eager order, without using recursion and blowing up the stack? Alternatively, is it possible to formulate a tail recursive factorial function in normal-order Scheme?</span><br style="font-family: arial,helvetica,sans-serif;">
<br style="font-family: arial,helvetica,sans-serif;"></span></font><pre style="font-family: arial,helvetica,sans-serif;"><div><font size="2"><span>(</span><span>define </span><span>(</span><span>fact</span> <span>x</span><span>)</span></font></div>
<div><font size="2"> <span>(</span><span>begin</span></font></div><div><font size="2"> <span>(</span><span>define </span><span>(</span><span>rec</span> <span>y</span> <span>acc</span><span>)</span></font></div>
<div><font size="2"> <span>(</span><span>cond </span><span>((</span><span>= </span><span>y</span> <span>0</span><span>)</span> <span>acc</span><span>)</span></font></div>
<div><font size="2"> <span>(</span><span>else </span><span>(</span><span>rec</span> <span>(</span><span>- </span><span>y</span> <span>1</span><span>)</span> <span>(</span><span>* </span><span>y</span> <span>acc</span><span>)))))</span></font></div>
<div><font size="2"> <span>(</span><span>rec</span> <span>x</span> <span>1</span><span>)))<br><br>(fact 4)<br><br>Stack logs are here: <a href="http://gist.github.com/48360" target="_blank">http://gist.github.com/48360</a>.<br>
</span></font></div></pre><br></div>
</div><br><br clear="all"><br>-- <br>James Coglan<br>