C311 Spring 1996: Exam 1

Haynes, Hilsdale, and Subramaniam

February 19, 1996

Instructions

1. 10 points What is the output of the following program assuming all variables prefixed by a colon (:) are scoped dynamically, while all others are scoped statically. (The dynlet and dyn forms are used to help you keep track of the name spaces.)

   (let ((x 1)
         (y 2))
     (dynlet ((:x 3))
       (let ((p (lambda (a) (+ x y (dyn :x) (dyn :z) a))))
         (let ((x 30)
   	    (y 40))
   	(dynlet ((:x 10)
   		 (:z 20))
   	  (p 20))))))
   

   Answer: 53

   ---

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

   (let ((x 5))
     (let ((f (let ((x 6))
   	     (lambda (m y)
   	       (if m
   		   (set! x (+ x y))
   		   x)))))
       (begin
         (f x x)
         (f (not x) x))))
   
   

   Answer: 11

   ((lambda (x)
      (+ x x))
    (let ((x 5))
      (add1 x)))
   

   Answer: 12

   ---

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 b a)
     ((lambda (d b e)
       ((lambda (c)
         ((lambda (a e f)
            (a b d))
          f c e))
        ((a d) b)))
      (a d b)))
   

   Answer:

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

   ---

4. 15 points Assume you are given the interpreter for the language that supports literals, variables, applications, and conditionals (i.e. if expressions). Now suppose we want to add an unless construct to the language with syntax

   (unless test exp)

   The semantics is: ``Evaluate test. If it is not true evaluate exp, otherwise return whatever test evaluated to''.

   Complete the appropriate clause to the interpreter below so that it now supports the unless feature. Assume the parser uses (define-record unless (test exp)).

   (Answers in strong text)

   (define eval-exp
     (lambda (exp env)
       (variant-case exp
         (lit (datum) datum)
         (varref (var) (apply-env env var))
         (app (rator rands)
   	(let ((proc (eval-exp rator env))
   	      (args (eval-rands rands env)))
   	  (apply-proc proc args)))
         (if (test then else)
   	  (if (true-value? (eval-exp test env))
   	      (eval-exp then env)
   	      (eval-exp else env)))
         (unless (test exp)
           (let ((t (eval-exp test env)))
   	  (if (true-value? t)
   	      t
   	      (eval-exp exp env))))
         (else (error 'eval-exp "Invalid abstract syntax ~s " exp)))))
   

   ---

5. 15 points Write a Scheme program that takes an expression in the simple lambda calculus and a symbol representing a variable that occurrs in the lambda calculus expression, and returns the maximal lexical depth of a reference to the variable. The BNF grammar for the simple lambda calculus is given below:

   <exp> ::=  <var>
           |  (lambda (<var>) <exp>)
           |  (<exp> <exp>)
   

   Answer:

   (define max-depth
     (lambda (exp var)
       (letrec ((md (lambda (exp depth)
   		   (cond
   		     [(variable? exp)
   		      (if (eq? exp var)
   			  depth
   			  -1)]
   		     [(lambda? exp)
   		      (if (eq? (lambda->formal exp) var)
   			  (md (lambda->body exp) 0)
   			  (md (lambda->body exp) (add1 depth)))]
   		     [else
   		       (max (md (car exp) depth)
   			 (md (cadr exp) depth))]))))
         (md exp 0))))
   
   (define variable? symbol?)
   (define lambda?
     (lambda (exp)
       (eq? (car exp) 'lambda)))
   (define lambda->formal caadr)
   (define lambda->body caddr)