Exam II Answers, CS 257

I want American computers in space. Don't want Russian computers. Russian computers are like Russian booster rockets ... biggest in world.

- Georgy Grechko, former Soviet cosmonaut

1. What value is printed when you type each of the following to Scheme? (2 points each)

   expression	result
   (define (foo x) (if (= x 0) + *)) ((foo 2) 3 4)	12
   (and 'a 'b 'c)	c
   (or 'a 'b 'c)	a
   (if 'a 'b 'c)	b
   (define a '(1 2 3)) `(a ,a b ,@a c (,a) (d ,@a a))	(a (1 2 3) b 1 2 3 c ((1 2 3)) (d 1 2 3 a))

2. Write a tail-recursive definition of add-nums, a function that takes a single argument, a list, a returns the sum of all the elements in the list that were numbers. The sum should not include numbers nested within sublists. Hint: use a helper function of two arguments (6 points for being tail recursive, 4 for being correct)

   Examples:

   (add-nums '())                    ; 0
   (add-nums '(a 1 b 2 c 3 d e))     ; 6
   (add-nums '((1) 2 (a 45 b) c 3))  ; 5
   

   ---

   (define (add-nums lis)
     (add-nums-aux lis 0))
   
   (define (add-nums-aux lis subtotal)
     (if (null? lis)
         subtotal
         (add-nums-aux (cdr lis)
                       (+ subtotal
                          (if (number? (car lis))
                              (car lis)
                              0)))))
   

3. Rewrite the following pseudocode in Scheme, using procedure calls in place of goto and assignment. (10 points)

   foo(i,j)
   {
    L1:
     if (i < j) {
       j = j-i;
       goto L1;
     } else if (j < i) {
       i = i-j;
       goto L1;
     } else
       return i;
   }
   

   ---

   (define (foo i j)
     (cond ((< i j) (foo i (- j i)))
   	((< j i) (foo (- i j) j))
   	(else i)))
   

4. Convert each expression into an equivalent backquote form. (2 points each)

   expression	equivalent using backquote
   (list 'this 'is 'example n 'of m)	`(this is example ,n of ,m)
   (append s1 '(followed by) s2)	`(,@s1 followed by ,@s2)
   (cons 'foo (append s '(more)))	`(foo ,@s more)
   (list 'joe (list 'the x) 'saw (car y))	`(joe (the ,x) saw ,(car y))
   (cons 'a (car y))	`(a ,@y) or `(a . ,y)
   (append (list (+ a 3) (+ a 4)) '(and more))	`(,(+ a 3) ,(+ a 4) and more)

5. Extra credit: Given these definitions

   (define (c-car x c) (c (car x)))
   
   (define (c-cdr x c) (c (cdr x)))
   
   (define (c-cons x lis c) (c (cons x lis)))
   
   (define (c-null? x c1 c2) (if (null? x) (c1) (c2)))
   
   (define (foo a b c)
     (c-null? a
   	   (lambda () (c b))
   	   (lambda ()
   	     (c-car a
   		    (lambda (caa)
   		      (c-cdr a
   			     (lambda (cda)
   			       (foo cda b
   				    (lambda (fcdab)
   				      (c-cons caa fcdab c))))))))))
   

   What does (foo '(x y z) '(p d q) (lambda (x) x)) return? (3 points + Scheme self actualization)

   ---

   (x y z p d q)
   

   Explanation: the c- functions take an extra argument, a procedure, which they call with the result of the non-c- version.

   Similarly, c-null? calls either it's second or it's third argument, depending on whether its first argument is the empty list.

   Since these procedures are here made with lambda, we can untangle things by rewriting them with if and let as follows, and also using a new version of foo that returns its result rather than calling its third argument upon it

   (define (foo a b)
     (if (null? a)
         b
         (let ((caa (car a)))
   	(let ((cda (cdr a)))
             (let ((fcdab (foo cda b)))
   	    (cons caa fcdab))))))
   

   Now we can substitute in variables' values where they occur,

   (define (foo a b)
     (if (null? a)
         b
         (cons (car a) (foo (cdr a) b))))
   

   which is our old friend append.

   The original version, in which all functions take an extra argument which they call tail-recursively upon their result, is called continuation passing style or CPS. It is simple to mechanically translate programs into CPS, which make the order of evaluation very explicit, and contains names for intermediate values that were anonymous in the original code. These and other properties make it particularly suitable for compilers, and many compilers convert represent the program in CPS form as in intermediate stage of compilation.