CS217 Day 16 Wednesday, May 3, 2000

Assignment, Parameter Passing I
Call-by-value vs Call-by-reference

Assignment and call-by-value have been implemented as part of the midterm.

• Assignment, Call-by-value
  Code from book, suitable modified for midterm is in 3.7code.scm.
  Resulting interpreter is interp3-7clean.scm.
  • Our syntax for assignment is
    

    expression ::= set [identifier] = [expression]
    

    which is parsed to

    (varassign-exp
      (id symbol?)
      (rhs-exp expression?))
    

    by adding

    (expression
      ("set" id "=" expression)
      varassign-exp)
    

    to the grammar.

  • In order to implement assignment, we make denoted values references to expressed values.

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

    References are implented with a reference datatype.

    (define-datatype reference reference?
      (a-ref
        (position integer?)
        (vec vector?)))
    

    This is convenient because we are implementing environments with vectors, whose elements are settable locations in Scheme, but which are not themselves data types in Scheme. Such references essentially make elements of a vector into a data type, which can be accessed and set with

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

  • Assignment is then implemented by adding the following to eval-expression

    (varassign-exp (id rhs-exp)
      (begin
        (setref!
          (apply-env-ref env id)
          (eval-expression rhs-exp env))
        1))
    

    apply-env-ref returns a reference to a location in an environment.

    In the case of a recursive environment, a reference is created to a 1-vector whose element contains the closure which is constructed. The book does not consider this case, perhaps assuming a cyclic environment is created for the recursive case.

    apply-env is then modified to dereference the the newly created reference.

    (define apply-env-ref
      (lambda (env sym)
        (cases environment env
          (empty-env-record ()
    	(error 'apply-env "no association for symbol ~s" sym))
          (extended-env-record (syms vals env)
    	(let ((position (list-find-position sym syms)))
    	  (if (number? position)
    	      (a-ref position vals)
    	      (apply-env-ref env sym))))
          (extended-env-recursively-record (proc-names ids-vec body-vec env0)
    	(let ((position (list-find-position sym proc-names)))
    	  (if (number? position)
    	      (a-ref
    		0
    		(vector
    		  (closure
    		    (vector-ref ids-vec position)
    		    (vector-ref body-vec position)
    		    env)))
    	      (apply-env-ref env0 sym)))))))
    
    (define apply-env
      (lambda (env sym)
        (deref (apply-env-ref env sym))))
    
    

  • The resulting interpreter is call-by-value, since actual parameters are evaluated and their values stored in new references. Values of formal paramters in a procedure call are derefed refs.

• Begin
  • The concrete syntax

    [expression] ::= begin [expression] {; [expression]}* end
    

    is parsed to

    (begin-exp
      (exp expression?)
      (exps (list-of expression?)))
    

    by adding

    ("begin" expression (arbno ";" expression) "end")
    

    to the grammar.

  • Begin expressions can be interpreted in eval-expression by

    (begin-exp (exp exps)
      (eval-begin exp exps env)
    

    where

    (define eval-begin
      (lambda (exp exps env)
        (let ((val (eval-expression exp env)))
          (if (null? exps)
    	  val
    	  (eval-begin
    	    (car exps)
    	    (cdr exps)
    	    env)))))
    

    This evaluates the semi-colon separated expressions in a begin expression in order, returning the value of the last (and ignoring the values of all but the last).

    E.g.,

    let a = 2
        f = proc(x) *(x, x)
    in begin
         print(list(a, (f a)));
         set a = 4;
         print(list(a, (f a)));
         (f (f a))
       end
    
    prints:  (2 4)
             (4 16)
    returns: 256
    

• Arrays
  interp3-7clean.scm also implements arrays (Ex 3.7.6, p94), adding primitives array, arrayref, and arrayset, so

  Arr = (Ref(Expressed Value))*
  Expressed Value = Number + ProcVal +Arr
  Denoted Value = Ref(Expressed Value)

• Call-by-reference Code from book is in 3.8cbr.scm.
  Resulting interpreter is interp3-8clean.scm.

  With call-by-reference, in the case an actual parameter in a procedure call is a variable, the corresponding formal parameter is bound to the location of the actual parameter, rather than to a new location.

  Thus, when the formal parameter as assigned a value in the body of a procedure, the actual parameter is assigned this value.

  Call-by-reference is implemented by references to locations within a vector. But the location will contain either an expressed value (a direct target) or a reference to an expressed value (an indirect target).

  We define a target data type to represent these kinds of values.

  (define-datatype target target?
    (direct-target
      (expval expval?))
    (indirect-target
      (ref ref-to-direct-target?)))
  

  where

  (define expval?
    (lambda (x)
      (or (number? x) (procval? x)
  	(list? x) (bool-value? x))))
  

  and

  (define ref-to-direct-target?
    (lambda (x)
      (and (reference? x)
  	 (cases target (primitive-deref x)
  	   (direct-target (v) #t)
  	   (indirect-target (r) #f)))))
  

  The following example has different output under call-by-value and call-by-reference.

  let a = 3
      b = 4
      swap = proc (x, y)
               let temp = x
               in begin
                    set x = y;
                    set y = temp
                  end
  in begin
       print(list(a, b));
       (swap a b);
       print(list(a, b))
     end
  

  See 3.8cbr.scm.
  and interp3-8clean.scm.

• Scheme.java, a call-by-value interpreter in Java that parses and evaluates list syntax.