What the following code returns

\null
      (let ((a 3))
        (let ((a 4)
              (b a))
          (list a b)))

What is

 (4 3) 

The value returned by this expression:

     ((lambda (x f) 
        (f (f x))) 
      3 
      (lambda (y) 
        (+ y y)))
 

What is

 12 

Given the following definition of f:

   (define f 
     (lambda (x)
       (x (lambda (y) (* y 2)))))
 

What is:

 (lambda (z) (z 3)) 

 (lambda (z) 6) 

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

What is:

 (lambda (x) x) 

 (lambda (f) (lambda (y) 17)) 

The printed representation in Scheme of the following box and pointer diagram: \vspace{0.2in} \centerline{\psfig{figure=lists100.ps,width=5in}}

What is

 ((b c d) a c d) 

The expression returned by the following code:

(define x '(a b x))
(define y (list x x (list 'x x)))
(set-cdr! (cdr y) (list 'w))
y
 

What is

 ((a b x) (a b x) w) 

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

  (define (cons x y)
    (lambda (m) (m x y)))
 

What is

(define (cdr l)
  (l (lambda (x y) y)))
 

The missing expressions in this following definition

(define (accumulate f init lst)
  (if (null? lst)
      init
      (\rule{2in 

What are

 f 

 (car lst) 

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

What is {\tt C}

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

  (define (f x)
    (let ((y 10))
      (lambda (x) (+ x y))))
  (define g (f 5))
 

What is {\tt (*) y:10} and {\tt (+) x:5}

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

What is {\tt B}

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

What are: (1) hang a frame, (2) bind formal paramaters, (3) point back to where environment pointer of proc. object points, (4) evaluate body.

It is the error in this statement:

(assign lst (car (cdr (reg lst))))
 

What is ``nested operations are not allowed''

The definition of stack discipline.

What is Last In, First Out

The function computed by the following machine: \centerline{\psfig{figure=reg300.ps,height=3.5in}}

What is $ans = a^b$

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

 \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))
 

What is

 (append x y) 

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

What are shorter code and object code (also faster run-time)

The Scheme fragment that created the following code:

 \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
 

What is

 (lst null?) 

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

What are save and restore

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

 \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 

What is

 (assign argl (op list) (reg val)) 

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

What are Neural Networks

Your recitation instructor's email address (spelled correctly)

What is either {\tt leventon@ai.mit.edu} or {\tt leventon@mit.edu}

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

What is (b) a Patent

He developed LISP.

Who is John McCarthy

The simplest way the following expression can be written in big theta notation: \vspace{0.2in} \centerline{$n \log(n^2) + (\log(n))^2$}

What is $\Theta(n\log(n))$

The orders of growth in time and space of:

  (define (f n)
    (if (= n 0)
        1
        (f (- n 1))))
 

What are $\Theta(n)$ time and $\Theta(1)$ space

The orders of growth in time and space of:

  (define (g n)
    (if (= n 0)
        1
        (+ (g (- n 1))
           (g (- n 1)))))
 

What are $\Theta(2^n)$ time and $\Theta(n)$ space

The orders of growth in time and space of:

  (define (h n)
    (if (= n 0)
        1
        (+ (h (quotient n 3))
           (h (quotient n 3)))))
 

What are $\Theta(n)$ time and $\Theta(\log(n))$ space

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

What is memoization

The missing expressions in the definition below, which produces the following stream: {\tt (2,1,4,3,6,5,8,7,10,...)}

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

What are

 twos 

 s 

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

What are applicative and normal

What the following mystery stream calulates:

 
(define foo
  (cons-stream 1
    (cons-stream 2
      (stream-map * 
        (stream-cdr 
          (stream-cdr integers))
        (stream-cdr foo)))))
 

What is the factorial stream

 (1 2 6 24 120 720 ...) 

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

 \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))))))
 

What is {\bf dairy-product} inherits its traits from {\bf food}

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

What is (d)

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

What is either (1) we need our objects to have access to ``themselves'' (as a variable that can be used in methods); or (2) we need a way to inherit (or gain use of) the structure and methods of a superclass.

\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:

 \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
 

What is (d) Stack Overflow

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

What is

 (((var1 var2 ...) . 
         (val1 val2 ...))
          PARENT-ENV) 

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

 (let ((x 20))
   (let ((f (lambda (y) (- y x))))
     (let ((x 10))
       (f 30))))
 

What is

 20 

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

 ((lambda (x) (* x 2)) 3) 

What is

 7 

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

  ( := ) 

What is this added to the cond clause:

 
((eq? (cadr exp)) ':=)
    (eval (list 'define 
                (car exp) 
                (caddr exp)) env)
 

What LISP stands for

What is LISt Processing

Any one of Professor Grimson's bad jokes from lecture

\LARGE What are any of: ``You'll be Scrod'', ``You hoser, Canadian Bacon is an unbound variable, eh?'', ``LISP stands for `Lots of Insidious Silly Parentheses'.'', ``The recitation instructors are all asleep in the back'', etc. etc.

The inventors of Scheme.

Who are Hal Abelson and Gerry Sussman

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

What is (D) - Ben and Alyssa P. (Hacker) Bitdiddle

The value of the following expression: \vspace{0.2in}

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

What is

 \bf
((good luck on the final) 
 (thanks for a great semester) 
 (have a fun summer break))