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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.