{\center CS 61A Midterm \#3 ver0.91 --- April 13, 1998 {\bf Exam Version: B}}

This booklet contains 8 numbered pages including the cover page.  Put all
answers on these pages, please; don't hand in stray pieces of paper.
This is an open book exam, worth 40 points, or about 13\% of your total course grade.
Our expectation is that many of you will not complete one or two of these
questions.  If you find one question especially difficult, leave it for
later; start with the ones you find easier.
{\bf When writing procedures, don't put in error checks.  Assume that you
will be given arguments of the correct type.}
The exam contains 7 substantive questions, plus the following:

\vspace{0.4cm}

\noindent {\bf Question 0 (1 point):}  Fill out this front page correctly and
put your name and login correctly at the top of each of the following
pages.

\vspace{1.0cm}

{\bf READ AND SIGN THIS:}

I certify that my answers to this exam are all my own work, and that
I have not discussed the exam questions or answers with anyone prior
to taking this exam.
If I am taking this exam early, I certify that I shall not discuss
the exam questions or answers with anyone until after the scheduled
exam time.

\vspace{0.5cm}

Signed: \underbar{\hskip 3in}


{\bf Question 1:}

 Write a brief scheme expression that generates the following stream (2 marks):

{\tt $\{$ (1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 ... ) ... $\}$ }


Given the following definition:

(define (stream-maker start fn)
  (define result
    (cons-stream start (stream-map fn result)))
  result)

For each of the following streams, can you create the stream from one call
to {\tt stream-maker}?  If "yes" than provide the call.  If "no" then just write
"no". (2 marks total) 
\item The stream of zeros and ones {\tt {0 1 0 1 0 1 0 1 .....}}


\item The stream of words like {\tt {b ban banan bananan banananan ....}}

\vspace{1.0cm}

\item Construct the stream of data 

{\tt $\{$ 0 1 10 11 100 101 ....$\}$}  

that
looks like the integers in binary. (2 marks)

{\em Hint 1: You can use our old friend the word function to compute (word
1 1) to make 11. Or you can multiply 1 by 10 and add 1 to make 11.}
{\em Hint 2: Think about defining a function that takes a stream of numbers
(a b ...)  and makes a new stream that looks like (a0 a1 b0 b1 ...).}
{\em Hint 3: Note that all the numbers in the stream except the first begin with
the digit 1.}


\noindent {\bf Question 2:}

\begin{enumerate}
\item Which of the following three sets {\em requires} a stream representation? (underline the ones
that do; 1 mark)
\begin{itemize}
\item the powers of two
\item the prime numbers
\item the even prime numbers
\end{itemize}

\item Eva writes a program that produces an infinite stream 
whose elements are randomly chosen integers in the range $0$ to $n$ inclusive; 
all of the numbers in this range appear in the stream.
Louis claims to write a program that {\em sorts} this stream
In one English sentence, explain why Louis is lying.  (1 mark)

\vspace{1.0cm}

\item Explain why Louis can write a program that looks as though it does this;
Eva cannot tell whether it has sorted her stream or not. (1 marks)

\vspace{1.0cm}

\item Write a program that returns a stream that is indistinguishable from a sorted
version of Eva's stream. (1 mark)

\vspace{1.0cm}

\end{enumerate}

\pagebreak

\large
{\center Your name \underbar{\hskip 2.5in} 
login cs61a--\underbar{\hskip 0.3in}{\bf Exam Version: B}}
\normalsize

\vspace{0.4cm}

\noindent{\bf Question 3:}   The following 
expressions have been entered in the order given, after opening a new Scheme
session:
\begin{verbatim}
> (define x 100)
> (define (foo x)
    (let ((x 5) (y x))
      (define (bar y)
        (* x y))
      (lambda (x)
        (if (= x y)
	    (+ x (bar x))
	    (+ y (bar x)))) ) )
> ((foo 4) 3)
\end{verbatim}
Answer the following questions, for one mark each:
\begin{enumerate}
\item What is returned from evaluating the last expression (i.e. 
{\tt ((foo 4) 3)})?

\vspace{0.3cm}

\item During the execution of these expressions, how many frames are 
created by user-defined functions, {\em other than the global 
environment}?

\vspace{0.3cm}

\item How many procedure pairs (pairs of circles) are created as a result of
executing these expressions?

\vspace{0.3cm}

\item Of these procedure pairs (pairs of circles), how many circles point 
to the global environment?

\vspace{0.3cm}

\item List everything {\it new} that is defined in the global environment as a
consequence of running this sequence of commands.

\vspace{0.3cm}


\item Is there an environment frame in the environment diagram 
created by executing these expressions which
looks like this?
\begin{verbatim}
+-------+
| y: 3  |	
|       |
|       |
+-------+
\end{verbatim}
\item If this frame exists, does it point to the global environment directly?
\vspace{0.3cm}
\item Is there an environment frame in the environment diagram 
created by executing these expressions which
looks like this?
\begin{verbatim}
+-------+
| y: 4  |	
|       |
|       |
+-------+
\end{verbatim}
\item If this frame exists, does it point to the global environment directly?
\end{enumerate}

\pagebreak
\large

{\center Your name \underbar{\hskip 2.5in} 
login cs61a--\underbar{\hskip 0.3in}{\bf Exam Version: B}}
\normalsize

\vspace{0.4cm}



\noindent {\bf Question 4:}   In a new scheme 
session, you enter the following forms in the order given:
\begin{verbatim}
(define (f) (let ((a 3))
   (lambda (x) (set! a (+ x a)) a)))

(define my-f (f))
(define my-f2 (f))
(define g (let ((a 3)) (lambda (x) (set! a (+ a x)) a)))
(define my-g1 g) 
(define my-g2 g)
\end{verbatim}
Next to each of the forms below {\it which are entered in this order}, 
write the return value (0.5 marks each):
\begin{itemize}
\item {\tt (my-f 4)}
\item {\tt (my-f 5)}
\item {\tt (my-f2 5)}
\item {\tt (my-f2 4)}
\item {\tt (my-g1 4)}
\item {\tt (my-g1 5)}
\item {\tt (my-g2 5)}
\item {\tt (my-g2 4)}
\end{itemize}
\pagebreak

\large

{\center Your name \underbar{\hskip 2.5in} 
login cs61a--\underbar{\hskip 0.3in}{\bf Exam Version: B}}

\normalsize

\vspace{0.4cm}

\noindent {\bf Question 5:} In a new scheme session, you enter the 
following expressions in the order given:
\begin{verbatim}
(define a (list 'a 'b 'c))
(define b (list 1 2 3))

(define (f x)
  (set! b (cdr b))
  (set-cdr! (cdr a) x))

(define g
  (let ((a (cddr a)))
    (lambda (b)
      (set-car! b a))))

(define (h x)
  (f x)
  (g x)
  (set-cdr! x b)
  (set-cdr! (car x) b))

(h a)
\end{verbatim}
\noindent Answer the following questions, for one mark each:
\begin{itemize}
\item When you evaluate {\tt a} at the prompt, what does scheme print out? 
\item When you evaluate {\tt b} at the prompt, what does scheme print out? 
\item Draw the box and pointer diagram for {\tt a}:
\vspace{1.0cm}
\item Draw the box and pointer diagram for {\tt b}:
\vspace{1.0cm}
\item
During the execution of these expressions, how many different frames 
were created by user-defined functions {\em excluding the global frame}? 
\item
How many of these DID NOT point to the global frame? 
\item
During the execution of these expressions, how many different procedure 
pairs (pairs of circles) were created by user-defined functions?


\noindent {\bf Question 6:} Into a fresh SCM session with our {\tt 
obj.scm}  loaded, you enter:
\begin{verbatim}
(define-class (staff) (method (help) "let me check")
                      (default-method "see me later"))

(define-class (ta)
 (parent (staff))
 (method (help) "Did you try this yourself?")
 (method (re-grade) "I'll give you 1 more point")
 (default-method   "see me during office hours"))

(define-class (prof)  (parent (staff)) (default-method "send me email"))

(define rjf (instantiate prof))
(define paul (instantiate ta))
\item Next to each of the forms below {\it which are entered in this order}, 
write the return value (3 marks total):

\item {\tt (ask paul 're-grade) }
\item {\tt (ask rjf 're-grade)}
\item {\tt (ask staff 'help) }
\item {\tt (ask rjf 'help)}


\item Since objects are procedures, in one English sentence explain 
why we encourage the use of {\tt ask}.  (i.e. explain why it is better 
to do {\tt (ask paul `help)} than {\tt (paul `help)}) (1 mark)

\noindent {\bf Question 7:} Into a clean Scheme session, you enter 
the following forms in the order given:
\begin{verbatim}
(define x 2)
(define s1 (make-serializer))
(define s2 (make-serializer))
(define f1 (s1 (lambda () (set! x (* x x)))))
(define f2 (s2 (lambda () (set! x (* x x)))))
\end{verbatim}
\begin{enumerate}
\item You now enter:
\begin{verbatim}
(parallel-exec f1 f2)
\end{verbatim}
What are the possible values for {\tt x} if this terminates? (2 marks)

\vspace{0.3 cm}

\item You now enter:
\begin{verbatim}
(parallel-exec (s2 f1) (s1 f2))
\end{verbatim}
What are the possible values for {\tt x} if this terminates? (2 marks)

\vspace{0.3cm}

\item
If either of the above parallel executions may result in deadlock, underline 
it. (1 mark)