C311 Fall 98 Exam 1

Instructors: C. Haynes and A. Koprulu

Write your name in the top right-hand corner of this page. There are 100 points total. You have the entire class period for this exam. Show your work to receive partial credit. If you use any procedure that is not in standard Scheme, define it (in any blank space that seems large enough). Check your work carefully!

1. (10 points) Write a procedure mark-depth that takes a nested list structure and replaces every occurrence of the symbol depth by the number of lists that it is contained in.

   (mark-depth '(depth 1 ((2 depth) #f) depth)) ==> (1 1 ((2 3) #f) 1)
   
   ANSWER:
   
   (define mark-depth
     (lambda (nlst)
       (letrec ((mark (lambda (nls depth)
                        (cond
                          [(null? nls) 
                             '()]
                          [(list? (car nls))
                             (cons (mark (car nls) (add1 depth))
                                   (mark (cdr nls) depth))]
                          [(eq? (car nls) 'depth)
                             (cons depth (mark (cdr nls) depth))]
                          [else 
                             (cons (car nls) (mark (cdr nls) depth))]))))
         (mark nlst 1))))
   
   

2. (4 points each) What is the value of each of the following expressions? Assume delta is as defined in the 5th assignment.

   a.  (let ((x 1)
   	  (y 10))
         (+ (begin (set! x 2)
   		(let ((x (* y 2))
   		      (y (+ 5 x)))
   		  (+ x y)))
   	 x))  
   
   ANSWER: 29
   
   b.  (let ((x 1))
         (let ((set!x (lambda (value) (set! x value))))
   	(let ((x (* x 4)))
   	  (set!x 5)
   	  x)))
   
   ANSWER: 4
   
   c.  (let ((x 1))
         (let ((set!x (lambda (value) (set! x value))))
   	(let ((x (* x 4)))
   	  (set!x 5))
   	x))
   
   ANSWER: 5
   
   d.  (let ([x 1])
         (let ([f (lambda (y) (+ x y))]
   	    [g (delta (y) (+ x y))])
   	(let ([x 2])
   	  (+ (f x) (g x))))))
   
   ANSWER: 7
   
   e.  (let ((x 1))
         (let ((f (lambda (y) (+ x y))))
   	(let ((g (delta (z) (+ x (f z)))))
   	  (let ((x 10))
   	    (g 5))))))
   
   ANSWER: 16
   
   f.  (let ((x 1))
         (let ((f (lambda (y) (+ x y))))
   	(let ((g (lambda (z) (+ x (f z)))))
   	  (let ((x 10))
   	    (g 5))))))
   
   ANSWER: 7
   
   g.  (let ((x 1))
         (let ((f (delta (y) (+ x y))))
   	(let ((g (delta (z) (+ x (f z)))))
   	  (let ((x 10))
   	    (g 5))))))
   
   ANSWER: 25
   
   

3. (7 points) In the following expression, which variables occur free in the expression, and what is the lexical depth (zero-based) of the variable reference of maximal depth?

   (let ((x 5))
     (let ((y (+ x 1))
           (f (lambda (a) (lambda () (+ y x)))))
       (let ((z y))
         (* z ((f 3))))))     
   
   ANSWER: FV = {+,y,*}
           max. lexical depth = 2 
   
   (let ((x 5))
         (let ((y ([+: free] [x: 0] 1))
               (f (lambda (a) (lambda () ([+: free] [y: free] [x: 2])))))
           (let ((z [y: 0]))
             ([*: free] [z: 0] (([f: 1] 3))))))     
           
   

4. (10 points) Show how a correct implementation of Scheme might expand the following expression into an equivalent one not using letrec such that evaluation of the expression will return 3. Why might this expression not work in another Scheme implementation?

   (letrec ((y (+ x 1)) 
            (x 2))
     y)
   
   ANSWER:
   
   (let [(x 'ignore) (y 'ignore)]
       (set! x 2)
       (set! y (+ x 1))
     y)
   
   

   If another Scheme implementation tries to evaluate the value of y before it assigns the value of x, then this expression might not work.

5. (10 points) Consider a language in which a expressions can return numbers, characters, pointers to assignable variable locations, or pointers to procedures. Variables may be bound to procedures or assignable locations containing the value of an expression. (These properties are true of the language C, though there are also other possibilities in C.) Write concise formulates indicating the expressed and denoted values in this language.

   
   ANSWERS:
   
   expressed values = num + char + ptr(cell(expressed value)) + ptr(procedure)
   
   
   denoted values = procedure + cell(expressed value)
   
   

6. (35 points) The extended BNF grammar of an arithmetic expression is given as:

   <exp> -> <number>
         |  (<operator> <exp> ...)
   
   <operator> -> + | - | * | /
   

   Your program begins with

   (load "datatype.ss")
   
   (define-datatype arith-exp
     (num (value number?))
     (exp (operator operator?)
          (operands (list-of arith-exp?))))
   

   Define recordify, evaluate, and any other procedures necessary to obtain an implementation of this simple language, with the usual meaning of expressions and numbers being any Scheme number.

   (evaluate (recordify '(* 2 (+ 3 (/ 6 2))))) ==> 12
   
   ANSWER:
   
   (define operator?
     (lambda (sym)
       (memv sym '(+ - * /)))
   
   (define list-of
     (lambda (pred)
       (lambda (lst)
         (andmap pred lst))))
   
   (define recordify
     (lambda (e)
       (cond
         [(number? e)
            (make-num e)]
         [(operator? (car e))
            (make-exp (car e) (map recordify (cdr e)))]
         [else
            (error 'expression "Invalid arithmetic expression syntax")])))
   
   (define evaluate
     (lambda (myexp)
       (type-case arith-exp myexp
         [(num val)
            val]
         [(exp rator rands)
            (apply (eval rator) (map evaluate rands))])))