3
$\begingroup$

In SICP, lazy evaluation is defined as delaying the evaluation of procedure arguments until the actual values are needed. (https://mitpress.mit.edu/sicp/full-text/sicp/book/node85.html)

letrec can be implemented by creating a closure (an expression + an environment) and mutating its environment to add a binding to itself. It looks like this in the host language (PLAI, a typed racket similar to ML):

(define (interp expression env)
    (type-case expression
        [letrec (name value body)
                (let (value' (interp value env))
                    (if (is-closure? value')
                        (let (new-binding (bind name value'))
                            (let (new-env (extend-env new-binding env))
                                (begin (set-closure-env! value' new-env)
                                       (interp body new-env))))
                        (interp body (extend-env new-binding env))))]))

In english, (letrec (name value) body) is then interpreted as follows. First evaluate value and if it is a closure then mutate its own environment to point to itself. If it is not a closure then just pass it as is. Evaluate body in a new environment containing this value bound to "name".

Now on to a lazy implementation.

In SICP, lazy evaluation is defined as delaying the evaluation of procedure arguments until the actual values are needed. (https://mitpress.mit.edu/sicp/full-text/sicp/book/node85.html)

So a function application of "fun" to "arg" is interpreted as evaluating "fun" to give a closure and then suspending its interpretation to "arg" until the value is needed (forced) by a strict operation (basically arithmethic primitives and side-effects).

When I try to implement letrec lazily, I fall into a trap.

In (letrec (name value) body) I must evaluate "value" to a closure and mutate its environment to include a binding of name to itself. Then value is fed to body as a function application: ((lambda (name) body) value). But this means that we will evaluate a function's argument strictly: we have to evaluate "value" in order to "close the knot" and make it point to itself.

Additionally, I can't use Y combinators easily because the host language is typed.

How can I get out of this?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.