\documentstyle[12pt]{article}
\include{ianMacros}
%\newcommand\entryBlank[1]{\rule{#1}{0.1pt}\makeStrut{3.5ex}}
%\newcommand\stdBlank{\entryBlank{2.7in}}
\expandMargins{0.6in}

\begin{document}
% \pagestyle{empty}

\vspace*{0.4in}
\begin{centering}
{\huge
Comp 210 \\
Exam \#2 \\
1998 Fall \\}
\end{centering}

\vspace{0.65in}

\noindent
Name: \rule{2.7in}{0.1pt}\makeStrut{3.5ex}

\noindent
This is a closed-book, closed-computer, {\it 3.5 hour} exam,
due 98.Dec.02 (Wed), 10:00. \\
%This should be plenty enough time.
{\bf Make sure to read each problem carefully.}
If you need to make any reasonable assumption to do a problem,
  just state that in the margin. \\
Please refrain from discussing the exam until after the due-date.

Except as indicated,
 you may (only) use the following built-in Scheme functions:
 {\it symbol? eq? boolean? empty? cons? cons first rest list
  number? zero? positive? negative? add1 sub1 + - * / = $<\  >\  \le\  \ge$}
 and the special forms {\it lambda define cond define-struct and or}
 (plus functions created by {\it define-struct}). %w/o ``!'' in their name.
Furthermore, you also use the special forms {\it local, set!, begin}.

Include contracts for all functions you write, 
if not provided in the problem.

\noindent
Time started:\rule{1.0in}{0.1pt}\makeStrut{3.5ex} \\
Time finished:\rule{1.0in}{0.1pt}\makeStrut{3.5ex} \\
{\bf Pledge:}
\vspace*{1.5in}

\begin{tabular}{|l|l|l|}
\hline
Problem 1 &  15 & \hspace*{0.75in} \\ \hline
Problem 2 &  20 & \\ \hline
Problem 3 &  20 & \\ \hline
Problem 4 &  15 & \\ \hline
Problem 5 &  20 & \\ \hline
Problem 6 &  10 & \\ \hline
Total     & 100 & \\ \hline
\end{tabular}



\pagebreak

\begin{enumerate}

\item (15 pts)
\label{log}
% generative recursion, (easy).
Given a number $n$, how many terms of the
doubling sequence $1, 2, 4, 8, 16, \ldots$
must be looked at until one is $\ge n$?
One way to calculate this is to work backwards:
count how many comparisons we must
make until $n$ successively halved becomes $\le 1$:
\begin{verbatim}
  ;; times-halved: number --> natNum
  ;;
  (define (times-halved n)
    (if (<= n 1)
        1
        (add1 (times-halved (/ n 2)))))

  ; Test:
  (times-halved 2) = 2
  (times-halved 6) = 4
  (times-halved 8) = 4
  (times-halved 1/7) = 1
\end{verbatim}
An equivalent, but slightly different, approach would be to
work forwards:
count how many comparisons we must make until $1$ successively doubled
becomes $\ge n$.
Implement this approach by writing
a function {\tt times-doubled} using an accumulator, so that
it is tail-recursive.  (Do not use {\tt set!}.)
\vspace*{3in}
\pagebreak



\item (20 pts)
% set!/local to remember history.
We will use the following structure in this problem and the next.
\begin{verbatim}
(define-struct student (name id friend))
; where <name> is a symbol, <id> is a natNum, and <friend> is a student or #f.
\end{verbatim}
Write a function {\tt create-student: symbol --> student}
which takes a name, and creates the corresponding student structure.
Initially the {\tt friend} field is {\tt \#f}.
The interesting part is the {\tt id}:
The first student created should have an {\tt id} of 1,
whe next an {\tt id} of 2, the nexts with {\tt id}s of 3,4,\ldots.
(So your function must remember how many times it has previously
been called.)
Note that while somebody could later use
 {\tt set-student-id!} to fake a student's
id, there should be no way they could cause {\tt create-student} to give
an incorrect id\footnote{To think about only: using what we know, it is
possible to make the function {\tt set-student-id!} inaccessible
to people calling your function.  How? (3pts extra credit if you
answer this {\em after} completing all the other exam questions.)}.

Hint: Define the function inside a {\tt local} (perhaps giving it
a silly name); have the {\tt local} return that function, giving
it a proper name outside the define.)
\vspace*{3.5in}

\pagebreak
Write the function 
{\tt befriend: student, student --> (void)}\footnote{You may return 
the symbol {\tt 'pal} instead of {\tt (void)}, if you prefer.}, which
sets the first student's friend to be the second student.
(Note that alas, the second student's friend does not automatically
become the first student.)
\vspace*{1.5in}

What functions would you call, to represent students 
Chris (whose friend is Pat),
Pat (whose friend is Kim), and Kim (whose friend is Pat).
Draw a picture
which also includes Jo (whose friend is Kim) (show no code for for Jo).
\vspace*{2.5in}





% Doing this securely is roundabout:  need to return two functions
% from a local:
%Now write {\tt num-students}, which takes no argument, and returns
%the number of students who have been created (i.e., how many times
%create-student has been called).
%It should be impossible for somebody to be able to 


\pagebreak
\item (20 pts)

At Nepotism State University, the child of the most generous alumnus
is guaranteed to be assigned to live in a suite
with their friend,
their friend's friend, their friend's friend's friend, etc.
(In the previous example, if Chris' parent donated enough money,
Chris would be in a suite with both Pat and Kim, but not Jo.)

%The son of a distinguished alumnus 
%Sydney Jones Wiess brown baker
%Mary Jo Eggleton

Write a function which accepts a student, and returns
the smallest size suite in which they can be housed,
if their parents pay up.
In order to avoid loops, go back and add a field {\tt assigned?}
to the student structure, and use this field to ensure finishing.

You may assume that every student has a friend (that is,
the friend field is never {\tt \#f} when this function is called).
\vspace*{3.9in}

What would you need to do,
so that your function could be called on several potential donor's children?
(State exactly what function(s) you would add/modify, to effect this.)
Describe your approach {\em concisely} (code not required).
\pagebreak





\item (15pts)
Many programming languages include other looping constructs
in addition to a for-loop.
One such construct is ``do-until'', which works as follows:
\begin{itemize}
\item
Syntax: do-until involves a body and a condition, e.g.
\mbox{{\tt (do-until {\it body!} {\it condition})}}.
In scheme, we'll make {\it body!} and {\it condition} 
both be functions that take zero arguments.
%(What should the return types be, if any?)
\item Semantics (meaning):
Execute (evaluate) {\it body!},
and then test the {\it condition}: if it returns true, 
then the loop terminates, otherwise the whole process is repeated.
\item
Pragmatics: Note that unlike a for-loop, the body is 
always executed at least once.  This tends to be handy in loops involving
input/output, where you want to at least read one input before quitting.
{\bf Example}: the main loop of the maze-program could be written:
\begin{verbatim}
(do-until (lambda () (handle-command! (read))) 
          (lambda () done-yet?))
\end{verbatim}
(Presumably, the variable {\tt done-yet?} is initially false,
and {\tt handle-command!} might {\tt (set! done-yet? \#t)}.)
\end{itemize}

Write {\tt do-until} in Scheme.  (Remember to include the contract.)
\vspace*{3in}

Using {\tt do-until}, rewrite {\tt timesDoubled}, from Problem~\ref{log}
(now you may use {\tt set!}).
\pagebreak



\item (20 pts)
% JAM
In Jam2000,
\begin{itemize}
\item
What assembly instruction is encoded as 00204335?
\item
What is a machine encoding of the assembly instruction (st R4 R3)?

\item
Translate the following (tail-recursive) Scheme function 
to JAM assembly language.
Indicate where in memory each instruction is stored,
and include comments about what each (group of) lines does.
(This program is able to fit all its variables into registers;
it does not need to load/store from main memory.)
Instead of returning a value, your assembly program should print 
the answer (in this case, it will be 32).

%e.c.: gcd.  Not for test, since you swap args.
\begin{verbatim}
;; Return result * 2^k.
;;
(define (powerOfTwo k result)
  (if (zero? k)
      result
      (powerOfTwo (sub1 k) (* 2 result))))

(powerOfTwo 5 1)  = 32 ; Two to the fifth; 1 is initial accum value.
\end{verbatim}
\vspace*{5in}
\end{itemize}
\pagebreak

\item (10pts)
Write {\tt map}, using {\tt make-list-fun}.

As reminders:
\begin{itemize}
\item {\tt map} takes a function $f$ and a list $lyst$,
      and returns a list containing the $f$ applied to each element of $lyst$.
      For example, {\tt \mbox{(map sqrt (list 16 1 25))} = \mbox{(list 4 1 5)}}.
\item 
\begin{verbatim}
(define make-list-fun
  (lambda (base combine)
    (local [(define the-fun
              (lambda (lyst)
                (cond [(empty? lyst) base]
                      [(cons?  lyst) (combine (first lyst)
                                              (the-fun (rest lyst)))])))]
      the-fun)))
\end{verbatim}
\end{itemize}
\vspace*{3in}
\pagebreak

\end{enumerate}
\end{document}
