% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Friday, May 7}

\vspace{-0.1in}
\centerline{{\bf Final Review Handout}
\footnote{\bf Disclaimer: This handout was created as a study
guide for the final.  It is NOT necessarily complete.  There could be
other material not covered in this handout that is still fair game for
the final.  This is also NOT a practice final, in that I didn't time
how long it should take.  I just tried to come up with some problems
that would help in reviewing for the final.}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf Iterative vs. Recursive Processes and Order of Growth}

Consider the two procedures below.  Assume the arguments passed in are
always positive integers.

\beginlisp
(define (odd? x)
  (if (= x 1)
      \#t
      (even? (- x 1))))
\null
(define (even? x)
  (not (odd? x)))
\endlisp

Given the above definitions, when the expression {\tt (odd? 24)} is
evaluated, does that generate a recursive or iterative process?  Why?

{{\Huge$\Rightarrow$}} \ANSWER{This generates a recursive process
because the {\tt not} operations are delayed.}

What is the order of growth of in time of the procedure {\tt even?}?

{{\Huge$\Rightarrow$}} \ANSWER{$\bf\Theta(x)$}

What is the order of growth of in space of the procedure {\tt odd?}?

{{\Huge$\Rightarrow$}} \ANSWER{$\bf\Theta(x)$}

Change one of the two functions above to make the process the opposite
of what it currently is (eg. If it's a recursive process, make it
iterative and if it's an iterative process, make it recursive).  

{{\Huge$\Rightarrow$}}
\beginlisp
\ANSWER{
(define (even? x)
  (if (= x 0)
      \#t
      (odd? (- x 1))))
}
\endlisp

\vspace{0.2in}

Consider the function below:

\beginlisp
(define (power-of-2? n)
  (cond ((= n 1) \#t)
        ((< n 1) \#f)
        (else
          (power-of-2? (/ n 2)))))
\endlisp

Does the function {\tt power-of-2?} generate a recursive or iterative
process?  Why?

{{\Huge$\Rightarrow$}}  \ANSWER{Iterative.  No delayed operations.}

What is the order of growth of in time of the procedure {\tt power-of-2?}?

{{\Huge$\Rightarrow$}} \ANSWER{$\bf\Theta(\log(n))$}

What is the order of growth of in space of the procedure {\tt power-of-2?}?

{{\Huge$\Rightarrow$}} \ANSWER{$\bf\Theta(1)$}

\newpage

{\Large\bf Higher Order Procedures and Tree Structures}

We'd like to write an evaluator for simple in-fix numerical
expressions.  For example, consider the trees generated by the
following expressions.  Careful: Notice that the operators are {\bf
not} quoted.

\beginlisp
(define exp1 (list 3 + 5))
(define exp2 (list 3 * (list (list 4 + (list 6 - 2)) / 2)))
\endlisp

How does {\tt exp1} print when evaluated?  

{{\Huge$\Rightarrow$}} \ANSWER{\tt (3 \#[arity-dispatched-procedure 16] 5)}

Draw the box and pointer diagram for the tree structure of {\tt exp2}

{{\Huge$\Rightarrow$}} 

\ANSWERIS{\centerline{\psfig{figure=r26-ans-a.ps,height=2in}}}{\vspace{2in}}

Write a function {\tt infix} that evaluates these types of
expressions.  For example,

\beginlisp
(infix 4)     ==>  4
(infix exp1)  ==>  8
(infix exp2)  ==> 12
\endlisp

{{\Huge$\Rightarrow$}}
\beginlisp
\ANSWER{
(define (infix exp)
  (if (not (pair? exp))
      exp
      ((cadr exp)
       (infix (car exp))
       (infix (caddr exp)))))
}
\endlisp

Consider a function {\tt infix->prefix} that takes an infix expression
like {\tt exp1} and {\tt exp2} above, and transforms the expression
into prefix form (e.g. it swaps the order of the operator and first
operand).  For example, the expression {\tt (infix->prefix (list (list
3 * 2) + 4))} will produce the same list structure as (i.e. will be
{\tt equal?}  with) the value of following expression: \\ {\tt (list +
(list * 3 2) 4)}.

Write the function {\tt infix->prefix}.

{{\Huge$\Rightarrow$}}
\beginlisp
\ANSWER{
(define (infix->prefix exp)
  (if (not (pair? exp))
      exp
      (list (cadr exp)
            (infix (car exp))
            (infix (caddr exp)))))
}
\endlisp


\newpage

{\Large\bf Local State}

Assume scheme has the following special form {\tt time}, which takes
one argument and times how long it takes to evaluate the argument.
Time returns a list of two elements, the first is the amount of time
it took to evaluate the expression, and the second is the value of the
expression.  For example,

\beginlisp
(time (sqrt 4))     ==>  (20 2)
(time (sqr 5))      ==>  (10 25)
(time (list 1 2 3)) ==>  (7 (1 2 3))
(time (/ 1 0))      ==>  Error: divide by zero
\endlisp

Assume, for simplicity, that {\tt (sqrt x)} always takes 20 time units
to compute and {\tt (sqr x)} always takes 10 time units to compute for
all positive numbers.

Louis has a program that he wants to make run faster.  He wants to see
what procedures are eating up the most amount of time.  He decides to
write a procedure called {\tt make-timed-procedure} which takes a
procedure and returns a procedure that does the same thing as the
original, but also keeps track of the total time spent in the
procedure.  For example,

\beginlisp
(define tsqrt (make-timed-procedure sqrt))
(define tsqr (make-timed-procedure sqr))
\endlisp

\begin{tabular}{p{3in}p{3in}}
\beginlisp
(tsqrt 'time) ==> 0
(tsqrt 4)     ==> 2
(tsqrt 'time) ==> 20
(tsqrt 4)     ==> 2
(tsqrt 'time) ==> 40
\endlisp &
\beginlisp
(tsqr 'time)  ==> 0
(tsqr 10)     ==> 100
(tsqr 'time)  ==> 10
(tsqr 10)     ==> 100
(tsqr 'time)  ==> 20
\endlisp
\end{tabular}

Louis writes the following procedure:

\beginlisp
(define make-timed-procedure-1
  (let ((total-time 0))
    (lambda (proc)
      (lambda (x)
        (if (eq? x 'time) 
            total-time
            (let ((result (time (proc x))))
              (set! total-time (+ total-time (car result)))
              (cadr result)))))))
\endlisp

After defining the following two functions, Louis trys out his code.
Show the output of each of the following expressions, assuming that
each call to {\tt sqrt} takes 20 and each call to {\tt sqr} takes 10
time units.

\beginlisp
(define tsqrt-1 (make-timed-procedure-1 sqrt))
(define tsqr-1 (make-timed-procedure-1 sqr))
\endlisp

{{\Huge$\Rightarrow$}}
\beginlisp
(map tsqrt-1 (map tsqr-1 '(-1 2 -3 4 -5))) ==> \ANSWER{(1 2 3 4 5)}
(tsqrt-1 'time)                            ==> \ANSWER{150}
(tsqr-1 'time)                             ==> \ANSWER{150}
\endlisp

This isn't quite the behavior we wanted.  What change needs to be made
to {\tt make-timed-procedure} so that we get the correct behavior?

{{\Huge$\Rightarrow$}}
\beginlisp
\ANSWER{
(define make-timed-procedure
  (lambda (proc)
    (let ((total-time 0))
      (lambda (x)
        (cond ((eq? x 'time) total-time)
              ((eq? x 'reset) (set! total-time 0) 0)
              (else (let ((result (time (proc x))))
                      (set! total-time (+ total-time (car result)))
                      (cadr result))))))))
}
\endlisp

\newpage

{\Large\bf Object Oriented Programming and Environment Diagrams}

Below is the object oriented system from the March 19th Lecture Notes
(just included for reference)

\beginlisp 
\scriptsize
(define (get-method object message)
  (object message))
\null
(define (no-method name)
  (list 'no-method name))
\null
(define (no-method? x)
  (if (pair? x)
      (eq? (car x) 'no-method)
      false))
\null
(define (method? x)
  (not (no-method? x)))
\null
(define (ask object message . args)
  (let ((method (get-method object message)))
    (if (method? method)
        (apply method (cons object args))
        (error "No method" message (cadr method)))))
\endlisp

Consider the following expressions:

\beginlisp
(define (create-counter)
  (let ((count 0))
     (lambda (message)
        (case message
          ((VALUE) (lambda (self) count))
          ((INCR) (lambda (self)
                    (set! count (+ 1 count))
                    count))
          ((DECR) (lambda (self)
                    (set! count (- count 1))
                    count))))))
\null
(define c1 (create-counter))
(define c2 (create-counter))
\endlisp

Draw the environment diagram for the above three expressions.

{{\Huge$\Rightarrow$}}

\ANSWERIS{\centerline{\psfig{figure=r26-ans-b.ps,height=1.8in}}}{\vspace{1.8in}}

Write the expression that you would use to get the value of counter {\tt c1}.

{{\Huge$\Rightarrow$}} \ANSWER{\tt (ask c1 'value)}

\vspace{0.1in}

Write the expression that you would use to increment counter {\tt c1}.

{{\Huge$\Rightarrow$}} \ANSWER{\tt (ask c1 'incr)}

\vspace{0.1in}

\newpage

{\Large\bf Streams and Higher Order Procedures}

In this part, we are going to create an infinite stream of
higher-order procedures.  First, here are some simple functions that
we are going to be using.

\beginlisp
(define (compose f g) (lambda (x) (f (g x))))
(define (incr x) (+ x 1))
(define (sqr x) (* x x)
\endlisp

Now, Consider the function {\tt compose-fstreams} that takes two
streams-of-functions, {\tt fs1} and {\tt fs2}, and returns another
stream-of-functions where each element is the result of composing the
corresponding elements of {\tt fs1} and {\tt fs2}.

\beginlisp
(define (compose-fstreams fs1 fs2)
  (cons-stream (compose (stream-car fs1) (stream-car fs2))
               (compose-fstreams (stream-cdr fs1) (stream-cdr fs2))))
\endlisp

We define the following two infinite streams of functions, one that
increments and one that squares.

\beginlisp
(define fs-incr (cons-stream incr fs-incr))
(define fs-sqr (cons-stream sqr fs-sqr))
\endlisp

We can now define another infinite stream-of-functions {\tt fs} (Hint:
this is similar to how we defined integers in terms of ones).

\beginlisp
(define fs
  (cons-stream incr (compose-fstreams fs-incr fs)))
\endlisp

What is the first element of the stream {\tt fs}?

{{\Huge$\Rightarrow$}} \ANSWER{The function that increments.}

What is the second element of the stream {\tt fs}?

{{\Huge$\Rightarrow$}} \ANSWER{The function that adds 2 to a number.}

Consider the function {\tt apply-fstream} and the definition of the
stream {\tt s}, below.  

\beginlisp
(define (apply-fstream fs x)
  (cons-stream
   ((stream-car fs) x)
   (apply-fstream (stream-cdr fs) x)))
\null
(define s (apply-fstream fs 0))
\endlisp

What are the first 10 elements of the stream {\tt s}?

{{\Huge$\Rightarrow$}} \ANSWER{(1 2 3 4 5 6 7 8 9 10 ...)}

Consider the following two streams that are defined.

\beginlisp
(define t1 (apply-fstream (compose-fstreams fs fs-sqr) 0))
(define t2 (apply-fstream (compose-fstreams fs-sqr fs) 0))
\endlisp

What are the first 5 elements of the stream {\tt t1}?

{{\Huge$\Rightarrow$}} \ANSWER{(1 2 3 4 5 ...)}

What are the first 5 elements of the stream {\tt t2}?

{{\Huge$\Rightarrow$}} \ANSWER{(1 4 9 16 25 ...)}

\newpage

{\Large\bf Meta Circular Evaluator}

We would like to introduce a new special form to our evaluator called
{\tt same?}.  {\tt Same?} always takes three arguments, and returns
{\tt \#t} if all three arguments are {\tt eq?}.  {\tt Same?}, however
is smart in that if the first two arguments are different, then the
third argument is {\bf not} evaluated.  Here are some examples of
using {\tt same?}.

\beginlisp
(same? 'x 'x 'x)       ==>  \#t
(same? 'x 'x 'y)       ==>  \#f
(same? 'x 'y 'y)       ==>  \#f
(same? 'x 'y (/ 1 0))  ==>  \#f
(same? 'x 'x (/ 1 0))  ==>  Divide by Zero Error
\endlisp

To add this special form to the evaluator, we need to define some data
abstraction.  

Define the function {\tt same??} that checks to see if an expression
is a {\tt same?} expression.

{{\Huge$\Rightarrow$}} 
\beginlisp
\ANSWER{(define (same?? exp) (tagged-list? exp 'same?))}
\endlisp

Define the functions {\tt same?-first} and {\tt same?-second} 
that select out the first and second sub-expressions (assume someone else
defined {\tt same?-third}).

{{\Huge$\Rightarrow$}} 
\beginlisp
\ANSWER{(define (same?-first exp) (cadr exp))}
\endlisp

{{\Huge$\Rightarrow$}} 
\beginlisp
\ANSWER{(define (same?-second exp) (caddr exp))}
\endlisp

Next, write the appropriate clause to add to the {\tt cond} clause of
{\tt eval}, assuming that we have the function {\tt eval-same?} that
will evaluate a {\tt same?} expression.

{{\Huge$\Rightarrow$}} 
\beginlisp
\ANSWER{  ((same?? exp) (eval-same? exp env))}
\endlisp

Finally, write the {\tt eval-same?} function that takes a {\tt same?}
expression and an environment and implements the special form as
described above.

{{\Huge$\Rightarrow$}} 
\beginlisp
\ANSWER{
(define (eval-same? exp env)
  (let ((val1 (eval (same?-first exp) env))
        (val2 (eval (same?-second exp) env)))
    (if (eq? val1 val2)
        (eq? val1 (eval (same?-third exp) env))
        \#f)))
}
\endlisp

Fill in the blanks:

{{\Huge$\Rightarrow$}} 
We need to make {\tt same?} a special form in our language because our
language has 
\ANSWERIS{\underline{applicative order}}{\rule[0.0in]{1.5in}{0.012in}}
evaluation.  If, instead, our language had 
\ANSWERIS{\underline{normal order}}{\rule[0.0in]{1.5in}{0.012in}}
evaluation, then we could simply
define {\tt same?} as a function.

Assuming our Scheme has the alternative method of evaluation (stated
in the previous paragraph), define {\tt same?} as a function.

{{\Huge$\Rightarrow$}} 
\beginlisp
\ANSWER{
(define (same? a b c)
  (if (eq? a b) 
      (eq? b c) 
      \#f))
}
\endlisp

\newpage

{\Large\bf Explicit Control Evaluator}

The special form {\tt same?} from the previous example was so helpful
that we decided to add it to the explicit control evaluator.  Assume
that in addition to the registers we've used in the past, we've also
got the register {\tt TMP}.  Fill in the blanks in the following code
that evaluates a {\tt same?}  expression.


{{\Huge$\Rightarrow$}} 
\beginlisp
 1. ev-same?
 2.   (assign unev (reg exp))
 3.   (assign exp ((op same?-first) (reg exp)))
 4.   (save continue)
 5.   \ANSWERIS{\underline{(save env)}}{\rule[0.0in]{1.5in}{0.012in}}
 6.   (save unev)
 7.   (assign \ANSWERIS{\underline{continue}}{\rule[0.0in]{1.5in}{0.012in}} \ANSWERIS{\underline{eval-after-first}}{\rule[0.0in]{1.5in}{0.012in}})
 8.   (goto \ANSWERIS{\underline{(label eval-dispatch)}}{\rule[0.0in]{1.5in}{0.012in}})
 9. eval-after-first
10.   (restore unev)
11.   \ANSWERIS{\underline{(restore env)}}{\rule[0.0in]{1.5in}{0.012in}}
12.   (assign tmp (reg val))
13.   (assign exp ((op same?-second) (reg unev)))
14.   (save tmp)
15.   \ANSWERIS{\underline{(save env)}}{\rule[0.0in]{1.5in}{0.012in}}
16.   (save unev)
17.   (assign continue eval-after-second)
18.   (goto \ANSWERIS{\underline{(label eval-dispatch)}}{\rule[0.0in]{1.5in}{0.012in}})     
19. eval-after-second
20.   (restore unev)
21.   \ANSWERIS{\underline{(restore env)}}{\rule[0.0in]{1.5in}{0.012in}}
22.   (restore tmp)
23.   (test (op eq?) \ANSWERIS{\underline{(reg tmp)}}{\rule[0.0in]{1.5in}{0.012in}} \ANSWERIS{\underline{(reg val)}}{\rule[0.0in]{1.5in}{0.012in}})
24.   (branch (label eval-third-arg))
25.   (assign val \#f)
26.   \ANSWERIS{\underline{(restore continue)}}{\rule[0.0in]{1.5in}{0.012in}}
27.   (goto (reg continue))
28. eval-third-arg
29.   (assign exp ((op same?-third) (reg unev)))
30.   \ANSWERIS{\underline{(assign continue eval-after-third)}}{\rule[0.0in]{1.5in}{0.012in}}
31.   (save tmp)
32.   (goto \ANSWERIS{\underline{(label eval-dispatch)}}{\rule[0.0in]{1.5in}{0.012in}})
33. eval-after-third 
34.   (restore tmp)
35.   \ANSWERIS{\underline{(restore continue)}}{\rule[0.0in]{1.5in}{0.012in}}
36.   (test (op eq?) \ANSWERIS{\underline{(reg tmp)}}{\rule[0.0in]{1.5in}{0.012in}} \ANSWERIS{\underline{(reg val)}}{\rule[0.0in]{1.5in}{0.012in}})
37.   (branch (label all-same))
38.   (assign val \#f)
39.   (goto (reg continue))
40. all-same
41.   (assign val \#t)
42.   (goto (reg continue))
\endlisp

{{\Huge$\Rightarrow$}} Does this {\tt same?} operation handle tail
recursion?  Why or why not?  

\ANSWER{The special form {\tt same?} is not (and cannot be) tail recursive
because they're always a delayed operation to check whether the value
of the third argument is {\tt eq?} with the second.}

{{\Huge$\Rightarrow$}} For example, is the following recursive or
iterative?

\beginlisp
(define (foo x y)
  (same? (even? x) (even? y) (foo x (/ y 2))))
\endlisp

\ANSWER{Recursive.  There is an implicit delayed operation to check to
see if the value of {\tt (even? y)} is {\tt eq?} with the value of
{\tt (foo x (/ y 2))}}


\newpage

{\Large\bf Concurrency}

Consider the following definitions of {\tt x} and {\tt y}

\beginlisp
(define x 2)
(define y 3)
\endlisp

In the table below, list all possible final values of {\tt z} after
the following expressions are evaluated.

\beginlisp
(parallel-execute 
  (lambda () (set! x (+ y y)))
  (lambda () (set! y (* x y))))
\null
(define z (list x y))
\endlisp

\vspace{0.2in}

{{\Huge$\Rightarrow$}} 
\beginlisp
\ANSWER{
(6 18), (6 6), (9 6), (12 6)
}
\null
\null
\endlisp

% \newpage
\vspace{0.2in}

{\Large\bf Implementing Put and Get}

Assume that we have one global {\tt put} and {\tt get} table called
{\tt *global-put-table*}.  Define (a simplified version of) put and
get as follows\footnote{Note that the put we used before took any
number of keys such as \lisp{(put 'a 'b '(c d) 5)} and then to
retrieve, \lisp{(get 'a 'b '(c d)) ==> 5}.  For this example, we'll be
simplifying it to take one list of keys.}.

\beginlisp
(put keys value)  --  Places the value in the global table indexed by keys
(get keys)        ==> value
\endlisp

For example,

\beginlisp
(put '(6001 is) 'fun)
(put '(the season is) 'spring)
(get '(6001 is))                ==>  fun
(put '(6001 is) '(almost over))
(put 'year 1999)
(get 'house)                    ==>  \#f
(get '(6001 is))                ==>  (almost over)
(get 'year)                     ==>  1999
\endlisp

Complete the following three definitions for put and get.

\beginlisp
{{\Huge$\Rightarrow$}} 
(define *global-put-table* \ANSWER{'()}               )
\null
{{\Huge$\Rightarrow$}} 
(define (put keys value)
\ANSWER{
  (set! *global-put-table* (cons (cons key value) *global-put-table*))
}
)
\null
{{\Huge$\Rightarrow$}} 
(define (get keys)
\ANSWER{
  (define (iter table)
    (cond ((null? table) \#f)
	  ((equal? (caar table) keys)
	   (cdar table))
	  (else (iter (cdr table)))))
  (iter *global-put-table*)
})
\endlisp


% {\Large\bf AMB Evaluator}
% 
% Using the AMB evaluator, write an expression that returns the list
% {\tt (x y z w)} such that 
% \[1 \le x < y < z < w \le 10\]
% and 
% \[x^2 + y^2 + z^2 = w^2 \;.\]
% 
% You may find the following procedures helpful.
% 
% \beginlisp
% (define (require pred)
%   (if (not pred) (amb) 'ok))
% \null
% (define (ints-from-to a b)
%   (if (> a b)
%       (amb)
%       (amb a (ints-from-to (+ a 1) b))))
% \endlisp
% 
% \vspace{0.2in}
% 
% {{\Huge$\Rightarrow$}} 
% \beginlisp
% \ANSWER{
% (let ((x (ints-from-to 1 10)))
%   (let ((y (ints-from-to (+ x 1) 10)))
%     (let ((z (ints-from-to (+ y 1) 10)))
%       (let ((w (ints-from-to (+ z 1) 10)))
%         (require (= (+ (* x x) (* y y) (* z z)) (* w w)))
%         (list x y z w)))))
% }
% \endlisp

\newpage

{\Large\bf Register Machines}

Draw the Data Paths AND Controller for a machine to compute whether
the input {\tt x} is odd by successively subtracting 1 from the input.
You can assume that the input will be a positive integer.  Assume the
only primitive operations you have are subtraction, logical not, and
testing equality.  After your machine finishes running, the result in
the {\tt answer} register should be either {\tt \#t} or {\tt \#f}.

\begin{tabular}{l}
Data Path  \\
{{\Huge$\Rightarrow$}} \\

\ANSWERIS{\centerline{\psfig{figure=r26-ans-c.ps,height=2.8in}}}{\vspace{2.8in}} \\
\\
\\
\hline
\\
Controller \\
{{\Huge$\Rightarrow$}} \\

\ANSWERIS{\centerline{\psfig{figure=r26-ans-d.ps,height=3.2in}}}{\vspace{3.2in}} \\

\end{tabular}

\newpage

{\Large\bf Compilers}

Consider the following compiled code:

\beginlisp
{\scriptsize
 1.    (assign val (op make-compiled-procedure) (label entry23) (reg env))
 2.    (goto (label after-lambda22))
 3.  entry23
 4.    (assign env (op compiled-procedure-env) (reg proc))
 5.    (assign env (op extend-environment) (const (f c)) (reg argl) (reg env))
 6.    (save continue)
 7.    (save env)
 8.    (assign proc (op lookup-variable-value) (const c) (reg env))
 9.    (assign val (op lookup-variable-value) (const f) (reg env))
10.    (assign argl (op list) (reg val))
11.    (test (op primitive-procedure?) (reg proc))
12.    (branch (label primitive-branch29))
13.  compiled-branch28
14.    (assign continue (label proc-return30))
15.    (assign val (op compiled-procedure-entry) (reg proc))
16.    (goto (reg val))
17.  proc-return30
18.    (assign proc (reg val))
19.    (goto (label after-call27))
20.  primitive-branch29
21.    (assign proc (op apply-primitive-procedure) (reg proc) (reg argl))
22.  after-call27
23.    (restore env)
24.    (restore continue)
25.    (assign val (op lookup-variable-value) (const f) (reg env))
26.    (test (op false?) (reg val))
27.    (branch (label false-branch25))
28.  true-branch26
29.    (assign val (const 1))
30.    (goto (label after-if24))
31.  false-branch25
32.    (assign val (const 2))
33.  after-if24
34.    (assign argl (op list) (reg val))
35.    (assign val (op lookup-variable-value) (const a) (reg env))
36.    (assign argl (op cons) (reg val) (reg argl))
37.    (test (op primitive-procedure?) (reg proc))
38.    (branch (label primitive-branch33))
39.  compiled-branch32
40.    (assign val (op compiled-procedure-entry) (reg proc))
41.    (goto (reg val))
42.  primitive-branch33
43.    (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
44.    (goto (reg continue))
45.  after-call31
46.  after-lambda22
47.    (perform (op define-variable!) (const a) (reg val) (reg env))
48.    (assign val (const ok))
}
\endlisp

Decompile the following groups of code.  (Hint: Don't worry if the
overall code looks a bit unusual.)

{{\Huge$\Rightarrow$}} Lines 8--22:
\ANSWER{\tt (c f)}

{{\Huge$\Rightarrow$}} Lines 25--33:
\ANSWER{\tt (if f 1 2)}

{{\Huge$\Rightarrow$}} Lines 8--45:
\ANSWER{\tt ((c f) a (if f 1 2))}

{{\Huge$\Rightarrow$}} Lines 1--48:
\beginlisp
\ANSWER{
(define a
  (lambda (f c) 
    ((c f) a (if f 1 2))))
}
\endlisp

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
