Interpreters

Advanced Methods in Programming Languages (201-2-4411-01)
Notes Week 5 - Michael Elhadad

Building Interpreters (3): Parameter Passing

The interpreters up to L5 were passing parameters to arguments by value. The model also corresponds to the evaluation strategy called "applicative order" -- that is, parameters are computed before the body of the procedure is evaluated.

We now introduce 2 variations to the parameter passing modes:

Passing parameters by reference - this allows modifications on parameters inside a procedure to be visible outside the procedure
Passing parameters by need - this allows us to delay the computation of parameters until they are actually used inside the procedure.

Passing Parameters by Reference: L6

Consider the following program in the object language L5:

(let ((a 3)
      (p (proc (x) (set! x 4))))
  (begin
    (p a)
    a))

In L5, because of the call-by-value model, the modification to x inside the body of p does not affect the variable a in the calling environment. This provides a useful isolation between caller and callee code.

Sometimes, we want to allow the code in the caller to pass variables and make the callee assign a value to these variables. This is obtained in call-by-reference. For example, this can be used to return several values out of a procedure (the variables are used as "out parameters"). Another standard example is the swap procedure which is used to swap the value of two variables.

We will develop a call-by-reference interpreter with the following domain structure:

Expressed Value = Number + ProcVal
ProcVal = PrimOp + Closure
Denoted Value = Ref(Expressed Value)

In call-by-reference, we could have a reference that refers to another reference (an indirect reference). The following example illustrates this case:

(proc (t u v w)
  (proc (a b)
    (proc (x y z)
      set y = 13
    a b 6)
  3 v)
5 6 7 8)

In this example, y is bound to b which is bound to v which is bound to 7 -- that is, y is bound to an indirect target. Note however, that we do not need to maintain chains of unlimited length - we only have 2 cases: either a reference to an expressed value (direct target), or a reference to another variable (an indirect value).

To make this distinction, we define the following datatype:

(define expval?
  (lambda (x) (or (number? x) (procval? x))))

;; Assume a vector-based implementation
;; of environments
(define-datatype env env?
  (empty-env)
  (extended-env (vars (vector-of? symbol?))
                (vals (vector-of? expval?))
                (next-env env?)))


(define apply-env
  (lambda (env sym)
    (deref (apply-env-ref env sym))))

(define apply-env-ref
  (lambda (env sym)
    (cases env env
      (empty-env () (error "No binding"))
      (extended-env (vars vals next-env)
        (let ((pos (find-position sym vars)))
          (if (number? pos)
              (a-ref pos vals)
              (apply-env-ref next-env sym)))))))

;; A reference to a position in the vals vector
;; of an environment
(define-datatype reference reference?
  (a-ref (position integer?)
         (vec vector?)))

;; Manipulation of primitive references
(define primitive-deref
  (lambda (ref)
    (cases reference ref
      (a-ref (pos vec) (vector-ref vec pos)))))

(define primitive-setref!
  (lambda (ref val)
    (cases reference ref
      (a-ref (pos vec) (vector-set! vec pos val)))))

;; Define targets for call-by-reference
(define-datatype target target?
  (direct-target (expval expval?))
  (indirect-target (ref ref-to-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)))))))

;; Deref taking into account indirect targets
(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")))))))

(define setref!
  (lambda (ref expval)
    (let ((ref (cases target (primitive-deref ref)
                 (direct-target (expval1) ref)
                 (indirect-target (ref1) ref1))))
      (primitive-setref! ref (direct-target expval)))))

The changes occur each new references are created. Under call-by-value, a new reference is created for every evaluation of an operand; under call-by-reference, a new reference is created for every evaluation of an operand other than a variable.

We therefore inspect all places in the interpreter where a reference is created:

;; Primitive application: no modification.

;; Let binding: we keep the call-by-value behavior:

(let-exp (vars rands body)
  (let ((args (eval-let-rands rands env)))
    (eval-exp body (extend-env vars args env))))

;; Procedure application: we compute new bindings using eval-rand
;; Special treatment for var-ref parameters - do not create reference chains.
(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)
              (indirect-target (ref1) ref1)))))
      (else
        (direct-target (eval-expr rand env))))))

Last modified Mar 23, 2003 Michael Elhadad