[plt-scheme] Lazy evaluation and tail calls

> There is an important difference between normal order and lazy order. But
> let's assume you really mean lazy order.
>
> 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.
>


At the moment, it's lazy. In the above expression, x would be assigned the
expression "(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.

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.

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?

(define (fact x)
  (begin
    (define (rec y acc)
      (cond ((= y 0) acc)
            (else (rec (- y 1) (* y acc)))))
    (rec x 1)))

(fact 4)

Stack logs are here: http://gist.github.com/48360.





-- 
James Coglan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090117/01fad0f6/attachment.html>