Prelim 1 Fall 1997

1. (10 pts) For each of the following expressions, determine what value would be
returned by a Dylan interpreter, or explain what kind of problem would occur.

(a) (bind (((f <function>) car)
           ((x <integer>) 10))
      (f (cons x f)))

==> 10

(b) (bind (((f <function>) (method (x) (+ x 1)))
           ((x <integer>) 10))
      (f x))

==> 3

(c) (bind (((x <integer>) 6))
      (bind (((x <integer>) 7)
             ((f <function>)
               (method ((x <integer>)) x)))
        (+ x (f x))))

==> 14

(d) (bind (((dino <function>) cdr)
           ((barney <function>) (method (x) (cons x 42))))
       (barney (dino (barney dino))))

==> (42.42)

(e) (bind (((f <list>) '(method (x) (+ x 1)))
           ((x <integer>) 2))
      (f x))

==> Error: first element in combination must evaluate to a function

2. (15 pts)
Suppose we define a list godzilla by
(define (godzilla <list>)
  

(a) Draw the box and pointer diagram corresponding to gorilla.

[|][-]->[|][-]->[|][-]->[|][/]
 |       |       |       |
'who    'does   [|][/]  [|][-]->[|][/]
                 |       |       |
                'not   'like   'barney

(b) What is the value of (car (cdr (cdr godzilla)))?

==> (not!)

(c) Define a procedure lunch that only uses car and
cdr such that (lunch godzilla) returns (barney).

==> (define lunch
      (method ((l <list>))
         (cdr (car (cdr (cdr (cdr l)))))))


3.
(a) (car barney)
type: <list>
exp: (list 42)

(b) (barney 'car)
type: <function>
exp: (method (x) 42)

(c) ((barney car))
type: <function>
exp: (method (x) (method () 42))

(d) (barney (barney barney))
type: <function>
exp: (method (x) 42)

(e) ((method () (barney))
type: <function>
exp: (method () 42)

4.
I'll type the proof up later.

(b) T(n) = T(n-1) + O(n) + c

(c) O(n^2)

5. (35 pts)

(a)
(define (count <function>)
  (method ((x <object>) (l <list>))
    (cond ((null? l) 0)
          ((= (head l) x) (+ 1 (count x (tail l))))
          (else: (count x (tail l))))))

(b)
(define (count <function>)
  (method ((x <object>) (l <list>))
    (accumulate 0  
                (method (o (total <integer>))
                        (if (= x o) (inc total) total))
                l)))

(c)
(define (map <function>)
  (method ((f <function>) (l <list>))
    (accumulate '()
                (method (x (result <list>))
                        (cons (f x) result))
                l)))

(d)
(define (filter <function>)
  (method ((f <function>) (l <list>))
    (accumulate '()
                (method (x (result <list>))
                        (if (f x)
                            (cons x result)
                            result))
                l)))

(e)
(define (compose-list <function>)
  (method ((l <list>))
    (accumulate (method (x) x) compose l)))