This is a quick file I wrote for trying to prepare for the test.
This is certainly no indication of the material that will be on the test.
It was originally written in Scheme, there might be some differences that
I might of forgot to fix:
  - If you see "lambda" - just replace it by "method"
  - If you see "(define (f x) ...)" - replace it by
    "(define f (method (x) ...))"
  - Replace any "let" by "bind"
  - "equal?" and "eq?" by "=" and "id?"
  - Scheme uses arbitrarily big integers.

1. Suppose we have:
     (define plus (method (x) (method (y) (+ x y))))
   Explain the following:
   a. plus
   b. (plus 3)
   c. ((plus 3) 8)
   Using - your explanation (human language).
         - the substitution model.
         - the environment model.
   d. Can "plus" be used under dynamic scoping?  Explain.

2. Heavy RSM/Enviornment model workout:
   We can define "numbers" in a language that only uses methods:
     (define ZERO (method (x y) y))
     (define succ (method (n) (method (x y) (x (n x y)))))
     (define ONE (succ ZERO))
     (define TWO (succ ONE))
     (define THREE (succ (succ ONE)))
     (define value (method (n) (n inc 0)))
     (value ONE) -> 1
     (value TWO) -> 2
     (value THREE) -> 3
   Use the RSM/Environment model to explain the above.
   If you really want to sweat, do the same for:
     (define plus (method (n1 n2) (method (x y) (n1 x (n2 x y)))))
     (value (plus (succ (succ ZERO)) (succ (succ (succ ZERO)))))

3. Draw the environments generated by the following:
   (If you'll write the bind as an anonymous method form application, then
   things might become easier...)
     (define x 2)
     (define y 3)
     (bind ((x (bind ((y x)) y)))
       (bind ((x (bind ((y x)) y)))
         (cons x y)))

4. Here is a Fibonacci number Pascal function:
     function fib( n : integer ) : integer;
     var i, a, b, c : integer;
     begin
       a := 0;
       b := 1;
       for i := 1 to n do begin
         c := a + b;
         a := b;
         b := c;
       end;
       fib := a;
     end;
   Or in C:
     int fib( int n) {
       int i, a, b, c;
       a = 0;
       b = 1;
       for (i = 1; i < n; i++) {
         c = a + b;
         a = b;
         b = c;
       }
       return a;
     end;
   Write a Dylan version of this function, use tail-recursion for looping.

5. Define two association list procedures:
     ;; Used to add an 'association' to an association list.
     (define acons
       (method (x y l)
         (cons (cons x y) l)))
     ;; Get an association value for a given key.
     (define assoc
       (method (x l)
         (cond
           ((null? l) #f)
           ((= x (car (car l))) (car l))
           (else: (assoc x (cdr l))))))
   * Suppose we want to make memoized functions that work efficiently:
       (define memoize
         (method (f)
           (bind ((values '()))
             (method (x)
               (bind ((val (assoc x values)))
                 (if val
                   (cdr val)
                   (bind ((result (f x)))
                     (set! values (acons x result values))
                     result)))))))

   a. Explain the following using environments:
       (define fib
         (method (n)
           (if (<= n 1)
             n
             (+ (fib (- n 1)) (fib (- n 2))))))
       (define mfib
         (memoize
           (method (n)
             (if (<= n 1)
               n
               (+ (mfib (- n 1)) (mfib (- n 2)))))))
       > (fib 0) -> 0
       > (fib 1) -> 1
       > (fib 10) -> 55
       > (fib 25) -> 74025    (way too much time)
       > (fib 100) -> ...     (kids, do not try this at home...)
       > (mfib 25) -> 74025   (This is fast...)
       > (mfib 100) -> 354224848179261915075 (Couldn't do that with fib.)

   b. Explain why the following won't work using environments:
       (define memoize!
         (method (f) (set! f (memoize f))))
       (define fib
         (method (n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))))
       (memoize! fib) ; This doesn't work...
       > (fib 25) -> 75025  (but it took a lot of time again)

   c. Explain why the following won't work either:
       (define fib
         (method (n)
           (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))))
       (define memoized-fib (memoize fib))
       > (memoized-fib 25) -> 75025

6. Brenda:
   a. Make the minimal amount of changes to brenda to make it use Dynamic
      Scoping.
   b. Add a simple macro facility to Brenda.
   c. Use this macro to implement a "while" loop special form.
   d. Make Brenda lazy - so that
       (define new-if (method (x y z) (if x y z)))
      works properly.  This is not trivial! - think about promises.
   e. Explain what is the problem with making Brenda define functions easily
      like Scheme - translating:
        (define (f x) ...)
      to
        (define f (method (x) ...))
      Can you suggest a solution?
   f. Add a special form called fluid-bind that will behave as follows:
        > (define x 3)
        > (define get-x (method () x))
        > (get-x) -> 3
        > (cons (get-x) (fluid-bind ((x 4)) (get-x)))
          -> (3 . 4)
        > (get-x) -> 3

7. Streams:
   a. Create a stream that looks like the infinite grid of rational numbers.
   b. Write a method that will get two streams and will merge them somehow.
      -- Explain why an append function is not suitable for this.
   c. Write a method that will get a stream of streams and merge them all.
      (You should use the trick from the last lecture to do this.)
   d. Use this method to create a stream of all (positive) rational numbers.
      -- You can try to add a filter that will make each rational appear only
         once in this list.
   e. Show how you can handle infinite arbitrary trees (arbitrary - any number
      of childrens for a node).
      -- Should write the constructor, accessors, and utility functions like
         filter, map etc.

8. This is an exercise plus a solution.  The subject is abstractions, we have
   two very similar functions that can be represented by a single one.  Note
   that this is all I could think of, it is too complex... however, it is only
   the main idea which is important.

   The following two procedures are just for whoever is interested...  We'll
   use them later.
    (define min
      (method (#rest l)
        (bind-methods ((loop (a l)
                         (cond ((null? l) a)
                               ((< (car l) a) (loop (car l) (cdr l)))
                               (else: (loop a (cdr l))))))
          (if (null? l)
            #f
            (loop (car l) (cdr l))))))
    (define remove-dups
      (method (l)
        (bind-methods ((remove (x l)
                         (cond
                           ((null? l) '())
                           ((= (car l) x) (remove x (cdr l)))
                           (else: (cons (car l) (remove x (cdr l))))))
                       (loop (l a)
                         (if (null? l)
                           a
                           (bind ((m (apply min l)))
                             (loop (remove m l) (cons m a))))))
          (reverse (loop l '())))))
    (define divisor
      (method (n)
        (bind-methods ((loop (i)
                         (if (= (modulo n i) 0)
                           i
                           (loop (inc i)))))
          (loop 2))))
    (define rev-rev
      (method (l) (reverse (map reverse l))))

   Suppose we want to get the list of divisors of a number (sorted and unique):
    (define divisors
      (method (n)
        (bind-methods ((loop (n a)
                         (if (= n 1)
                           (list a)
                           (bind ((n-item (/ n (divisor n)))
                                  (n-acc (* a (divisor n))))
                             (append (loop n-item a) (loop n-item n-acc))))))
          (remove-dups (loop n 1)))))
    (divisors 36) -> (1 2 3 4 6 9 12 18 36)

   Now suppose we want a list's list of sublists (ha ha ha...), when lists
   represent sets:
    (define sublists
      (method (l)
        (bind-methods ((loop (l a)
                         (if (null? l)
                           (list a)
                           (bind ((n-item (cdr l))
                                  (n-acc (cons (car l) a)))
                             (append (loop n-item a) (loop n-item n-acc))))))
          (rev-rev (loop l '())))))
    (sublists '(1 2 3)) -> ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())

   Those two functions resemble each other - as a matter of fact - they do the
   same thing.  So, we can use some kind of an abstraction to represent both of
   them.  Now is the point where you can think of a solution and maybe even
   implement it (I think it will take more than a little work... this may be a
   too complex example) - or, you can just see my solution below...

   We call this function 'sub-items' - it gets the following arguments:
     items         - the item to get its sub items
     init-acc      - the initial accumulator
     finilize      - finilize the resulting sequence (gets final list)
     last?         - is our item last?
     get-next-item - gets next item the loop will work on (gets cur item)
     get-next-acc  - gets next accumulator for the loop (gets cur item & acc)

    (define sub-items
      (method (item init-acc finalize last? get-next-item get-next-acc)
        (bind-methods ((loop (i a)
                         (if (last? i)
                           (list a)
                           (bind ((n-item (get-next-item i))
                                  (n-acc (get-next-acc i a)))
                             (append (loop n-item a) (loop n-item n-acc))))))
          (finalize (loop item init-acc)))))

   We can now use sub-items to define the two above procedures:
    (define divisors
      (method (n)
        (sub-items n 1 remove-dups
                   (method (n) (= n 1))
                   (method (n) (/ n (divisor n)))
                   (method (n a) (* a (divisor n))))))
    (define sublists
      (method (n)
        (sub-items n '() rev-rev null? cdr (method (l a) (cons (car l) a)))))

    (divisors 36) -> (1 2 3 4 6 9 12 18 36)
    (sublists '(1 2 3)) -> ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())

9. An extremely difficult exercise with destructive operations:
   Assume that a matrix is represented as a list of columns which are
   themselves lists, so the matrix:
     1 4 7
     2 5 8
     3 6 9
   is represented by ((1 2 3) (4 5 6) (7 8 9)).  Now, try to write a function
   that will return the transposition of a given square matrix.
   The simple version is very short, elegant, and tricky.  The destructive
   version is long, complicated.
   Try to write programs for both problems, without looking below.
   If you give up - then try to understand my solutions.
   Here is the non-destructive version:
    (define simple-transpose (method (matrix) (apply map (cons list m))))
   The destructive version:
    (define transpose
      (method (matrix)
        (bind-methods ((do-line (p)
                         (if (null? p)
                           ()
                           (bind ((col (car p)))
                             (set-car! p (cdr col))
                             (set-cdr! col (do-line (cdr p)))
                             col)))
                       (append-col! (row col)
                         (if (null? (car row))
                           (set-car! row col)
                           (bind-methods ((loop (p)
                                            (if (null? (cdr p))
                                              (set-cdr! p col)
                                              (loop (cdr p)))))
                             (loop (car row)))))
                       (loop (row)
                         (if (null? row)
                           matrix
                           (begin
                             (append-col! row (do-line matrix))
                             (loop (cdr row))))))
          (loop matrix))))
   And an example:
    (define x '(1 2 3))
    (define y '(4 5 6))
    (define z '(7 8 9))
    (define m (list x y z))
    m -> ((1 2 3) (4 5 6) (7 8 9))
    (transpose m) -> ((1 4 7) (2 5 8) (3 6 9))
    x -> (1 4 7)
    y -> (4 7)
    z -> (7)

   * Analyze the runtime of this function.

10. Induction:
    Prove that the number of subsets of a set with n elements is 2^n.