C311 Fall 1996: Exam 1

Instructors: C. Haynes and G. Gomez-Espinoza

---

1. 10 points What is the output of the following program, assuming the delta form is as defined in assignment 5? Show your work.

   (let ((x 1)
         (y 1)
         (count 0))
     (letrec ((static (lambda (x count)
                        (if (zero y)
                          count
                          (dynamic (sub1 y) (add1 count)))))
              (dynamic (delta (y count)
                         (if (zero x)
                           count
                           (static (sub1 x) (add1 count))))))
       (cons (static x count) (dynamic y count))))
   

   Answer: (3 . 2)

   ---

2. 10 points What is the value of the following Scheme expressions?

    (let ((my-set! (lambda (var exp) (set! var exp))))
      (let ((a 1) (b 2) (c 3))
        (begin
           (set!    a 4)
           (my-set! a 5)
           (set!    b 6)
           (my-set! c 7)
           (list a b c))))
   

   Answer: (4 6 3)

   
   
   
   (let ((x 3))
     (let ((x 4)
           (y (+ x 5)))
       y))
   

   Answer: 8

   ---

3. 10 points For the following Scheme expression, rewrite the expression replacing each variable, v, with (v : depth offset), where depth and offset give the lexical address of the variable (using zero-based indexing). If the variable occurs free, then replace it with (v : free).

   (lambda (c a b)
     ((lambda (d e b)
       ((lambda (c)
         ((lambda (a e f)
            (a b d))
          f c e))
        ((a d) b)))
      (a d b)))
   

   Answer:

   (lambda (c a b)
     ((lambda (d e b)
       ((lambda (c)
         ((lambda (a e f)
            ((a : 0 0) (b : 2 2) (d : 2 0)))
          (f : free) (c : 0 0) (e : 1 1)))
        (((a : 1 1) (d : 0 0)) (b : 0 2))))
      ((a : 0 1) (d : free) (b : 0 2))))
   
   

   ---

4. 20 points Modify the code of the following interpreter to support procedures that take a variable number of arguments. Extend the source language to include expressions of the form
   (lambda variable body)

   that behave like the existing closures, except that variable is bound to a list (represented as a host language list) of argument values. Thus

   (eval-exp '((lambda x x) '1 '2) init-env)
   

   yields (1 2). You may mark up the following code and/or define new code in the space that follows.

   New code marked with <STRONG>.

   (define eval-exp
       (lambda (exp env)
         (if (variable? exp) (apply-env env exp)
           (record-case exp
             (quote (datum) datum)
             (lambda (formals body) (make-closure formals body env))
             (else
               (let ((proc (eval-exp (app->rator exp) env))
                     (args (eval-rands (app->rands exp) env)))
                 (apply-proc proc args)))))))
   
   (define make-closure
     (lambda (formals body env)
       (list 'closure formals body env)))
   
   (define apply-proc
       (lambda (proc args)
         (record-case proc
           (prim-proc (prim-op) (apply-prim-op prim-op args))
           (closure (formals body env)
             (eval-exp body
               (if (variable? formals)
                 (extend-env (list formals) (list args) env)
                 (extend-env formals args env))))
           (else (error 'apply-proc "Invalid procedure: ~s" proc)))))
   
   (define eval-rands
       (lambda (rands env)
         (map (lambda (exp) (eval-exp exp env))
           rands)))
   
   

   ---

5. 30 points Indicate in the space below or on the reverse side modifications to the interpreter given in the last problem (not your solution to the last problem) that will extend its source language to include a form with the following syntax:
   (dyncall operator operand ...)

   The semantics of a dyncall differs from an ordinary procedure call only in that if the operator expression evaluates to a closure, it is invoked as if it were created with the delta form of assignment 5. Thus if all procedure calls in a program were replaced by dyncall, the resulting program would obey dynamic scope.

   Assuming an expander that treats let in the usual way, what would be returned by:

   (let ((x 1))
       (let ((f (lambda () x)))
         (let ((x 2))
           (cons (dyncall f) (f)))))
   

   Answer: (2 . 1)

   Interpreter modifications:

   New code marked with <STRONG>.

   (define eval-exp
       (lambda (exp env)
         (if (variable? exp) (apply-env env exp)
           (record-case exp
             (quote (datum) datum)
             (lambda (formals body) (make-closure formals body env))
             (dyncall exp
               (let ((proc (eval-exp (app->rator exp) env))
                     (args (eval-rands (app->rands exp) env)))
                 (apply-proc proc args env)))))))
             (else
               (let ((proc (eval-exp (app->rator exp) env))
                     (args (eval-rands (app->rands exp) env)))
                 (apply-proc proc args #f)))))))
   
   (define apply-proc
       (lambda (proc args env^)
         (record-case proc
           (prim-proc (prim-op) (apply-prim-op prim-op args))
           (closure (formals body env)
             (eval-exp body
               (extend-env formals args
               (if env^ env^ env))))
           (else (error 'apply-proc "Invalid procedure: ~s" proc)))))