Final Exam - CS257 Spring 1999

Name:_______________________________

CIRT user-id:________________@unm.edu

We dissect nature along lines laid down by our native language. ... Language is not simply a reporting device for experience but a defining framework for it.
-- Benjamin Whorf, Thinking in Primitive Communities

It is up to us to produce better-quality movies.

-- Lloyd Kaufman, producer of Stuff Stephanie in the Incinerator

Draw the call graph of (foo 12345). Be sure to show the argument to each call, and the result returned from each call. (You need only show calls to foo, not to other functions it calls. Reminder: (quotient x y) returns the largest integer less than or equal to x/y.) (10 points.)
```
(define foo
  (lambda (n)
    (if (< n 10)
        n
	(let ((m (quotient n 10)))
	  (+ (- n (* m 10))
	     (* 100 (foo m)))))))
```

Draw a box-and-pointer diagram corresponding to this s-expression. (10 points)

((mary had (a (little) lamb)) (its fleece) was (white (as snow)))

What value is printed when you type each of the following to MzScheme? (5 points each)

expression	result
((lambda (x f) (f x x)) 'aye (lambda (y z) (list z y y)))
(map (repeat car 2) '(((a b) (c d)) ((e f) (g h)) ((h i) (j k))))
(map (lambda (x) (if (number? x) x (x 6))) (list 13 - list (lambda (x) (/ x 2)) even?))
(accumulate (lambda (x y) (list (car y))) '((a b) (d e f) (g h)))
(list (or 'w 'x 'y) (and 'm 'n 'o) (caadr (assoc 'x '(((y z) x) (x (w y)) (p (d q))))))
(let ((x 'ex) (y 'why)) (let ((y (list x y)) (z (list y y x))) (list x y z)))

Define dubsum which takes a list of integers and returns a list of two elements: the sum of all the numbers in the list it was passed, and the sum of just the even ones. Eg (dubsum '(1 2 3 4 5)) returns (15 6).
1. Non-recursive definition using higher-order functions (10 points):
2. Tail-recursive definition (10 points):

Mark which of the following functions are defined tail-recursively, by putting an X in the appropriate box on each row. (5 points each)

definition

tail
recursive

not t.r.

(define bar
  (lambda (x y)
    (and (not (null? y))
         (if (equal? x (car y))
	     y
	     (bar x (cdr y))))))

(define tr
  (lambda (s q)
    (cond ((pair? s)
           (cons (tr (cdr s) q)
	         (tr (car s) q)))
          ((null? s) q)
	  (else (list s)))))

Define map-skip which takes a function and list, and returns the list it was passed except that every other element (starting with the first) is replaced by the result of applying the passed function to it. (10 points)
Example:
```
(map-skip car '((a b) (c d) (e f) (g h) (i j) (p q) (r s) (t u)))
;;; returns: (a (c d) e (g h) i (p q) r (t u))
```

What value is printed when you type each of the following to MzScheme? (5 points each)

expression	result
`(a ,(+ 1 2) (+ 3 4) ,5)
(let ((x '(a b c))) `(1 (+ 2 3) ,@x 4 (5 ,x 6)))
(map (lambda (x) `(,(+ 1 (car x)) ,@(cdr x) foo)) '((10 100 1000) (20 200 2000) (50 5 555)))
(accumulate (lambda (x y) `(,@x - ,@y -)) '((a b c) (d e) (f g h)))

Define acrost which takes as input a list of lists, and returns a list of the first element of the first element of its input, the second element of the second element of its input, the third element of the third element of its input, etc. (10 points)
For instance
```
(acrost '((a b c) (1 2 3) (d e f g) (w x y z) (11 12 13 14 15 16)))
;;; returns: (a 2 f z 15)
```

Extra Credit: what will the below call to foo return? In English, briefly, what does foo do? Define unfoo which, given an output from foo, returns the corresponding input. (1 point; 1 point; 3 points)

(define foo
  (lambda (s)
    (define aux
      (lambda (s ops)
        (cond ((pair? s)
	       (append (aux (car s) (cons 0 ops))
	               (aux (cdr s) (cons 1 ops))))
	      (else `((,(reverse ops) ,s))))))
    (aux s '())))

(foo '((a b) c d))