
\documentstyle[11pt,epsf,psfig,fullpage]{article}

\textheight 10in
\textwidth 7.5in

\def\TITLE#1#2{{\bf\centerline{#1 - #2}}}

\def\ANSWER{}

\def\LISP{\obeyspaces \obeylines \tt \vspace{0.1in}}

{\obeyspaces\gdef {\ }}

\def\QUESTION{}

\pagestyle{empty}

\setlength{\topsep}{0in}
\setlength{\partopsep}{0in}
\setlength{\itemsep}{0in}
\setlength{\parsep}{0in}
\setlength{\leftmargin}{0in}
\setlength{\rightmargin}{0in}
\setlength{\itemindent}{0in}
\oddsidemargin -0.5in
\evensidemargin \oddsidemargin

\begin{document}

\Huge



\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Lambda Calculus}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

What the following code returns
{\LISP 
\null
      (let ((a 3))
        (let ((a 4)
              (b a))
          (list a b)))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Lambda Calculus}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The value returned by this expression:
{\LISP
     ((lambda (x f) 
        (f (f x))) 
      3 
      (lambda (y) 
        (+ y y)))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Lambda Calculus}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{

Given the following definition of f:

{\LISP
   (define f 
     (lambda (x)
       (x (lambda (y) (* y 2)))))
}

It's the expression which, 
when f is applied to it, returns 6.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Lambda Calculus}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{

A function, that when applied to itself, returns a function, that when
applied to 17 returns 17.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Lists}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The printed representation in Scheme of the following
box and pointer diagram:

\vspace{0.2in}

\centerline{\psfig{figure=lists100.ps,width=5in}}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Lists}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The expression returned by the following code:

{\LISP
(define x '(a b x))
(define y (list x x (list 'x x)))
(set-cdr! (cdr y) (list 'w))
y
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Lists}{DAILY DOUBLE} 
\\
\hbox{\vspace{5in}} & \ANSWER{

    If we were to implement cons, car, and cdr as
    procedures, by writing cons as a procedure of its two
    arguments, like so:

{\LISP
  (define (cons x y)
    (lambda (m) (m x y)))
}

    then this is how ``cdr'' would be defined.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Lists}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The missing expressions in this following definition

{\LISP
(define (accumulate f init lst)
  (if (null? lst)
      init
      (\rule{2in}{0.01in} \rule{2in}{0.01in}
         (accumulate f init 
           (cdr lst)))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Environment Model}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The reason that the environmental model is useful:

(a) procedures may contain free variables 

(b) environments use frames

(c) the substitution model is inadequate to deal with
    procedural side effects

(d) your TA likes to see you extremely confused

(e) garbage collection takes a shorter amount of time for
    environmental models

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Environment Model}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

    The expressions that should appear in place of the
    asteriks and the pluses in the environment diagram below, corresponding 
    to the following code:

{\LISP
  (define (f x)
    (let ((y 10))
      (lambda (x) (+ x y))))
  (define g (f 5))
}

\centerline{\psfig{figure=env200.ps,height=2.5in}}


}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Environment Model}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{

    In a lexically scoped language like scheme, this is, by
    definition, where free variables in procedures passed as
    arguments are looked up:

(a) in the environment where the procedure is called

(b) in the environment where the lambda expression was evaluated

(c) in the global environment

(d) in the primitive list of the global environment

(e) in Billings, Montana

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Environment Model}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{

These are the steps that result from applying a
procedure in the environment model.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Register Machines}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

It is the error in this statement:
{\LISP
(assign lst (car (cdr (reg lst))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Register Machines}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The definition of stack discipline.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Register Machines}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{
 
The function computed by the following machine:
\centerline{\psfig{figure=reg300.ps,height=3.5in}}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Register Machines}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The function performed on registers x and y by the
following register machine.

{\LISP \Large \bf
(define-machine mystery
 (register x y aux val continue)
 (controller
   (assign continue (label mystery-done))
 mystery-loop
   (test (op null?) (reg x))
   (branch (label base-case))
   (assign aux (op car) (reg x))
   (save continue)
   (save aux)
   (assign x (op cdr) (reg x))
   (assign continue (label after-loop))
   (goto (label mystery-loop))
 after-loop
   (restore x)
   (restore continue)
   (assign val (op cons) (reg x) (reg val))
   (goto (reg continue))
 base-case
   (assign val (reg y))
   (goto (reg continue))
 mystery-done))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Compilers}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

Either of the two biggest advantages of a compiler over
an interpreter.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Compilers}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The Scheme fragment that created the following code:

{\LISP \LARGE 
  (assign proc (op lookup-variable-value) (const lst) (reg env))
  (assign val (op lookup-variable-value)  (const null?) (reg env))
  (assign argl (op list) (reg val))
  (test (op primitive-procedure?) (reg proc))
  (branch (label prim-branch11))
compound-branch12
  (assign continue (label after-call71))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
prim-branch11
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call71
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Compilers}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{

When interpreted code and compiled code are compared,
these are the instructions eliminated most often.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Compilers}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The missing line in the code, which is
the result of compiling {\tt (f (+ 1 x) y)}:

{\LISP \LARGE
  (assign proc (op lookup-variable-value) (const f) (reg env))
  (save proc)
  (save env)
  (assign proc (op lookup-variable-value) (const +) (reg env))
  (assign val (op lookup-variable-value) (const x) (reg env))
  (assign argl (op list) (reg val))
  (assign val (const 1))
  (assign argl (op cons) (reg val) (reg argl))
  $<$apply-dispatch$>$
after-call21
  \rule[-0.05in]{4in}{0.02in}
  (restore env)
  (assign val (op lookup-variable-value) (const y) (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (restore proc)
  $<$apply-dispatch$>$
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Miscellaneous}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

Carver Mead is now working on these; Alan Turing
was working on the same when he died.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Miscellaneous}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

Your recitation instructor's email address (spelled correctly)

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Miscellaneous}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{

This is commonly used to protect a disclosed invention from being used
by others.

\vspace{0.2in}

(a)  Copyright

(b)  Patent

(c)  Court Order

(d)  Jesse ``The Body'' Ventura

(e)  Trade Secret

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Miscellaneous}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{

He developed LISP.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Orders of Growth}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The simplest way the following expression can be written in 
big theta notation:

\vspace{0.2in}

\centerline{$n \log(n^2) + (\log(n))^2$}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Orders of Growth}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The orders of growth in time and space of:

{\LISP
  (define (f n)
    (if (= n 0)
        1
        (f (- n 1))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Orders of Growth}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The orders of growth in time and space of:

{\LISP
  (define (g n)
    (if (= n 0)
        1
        (+ (g (- n 1))
           (g (- n 1)))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Orders of Growth}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The orders of growth in time and space of:

{\LISP
  (define (h n)
    (if (= n 0)
        1
        (+ (h (quotient n 3))
           (h (quotient n 3)))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Streams}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

    It's the method streams use that prevents the need for
    repetitive calculations.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Streams}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The missing expressions in the definition below, which
produces the following stream:

{\tt (2,1,4,3,6,5,8,7,10,...)}

{\LISP \LARGE \bf 
(define s 
  (cons-stream 2
    (cons-stream 1
      (stream-map + \rule[-0.05in]{1.5in}{0.02in} \rule[-0.05in]{1.5in}{0.02in} ))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Streams}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{

Lists are to streams as \rule[-0.05in]{2in}{0.02in} order is to
\rule[-0.05in]{2in}{0.02in} order.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Streams}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{

What the following mystery stream calulates:

{\LISP 
(define foo
  (cons-stream 1
    (cons-stream 2
      (stream-map * 
        (stream-cdr 
          (stream-cdr integers))
        (stream-cdr foo)))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Object Oriented Programming}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

In the following example, this class inherits from this
(other) class:

{\LISP \LARGE \bf 
(define (make-dairy-product name temp)
  (let ((container 'none)
        (bad false)
        (scent 'lemon)
        (food-obj (make-food name temp)))
   (lambda (message)
     (cond ((eq? message 'name) (lambda (self) name))
           ((eq? message 'scent) (lambda (self) scent))
           ((eq? message 'spoiled?)
             (lambda (self) (set! scent 'vile) true))
                  (else (get-method food-obj message))))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Object Oriented Programming}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The value of inheritance in object oriented languages is
that it makes it convenient to define new kinds of
objects:

\vspace{0.2in}

(a) recursively

(b) that send messages to other objects

(c) that enable a student to pass 6.001

(d) as variants of previously defined objects

(e) without using applicative order

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Object Oriented Programming}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{

By convention, we implement all methods in object-
oriented code to accept an argument named ``self''
for this reason.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Object Oriented Programming}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{
 \LARGE
In an effort to better integrate the worlds of biology
and computer science, Ben Bitdiddle sets out to write a
Scheme program which could be used to determine the gender
of a woman's imminent child, as an alternative to the
more invasive clinical procedures:

{\LISP \Large \tt 
(define (make-kid)
  (lambda (self msg)
    (cond ((eq? msg 'male?) (not (ask self 'female?)))
	  ((eq? msg 'female?) (not (ask self 'male?))))))
\null
(define (ask kid msg) (kid kid msg))
\null
(define patients-kid (make-kid))
\null
(ask patients-kid 'female?)
\null
}

This would be the response:

(a) true

(b) false

(c) no response (runs forever)

(d) error response

(e) none of the above

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Meta Circular Evaluator}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

This is how environments are represented in our
meta-circular evaluator.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Meta Circular Evaluator}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The value of the following expression in a
*dynamic-binding* Scheme:

{\LISP
 (let ((x 20))
   (let ((f (lambda (y) (- y x))))
     (let ((x 10))
       (f 30))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Meta Circular Evaluator}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The number of times the eval procedure is invoked when
the following expression is entered into the evaluator:

{\LISP ((lambda (x) (* x 2)) 3)}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Meta Circular Evaluator}{Daily Double} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The one and only line needed to modify the evaluator to
handle define statements of the form:

{\LISP  (<variable> := <binding>)}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Potpourri}{100} 
\\
\hbox{\vspace{5in}} & \ANSWER{

What LISP stands for

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Potpourri}{200} 
\\
\hbox{\vspace{5in}} & \ANSWER{

Any one of Professor Grimson's bad jokes from lecture

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Potpourri}{300} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The inventors of Scheme.

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Potpourri}{400} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The person(s) to whom there is a seat dedicated in the
10-250 lecture hall.

\vspace{0.2in}

(a) Hal Abelson

(b) Eric Grimson

(c) Gerry Sussman

(d) Ben and Alyssa P. (Hacker) Bitdiddle

(e) Louis Reasoner


}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage


\begin{tabular}{p{0.01in}p{6.5in}}
\hbox{\vspace{0.2in}} & \TITLE{Final Jeopardy}{Lists} 
\\
\hbox{\vspace{5in}} & \ANSWER{

The value of the following expression:

\vspace{0.2in}

{\LISP \bf
(apply map 
   (cons list 
     (quote 
       ((good thanks have) (luck for a) 
        (on a fun) (the great summer) 
        (final semester break)))))
}

}
\\
\hbox{\vspace{2in}} & \QUESTION{

}
\end{tabular}

\newpage

 
\end{document}

