\documentclass[10pt,twoside]{article}
\pagestyle{plain}
%%%%%%
%%%%%%
%%%%%% Modified by Kurt Meinz and Greg Krimer for Summer 2003
%%%%%%
%%%%%%
%%%%%%
%%%%%%
\setlength{\textwidth}{6.5in} \setlength{\textheight}{9.00in}
\setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in}
\setlength{\topmargin}{-.5in} \setcounter{page}{35}

\font\ninerm=cmr9 \font\nineit=cmti9 \font\ninebf=cmbx9
\font\ninett=cmtt9
\parindent=0pt
\parskip=8pt
%%\hyphenchar\tentt=-1
\def\invis#1{$\phantom{{\rm #1}}$}
\def\^{\char'136}
\def\{{\char'173}
\def\}{\char'175}
\def\bkslsh{\char'134}
\def\prgex{\smallskip\aftergroup\smallskip
\vskip 1pt
\tt\obeyspaces %
\def\par{\leavevmode\endgraf} %
\obeylines\parindent=0pt\parskip=0pt}
{\obeyspaces\global\let =\ }

\def\week#1#2{\vfill\eject
\begin{center}
\vspace{2mm}
 \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.2in { {\bf CS61A -- Homework #1 \hfill Kurt Meinz}}
       \hbox to 6.2in { University of California, Berkeley \ hfill Summer 2003}
       \vspace{1mm}
   }
}
\end{center}
\par
{\bf Topic:} #2
\par}

\def\ques#1{{\smallskip\bf Question #1.}}
\def\continue{{\bf The adventure continues on the next page.}\vfill\eject}
\def\oddlec#1#2{{\bf Lectures:} Monday #1, Tuesday #2 \par}
\def\evenlec#1#2{{\bf Lectures:} Wednesday #1, Thursday #2 \par}
\def\holidaylec#1{{\bf Lecture:} Wednesday #1 \par}
\def\as#1{{\bf Reading:} Abelson \& Sussman, #1\par}
\def\oddwr#1{\smallskip
{\bf Homework due at 8 PM Sunday, #1}\par}
\def\evenwr#1{\smallskip
{\bf Homework due at 8 PM Sunday, #1}\par}
\def\experts{\smallskip
{\bf Extra for experts:}\par}
\def\unix#1{\bigskip \hrule \hfill \par
Unix feature of the assignment: #1 \par}
\def\emacs#1{\par Emacs feature of the assignment: #1\par}

\begin{document}

%%%%%
%%%%%    Week 1.1
%%%%%     

\week {1.1}{Functional programming} 
{\bf Lecture:} Tuesday, June 24\par
\as{Section 1.1}

In this assignment you'll write simple recursive programs to
manipulate words and sentences, as well as explore what makes special forms,
well, special. You should use the functions {\tt sentence}, {\tt
first}, {\tt butfirst}, {\tt last} and {\tt butlast} presented in
lecture to operate on words and sentences. These functions are not
discussed in the book. If you have taken CS3 and know about
higher-order procedures such as {\tt every}, please do not use them;
use explicit recursion. 

This homework is due at {\bf 8 PM on Sunday, June 29}. Please put your
answers into a file called {\tt hw1-1.scm} and submit it electronically
by typing {\tt submit hw1-1} in the directory where the file is
located. You will probably find it convenient to make a new directory (folder)
for every week of the course and store the associated labs and
homeworks in it; to create a folder called {\tt week1} type 
{\tt mkdir week1} at the Unix prompt. We understand that many of you
have never used Unix before, and will be struggling to find your way
around. If you run into problems submitting the homework electronically
don't freak out. We'll be quite lenient about this the first time
around. Get your TA to help you submit on Monday. In subsequent weeks,
we expect you to have mastered the online submission process.  

Be sure to test each function you write; the sample calls given here
do not guarantee your code is bug-free. Include your test
cases in your submission, but make sure to comment them out (the
semicolon character begins a one-line comment in Scheme) so the file
loads smoothly. Unless explicitly disallowed, you may always write
helper procedures to help you solve the problem.\par

\ques 1 Write a procedure {\tt scale} that takes
two arguments: a number $n$ and a sentence of numbers. It should
multiply each number in the sentence by $n$ and return a sentence of
the results:

{\prgex%
STk> (scale 5 (se 1 2 0 10))
(5 10 0 50)
}

\ques 2 Write a procedure {\tt ends-e} that takes a sentence as its argument
and returns a sentence containing only those words of the argument whose last
letter is E:

{\prgex%
STk> (ends-e '(please put the salami above the blue elephant))
(please the above the blue)
STk> (ends-e '(absolutely nothing))
()
}

\ques 3 Write a procedure {\tt reverse} which reverses a
sentence:

{\prgex%
STk> (reverse '(the 1 after 99))
(99 after 1 the)
STk> (reverse '(kurt alex greg carolen))
(carolen greg alex kurt)
}

\continue

\ques 4 Write a predicate {\tt decreasing?} that takes a non-empty
sentence of numbers as its argument. It should return a true value if
the numbers are in strictly decreasing order and a false value
otherwise:

{\prgex%
STk> (decreasing? '(10 9 8 -2))
\#t
STk> (decreasing? '(5 5 4))
\#f
STk> (decreasing? '(17))
\#t
}

\ques 5 This question concerns special forms. 
\begin{itemize}
\item[{\bf A.}] Most versions of Lisp
provide {\tt and} and {\tt or} procedures like the ones described on Page 19 of
the book.  In principle there is no reason why these can't be ordinary
procedures, but some versions of Lisp make them special forms.
Suppose we evaluate

{\prgex%
STk> (or (= x 0) (= y 0) (= z 0))
}

If {\tt or} is an ordinary procedure, all three argument
expressions will be evaluated when {\tt or} is invoked.  But if
the variable {\tt x} has the value {\tt 0}, we know that {\tt or}
should return true regardless of the values of {\tt y} and {\tt z}.  
There is no reason to evaluate the other two expressions! A Lisp 
interpreter in which {\tt or} is a special form can evaluate the
arguments one by one until either a true one is found or it runs out
of arguments. (This is called {\it short-circuit} evaluation.)

Devise a test that will tell you whether Scheme's {\tt or} is a
short-circuit special form or an ordinary functions. That is, does 
{\tt or} evaluate all its arguments, or does it stop evaluating after
the first true value?

\item[{\bf B.}] Scheme has two special forms for making choices, {\tt
cond} and {\tt if}. Is it possible to define one in terms of the
other? Specifically, say we attempt to define our own {\tt if}
procedure:

{\prgex%
STk> (define (my-if predicate consequent alternative)
             (cond (predicate consequent)
                   (else alternative)))
}

Let's take it out for a spin:

{\prgex%
STk> (my-if (= 5 6) 'yes 'no)
     no
}

It seems to work. Let's try something more interesting:

{\prgex%
STk> (define (my-factorial n)
             (my-if (= n 0)
                    1
                    (* n (my-factorial (- n 1)))))
}

What happens when we attempt to use {\tt my-factorial}? Why?
\end{itemize}


% \unix{{\tt man}}
% \emacs{{\tt C-g}, {\tt M-x apropos}}

% There will be a ``feature of the assignment'' each assignment.  These first
% features come first because they are the ones that you use to find out about
% the other ones:  Each provides documentation of a Unix or Emacs feature.
% This assignment, type {\tt man~man} as a shell command to see the Unix manual
% page on the {\tt man} program.  Then, in Emacs, type {\tt M-x} (that's meta-{\tt X},
% or {\tt ESC~X} if you prefer) {\tt describe-function} followed by
% the Return or Enter key, then {\tt apropos} to see how the
% {\tt apropos} command works.  If you want to know about a command by its
% keystroke form (such as {\tt C-g}) because you don't know its long name (such
% as {\tt keyboard-quit}), you can say {\tt M-x~describe-key} then {\tt C-g}.

% You aren't going to be tested on these system features, but it'll
% make the rest of your life a {\it lot\/} easier if you learn about
% them. Seriously.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 1.2


\week {1.2}{Higher-order procedures}
\evenlec{June 25}{June 26}
\as{Section 1.3}

In this assignment you'll gain experience with Scheme's {\it first
class} procedures and the {\tt lambda} special form for creating
anonymous functions. Having first class procedures allows us to create
procedures that return procedures, as well as procedures which take
procedures as argument, called {\it higher order} functions.

This homework is due at {\bf 8 PM on Sunday, June 29}. Please put your
answers into a file called {\tt hw1-2.scm} and submit electronically
by typing {\tt submit hw1-2} in the directory where the file is
located. 

{\bf Note} that we are skipping 1.2; we'll get to it later.
Because of this, never mind for now the stuff about iterative versus
recursive processes in 1.3 and in the exercises from that section.

The book's treatment of this subject is highly mathematical because it
doesn't introduce symbolic data (such as words and sentences) until
later. Don't panic if you have trouble with the half-interval 
example on Page 67. Try to read and understand everything else.\par

\ques 1 Last week you wrote a procedure {\tt scale} that multiplied
each number in a sentence by $n$. Generalize this pattern to create a higher-order
procedure {\tt every} that takes two arguments: a one-argument
function and a sentence. It should apply the function to each element
of the sentence:

{\prgex%
STk> (every (lambda (x) (* x x)) '(1 2 3 4))
(1 4 9 16)
STk> (every pigl '(best class at cal))
(estbay assclay atay alcay)
}

How would you define {\tt scale} in terms of {\tt every}?

\ques 2 This question builds on the {\tt sum} procedure defined on Page 58.
\begin{itemize}
\item[{\bf A.}] The {\tt sum} function allows one to add up the
elements of a pattern defined by the parameters {\tt term} and {\tt
next} over some range $[a, b]$. Use {\tt sum} to define a function {\tt
sum-odds} that takes two numbers $a$ and $b$ and returns the sum of
all odd numbers between $a$ and $b$, inclusive:

{\prgex%
STk> (sum-odds 1 10)
     25                       ;; 1 + 3 + 5 + 7 + 9
     STk> (sum-odds 4 9)      
     21                       ;; 5 + 7 + 9
     STk> (sum-odds 7 7)      
     7                        ;; 7
}

\item[{\bf B.}] But what if we want to multiply numbers over a range? Define a
function {\tt product} that takes the same arguments as {\tt sum} but does multiplication
instead of addition:

{\prgex%
STk> (sum (lambda (x) 10) 1 (lambda (x) (+ x 1)) 3)
     30
     STk> (product (lambda (x) 10) 1 (lambda (x) (+ x 1)) 3)
     1000
}

The factorial of a number $n$ is $1 \cdot 2 \cdot 3 \cdot ... \cdot
n$. Use {\tt product} to define a {\tt factorial} function.

\item[{\bf C.}] Now use {\tt product} to approximate $\pi$
using the formula:

$${\pi\over4} = {2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \cdot ...\over{3
\cdot 3 \cdot 5 \cdot 5\cdot 7\cdot 7\cdot ...}}$$

Do this by writing a function {\tt pi} that takes one numeric
argument $i$. This parameter should in some way control the number of terms
computed; hence a larger value of $i$ should yield a closer
approximation to $\pi$. Exactly what is meant by ``number of terms''
is up to you. All we care about is that a larger value of $i$ produces a
better approximation. For example, our solution takes $i$ to be the
largest number in the numerator:

{\prgex%
STk> (pi 1000)
     3.1431607055322752
}

Depending on the meaning you give to $i$ and the algorithm you employ,
you might not get as close an approximation (or you might get an even
closer one!). It is also likely that making $i$ too big will overload
the machine, so don't be overeager. One way to do this problem is to compute the numerator and
denominator independently, then divide them. While this can be done, it's
trickier than it looks because you have to ensure the same number of
terms in both, and, as you can see the numerator and denominator don't
line up nicely. If you're stuck, try treating $2 \cdot 4 \over 3 \cdot
3$ as one unit.  

\item[{\bf D.}] If writing {\tt product} after {\tt sum} seemed
redunadant, it should have! They differ in only two ways: the
combiner and the value returned in the base case (often called the
``null value''). We'd like to generelize the pattern exhibited by both
functions to create a still more powerful procedure called {\tt
accumulate}. This function should take all the arguments that {\tt sum} and
{\tt product} do plus the two additional parameters: the combiner and
the null value. Once you have written {\tt accumulate} both {\tt sum}
and {\tt product} may be defined in terms of it like this:

{\prgex%
STk> (define (sum term a next b) (accumulate + 0 term a next b))
     sum
     STk> (define (product term a next b) (accumulate * 1 term a next b))
     product
}

Use {\tt accumulate} to define the function {\tt enumerate-interval},
which takes two numeric arguments $a$ and $b$, where $a \leq b$. It
returns a sentence of all the numbers between $a$ and $b$, inclusive:

{\prgex%
STk> (enumerate-interval 3 10)
     (3 4 5 6 7 8 9 10)
     STk> (enumerate-interval -3 3)
     (-3 -2 -1 0 1 2 3)
}
\end{itemize}

\ques 3 This question explores procedures as return values.
\begin{itemize}
\item[{\bf A.}] Define a procedure {\tt double} that takes a one argument
function $f$ and {\it returns a procedure} that applies $f$ twice:

{\prgex%
STk> (define 1+ (lambda (x) (+ x 1)))
     1+
     STk> (define 2+ (double 1+))
     2+
     STk> ((double 2+) 10)
     14
}

What value is returned by the following? Try to figure it out in your
head first!

{\prgex%
STk> (((double (double double)) 1+) 5)
}

\item[{\bf B.}] Now generalize {\tt double} by writing a procedure
{\tt repeated} that takes two arguments: a unary function $f$ and
and a nonnegative integer $n$ which is the number of times $f$ should be
applied. The {\tt repeated} procedure (which is built-in on our Scheme
system) should return a procedure which applies $f$ that many times: 

{\prgex%
STk> (repeated square 2)
     \#[closure arglist=(x) cd7fdc]        ;; returns a procedure!
     STk> ((repeated square 2) 5)
     625
     STk> ((repeated bf 3) '(a b c d e f))
     (d e f)
}

Needless to say, {\tt repeated} must be
recursive unlike {\tt double}. A particularly elegant solution exists
that uses {\tt compose} from Exercise 1.42 in the book. 

\end{itemize}

% \experts

% In principle, we could build a version of Scheme with no primitives except
% {\tt lambda}.  Everything else can be defined in terms of {\tt lambda},
% although it's
% not done that way in practice because it would be so painful.  But we can
% get a sense of the flavor of such a language by eliminating one feature at
% a time from Scheme to see how to work around it.

% In this problem we explore a Scheme without {\tt define}.  We can give things
% names by using argument binding, as {\tt let} does, so instead of

% {\prgex%
% (define (sumsq a b)
%   (define (square x) (* x x))
%   (+ (square a) (square b)))

% (sumsq 3 4)
% }



% {\bf Continued on next page.}

% \vfill\eject

% {\bf Homework assignment 1.2 continued...}

% we can say

% {\prgex%
% ((lambda (a b)
%    ((lambda (square)
%       (+ (square a) (square b)))
%     (lambda (x) (* x x))))
%  3 4)
% }

% This works fine as long as we don't want to use {\it recursive\/} procedures.
% But we can't replace

% {\prgex%
% (define (fact n)
%   (if (= n 0)
%       1
%       (* n (fact (- n 1)))))

% (fact 5)
% }

% by

% {\prgex%
% ((lambda (n)
%    (if ...))
%  5)
% }

% because what do we do about the invocation of {\tt fact} inside the body?


% Your task is to find a way to express the {\tt fact} procedure in a Scheme
% without any way to define global names.

% \unix{{\tt pine}, {\tt mail}, {\tt netscape}}
% \emacs{{\tt M-x info}, {\tt C-x u} (undo)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 2.1


\week {2.1}{Recursion and iteration}
\oddlec{June 30}{July 1}
\as{Section 1.2 through 1.2.4 (Pages 31--47)}

In this assignment you'll practice writing procedures that evolve
iterative processes. The homework is dues at {\bf 8 PM on Sunday,
July 6}. Please put your solutions into a file called {\tt hw2-1.scm}
and submit electronically by typing {\tt submit hw2-1} in the
appropriate directory. Be sure to include test cases!\par 

\ques 1 You've seen the {\tt keep} higher-order function in
lecture. It takes two arguments: a predicate and a sentence. It
returns a new sentence of only those elements that satisfy the
predicate (cause the predicate to return a true value):

{\prgex%
STk> (keep odd? '(1 2 3 4 5 6 7))
(1 3 5 7)
STk> (keep (lambda (x) (equal? x 'foo)) '(bar baz))
()
}

Write {\tt keep} so it generates an iterative process. 

\ques 2 The {\tt fast-expt} procedure presented on Page 45 performs
 exponentiation in a logarithmic number of steps using successive
 squaring. Its order of growth is approximately $\Theta(log_2(n))$, which is pretty damn
good. However, the book's version evolves a recursive process: each
time $n$ is even a call to {\tt square} needs to occur before the
function returns. Re-write {\tt fast-expt} so it evolves an iterative
process (and still uses a logarithmic number of steps, of
course). The idea behind successive squaring is:
$$b^n = (b^{n\over2})^2 = (b^2)^{n\over2}$$
To adapt this to an iterative algorithm, you'll need to maintain an
extra iteration variable, call it $a$ for ``answer,'' that is taken to
be 1 initially; the final value
of $a$ will be the result of {\tt fast-expt}. The value of $ab^n$ should not change from
one iteration to the next. In other words, $ab^n$ should remain {\it invariant}
throughout the computation. The individual values of $a$, $b$ and
$n$ may change from iteration to iteration.

\ques 3 An {\it infinite continued fraction} has the general form

$$ n_1\over{d_1 + {n_2\over{d_2 + {n_3\over{d_3 + ...}}}}}$$
 

\ques 4  A {\it perfect number} is defined as a number equal to the sum of all its
factors less than itself.  For example, the first perfect number is 6,
because its factors are 1, 2, 3 and 6, and $1 + 2 + 3 = 6$. The second perfect
number is 28, because $1 + 2 + 4 + 7 + 14 = 28$.  What is the third perfect number?
Write a procedure {\tt next-perfect} that takes a single number $n$ and
tests numbers starting with $n$ until a perfect number is found:
{\prgex%
STk> (next-perfect 4)
6
STk> (next-perfect 6)
6
STk> (next-perfect 7)
28
} 

To find the third perfect number evaluate {\tt (next-perf 29)}. To do
this problem, you'll need a {\tt sum-of-factors} subprocedure. If you
run this program when the system is heavily loaded, it may take a
while to compute the answer! Make sure your program can find 6 and 28
first.

Does {\tt next-perfect} evolve an iterative or recursive process?

% \experts

% 1.  The partitions of a positive integer are the different ways
% to break the integer into pieces.  The number 5 has seven partitions:

% {\prgex%
% 5       (one piece)
% 4, 1    (two pieces)
% 3, 2    (two pieces)
% 3, 1, 1 (three pieces)
% 2, 2, 1 (three pieces)
% 2, 1, 1, 1      (four pieces)
% 1, 1, 1, 1, 1   (five pieces)
% }

% The order of the pieces doesn't matter,
% so the partition 2, 3 is the same as the partition 3, 2
% and thus isn't counted twice.  0 has one partition.

% Write a procedure {\tt number-of-partitions}
% that computes the number of partitions of its nonnegative integer argument.

% 2.  Compare the {\tt number-of-partitions} procedure
% with the {\tt count-change} procedure by
% completing the following statement:
% {\prgex%
% Counting partitions is like making change, where the coins are ...
% }

% 3.  (Much harder!)  Now write it to generate an iterative process;
% every recursive call must be a tail call.

% \unix{{\tt mkdir}, {\tt cd}, {\tt pwd}, {\tt ls}}
% \emacs{{\tt C-M-f}, {\tt C-M-b}, {\tt C-M-n}, {\tt C-M-p} (move around Scheme code)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 2.2


\week {2.2}{Data abstraction}
\evenlec{July 2}{July 3}
\as{Sections 2.1 and 2.2.1 (Pages 79--106)}

In this assignment you'll practice working with Scheme lists. Although
lists look like sentences, you should treat them as a completely
separate type. Do not use sentence operators on lists! Below is a
table of sentence functions and their list counterparts:

$$\vbox{
\offinterlineskip
\halign{
\strut \vrule # & \vrule # \vrule \cr
\noalign{\hrule}
{\bf ~~Sentences} & {\bf ~~Lists} \cr
\noalign{\hrule}
{\tt ~first butfirst} & {\tt ~car cdr} \cr
\noalign{\hrule}
{\tt ~last butlast} & {\tt ~none} \cr
\noalign{\hrule}
{\tt ~sentence} & {\tt ~list append cons} \cr
\noalign{\hrule}
{\tt ~every} & {\tt ~map} \cr
\noalign{\hrule}
{\tt ~keep} & {\tt ~filter} \cr
\noalign{\hrule}
{\tt ~member?} & {\tt ~member} \cr
\noalign{\hrule}
{\tt ~item} & {\tt ~list-ref}  \cr
\noalign{\hrule}
{\tt ~empty?} & {\tt ~null?} \cr
\noalign{\hrule}
{\tt ~count} & {\tt ~length} \cr
\noalign{\hrule}
}
}$$

The homework is due at {\bf 8 PM Sunday, July 6}. Please put your
solutions into a file called {\tt hw2-2.scm} and submit them online.

Happy Fourth of July!\par

\ques 1 In the sentence world, {\tt keep} can be written in terms of
every, like this:

{\prgex%
STk> (define (keep pred sent) 
        (every (lambda (e) (if (pred e) e '())) sent))
STk> (keep word? '(in 1 day it will be 1999))
(in day it will be)
}

Can you use a similar trick to define {\tt filter} using {\tt map},
which is defined on Page 105? Why or why not?

\ques 2 Do Exercise 2.12 on Page 96. We'll represent percentages as
decimal values in the range $[0, 1]$. Here is the desired behavior:

{\prgex%
STk> (define my-interval (make-center-percent 10 .1))   ;; 10\% tolerance
int1
STk> (center my-interval)
10
STk> (percent my-interval)
.1
STk> (lower-bound my-interval)
9
STk> (upper-bound my-interval)
11    
}

Do not modify the selectors {\tt lower-bound} and {\tt upper-bound}.

\continue

\ques 3 The great thing about lists is that they can hold {\it any}
Scheme value: numbers, booleans, even procedures! Watch:

{\prgex%
STk> (define procs (list + * =))    ;; why doesn't '(+ * =) work?
procs
STk> ((car procs) 10 10 10)
30
STk> ((caddr procs) 9 11)
\#f
}

\begin{itemize}
\item[{\bf A.}] We'd like to exploit this feature by writing a
function {\tt call-all} that takes two arguments: a list of unary procedures
and an arbitrary Scheme value $x$. It should invoke all the procedures
in the list on $x$ in the intuitive order:

{\prgex%
STk> (call-all (list sqrt abs (lambda (x) (- x 6))) -10)
     4
     STk> (call-all (list car cdr cdr cdr cdr) '(a b c d e f))
     e
     STk> (call-all nil 'foo)   ;; identity function
     foo
     STk> (call-all (list list list list) \#t)
     (((\#t)))
}
  
Write {\tt call-all}.

\item[{\bf B.}] It'd be a lot nicer if instead of taking two arguments
{\tt call-all} could take {\it any number} of arguments, the last of
which is $x$, like this:

{\prgex%
STk> (call-all sqrt abs (lambda (x) (- x 6)) -10)
     4
     STk> (call-all car cdr cdr cdr cdr '(a b c d e f))
     e
     STk> (call-all 'foo)   ;; identity function
     foo
     STk> (call-all list list list \#t)
     (((\#t)))
}

Scheme provides a special {\tt dotted-tail notation} for definitions
that allows procedures to take an arbitrary number of arguments. For
example:

{\prgex%
STk> (define (f x y . z) (list x y z))
}

The procedure {\tt f} can be called with two or more arguments. The
first will be in {\tt x}; the second in {\tt y} and any
remaining arguments will be put into a list and be in {\tt z}:

{\prgex%
STk> (f 1 2 3 4)
     (1 2 (3 4))
     STk> (f 1 2)
     (1 2 ())
     STk> (f 1)
     *** Error: wrong number of arguments to procedure: (f 1)
}

Using this feature we can define the primitive operator {\tt list}
like this:

{\prgex%
STk> (define (list . args) args)
     list
     STk> (list 1 2 'three)
     (1 2 three)
     STk> (list)
     ()
}

Use dotted-tail notation to create a new version of {\tt call-all}
that behaves as above. It should accept one or more arguments. 
\end{itemize}

\ques 4 Since lists can contain other lists, it becomes possible to
create {\it nested} lists. Next week we'll explore nested lists and
other hierarchical data structures. As a prelude, write a function {\tt
group-3} that takes a single list as argument. The number of things in
the list will always be a multiple of three. The function should group
every three consecutive elements into a list, and return a list of
lists:

{\prgex%
STk> (group-3 '(a b c d e f g h i))
((a b c) (d e f) (g h i))
STk> (group-3 '(hello (there) fred))
((hello (there) fred))
}

First write {\tt group-3} so it generates a recursive process. Next
write a version that generates an iterative process. The iterative
approach is a bit more difficult; you may find {\tt append} useful. 

% \experts

% Write the procedure {\tt cxr-function} that takes as its argument a word
% starting with {\tt c}, ending with {\tt r}, and having a string of letters
% {\tt a} and/or {\tt d} in between, such as {\tt cdddadaadar}.  It should
% return the corresponding function.

% \unix{{\tt rm}, {\tt mv}, {\tt cp}, {\tt rmdir}, {\tt ln -s}}
% \emacs{{\tt M-\%} (find and replace text)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 3.1
 

\week {3.1}{Hierarchical data}
\oddlec{July X}{July X}
\as{Section 2.2.2--2.2.3, 2.3.1, 2.3.3}

In this assignment you'll gain experience working with structures that
have depth such as lists of lists and the Tree and Mobile abstract data
types. However, the book does not have a tree ADT. In fact, when the 
book refers to "trees"---as in {\tt scale-tree} on Page 112---it's really talking 
about deep lists. 

Our tree ADT---which consists of the functions {\tt make-tree}, {\tt children} 
and {\tt datum}---is itself usually implemented using lists:

{\prgex%
STk> (define make-tree cons)
STk> (define datum car)
STk> (define children cdr)
}

But remember, the underlying representation of any ADT is irrelevant! We can define {\tt make-tree} and friends in a thousand different ways. As you do this homework, fight the desire to
think of a Mobile or a Tree in terms of their underlying representations as lists.\par

\ques 1 Write a function {\tt deep-map} that takes a unary function
and a (possibly) nested list. It should apply the function to each
atomic element of the list and return a new list with the same nested 
structure:

{\prgex%
STk> (deep-map not '(\#f ((\#f) (\#t))))
(\#t ((\#t) (\#f)))
STk> (deep-map (lambda (a) 'foo) '())
()
STk> (deep-map (lambda (x) 'foo) '(((((3) 4) (5)) 6)))
(((((foo) foo) (foo)) foo))
STk> (deep-map square '(1 2 (3) 4))
(1 4 (9) 16)
STk> (deep-map list '(1 2 (3) 4))
((1) (2) ((3)) (4))
}

\ques 2 In this question we'll make use of the Tree ADT presented in
lecture. A Tree can have any number of children. The constructor is
{\tt make-tree} and takes two arguments, the second of which is a
{\it list of Trees} which are the children. The selectors are {\tt
datum} and {\tt children}. The following code builds up the tree 
at right (from the bottom up):
{\prgex%
(define eight (make-tree 8 '()))                             1
(define twelve (make-tree 12 '()))                         / \textbar \textbackslash
(define ten (make-tree 10 '()))                          /   \textbar   \textbackslash
(define six (make-tree 6 '()))                          2   12   3
(define seven (make-tree 7 '()))                        \textbar       / \textbar \textbackslash 
(define two (make-tree 2 (list eight)))                 8      6  9  7   
(define nine (make-tree 9 (list ten)))                            \textbar
(define three (make-tree 3 (list six nine seven)))                10
(define one (make-tree 1 (list two twelve three)))
}

This is a large Tree specifically so that you can play with
it. In testing your code, you may want to work with one of the
subtrees, such as {\tt three} or {\tt nine}. 

Write a function {\tt fringe} that takes a Tree and returns a list of
the datums of the leaf nodes, in any order:

{\prgex%
STk> (fringe one)
(8 12 6 10 7)
STk> (fringe three)
(6 10 7)
STk> (fringe six)
(6)
}

\ques 3 This question explores a Mobile ADT. A Mobile is very much like 
a tree with only two branches at every node: a right branch and a left branch. 
From each branch hangs either a weight, or another Mobile. Here is a constructor:

{\prgex%
STk> (define (make-mobile left right) (list left right))
}

A branch also consists of two parts: a length and a structure. The length of a 
branch is numeric; the structure at the end, however, can be {\it either} another 
Mobile or a weight (a number).

{\prgex%
STk> (define (make-branch length structure) (cons length structure))
}

The following code builds the Mobile at right (from the bottom up):

{\prgex%
STk> (define mobile-1 (make-mobile (make-branch 4 5) (make-branch 2 10)))
STk> (define mobile-2 (make-mobile (make-branch 3 10) (make-branch 2 mobile-1)))
STk> (define mobile-3 (make-mobile (make-branch 8 mobile-2) (make-branch 5 10)))
}

\begin{itemize}
\item[{\bf A.}] Write the four selectors. Two are for Mobiles: {\tt right-branch} and
 {\tt left-branch}. And two are for branches: {\tt branch-structure} and {\tt branch-length}. Try
 them out on {\tt mobile-3} above:
 
 {\prgex%
 STk> (branch-structure (right-branch mobile-3))
 10
 STk> (branch-length (left-branch (left-branch mobile-3)))
 3
 STk> (branch-structure (left-branch (right-branch (left-branch mobile-3))))
 5
 }
 
\item[{\bf B.}] Write a function {\tt total-weight} which returns the weight
of a Mobile. Assume branches are weightless; hence, only the weights increase the total weight
of a Mobile:

{\prgex%
STk> (total-weight mobile-1)
15
STk> (total-weight mobile-2)
25
STk> (total-weight mobile-3)
35
}

Students tend to solve this problem with many more base cases than are needed. You only
need {\it one} base case and one recursive case! Ask yourself, what are the "leaves" of a Mobile?

\item[{\bf C.}] A mobile is said to be {\it balanced} if the torque applied by its top-left
branch is equal to that applied by its top-right branch, and 


% \experts

% Read section 2.3.4 and do exercises 2.67--2.72.

% \unix{{\tt head}, {\tt tail}, {\tt more}, {\tt less}, {\tt cat}}
% \emacs{{\tt Ctrl-W, Ctrl-Y}; {\tt M-x line-number-mode}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 3.2


\week {3.2}{Representing abstract data}
\as{Sections 2.4 through
2.5.2 (pages 169--200)}
\evenlec{7/10}{7/11}
\evenwr{7/15}
\as{exercises 2.75, 2.76, 2.77, 2.79, 2.80, 2.81, 2.83}

Note: Some of these are thought-exercises; you needn't actually run any Scheme
programs for them!  (Some don't ask you to write procedures at all;
others ask for modifications to a program that isn't online.)

\experts

Another approach to the problem of type-handling is {\it type inference}.
If, for instance, a procedure includes the expression {\tt (+ n k)},
one can infer that {\tt n} and {\tt k} have numeric values.
Similarly, the expression {\tt (f a b)} indicates that the value of {\tt f}
is a procedure.

Write a procedure called {\tt inferred-types} that, given a definition of a
Scheme procedure as argument, returns a list of information about the
parameters of the procedure.  The information list should contain one
element per parameter; each element should be a two-element list whose first
element is the parameter name and whose second element is a word indicating
the type inferred for the parameter.  Possible types are listed on the next
page.

\medskip
{\parindent=1.5in
\begin{itemize}
\item{{\tt ?}} (the type can't be inferred)
\item{{\tt procedure}} (the parameter appeared as the first word in an
unquoted expression or as the first argument of {\tt map} or {\tt every})
\item{{\tt number}} (the parameter appeared as an argument of {\tt +}, {\tt -},
{\tt max}, or {\tt min})
\item{{\tt list}} (the parameter appeared as an argument of {\tt append}
or as the second argument of {\tt map} or {\tt member})
\item{{\tt sentence-or-word}} (the parameter appeared as an argument of {\tt first,}
{\tt butfirst,} {\tt sentence,} or {\tt member?}, or
as the second argument of {\tt every})
\item{{\tt x}} (conflicting types were inferred)
\end{itemize}
}
\medskip


{\bf Continued on next page.}

\vfill\eject

{\bf Homework assignment 3.2 continued...}


You should assume for this problem that the body of the procedure to
be examined does not contain any occurrences of {\tt if} or {\tt cond},
although it may contain arbitrarily nested and quoted expressions.
(A more ambitious inference procedure both would examine a more comprehensive
set of procedures and could infer conditions like "nonempty list".)

Here's an example of what your inference procedure should return.

{\prgex
(inferred-types
  '(define (foo a b c d e f)
    (f (append (a b) c '(b c)) (+ 5 d) (sentence (first e) f)) ) )
}

should return

{\prgex
((a procedure) (b ?) (c list) (d number)
 (e sentence-or-word) (f x))
}

If you're {\it really\/} ambitious, you could maintain a database of
inferred argument types and use it when a procedure you've seen is
invoked by another procedure you're examining!

\unix{{\tt du}, {\tt df}, {\tt quota}}
\emacs{{\tt M-q} (format paragraphs), {\tt C-M-q} (format Scheme code)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 4.1


\week {4.1}{Object-oriented programming}
\oddlec{7/15}{7/16}

Read ``Object-Oriented Programming---Above-the-line view'' (in course reader).

\oddwr{7/22}
{\bf Note:} Make sure to type
{\prgex%
(load "\~{}cs61a/lib/obj.scm")
}  before using {\tt define-class} and other features of the OOP language.

\begin{itemize}
\item[1] We have seen how to make a simple {\tt counter} class. Now let's
count by Fibs! Create a {\tt fib-counter} class that responds to
exactly two messages: {\tt next} and {\tt previous}. Instances of
this class will traverse the Fibonnacci sequence forward and
backward. When given the {\tt next} message an instance of this
class should return the next Fibonnacci number in sequence
(starting from 0); when given the {\tt previous} message, the
instance should go back (and return) the previous Fibonnacci
number. For example: 

{\prgex%
STk> (define fib1 (instantiate fib-counter))
STk> (ask fib1 'next)
0
STk> (ask fib1 'next)
1
STk> (ask fib1 'next)
1
STk> (ask fib1 'next)
2
STk> (ask fib1 'next)
3
STk> (ask fib1 'next)
5
STk> (ask fib1 'previous)
3
STk> (ask fib1 'next)
5}

\item[2] For a statistical project you need to compute lots of random numbers in
various ranges.  (Recall that {\tt (random~10)} returns a random number
between 0 and 9.)  Also, you need to keep track of {\it how many\/} random
numbers are computed in each range.  You decide to use object-oriented
programming.  Objects of the class {\tt random-generator} will accept two
messages.  The message {\tt number} means ``give me a random number in your
range'' while {\tt count} means ``how many {\tt number} requests have you
had?'' The class has an instantiation argument that specifies the range of
random numbers for this object, so

{\prgex%
(define r10 (instantiate random-generator 10))
}

will create an object such that {\tt (ask~r10~'number)} will return a random
number between 0 and 9, while {\tt (ask~r10~'count)} will return the number
of random numbers {\tt r10} has created.

\item[3] Define the class {\tt coke-machine}.  The instantiation
arguments for a {\tt coke-machine} are the number of Cokes that can fit
in the machine and the price (in cents) of a Coke:

{\prgex%
(define my-machine (instantiate coke-machine 80 70))
}

creates a machine that can hold 80 Cokes and will sell them for 70 cents
each.  The machine is initially empty.  {\tt Coke-machine} objects must
accept the following messages:

{\bf Continued on next page.}

\vfill\eject

{\bf Homework assignment 4.1 continued...}

{\tt (ask my-machine 'deposit 25)} means deposit 25 cents.
You can deposit several coins and the machine should remember the total.

{\tt (ask my-machine 'coke)} means push the button for a Coke.  This either
gives a {\tt Not enough money} or {\tt Machine empty} error message or
returns the amount of change you get.

{\tt (ask my-machine 'fill 60)} means add 60 Cokes to the machine.

Here's an example:

{\prgex%
(ask my-machine 'fill 60)
(ask my-machine 'deposit 25)
(ask my-machine 'coke)
NOT ENOUGH MONEY
(ask my-machine 'deposit 25)      ;; Now there's 50 cents in there.
(ask my-machine 'deposit 25)      ;; Now there's 75 cents.
(ask my-machine 'coke)
5                                 ;; return val is 5 cents change.
}

You may assume that the machine has an infinite supply of change.

\bigskip
We are going to use objects to represent decks of cards.  You are given
the list {\tt ordered-deck} containing 52 cards in standard order:

{\prgex%
(define ordered-deck '(AH 2H 3H ... QH KH AS 2S ... QC KC))
}

You are also given a function to shuffle the elements of a list:

{\prgex%
(define (shuffle deck)
  (if (null? deck)
      '()
      (let ((card (nth (random (length deck)) deck)))
        (cons card (shuffle (remove card deck))) )))
}

A deck object responds to two messages: {\tt deal} and {\tt empty?}.
It responds to {\tt deal} by returning the top card of the deck,
after removing that card from the deck;
if the deck is empty, it responds to {\tt deal} by returning {\tt ()}.
It responds to {\tt empty?} by returning {\tt \#t} or {\tt \#f},
according to whether all cards have been dealt.

Write a class definition for {\tt deck}.  When instantiated, a deck
object should contain a shuffled deck of 52 cards.

{\bf Continued on next page.}

\vfill\eject

{\bf Homework assignment 4.1 continued...}

\item[5] We want to promote politeness among our objects.  Write a class
{\tt miss-manners} that takes an object as its instantiation argument.
The new {\tt miss-manners} object should accept only one
message, namely {\tt please}.  The arguments to the {\tt please}
message should be, first, a message understood by the original
object, and second, an argument to that message.  {\bf (Assume
that all messages to the original object require exactly one
additional argument.)}  Here is an example using the {\tt person} class
from the upcoming adventure game project:

{\prgex%
> (define BH (instantiate person 'Brian BH-office))

> (ask BH 'go 'down)
BRIAN MOVED FROM BH-OFFICE TO SODA

> (define fussy-BH (instantiate miss-manners BH))

> (ask fussy-BH 'go 'east)
ERROR: NO METHOD GO

> (ask fussy-BH 'please 'go 'east)
BRIAN MOVED FROM SODA TO PSL
}

\end{itemize}

\experts

The technique of multiple inheritance
is described on pages 9 and 10 of ``Object-Oriented Programming --
Above-the-line view''.
That section discusses the problem of resolving ambiguous patterns
of inheritance, and mentions in particular that it might be better
to choose a method inherited directly from a second-choice parent
over one inherited from a first-choice grandparent.

Devise an example of such a situation.
Describe the inheritance hierarchy of your example,
listing the methods that each class
provides.  Also describe why it would be more appropriate in this example
for an object to inherit a given method from its second-choice parent
rather than its first-choice grandparent.

\unix{{\tt |} (pipes in the shell)}
\emacs{{\tt C-r, C-s}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 4.2


\week {4.2}{Assignment, state, environments}
\evenlec{7/17}{7/18}
\as{Section 3.1, 3.2}

Also read ``Object-Oriented Programming---Below-the-line view'' (in course
reader).

{\bf Note:} This is a large homeowrk assignment. Best to get
started early.

\evenwr{7/22} \as{exercises 3.1 through 3.11, skipping 3.5}

\experts

The purpose of the environment model is to represent the scope of
variables; when you see an {\tt x} in a program, which variable {\tt x}
does it mean?

Another way to solve this problem would be to {\it rename\/} all the
local variables so that there are never two variables with the same name.
Write a procedure {\tt unique-rename} that takes a (quoted) lambda expression
as its argument, and returns an equivalent lambda expression with the
variables renamed to be unique:

{\prgex%
> (unique-rename '(lambda (x) (lambda (y) (x (lambda (x) (y x))))))
(lambda (g1) (lambda (g2) (g1 (lambda (g3) (g2 g3)))))
}

Note that the original expression had two variables named {\tt x}, and
in the returned expression it's clear from the names which is which.
You'll need a modified counter object to generate the unique names.

You may assume that there are no {\tt quote}, {\tt let}, or {\tt define}
expressions, so that every symbol is a variable reference, and variables are
created only by {\tt lambda}.

Describe how you'd use {\tt unique-rename} to allow the evaluation of
Scheme programs with only a single (global) frame.

\unix{{\tt foreach}, {\tt grep}, {\tt find}}
\emacs{{\tt C-t} (transpose), {\tt M-c}, {\tt M-u}, {\tt M-l} (change case)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 5.1



\week{5.1}{Mutable data, queues, tables} \oddlec{7/22}{7/23}
\as{Section 3.3.1--3} (If you are a hardware type you might enjoy
reading 3.3.4 even though it isn't required.)

\evenwr{7/29}

\ques 1 In this question we look at destructive removal of elements
from a proper list and the associated difficulties. 
\begin{itemize}
\item[{\bf A.}] Write the procedure {\tt remove-nth!} that takes a list
and a number $n$. It should {\it destructively} remove the $n$th
element of the list (counting from zero). The return value of {\tt remove-nth!} is up to
you; it's the side-effect that we're after here. You may assume that
$n$ is nonzero and within the length of the list. The desired behavior
is this:

{\prgex%
STk> (define a (list 'a 'b 'c 'd))
     a
     STk> (remove-nth! a 2)       ;; return value ommitted
     STk> a
     (a b d)
}

\item[{\bf B.}] Now the interesting part: why can't $n$ be zero in
{\tt remove-nth!} above? Specifically, why is it impossible to write a
{\tt remove-nth!} function that behaves as follows:

{\prgex%
STk> (define a (list 'hello))
     a
     STk> (remove-nth! a 0)       ;; return value ommitted
     STk> a
     ()
}

Assuming you have a working {\tt remove-nth!} from Part A, why does
this definition of {\tt remove-nth-with-zero!}, which attemts to
handle the case when $n$ is zero, fail?

{\prgex%
STk> (define (remove-nth-with-zero! lst n)
             (if (= n 0)
                 (set! lst (cdr lst))
                 (remove-nth! lst n)))
}

\end{itemize}

\as{exercises 3.16, 3.17, 3.21, 3.25, 3.27}

You don't need to draw the environment diagram for exercise 3.27.
Instead, use a trace to provide the requested explanations.
Treat the table procedures {\tt lookup} and {\tt insert!}\ as primitive;
i.e.\ don't trace the procedures they call.
Also, assume that those procedures work in constant time.
We're interested to know about the number of times {\tt memo-fib} is
invoked.


% \experts

% 1. Abelson and Sussman, exercises 3.19 and 3.23.

% Exercise 3.19 is incredibly hard
% but if you get it, you'll feel great about yourself.  You'll need to
% look at some of the other exercises you skipped in this section.

% Exercise 3.23 isn't quite so hard,
% but be careful about the O(1)---i.e.\ {\it constant}---time requirement.

% 2.  Write the procedure {\tt cxr-name}.  Its argument will be a function
% made by composing {\tt car}s and {\tt cdr}s.  It should return the
% appropriate name for that function:

% {\prgex%
% > (cxr-name (lambda (x) (cadr (cddar (cadar x)))))
% CADDDAADAR
% }

% \unix{{\tt alias}, {\tt unalias}}
% \emacs{{\tt C-x 2; C-x 3; C-x 1; C-x o}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 5.2


\week{5.2}{Concurrency} \evenlec{3/19}{3/21} \as{Section 3.4}

\oddwr{7/29}
\as{exercises 3.38, 3.39, 3.40, 3.41, 3.42, 3.44,
3.46, 3.48}

\experts

Read Section 3.3.5 and do exercises 3.33--3.37.

\unix{{\tt \&}, {\tt \^{}Z}, {\tt fg}, {\tt bg}, {\tt jobs}, {\tt
kill}}
\emacs{{\tt M-x abbrev-mode}, {\tt M-x add-mode-abbrev}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 6.1


\week{6.1}{Streams}

\oddlec{7/29}{7/30}
\as{Section 3.5.1--3, 3.5.5}

This assignment explores infinite streams. Use {\tt show-stream}
(abbreviated as {\tt ss}) to print a
stream; it takes an optional second argument specifying the number of
elements to print. This homework is due at {\bf 8PM on Sunday, August
X}. Please put your solutions into a file
called {\tt hw6-1.scm} and submit it electronically with {\tt submit
hw6-1}. As always, include test cases in your file but be sure to
comment them out so the file loads smoothly. 

\ques 1 Write a procedure {\tt list->stream} that takes a list as its
argument and returns an infinite stream of the elements of the list,
re-starting at the beggning once the end of the list is reached:

{\prgex%
STk> (ss (list->stream '(cs61a is cool)))        
(cs61a is cool cs61a is cool cs61a is cool cs61a ...)    ;; it's true!
}

\ques 2 In this question, you'll write a more general {\tt stream-map}
procedure and use it to define a stream {\it implicitly}. 
\begin{itemize}
\item[{\bf A.}] We'd like to generalize the two-argument {\tt stream-map} function
defined on Page 320 so that it behaves as follows (Assume {\tt ones}
and {\tt integers} are both infinite streams.):

{\prgex%
STk> (ss (stream-map list ones integers) 5)
     ((1 1) (1 2) (1 3) (1 4) (1 5) ...)
}

As you can see, the new {\tt stream-map} takes $n$ streams and a procedure that can take $n$
arguments. The procedure is applied to the correponding elements of
each stream. You may assume that the streams given to {\tt stream-map}
will be infinite. Hence, a base case is not needed. Complete this
definition of {\tt stream-map}:

{\prgex%
(define (stream-map proc . streams)
        ({\it ??}
          (apply proc (map {\it ??} streams))
          (apply stream-map (map {\it ??} streams))))
}

\item[{\bf B.}] We'd now like to create an infinite stream of
factorials:

{\prgex%
STk> (ss factorials)
     (1 2 6 24 120 720 5040 40320 362880 3628800 ...)
}

The $n$th element of this stream is $n + 1$ factorial. Complete the
following implicit definition of this stream:

{\prgex%
(define factorials (cons-stream 1 (stream-map * {\it ??} {\it ??})))
}

Notice that unlike {\tt list->stream} from Question 1, you're not writing a function
that returns a stream; instead, you're defining the variable {\tt
factorials} to be the {\it stream itself}. Yet, because of the delayed
evaluiation afforded by streams, you may refer to the stream you're
defining as you're defining it! See Page 328 for a more complete discussion
of {\it implicit} stream definitions. Do not define any helper
functions for this problem. You may, however, use the {\tt integers}
stream.

\end{itemize}

\continue

\ques 3 Create an infinite stream called {\tt runs} that looks like
this:

{\prgex%
STk> (ss runs 15)
(1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 ... )
}

You'll probably want to use the generator approach to creating streams by defining an
auxilary function, say, {\tt runs-generator} and calling it with some
initial values. Then use it to define {\tt runs}:

{\prgex%
STk> (define runs (runs-generator{\it parameters}))
}

\ques 4 Write a procedure {\tt chocolate} that takes the name of
someone who likes chocolate a lot and creates an infinite stream that
says so:

{\prgex%
STk> (ss (chocolate 'puja) 25)
(puja likes chocolate puja really likes chocolate puja really really likes chocolate puja 
really really really likes chocolate puja really really really really likes chocolate ... )
}

If you have trouble with this problem, try to first define a version
of {\tt chocolate} for lists that takes an additional argument: the
maximum number of ``really''s. Then gradually change list operations
like {\tt cons} and {\tt append} to stream operations like {\tt
cons-stream} and {\tt stream-append}. You'll probably need a helper function.

\ques 5 The {\tt pairs} procedure defined on Page 341 seems more
complicated than needed. In the book's version, the first pair,
representing $(S_0, T_0)$ on the diagram on Page 339, is formed
expliticly. The {\tt stream-map} handles the subsequent pairings of
$S_0$. Why is the first pair a special case? Why can't {\tt
stream-map} take care of the entire row? Here is a simpler version of
{\tt pairs}:

{\prgex%
STk> (define (pairs s t)
    (interleave (stream-map (lambda (x) (list (stream-car s) x)))
                 t)
        (pairs (stream-cdr s) (stream-cdr t)))
}

Does this work? Explain what happens when we attempt to evaluatethe
following with the new definition:

{\prgex%
STk> (pairs integers ones)
}

% \experts

% 1.  Do exercises 3.59--3.62.

% 2.  Consider this procedure:

% {\prgex%
% (define (hanoi-stream n)
%   (if (= n 0)
%       the-empty-stream
%       (stream-append (hanoi-stream (- n 1))
%                      (cons-stream n (hanoi-stream (- n 1))))))
% }

% It generates finite streams; here are the first few values:

% {\prgex%
% (hanoi-stream 1)    (1)
% (hanoi-stream 2)    (1 2 1)
% (hanoi-stream 3)    (1 2 1 3 1 2 1)
% (hanoi-stream 4)    (1 2 1 3 1 2 1 4 1 2 1 3 1 2 1)
% }

% Notice that each of these starts with the same values as the one above it,
% followed by some more values.  There is no reason why this pattern can't be
% continued to generate an infinite stream whose first $2^n - 1$ elements are
% {\tt (hanoi-stream~n)}.  Generate this stream.

% \unix{{\tt diff}, {\tt wc}}
% \emacs{{\tt M-a}, {\tt M-e}, {\tt M-\{}, {\tt M-\}}, {\tt M-<}, {\tt M->} (move around buffer)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 6.2


\week{6.2}{Metacircular evaluator, Part I}
\evenlec{7/31}{8/1}
\as{Section
4.1.1--6}

A version of the metacircular evaluator is online in
{\tt \~{}cs61a/lib/mceval.scm}

\evenwr{8/5}

\ques 1 This question concerns adding special forms to the
metacircular evaluator as derived expressions. 
\begin{itemize}
\item[{\bf A.}] Add {\tt let} as a special form to the metacircular
evaluator by implementing a syntactic translation {\tt let->lambda}
that transforms a {\tt let} expression into the equivalent procedure
call:

{\prgex%
STk> (let->lambda '(let ((a 1) (b (+ 2 3))) (* a b))))
((lambda (a b) (* a b)) 1 (+ 2 3))                       ;; returns a list!
}

Remember, {\tt let->lambda} takes a {\it list} that represents a {\tt
let} expression and returns another {\it list} that represents the
equivalent procedure call. Do not be intimidated by this problem
simply because it appears in the context of the MCE. This is a simple
list-manipulation problem; the only thing that is new is that the list
happens to look like Scheme code. Make sure your {\tt let->lambda}
function works correctly before proceding; test it in isolation, at
the STk (not MCE!) prompt. After you have written {\tt
let->lambda}, install {\tt let} into the interpreter by adding the
following clause to {\tt mc-eval}:

{\prgex%
((let? exp) (mc-eval (let->lambda exp) env))
}

Don't forget to define the predicate {\tt let?} in the obvious
way. You should now be able to use the {\tt let} form in your
metacircular interpreter, like this:

{\prgex%
;;; M-Eval input:
(let ((cadr (lambda (x) (car (cdr x)))))
  (cadr '(one two three)))

;;; M-Eval value:
two
}

\item[{\bf B.}] The {\tt let*} special form is similar to {\tt let}
except that the bindings are preformed sequentially (from left to
right), allowing you to refer to one {\tt let} variable in defining
the another:

{\prgex%
STk> (let* ((a 10) (b (* a a)) (c (+ a b)))
    (list a b c))
(10 100 110)
}
      
One way to implement {\tt let*} is by transforming it into nested {\tt
let} expressions. That is, the expression

{\prgex%
(let* ((a 10) (b (* a a)) (c (+ a b))) 
   (list a b c))
} 

is just syntactic sugar for 

{\prgex%
(let ((a 10))
  (let ((b (* a a)))
    (let ((c (+ a b))) 
      (list a b c))))
} 

Add {\tt let*} to the MCE by implementing this syntactic
transformation. Write the function {\tt let*->lets} which takes a {\it
list} that looks like a {\tt let*} expression and returns nested
lets. Before doing anything else, test your function in isolation
first:

{\prgex%
STk> (let*->lets '(let* ((a 10) (b (* a a)) (c (+ a b))) (list a b c)))
(let ((a 10)) (let ((b (* a a))) (let ((c (+ a b))) (list a b c))))
}

Then do everything else neccessary to allow {\tt let*} to be used in
metacircular scheme.
\end{itemize}
 
\ques 2 Sometimes it's convenient to initialize a whole slew of
variables with a single {\tt define}. Modify the {\tt eval-definition}
function to cope with a definition such as:

{\prgex%
;;; M-Eval input:
(define a (+ 2 3)
        b (* 2 5)
        c (+ a b))

;;; M-Eval value:
ok

;;; M-Eval input:
(list a b c)

;;; M-Eval value:
(5 10 15)
}

Like {\tt let*} in the previous problem, the bindings should be
performed sequentially in a left-to-right order, allowing later
bindings to refer to earlier ones. Do not implement this feature as a
derived expression by, say, turning 

{\prgex%
(define a (+ 2 3) b (* 2 5) c (+ a b))
} 

into

{\prgex%
(begin (define a (+ 2 3)) (define b (* 2 5)) (define c (+ a b)))
} 

Change {\tt eval-definition} instead. Remember to always test in
isolation first:

{\prgex%
STk> (eval-definition '(define a (+ 2 3) b (* 2 5) c (+ a b))
                      the-global-environment)
ok
}

\ques 3 In lab (Exercise 4.4) you added {\tt and} and {\tt or} to the
MCE. An important detail of these two special forms is that {\tt and}
returns \#f or the {\it last true value}. For example:

{\prgex%
STk> (and 1 2 3 4)
4
}

Similarly, {\tt or} returns \#f or the {\it first true value}:

{\prgex%
STk> (or 1 2 3 4)
1
}

Here is a na\"\i ve implementation of {\tt or}:

{\prgex%
(define (eval-or exp env)
    (if (null? exp)
        \#f
        (if (true? (mc-eval (car exp) env))
            (mc-eval (car exp) env)
            (eval-or (cdr exp) env))))
}

Assume we've defined {\tt or?} in the obvious way and added the
following clause to {\tt mc-eval}:

{\prgex%
((or? exp) (eval-or exp env))
}

Show a sample interaction with the MCE that reveals a bug in {\tt
eval-or}. You can use STk to see what the ``right answer'' is for any
given {\tt or} expression. How would you fix this bug? (You don't
actually need to fix it if you don't want to.) 

\ques 4 The MCE is missing quite a few primitive procedures. Evaluate
{\tt primitive-procedures} in STk to see which ones are
available. Some primitives can be added by sticking them into the
list:

{\prgex%
(define primitive-procedures
  (list (list 'car car)
        (list 'cdr cdr)
        (list 'display display)     ;; new!
             ...
}

We'd like to make the higher-order function {\tt map} available as a
primitive procedure in the metacircular evalutor:

{\prgex%
STk> (mce)   ;; initializes interpreter

;;; M-Eval input:
(map (lambda (x) (* x x)) '(1 2 3))

;;; M-Eval value:
(1 4 9)
}

First, explain why adding STk's {\tt map} procedure to the list of
primitives:

{\prgex%
(define primitive-procedures
  (list (list 'car car)
        (list 'cdr cdr)
        (list 'map map)     ;; new!
}

{\it does not} work. (Hint: STk's {\tt map} is designed to be used
with STk procedures, which look like {\tt \#[closure arglist=(x)
d3afbc]}. What do MCE procedures look like?)

\unix{{\tt !}, {\tt history}}
\emacs{{\tt C-x (}, {\tt C-x )}, {\tt C-x e} (keyboard macros)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 7.1


\week{7.1}{Analyzing evaluator, Lazy evaluator}
\oddlec{8/5}{8/6}
\as{Sections 4.1.7, 4.2}

A version of the analyzing evaluator is online in
{\tt \~{}cs61a/lib/analyze.scm}

A version of the lazy evaluator is online in
{\tt \~{}cs61a/lib/lazy.scm}

\oddwr{8/12}

\as{exercises 4.22, 4.23, 4.24, 4.25, 4.26, 4.28, 4.30, 4.32, 4.33}

\experts

Exercise 4.31 in Abelson and Sussman.  This exercise doesn't require
great brilliance, but it's a lot of work and involves a lot of debugging
of details.  On the other hand, completing this exercise will teach you
a lot about the evaluator.

\unix{{\tt echo}, {\tt set}, {\tt setenv}, {\tt printenv}}
\emacs{{\tt M-!} (run shell command)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 7.2

\week{7.2}{Nondeterministic evaluator}
\evenlec{8/12}{8/13}
\as{Section 4.3}

A version of the nondeterministic evaluator is online in
{\tt \~{}cs61a/lib/ambeval.scm}

\evenwr{8/12}

\as{exercises 4.36, 4.42, 4.45, 4.47, 4.48, 4.49, 4.50, 4.52}

\experts

Fix the {\tt handle-infix} procedure from project 4
to handle infix precedence for arithmetic operators properly.
That is, multiplications and divisions should be done before
additions and subtractions.  Comparison operators like {\tt =}
come last of all.

\unix{{\tt bash}, {\tt zsh}}
\emacs{{\tt C-x} {\tt C-o}, {\tt M-\bkslsh} (delete blank space)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 8.1

\week{8.1}{Logic programming} \oddlec{8/13}{8/14} \as{Section
4.4.1--3}

We are not assigning section 4.4.4, which discusses the implementation of the
query system in detail.  Feel free to read it just for interest; besides
deepening your understanding of logic programming, it provides an example of
using streams in a large project.

\oddwr{8/15}
\as{exercises 4.56, 4.57, 4.58, 4.65}

For all problems that involve writing queries or rules,
test your solutions. To run the query system and load in the sample data:

{\prgex%
scm
(load "\~{}cs61a/lib/query.scm")
(initialize-data-base microshaft-data-base)
(query-driver-loop)
}

You're now in the query system's interpreter.  To add an assertion:

{\prgex%
(assert! (foo bar))
}

To add a rule:

{\prgex%
(assert! (rule (foo) (bar)))
}

Anything else is a query.

\ques 2 This question explores a query arithmetic system where numbers
are represented as lists. That is, a number $n$ will be represented by
an $n$-element list of {\tt a}'s. The number five, for example, looks
like {\tt (a a a a a)} and zero is just {\tt ()}. 
\begin{itemize}
\item[{\bf A.}] Note that summing two of these funny query numbers
merely involves joinging the lists that represent them. We can define
a rule for adding query numbers using {\tt append-to-form}:

{\prgex%
;;; Query input:
    (assert! (rule (?a + ?b = ?c)
                     (append-to-form ?a ?b ?c)))

     Assertion added to data base.

     ;;; Query input:
     ((a a a a) + (a a a) = ?what)

     ;;; Query results:
     ((a a a a) + (a a a) = (a a a a a a a))
}

Devise rules to allow multiplication of query numbers:

{\prgex%
;;; Query input:
     ((a a a a) * (a a a) = ?what)

     ;;; Query results:
     ((a a a a) * (a a a) = (a a a a a a a a a a a a))  ;; 4 * 3 = 12
}

\item[{\bf B.}] Using your multiplication rule from above, implement a
factorial relation for query numbers:

{\prgex%
;;; Query input:
     ((a a a a) ! = ?what)

     ;;; Query output:
     ((a a a a) ! = (a a a a a a a a a a a a a a a a a a a a a a a a))  ;; 4! = 24 
}
\end{itemize}

\ques 3 We can interpret the query interpreter's failure to return any
results as saying, ``Your query was not consistent with any assertions
I know or any rules I can apply on the basis of those assertions.''
This can be used to implement true/false queries where the
interpreter echoes the query if it is true and display no results
otherwise. For example:

{\prgex%
;;; Query input:
(deep-member a '((a) b))

;;; Query output:        
(deep-member a '((a) b))           ;; true

;;; Query input:
(deep-member c '((b ((a)))))

;;; Query output: 
                                    ;; false

;;; Query input:
(deep-member c '((b ((a c)))))

;;; Query output:
(deep-member c '((b ((a c)))))
}

Write rules for the {\tt deep-member} relation that behaves as above.





\ques 4 Write query rules for the {\tt assoc} relation. It should work
like this:

{\prgex%
;;; Query input:
(assoc carolen ((greg 10) (kurt 12) (carolen 10) (alex 13) (carolen 15)) ?what)

;;; Query results:
(assoc carolen ((greg 10) (kurt 12) (carolen 10) (alex 13) (carolen 15)) (carolen 7))

;;; Query input:
(assoc todd ((greg 10) (kurt 12) (carolen 10) (alex 13) (carolen 15)) ?what)

;;; Query results:
                                              ;; no results!

}

Notice that the {\it first} sublist beggining with {\tt carolen} is
brought forth. It should run backwards, too:

{\prgex%
;;; Query input:
(assoc ?who ((greg 10) (kurt 12) (carolen 7) (alex 13) (carolen 15)) (?who 10))

;;; Query results:
(assoc greg ((greg 10) (kurt 12) (carolen 7) (alex 13) (carolen 15)) (greg 10))
(assoc carolen ((greg 10) (kurt 12) (carolen 7) (alex 13) (carolen 15)) (carolen 10))
}


% \experts

% The lecture notes for this week
% describe rules that allow inference of the {\tt reverse} relation
% in one direction, i.e.,

% {\prgex
% ;;; Query input:
% (forward-reverse (a b c) ?what)

% ;;; Query results:
% (FORWARD-REVERSE (A B C) (C B A))
% }

% {\bf Continued on next page.}

% \vfill\eject

% {\bf Homework assignment 8.1 continued...}

% {\prgex%
% ;;; Query input:
% (forward-reverse ?what (a b c))

% ;;; Query results:
% {\rm{}... infinite loop}
% }

% or

% {\prgex
% ;;; Query input:
% (backward-reverse ?what (a b c))

% ;;; Query results:
% (BACKWARD-REVERSE (C B A) (A B C))

% ;;; Query input:
% (backward-reverse (a b c) ?what)

% ;;; Query results:
% {\rm{}... infinite loop}
% }

% Define rules that allow inference of the {\tt reverse} relation in both
% directions, to produce the following dialog:

% {\prgex
% ;;; Query input:
% (reverse ?what (a b c))

% ;;; Query results:
% (REVERSE (C B A) (A B C))

% ;;; Query input:
% (reverse (a b c) ?what)

% ;;; Query results:
% (REVERSE (A B C) (C B A))
% }

% \unix{{\tt perl}, {\tt awk}, {\tt sed}}
% \emacs{{\tt M-x shell-command-on-region}}


\end{document}


