Advanced Methods in Programming Languages (201-2-4411-01)
Notes Week 6 - Michael Elhadad
previous class main page next class

Building Interpreters (4): Call by Need

When Passing parameters by need we can delay the computation of parameters until they are actually used inside the procedure. This is apparently the best of both worlds - between applicative order and normal order computation.

In practice, call-by-need has 2 problems:

  1. The overhead of argument passing is very high (construction of thunks)
  2. The order of computation of actual parameters is not predictable anymore. This does not combine well that languages which allow side effects (assignments).

Call by Need: L7

In call-by-value, when computing the value of an application expression, we proceed as follows:
  1. Compute the value of the actual parameters
  2. Extend the closed environment by binding the formal parameters of the closure to the value of the actual parameters
  3. Compute the body of the closure in the extended environment
In call-by-need, in contrast, we do not compute the value of actual parameters when computing an application expression. Instead, we bind the formal parameter to a special construct - called a thunk which delays the computation of the actual parameter until it is actually needed - that is, until the formal parameter is used as a varref expression in a computed expression.

To allow for this behavior, we extend the target datatype - it can now be: 

;; Define targets for call-by-reference
(define-datatype target target?
  (direct-target (expval expval?))
  (indirect-target (ref ref-to-direct-target?))
  (thunk-target    (exp exp?)
                   (env env?)))

;; A thunk is considered a direct target                   
(define ref-to-direct-target?
  (lambda (x)
    (and (reference? x)
         (cases reference x
           (a-ref (pos vec)
             (cases target (vector-ref vec pos)
               (direct-target (v) #t)
               (indirect-target (v) #f)
               (thunk-targer (exp env) #t)))))))

;; Deref taking into account indirect targets and thunks
(define deref
  (lambda (ref)
    (cases target (primitive-deref ref)
      (direct-target (expval) expval)
      (indirect-target (ref1)
        (cases target (primitive-deref ref1)
          (direct-target (expval) expval)
          (indirect-target (p) (error "Illegal reference"))
          (thunk-target (exp env) (eval-thunk ref1))))
      (thunk-target (exp env) (eval-thunk ref)))))

;; Implement memoization: a thunk is only computed once
(define eval-thunk
  (lambda (ref)
    (let ((target (primitive-deref ref)))
      (cases target target
        (thunk-target (exp env)
          (let ((expval (eval-exp exp env)))
            (begin 
              (primitive-setref! ref (direct-target expval))
              expval)))
        (else (error "Bad thunk"))))))
            
(define setref!
  (lambda (ref expval)
    (let ((ref (cases target (primitive-deref ref)
                 (direct-target (expval1) ref)
                 (indirect-target (ref1) ref1)
                 (thunk-targer (exp env) ref))))
      (primitive-setref! ref (direct-target expval)))))
Thunk-targets are created in eval-rand according to the following rules: 
;; Procedure application: we compute new bindings using eval-rand
;; Special treatment for var-ref parameters - do not create reference chains.
;; Simple computations are performed immediately (lit and proc)
;; Other computations are delayed as thunks
(define eval-rand
  (lambda (rand env)
    (cases expr rand
      (var-exp (var)
        (indirect-target
          (let ((ref (apply-env-ref env var)))
            (cases target (primitive-deref ref)
              (direct-target (expval) ref)
              (thunk-target (exp env) ref)
              (indirect-target (ref1) ref1)))))
      (lit (datum) (direct-target datum))
      (proc (formals body) (direct-target (closure formals body env)))
      (else (thunk-target rand env)))))
Last modified Mar 31, 2003 Michael Elhadad