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

%%%%%%%%%%%
%%%%%%%%%%% Modified by A. Coates
%%%%%%%%%%% Turned into appropriate for summer session
%%%%%%%%%%% Homework Assignments

%%%%%%%%%%%
%%%%%%%%%%% This can be used as a template for summer session
%%%%%%%%%%% since the redate code is difficult to modfy to support summer session
%%%%%%%%%%% ( the date files are coded to think of weeks...)

\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 2002}
       \vspace{1mm}
   }
}
\end{center}
\par
{\bf Topic:} #2
\par}

\def\oddlec#1#2{{\bf Lectures:} Monday #1, Tuesday #2 \par {\bf Reading:}}
\def\evenlec#1#2{{\bf Lectures:} Wednesday #1, Thursday #2 \par {\bf Reading:}}
\def\holidaylec#1{{\bf Lecture:} Wednesday #1 \par {\bf Reading:}}
\def\as#1{Abelson \& Sussman, #1\par}
\def\oddwr#1{\smallskip
{\bf Homework due 10 AM  Monday, #1:}\par}
\def\evenwr#1{\smallskip
{\bf Homework due 10 AM  Monday, #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} \oddlec{6/24}{6/25}
%%%%%%%
\as{Section 1.1}

\oddwr{7/1}

\newcount\question
\global\question=0
\def\newq{\global\advance\question by 1
\noindent{\bf\the\question . }}
\def\hot{\noindent{\bf Hotshots: }}

{\bf People who've taken CS 3:  Don't use the CS~3 higher-order procedures
such as {\tt every} in these problems; use recursion.}

\newq Exercise 1.5, page 21.

\newq Exercise 1.6, page 25.
If you had trouble understanding the square root
program in the book, explain instead what will happen if you use
{\tt new-if} instead of {\tt if} in the {\tt pigl} Pig Latin procedure.

\newq Write a procedure {\tt squares} that takes a sentence of numbers as
its argument and returns a sentence of the squares of the numbers:

{\prgex%
> (squares '(2 3 4 5))
(4 9 16 25)
}

\newq Write a procedure {\tt switch} that takes a sentence as its argument
and returns a sentence in which every instance of the words {\tt I} or {\tt
me} is replaced by {\tt you}, while every instance of {\tt you} is replaced
by {\tt me} except at the beginning of the sentence, where it's replaced by
{\tt I}.  (Don't worry about capitalization of letters.)  Example:

{\prgex%
> (switch '(you told me that i should wake you up))
(i told you that you should wake me up)
}

\newq Write a predicate {\tt ordered?} that takes a sentence of numbers as
its argument and returns a true value if the numbers are in ascending order,
or a false value otherwise.

\newq 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%
> (ends-e '(please put the salami above the blue elephant))
(please the above the blue)
}

{\bf Continued on next page.}

\vfill\eject

{\bf Homework assignment 1.1 continued...}

\newq Most versions of Lisp provide {\tt and} and {\tt or}
procedures like the ones on page 19.  In principle there is no reason why
these can't be ordinary procedures, but some versions of Lisp make them
special forms.  Suppose, for example, we evaluate

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

\noindent If {\tt or} is an ordinary procedure, all three argument
expressions will be evaluated before {\tt or} is invoked.  But if
the variable {\tt x} has the value {\tt 0}, we know that the
entire expression has to be true regardless of the values of {\tt
y} and {\tt z}.  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.)

Your mission is to devise a test that will tell you whether
Scheme's {\tt and} and {\tt or} are short-circuit special forms or
ordinary functions.  This is a somewhat tricky problem, but it'll
get you thinking about the evaluation process more deeply than you
otherwise might.

Why might it be advantageous for an interpreter to treat {\tt or} as a
special form and evaluate its arguments one at a time?  Can you think of
reasons why it might be advantageous to treat {\tt or} as an ordinary
function?

\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{6/26}{6/27}
\as{Section 1.3}

\evenwr{7/1}

{\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.

Don't panic if you have
trouble with the half-interval example on pp. 67--68; you can just skip
it.  Try to read and understand everything else.

1.  \as{exercises 1.31(a), 1.32(a), 1.33, 1.40, 1.41, 1.43, 1.46}

(Pay attention to footnote 51; you'll need to know the ideas in
these exercises later in the semester.)

2.  Last week you wrote procedures {\tt squares}, that squared each number
in its argument sentence, and saw {\tt pigl-sent}, that {\tt pigl}ed each word
in its argument sentence.  Generalize this pattern to create a higher-order
procedure called {\tt every} that applies an {\it arbitrary\/} procedure,
given as an argument,
to each element of an argument sentence.
This procedure is used as follows:

{\prgex%
> (every square '(1 2 3 4))
(1 4 9 16)
> (every 1+ '(1 2 3 4))
(2 3 4 5)
}

\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{7/1}{7/2}
\as{Section
1.2 through 1.2.4 (pages 31--47)}


{\smallskip {\bf Homework due 10 AM  Monday, 7/8:}\par}

1.  \as{exercises 1.16, 1.35, 1.37, 1.38}

2.  A ``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-perf n)} that tests numbers starting with {\tt
n} and continuing with {\tt n+1}, {\tt n+2}, etc.\ until a perfect number is
found.  Then you can evaluate {\tt (next-perf 29)} to solve the problem.  Hint:
you'll need a {\tt sum-of-factors} subprocedure.

[Note: If you run this program when the system is heavily loaded, it may
take half an hour to compute the answer!  Try tracing helper procedures to
make sure your program is on track, or start by computing {\tt (next-perf 1)}
and see if you get 6.]

3.  Explain the effect of interchanging the order in which the base cases in
the {\tt cc} procedure on page 41 of Abelson and Sussman are checked.  That
is, describe completely the set of arguments for which the original {\tt cc}
procedure would return a different value or behave differently from a {\tt
cc} procedure coded as given below, and explain how the returned values
would differ.

{\prgex%
(define (cc amount kinds-of-coins)
  (cond
    ((or (< amount 0) (= kinds-of-coins 0)) 0)
    ((= amount 0) 1)
    (else ... ) ) )        ; as in the original version
}

4.  Give an algebraic formula relating the values of the parameters
{\tt b, n, counter,} and {\tt product} of the {\tt expt} and {\tt exp-iter}
procedures given near the top of page 45 of Abelson and Sussman.
(The kind of answer we're looking for is
``the sum of b, n, and counter times product is always equal to 37.'')

{\bf Continued on next page.}

\vfill\eject

{\bf Homework assignment 2.1 continued...}

\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}
\holidaylec{7/3}
\as{Sections 2.1
and 2.2.1 (pages 79--106)}
\evenwr{7/8}

\as{exercises 2.7, 2.8, 2.10, 2.12, 2.17, 2.20, 2.22, 2.23}

(Note:  ``Spans zero'' means that one bound is $\le$ zero and the other
is $\ge$ zero!)

\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{7/8}{7/9}
\as{Section 2.2.2--2.2.3, 2.3.1, 2.3.3}

\oddwr{7/15}
\as{exercises 2.24, 2.26, 2.29, 2.30, 2.31, 2.32,
2.36, 2.37, 2.38, 2.54.}  Some of these exercises are harder than
they look; don't give up in frustration if your early attempts
fail.


3.  The list versions of {\tt every} and {\tt keep} are called
{\tt map} and {\tt filter}.  Can you use {\tt map} to implement
{\tt filter}? If so, how?  If not, why not?

\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:}  To use the OOP language you must first
{\prgex%
(load "\~{}cs61a/lib/obj.scm")
}  before using {\tt define-class}, etc.

1.  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.

2.  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
3.  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...}

4.  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
}

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

\oddwr{8/5}

1.  \as{exercises 3.50, 3.51, 3.52, 3.53, 3.54, 3.55, 3.56, 3.64, 3.66, 3.68}

2.  Write and test two functions to manipulate nonnegative proper
fractions.
The first function, {\tt fract-stream}, will take as its argument a list of
two nonnegative integers, the numerator and the denominator, in which
the numerator is less than the denominator.  It will return
an infinite stream of decimal digits representing the decimal expansion of
the fraction.  The second function, {\tt approximation}, will take two
arguments:\ a fraction stream and a nonnegative integer {\tt numdigits}.
It will return a list (not a stream) containing the first {\tt numdigits}
digits of the decimal expansion.

{\parskip=2pt

{\tt (fract-stream '(1 7))} should return the stream representing the
decimal expansion of $1\over 7$, which is 0.142857142857142857...

{\tt (stream-car (fract-stream '(1 7)))} should return 1.

{\tt (stream-car (stream-cdr (stream-cdr (fract-stream '(1 7)))))} should return 2.

{\tt (approximation (fract-stream '(1 7)) 4)} should return {\tt (1 4 2 8)}.

{\tt (approximation (fract-stream '(1 2)) 4)} should return {\tt (5 0 0 0)}.

}

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

1.  \as{exercises 4.3, 4.6, 4.7, 4.10, 4.11, 4.13, 4.14, 4.15}

2. Modify the metacircular evaluator to allow {\it type-checking\/} of arguments to
procedures.  Here is how the feature should work.  When a new procedure is
defined, a formal parameter can be either a symbol as usual or else a list
of two elements.  In this case, the second element is a symbol, the name of
the formal parameter.  The first element is an expression whose value is
a predicate function that the argument must satisfy.
That function should return {\tt \#t} if the argument
is valid.  For example, here is a procedure {\tt foo} that has type-checked
parameters {\tt num} and {\tt list}:

{\prgex%
> (define (foo (integer? num) ((lambda (x) (not (null? x))) list))
    (nth num list))
FOO
> (foo 3 '(a b c d e))
D
> (foo 3.5 '(a b c d e))
Error: wrong argument type -- 3.5
> (foo 2 '())
Error: wrong argument type -- ()
}

In this example we define a procedure {\tt foo} with two formal parameters,
named {\tt num} and {\tt list}.  When {\tt foo} is invoked, the evaluator
will check to see that the first actual argument is an integer and that the
second actual argument is not empty.  The expression whose value is the
desired predicate function should be evaluated with respect to {\tt foo}'s
defining environment.

\experts
\as{exercises 4.16 through 4.21}
\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.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 8.2



\week{8.2}{Review} \evenlec{8/15}{8/16}

No new reading or homework; study for the final.

\end{document}
