\documentclass[]{article}
% \usepackage{ifthen}
%%%%%%
%%%%%%
%%%%%% Modified by A. Coates
%%%%%%
%%%%%%
%%%%%% Last modified: 6 june 02
%%%%%%
\setlength{\textwidth}{6.5in} \setlength{\textheight}{9.00in}
\setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in}
\setlength{\topmargin}{-.5in} \setcounter{page}{14}
%\pageno=121



%\voffset=0.5in
%\nopagenumbers
\def\normal{
\font\tenrm=cmr10
\font\sevenrm=cmr7
\font\teni=cmmi10
\font\seveni=cmmi7
\font\tensy=cmsy10
\font\sevensy=cmsy7
\font\tenex=cmex10
\font\tenbf=cmbx10
\font\sevenbf=cmbx7
\font\tensl=cmsl10
\font\tentt=cmtt10
\font\tenit=cmti10
\font\fiverm=cmr5
\font\fivei=cmmi5
\font\fivesy=cmsy5
\font\ninerm=cmr9
\font\nineit=cmti9
\font\ninebf=cmbx9
\font\ninett=cmtt9
\parindent=0pt
\parskip=8pt
\smallskipamount=3pt plus1pt minus1pt
\medskipamount=6pt plus2pt minus2pt
\bigskipamount=12pt plus4pt minus4pt
\baselineskip=12pt
\lineskip=1pt
\def\vv{\vskip 6pt}
\vsize=8.9in
\hyphenchar\tentt=-1
}

\def\bb{\item{$\bullet$}}

\def\maghalf{
\font\tenrm=cmr10 scaled\magstephalf
\font\sevenrm=cmr7 scaled\magstephalf
\font\teni=cmmi10 scaled\magstephalf
\font\seveni=cmmi7 scaled\magstephalf
\font\tensy=cmsy10 scaled\magstephalf
\font\sevensy=cmsy7 scaled\magstephalf
\font\tenex=cmex10 scaled\magstephalf
\font\tenbf=cmbx10 scaled\magstephalf
\font\sevenbf=cmbx7 scaled\magstephalf
\font\tensl=cmsl10 scaled\magstephalf
\font\tentt=cmtt10 scaled\magstephalf
\font\tenit=cmti10 scaled\magstephalf
\font\fiverm=cmr5 scaled\magstephalf
\font\fivei=cmmi5 scaled\magstephalf
\font\fivesy=cmsy5 scaled\magstephalf
\font\ninerm=cmr9 scaled\magstephalf
\font\nineit=cmti9 scaled\magstephalf
\font\ninebf=cmbx9 scaled\magstephalf
\font\ninett=cmtt9 scaled\magstephalf
\parindent=0pt
\parskip=8.76356pt
\smallskipamount=3.28634pt plus1.095pt minus1.095pt
\medskipamount=6.57267pt plus2.19089pt minus2.19089pt
\bigskipamount=13.14534pt plus4.3818pt minus4.3818pt
\baselineskip=13.14534pt
\lineskip=1.095pt
\def\vv{\vskip 6.57267pt}
\vsize=8.9in
\hyphenchar\tentt=-1
}

\def\mag1{
\font\tenrm=cmr10 scaled\magstep1
\font\sevenrm=cmr7 scaled\magstep1
\font\teni=cmmi10 scaled\magstep1
\font\seveni=cmmi7 scaled\magstep1
\font\tensy=cmsy10 scaled\magstep1
\font\sevensy=cmsy7 scaled\magstep1
\font\tenex=cmex10 scaled\magstep1
\font\tenbf=cmbx10 scaled\magstep1
\font\sevenbf=cmbx7 scaled\magstep1
\font\tensl=cmsl10 scaled\magstep1
\font\tentt=cmtt10 scaled\magstep1
\font\tenit=cmti10 scaled\magstep1
\font\fiverm=cmr5 scaled\magstep1
\font\fivei=cmmi5 scaled\magstep1
\font\fivesy=cmsy5 scaled\magstep1
\font\ninerm=cmr9 scaled\magstep1
\font\nineit=cmti9 scaled\magstep1
\font\ninebf=cmbx9 scaled\magstep1
\font\ninett=cmtt9 scaled\magstep1
\parindent=0pt
\parskip=9.6pt
\smallskipamount=3.6pt plus1.2pt minus1.2pt
\medskipamount=7.2pt plus2.4pt minus2.4pt
\bigskipamount=14.4pt plus4.8pt minus4.8pt
\baselineskip=14.4pt
\lineskip=1.2pt
\def\vv{\vskip 7.2pt}
\vsize=8.9in
\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\oddweek#1#2#3{\vfill\eject
\begin{center}
\vspace{2mm}
 \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.2in { {\bf CS61A -- Lab Assignment #1 \hfill Kurt Meinz}}
       \hbox to 6.2in { University of California, Berkeley \hfill Summer 2002}
       \vspace{1mm}
   }
}
\end{center}
\par}

\def\evenweek#1#2#3{\vfill\eject
\begin{center}
\vspace{2mm}
 \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.2in { {\bf CS61A -- Lab Assignment #1 \hfill Kurt Meinz}}
       \hbox to 6.2in { University of California, Berkeley \hfill Summer 2002}
       \vspace{1mm}
   }
}
\end{center}
\par}

\def\oddfirst#1#2#3{\vfill\eject
\begin{center}
\vspace{2mm}
 \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.2in { {\bf CS61A -- Lab Assignment #1 \hfill Kurt Meinz}}
       \hbox to 6.2in { University of California, Berkeley \hfill Summer 2002}
       \vspace{1mm}
   }
}
\end{center}
\par}

\def\oddsecond#1#2#3{\vfill\eject
\begin{center}
\vspace{2mm}
 \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.2in { {\bf CS61A -- Lab Assignment #1 \hfill Kurt Meinz}}
       \hbox to 6.2in { University of California, Berkeley \hfill Summer 2002}
       \vspace{1mm}
   }
}
\end{center}
\par}

\def\evenfirst#1#2#3{\vfill\eject
\begin{center}
\vspace{2mm}
 \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.2in { {\bf CS61A -- Lab Assignment #1 \hfill Kurt Meinz}}
       \hbox to 6.2in { University of California, Berkeley \hfill Summer 2002}
       \vspace{1mm}
   }
}
\end{center}
\par}

\def\evensecond#1#2#3{\vfill\eject
\begin{center}
\vspace{2mm}
 \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.2in { {\bf CS61A -- Lab Assignment #1 \hfill Kurt Meinz}}
       \hbox to 6.2in { University of California, Berkeley \hfill Summer 2002}
       \vspace{1mm}
   }
}
\end{center}
\par}

\def\regex{\smallskip\aftergroup\smallskip
\vskip 1.2pt
\obeyspace %
\def\par{\leavevmode\endgraf} %
\obeylines\parindent=.6in\parskip=0pt}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 1.1 Part A

\normalsize \oddfirst {1.1}{6/25}{6/26}
% \vsize=9.5in
% \voffset=-0.50in

Try to get as much done as possible, but don't panic if you don't
finish everything.

\medskip

%\noindent {\bf 0.} Read and complete the exercises in the UNIX
%tutorial in the reader.

\noindent {\bf 0.} Login to your user account and change your
password -- instructions are provided on the account form. Be
aware that it may take several minutes for your new password to be
recognized by all the machines.


%\noindent {\bf 0.} Start another shell by typing "{\tt xterm \&}"
%in your main window. In this new window, verify that you are in
%your home directory by typing {\tt pwd}. Make a subdirectory
%called {\tt lab11}. Now, without changing your current directory,
%make two subdirectories under {\tt lab11} called {\tt foo} and
%{\tt bar}. Now move into the {\tt lab11} directory. Without
%changing directories, copy the file {\tt cs61a/labs/lab11/yaping}
%to your current directory, copy the file {\tt
%cs61a/labs/lab11/ilya.txt} into {\tt foo}, and copy the entire
%contents of {\tt cs61a/labs/lab11} to {\tt bar}. Verify the
%contents of these directories by typing {\tt ls}, "{\tt ls -l}",
%"{\tt ls -la}", and "{\tt ls -la bar}".

\medskip

\noindent {\bf 1.} Start the Emacs editor, either by typing {\tt emacs} in
your main window or by selecting it from the alt-middle mouse menu.  (Your
TA will show you how to do this.)  From the {\tt Help} menu, select the
Emacs tutorial.  You need not complete the entire tutorial at the first
session, but you should do so eventually.

\medskip

\noindent {\bf 2.} Start Scheme, either by typing {\tt scm} in your
main window or by typing meta-S in your Emacs window.  Type each of
the following expressions into Scheme, ending the line with the Enter
(carriage return) key.  {\bf Think about the results!}  Try to understand
how Scheme interprets what you type.
\small
{\prgex%
3                                  (first 'hello)
(+ 2 3)                            (first hello)
(+ 5 6 7 8)                        (first (bf 'hello))
(+)                                (+ (first 23) (last 45))
(sqrt 16)                          (define pi 3.14159)
(+ (* 3 4) 5)                      pi
+                                  'pi
'+                                 (+ pi 7)
'hello                             (* pi pi)
'(+ 2 3)                           (define (square x) (* x x))
'(good morning)                    (square 5)
(first 274)                        (square (+ 2 3))
(butfirst 274)
}
\normalsize

% {\bf Continued on next page.}

% \vfill\eject

% {\bf Lab Assignment 1 continued...}

\noindent {\bf 3.} Use Emacs to create a file called {\tt pigl.scm} in
your directory containing the Pig Latin program shown below:
\small
{\prgex%
(define (pigl wd)
  (if (pl-done? wd)
      (word wd 'ay)
      (pigl (word (bf wd) (first wd)))))

(define (pl-done? wd)
  (vowel? (first wd)))

(define (vowel? letter)
  (member? letter '(a e i o u)))
}
\normalsize
{\bf If you end each line with the linefeed key, instead of the return key,
Emacs will automatically indent the lines of your program properly.}

\medskip

\noindent {\bf 4.}  Now run Scheme.  You are going to create a transcript
of a session using the file you just created, like this:
\small
{\prgex%
(transcript-on "lab1")       ; This starts the transcript file.
(load "pigl.scm")            ; This reads in the file you created earlier.
(pigl 'scheme)               ; Try out your program.
                             ; Feel free to try more test cases here!
(trace pigl)                 ; This is a debugging aid. Watch what happens
(pigl 'scheme)               ; when you run a traced procedure.
(transcript-off)
(exit)
}
\normalsize
\medskip

\noindent {\bf 5.}  Use {\tt lpr} to print your transcript file.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 1.1 Part B

%\normalsize \oddsecond {1.1}{6/26}{6/27}

\bigskip

{\bf Continued on next page.}

\vfill\eject

{\bf Lab Assignment 1.1 continued...}

\bigskip

\noindent {\bf 6.}  Predict what Scheme will print in response to
each of these expressions.  {\it Then\/} try it and make sure your
answer was correct, or if not, that you understand why! \small
\def\vss{\vskip 4pt}
{\prgex%
(define a 3)
\vss%
(define b (+ a 1))
\vss%
(+ a b (* a b))
\vss%
(= a b)
\vss%
(if (and (> b a) (< b (* a b)))
    b
    a)
\vss%
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
\vss%
(+ 2 (if (> b a) b a))
\vss%
(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))
\vss%
((if (< a b) + -) a b)
}

\bigskip
\normalsize \noindent {\bf 7.}
In the shell, type the command

{\prgex%
cp \~{}cs61a/lib/plural.scm .
}

\noindent (Note the period at the end of the line!)  This will copy
a file from the class library to your own directory.  Then, using
emacs to edit the file, modify the procedure so that it correctly
handles cases like {\tt (plural~'boy)}.

\bigskip

\noindent {\bf 8.}  Define a procedure that takes three numbers as
arguments and returns the sum of the squares of the two larger
numbers.

\bigskip

\noindent {\bf 9.}  Write a procedure {\tt dupls-removed} that,
given a sentence as input, returns the result of removing
duplicate words from the sentence.  It should work this way:
\small
{\prgex%
> (dupls-removed '(a b c a e d e b))
(c a d e b)
> (dupls-removed '(a b c))
(a b c)
> (dupls-removed '(a a a a b a a))
(b a)
}
\normalsize
\maghalf

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

\evenfirst {1.2}{6/27}{6/28}

1.  For each of the following expressions, what must {\tt f} be in order for
the evaluation of the expression to succeed, without causing an error?  For
each expression, give a definition of {\tt f} such that evaluating the
expression will not cause an error, and say what the expression's value will
be, given your definition.
\small
{\prgex%
f\vv%
(f)\vv%
(f 3)\vv%
((f))\vv%
(((f)) 3)
}
\normalsize
\medskip

2.  Find the values of the expressions
\small
{\prgex%
((t 1+) 0)\vv%
((t (t 1+)) 0)\vv%
(((t t) 1+) 0)
}
\normalsize
where {\tt 1+} is a primitive procedure that adds 1 to its argument, and
{\tt t} is defined as follows:
\small
{\prgex%
(define (t f)
  (lambda (x) (f (f (f x)))) )
}
\normalsize
Work this out yourself before you try it on the computer!

\medskip

3.  Find the values of the expressions
\small
{\prgex%
((t s) 0)\vv%
((t (t s)) 0)\vv%
(((t t) s) 0)
}
\normalsize
where {\tt t} is defined as in question 2 above, and {\tt s} is defined as
follows:
\small
{\prgex%
(define (s x)
  (+ 1 x))
}
\normalsize
\medskip

4.  Consider a Scheme function {\tt g} for which the expression
\small
{\prgex%
((g) 1)
}
\normalsize
\noindent returns the value 3 when evaluated.  Determine how many
arguments {\tt g} has.  In one word, also describe as best you can
the {\it type\/} of value returned by {\tt g}.

\medskip

5.  Write a procedure {\tt substitute} that takes three arguments:\ a
{\it new\/} word, an {\it old\/} word, and a sentence.  It should return
a copy of the sentence, but with every occurrence of the old word
replaced by the new word.  For example:

{\prgex%
> (substitute 'maybe 'yeah '(she loves you yeah yeah yeah))
(she loves you maybe maybe maybe)
}

\mag1

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%
%%%%     Week 1.2 Part B

%\evensecond {1.2}{6/28}{6/29}


\bigskip

{\bf Continued on next page.}

\vfill\eject

{\bf Lab Assignment 1.2 continued...}

\bigskip



6. First, type the definitions
{\prgex%
(define a 7)
(define b 6)
}
into Scheme.
Then, fill in the blank in the code below
with an expression whose value depends on both {\tt a} and {\tt b}
to determine a return value of 24.
Verify in Scheme that the desired value is obtained.
{\prgex%
(let
  ((a 3) (b (+ a 2)))
  \underbar{\hskip1in} )
}

\bigskip

7. Write and test the {\tt make-tester} procedure. Given a word
{\tt w} as argument, {\tt make-tester} returns a procedure of one
argument {\tt x} that returns true if {\tt x} is equal to {\tt w}
and false otherwise. Examples:
{\prgex%
> ((make-tester 'hal) 'hal)
\#t
> ((make-tester 'hal) 'cs61a)
\#f
> (define sicp-author-and-astronomer? (make-tester 'gerry))
> (sicp-author-and-astronomer? 'hal)
\#f
> (sicp-author-and-astronomer? 'gerry)
\#t
}

\maghalf

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

\oddweek {2.1}{7/2}{7/3}

This lab exercise concerns the change counting program on pages 40--41
of Abelson and Sussman.

1.  Identify two ways to change the program to {\it reverse\/} the order
in which coins are tried, that is, to change the program so that
pennies are tried first, then nickels, then dimes, and so on.

\medskip

2.  Abelson and Sussman claim that this change would not affect
the {\it correctness\/} of the computation.
However, it does affect the {\it efficiency\/} of the computation.
Implement one of the ways you devised in exercise 1
for reversing the order in which coins are tried,
and determine the extent to which the number of calls to cc
is affected by the revision.
Verify your answer on the computer,
and provide an explanation.
Hint: limit yourself to
nickels and pennies, and compare the trees resulting from {\tt (cc 5 2)}
for each order.

\medskip

3.  Modify the {\tt cc} procedure so that its {\tt kinds-of-coins}
parameter, instead of being an integer, is a {\it sentence\/}
that contains the values of the coins to be used in making change.
The coins should be tried in the sequence they appear in the sentence.
For the {\tt count-change} procedure to work the same in the revised
program as in the original, it should call {\tt cc} as follows:

{\prgex%
(define (count-change amount)
  (cc amount '(50 25 10 5 1)) )
}

\medskip

4.  Many Scheme procedures require a certain type of argument.  For
example, the arithmetic procedures only work if given numeric arguments.
If given a non-number, an error results.

Suppose we want to write {\it safe\/} versions of procedures, that can
check if the argument is okay, and either call the underlying procedure
or return {\tt \#f} for a bad argument instead of giving an error.
(We'll restrict our attention to procedures that take a single argument.)

{\prgex%
> (sqrt 'hello)
ERROR: magnitude: Wrong type in arg1 hello
> (type-check sqrt number? 'hello)
\#f
> (type-check sqrt number? 4)
2
}

Write {\tt type-check}.  Its arguments are a function, a type-checking
predicate that returns {\tt \#t} if and only if the datum is a legal
argument to the function, and the datum.

\medskip


{\bf Continued on next page.}

\vfill\eject

{\bf Lab Assignment 2.1 continued...}

5.  We really don't want to have to use {\tt type-check} explicitly
every time.  Instead, we'd like to be able to use a {\tt safe-sqrt}
procedure:

{\prgex%
> (safe-sqrt 'hello)
\#f
> (safe-sqrt 4)
2
}

Don't write {\tt safe-sqrt}!  Instead, write a procedure {\tt make-safe}
that you can use this way:

{\prgex%
> (define safe-sqrt (make-safe sqrt number?))
}

It should take two arguments, a function and a type-checking predicate,
and return a new function that returns {\tt \#f} if its argument doesn't
satisfy the predicate.

\maghalf

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


\evenweek {2.2}{7/5}{7/6}
% \vsize=9.5in
% \voffset=-0.5in

1.  Try these in Scheme:

{\prgex%
(define x (cons 4 5))\vv%
(car x)\vv%
(cdr x)\vv%
(define y (cons 'hello 'goodbye))\vv%
(define z (cons x y))\vv%
(car (cdr z))\vv%
(cdr (cdr z))
}

2.  Predict the result of each of these before you try it:

{\prgex%
(cdr (car z))\vv%
(car (cons 8 3))\vv%
(car z)\vv%
(car 3)\vv%
}

3.  Enter these definitions into Scheme:
\small
{\prgex%
(define (make-rational num den)
  (cons num den))\vv%
(define (numerator rat)
  (car rat))\vv%
(define (denominator rat)
  (cdr rat))\vv%
(define (*rat a b)
  (make-rational (* (numerator a) (numerator b))
                 (* (denominator a) (denominator b))))\vv%
(define (print-rat rat)
  (word (numerator rat) '/ (denominator rat)))
}
\normalsize
4.  Try this:

{\prgex%
(print-rat (make-rational 2 3))\vv%
(print-rat (*rat (make-rational 2 3) (make-rational 1 4)))
}

5.  Define a procedure {\tt +rat} to add two rational numbers,
in the same style as {\tt *rat} above.

6.  {\bf Now do exercises 2.2, 2.3, and 2.4 from {\it SICP}.}

7.  {\it SICP\/} ex. 2.18; this should take some thought, and you
should make sure you get it right, but don't get stuck on it for
the whole hour.  {\bf Note:} Your solution should reverse {\it lists},
not sentences!  That is, you should be using {\tt cons}, {\tt car},
and {\tt cdr}, not {\tt first}, {\tt sentence}, etc.

\mag1

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

\oddweek {3.1}{7/9}{7/10} \vsize=9.5in

1.  {\it SICP\/} ex.\ 2.25 and 2.53; these should be quick and easy.

2.  {\it SICP\/} ex.\ 2.55; {\bf explain your answer to your TA.}

3.  {\it SICP\/} ex.\ 2.27.  This is the central exciting adventure
of today's lab!  Think hard about it.

4.  Each person individually make up a procedure named {\tt mystery}
that, given two lists as arguments, returns the result of applying
{\it exactly two\/} of {\tt cons}, {\tt append}, or {\tt list} to
{\tt mystery}'s arguments, using no quoted values or other
procedure calls.  Here are some examples of what is and is not
fair game:

{\prgex%
okay                               not okay

(define (mystery L1 L2)            (define (mystery L1 L2)
  (cons L1 (append L2 L1)))          (cons L1 (cons L2 (cons L1 L2))))

(define (mystery L1 L2)            (define (mystery L1 L2)
  (list L1 (list L1 L1)))            (cons L1 L2))

(define (mystery L1 L2)            (define (mystery L1 L2)
  (append (cons L2 L2) L1))          (append L1 (cons L1 '(A B C))))
}

Type your {\tt mystery} definition into a file, and have one of
your partners load it into Scheme and try to guess what it is by
trying it out with various arguments.

After everyone has tried someone else's procedure, decide with your
partners which procedure was hardest to guess and why, and what
test cases were most and least helpful in revealing the definitions.

\mag1

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

\evenweek {3.2}{7/11}{7/12}

Start by reading {\it SICP\/} section 2.3.3 (pages 151--161).

1.  {\it SICP\/} ex. 2.62.

2.  The file {\tt \~{}cs61a/lib/bst.scm} contains the binary
search tree procedures from pages 156--157 of {\it SICP}.  Using
{\tt adjoin-set}, construct the trees shown on page 156.

3.  {\it SICP\/} ex. 2.74.

\maghalf

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

\oddweek {4.1}{7/16}{7/17}
%\vsize=10.5in
% \voffset=-1.5in

1.  Modify the {\tt person} class given in the lecture notes for week 3
(it's in the file {\tt demo2.scm} in the {\tt \~{}cs61a/lectures/3.0} directory)
to add a {\tt repeat}
method, which repeats the last thing said.  Here's an example of
responses to the {\tt repeat} message.
\small
{\prgex
> (define brian (instantiate person 'brian))
brian
> (ask brian 'repeat)
()
> (ask brian 'say '(hello))
(hello)
> (ask brian 'repeat)
(hello)
> (ask brian 'greet)
(hello my name is brian)
> (ask brian 'repeat)
(hello my name is brian)
> (ask brian 'ask '(close the door))
(would you please close the door)
> (ask brian 'repeat)
(would you please close the door)
}
\normalsize
2.  This exercise introduces you to the {\tt usual} procedure
described on page 9 of ``Object-oriented Programming -- Above-the-line
View''.  Read about {\tt usual} there to prepare for lab.
Suppose that we want to define a class called {\tt double-talker}
to represent people that always say things twice, for example as in
the following dialog.
\small
{\prgex
> (define mike (instantiate double-talker 'mike))
mike
> (ask mike 'say '(hello))
(hello hello)
> (ask mike 'say '(the sky is falling))
(the sky is falling the sky is falling)
}
\normalsize
Consider the following three definitions for the {\tt double-talker} class.
(They can be found online in the file {\tt \~{}cs61a/lib/double-talker.scm}.)
\small
{\prgex
(define-class (double-talker name)
  (parent (person name))
  (method (say stuff) (se (usual 'say stuff) (ask self 'repeat))) )

(define-class (double-talker name)
  (parent (person name))
  (method (say stuff) (se stuff stuff)) )

(define-class (double-talker name)
  (parent (person name))
  (method (say stuff) (usual 'say (se stuff stuff))) )
}
\normalsize
Determine which of these definitions work as intended. Determine also for which messages the three versions would respond
differently.

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

\evenweek {4.2}{7/18}{7/19}

1.  Given below is a simplified version of the {\tt make-account} procedure
on page 223 of Abelson and Sussman.
\small
{\prgex%
(define (make-account balance)
  (define (withdraw amount)
    (set! balance (- balance amount)) balance)
  (define (deposit amount)
    (set! balance (+ balance amount)) balance)
  (define (dispatch msg)
    (cond
      ((eq? msg 'withdraw) withdraw)
      ((eq? msg 'deposit) deposit) ) )
  dispatch)
}
\normalsize
Fill in the blank in the following code so that the result works
exactly the same as the {\tt make-account} procedure above, that is,
responds to the same messages and produces the same return values.
The differences between the two procedures are that the inside
of {\tt make-account} above is enclosed in the {\tt let} below,
and the names of the parameter to {\tt make-account} are different.

{\prgex%
(define (make-account init-amount)
  (let ( underbar{\hskip1in} )
    (define (withdraw amount)
      (set! balance (- balance amount)) balance)
    (define (deposit amount)
      (set! balance (+ balance amount)) balance)
    (define (dispatch msg)
      (cond
        ((eq? msg 'withdraw) withdraw)
        ((eq? msg 'deposit) deposit) ) )
    dispatch) )
}

2.  Modify either version of {\tt make-account} so that, given the message
{\tt balance}, it returns the current account balance, and given the message
{\tt init-balance}, it returns the amount with which the account
was initially created.  For example:

{\prgex%
> (define acc (make-account 100)
acc
> (acc 'balance)
100
}

{\bf Continued on next page...}

\vfill\eject

{\bf Lab Assignment 4.2 continued:}

3.  Modify {\tt make-account} so that, given the message {\tt transactions},
it returns a list of all transactions made since the account was opened.
For example:

{\prgex%
> (define acc (make-account 100))
acc
> ((acc 'withdraw) 50)
50
> ((acc 'deposit) 10)
60
> (acc 'transactions)
((withdraw 50) (deposit 10))
}

4.  Given this definition:

{\prgex%
(define (plus1 var)
  (set! var (+ var 1))
  var)
}

Show the result of computing

{\prgex%
(plus1 5)
}

\noindent using the substitution model.  That is, show the expression
that results from substituting {\tt 5} for {\tt var} in the body of
{\tt plus1}, and then compute the value of the resulting expression.
What is the actual result from Scheme?

%{\bf Continued on next page...}

\vfill\eject
%\normalsize
%\vsize=9.5in
% \voffset=-0.5in
% \voffset=0in


%{\bf Lab Assignment 4.2 continued:}

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

\oddweek {5.1}{7/23}{7/24} \normalsize
%\vsize=10.5in
 %\voffset=-1.5in

1. This lab activity consists of example programs for you to run
in Scheme. Predict the result before you try each example.  If you
don't understand what Scheme actually does, ask for help!  Don't
waste your time by just typing this in without paying attention to
the results. \small
{\prgex%
(define (make-adder n)                       ((lambda (x)
  (lambda (x) (+ x n)))                         (let ((a 3))
                                                  (+ x a)))
(make-adder 3)                                5)

((make-adder 3) 5)                           (define k
                                               (let ((a 3))
(define (f x) (make-adder 3))                    (lambda (x) (+ x a))))

(f 5)                                        (k 5)

(define g (make-adder 3))                    (define m
                                               (lambda (x)
(g 5)                                            (let ((a 3))
                                                   (+ x a))))
(define (make-funny-adder n)
  (lambda (x)                                (m 5)
    (if (equal? x 'new)
        (set! n (+ n 1))                     (define p
        (+ x n))))                             (let ((a 3))
                                                 (lambda (x)
(define h (make-funny-adder 3))                    (if (equal? x 'new)
                                                       (set! a (+ a 1))
(define j (make-funny-adder 7))                        (+ x a)))))

(h 5)                                        (p 5)

(h 5)                                        (p 5)

(h 'new)                                     (p 'new)

(h 5)                                        (p 5)

(j 5)                                        (define r
                                               (lambda (x)
(let ((a 3))                                     (let ((a 3))
  (+ 5 a))                                         (if (equal? x 'new)
                                                       (set! a (+ a 1))
(let ((a 3))                                           (+ x a)))))
  (lambda (x) (+ x a)))
                                             (r 5)
((let ((a 3))
   (lambda (x) (+ x a)))                     (r 5)
 5)
                                             (r 'new)

} \normalsize Continued on next page...
\vfill\eject
{\bf Lab
Assignment 5.1 continued:} \small
{\prgex%
                                             (r 5)

(define s                                    (define (ask obj msg . args)
  (let ((a 3))                                 (apply (obj msg) args)))
    (lambda (msg)
      (cond ((equal? msg 'new)               (ask s 'add 5)
             (lambda ()
               (set! a (+ a 1))))            (ask s 'new)
            ((equal? msg 'add)
             (lambda (x) (+ x a)))           (ask s 'add 5)
            (else (error "huh?"))))))
                                             (define x 5)
(s 'add)
                                             (let ((x 10)
(s 'add 5)                                         (f (lambda (y) (+ x y))))
                                               (f 7))
((s 'add) 5)
                                             (define x 5)
(s 'new)

((s 'add) 5)

((s 'new))

((s 'add) 5)
}
\normalsize

\medskip

%begin removed part

2.  Exercise 3.12 of Abelson and Sussman.

\medskip

3.  Suppose that the following definitions have been provided.
\small
{\prgex%
(define x (cons 1 3)) (define y 2) } \normalsize A CS 61A student,
intending to change the value of {\tt x} to a pair with {\tt car}
equal to 1 and {\tt cdr} equal to 2, types the expression {\tt
(set!\ (cdr x) y)} instead of {\tt (set-cdr!\ x y)} and gets an
error.  Explain why.

\medskip

4a.  Provide the arguments for the two {\tt set-cdr!}\ operations
in the blanks below to produce the indicated effect on {\tt list1}
and {\tt list2.} Do not create any new pairs; just rearrange the
pointers to the existing ones. \small
{\prgex%
> (define list1 (list (list 'a) 'b))
list1
> (define list2 (list (list 'x) 'y))
list2
> (set-cdr! \underbar{\hskip1in} \underbar{\hskip1in} )
okay
> (set-cdr! \underbar{\hskip1in} \underbar{\hskip1in} )
okay
> list1
((a x b) b)
> list2
((x b) y) } \normalsize

4b. After filling in the blanks in the code above and producing
the specified effect on {\tt list1} and {\tt list2}, draw a
box-and-pointer diagram that explains the effect of evaluating the
expression {\tt (set-car!\ (cdr list1) (cadr list2))} .



5.  Exercises 3.13 and 3.14 in Abelson and Sussman.

%end removed part

% In the following problem, {\tt let*} is like a bunch of nested {\tt let}s,
% so that each binding is done in sequence instead of all of them at once.  In
% other words, it's like
%
% {\prgex%
% (let ((z x))
%   (let ((y ...))
%     (let ((f ...))
%       (let ((x 2))
%         (f x)))))
% }
%
% Here's the problem:
%
% {\prgex%
% (let* ((z x)
%        (y (sequence (set! x (+ z 1)) (+ x 2)))
%        (f (lambda (w) (list w y x z)))
%        (x 2))
%   (f x))
% }


%\oddweek 9{7/23}{7/24}

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

\evenweek{5.2}{7/25}{7/26}

In this lab there is no actual Scheme programming; you are to
devise an algorithm in English to solve

\medskip

\centerline{\bf The Dining Philosophers Problem}

N philosophers are sitting around a round table for dinner. There
is one chopstick between each pair of philosophers, for a total of
N chopsticks altogether.  You need two chopsticks to eat.
Philosophers spend most of their time thinking, but every so often
one gets hungry and wants to eat.  A hungry philosopher must
obtain the two chopsticks on his or her left and right.  If one or
both of those chopsticks is already in use, the philosopher must
wait.

How can you use synchronization to solve that problem?  You must
come up with a solution that's

\medskip
\def\bb{\item{$\bullet$}}

1. correct (so you don't have two philosophers using the same
chopstick at the same time),

2. efficient (so you don't restrict eating more than
necessary---for example, you shouldn't have only one person
allowed to eat at a time),

3. not deadlocked (don't end up with each philosopher holding one
chopstick), and

4. preferably fair (so they all get an equal chance to eat).


\medskip

Be sure your solution works for both even and odd values of N.



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

\oddweek{6.1}{7/30}{7/31}


1.  What is the type of the value of {\tt (delay (+ 1 27))?}
What is the type of the value of {\tt (force (delay (+ 1 27)))?}

2.  Evaluation of the expression
\small
{\prgex%
(stream-cdr (stream-cdr (cons-stream 1 '(2 3))))
}
\normalsize
\noindent produces an error.  Why?


3.  Consider the following two procedures.
\small
{\prgex%
(define (enumerate-interval low high)
  (if (> low high)
    '()
    (cons low (enumerate-interval (+ low 1) high)) ) )

(define (stream-enumerate-interval low high)
  (if (> low high)
    the-empty-stream
    (cons-stream low (stream-enumerate-interval (+ low 1) high)) ) )
}
\normalsize
What's the difference between the following two expressions?
\small
{\prgex%
(delay (enumerate-interval 1 3))
(stream-enumerate-interval~1~3)
}
\normalsize

4.  An unsolved problem in number theory concerns the following algorithm
for creating a sequence of positive integers $s_1, s_2, ...$
\small
{\prgex%
Choose $s_1$ to be some positive integer.
For $n > 1$,
    if $s_n$ is odd, then $s_{n+1}$ is $3 s_n + 1$;
    if $s_n$ is even, then $s_{n+1}$ is $s_n / 2$.
}
\normalsize
No matter what starting value is chosen, the sequence always
seems to end with the values 1, 4, 2, 1, 4, 2, 1, ...
However, it is not known if this is always the case.

4a.  Write a procedure {\tt num-seq} that, given a positive integer {\tt n}
as argument, returns the stream of values produced for {\tt n}
by the algorithm just given.  For example, {\tt (num-seq 7)} should return
the stream representing the sequence
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

4b.  Write a procedure {\tt seq-length} that, given a stream produced
by {\tt num-seq}, returns the number of values that occur in the sequence
up to and including the first 1.
For example, {\tt (seq-length (num-seq 7))} should return 17.
You should assume that there is a 1 somewhere in the sequence.

%\mag1

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

\evenweek{6.2}{8/1}{8/2}

1.  List all the procedures in the metacircular evaluator
that call {\tt eval}.



2.  List all the procedures in the metacircular evaluator
that call {\tt apply}.



3.  Explain why {\tt make-procedure} does {\it not} call {\tt eval}.



4.  Abelson and Sussman, exercises 4.1, 4.2, 4.4, 4.5

% We have added a tracing feature to the metacircular evaluator.  To use it,
% you'll need two files:
%
% {\prgex%
% (load "\~{}cs61a/lib/meta.scm")
% (load "\~{}cs61a/lib/traced-eval.scm")
% }
%
% To activate tracing, evaluate the expression {\tt (mini-trace \#t)}. To
% turn off the trace, evaluate {\tt (mini-trace \#f)}.  To include default bindings
% in the environments produced by the trace, evaluate {\tt (mini-trace 'all)}.
% The following lab exercises will involve the use of this feature.
%
% \bigskip
%
% 4.  Load the metacircular evaluator, enable tracing,
% then call {\tt initialize-lisp}
% and evaluate the following expressions:
%
% {\prgex%
% (define car1 car)
% (define (car2 x) (car x))
% (define pair (cons 1 2))
% }
%
% Then evaluate the following expressions:
%
% {\prgex%
% (car pair)
% (car1 pair)
% (car2 pair)
% }
%
% Interpret the trace results by describing what the evaluator
% does when evaluating each of the expressions.
% Which of the three expressions requires the most work?
% Which expression requires the least work?
%
% \bigskip
%
% 5.  Provide a file of Scheme expressions that,
% when loaded using {\tt meta-load}, exercises all eight non-error cases of
% {\tt mini-eval}.


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

\oddweek{7.1}{8/6}{8/7}
% \voffset=-1.5in
%\vsize=10.0in

\gdef\deferfoot{}
\newbox\partialpage
\def\twocol{\begingroup\leftskip=0pt\topskip=0pt
 \output={\global\setbox\partialpage=\vbox{\unvbox255\bigskip}}\eject
 \output={\doublecolumnout} \hsize=3truein \vsize=18truein}
\def\onecol{\output={\balancecolumns}\eject
 \endgroup \pagegoal=\vsize}
\def\doublecolumnout{\splittopskip=0pt \splitmaxdepth=\maxdepth
 \dimen6=9truein \advance\dimen6 by-\ht\partialpage
 \setbox0=\vsplit255 to\dimen6 \setbox2=\vsplit255 to\dimen6
 \onepageout\pagesofar \unvbox255}
\def\onepageout#1{
 \shipout\vbox{{\hsize=6.5truein\makeheadline}\pbody{#1}
 {\hsize=6.5truein\makefootline}}
 \deferfoot\gdef\deferfoot{}
 \advancepageno
 \ifnum\outputpenalty>-20000 \else\dosupereject\fi}
\def\pbody#1{\vbox to 9truein{\boxmaxdepth=\maxdepth #1}}
\def\pagesofar{\unvbox\partialpage
 \wd0=\hsize \wd2=\hsize \hbox to 6.5truein{\box0\hfil\box2}}
\def\balancecolumns{\setbox0=\vbox{\unvbox255} \dimen6=\ht0
 \advance\dimen6 by\topskip \advance\dimen6 by-\baselineskip
 \divide\dimen6 by2 \splittopskip=\topskip
  {\vbadness=10000 \loop \global\setbox3=\copy0
   \global\setbox1=\vsplit3 to\dimen6
   \ifdim\ht3>\dimen6 \global\advance\dimen6 by 1pt \repeat}
 \setbox0=\vbox to\dimen6{\unvbox1}
 \setbox2=\vbox to \dimen6{\dimen2=\dp3 \unvbox3 \kern-\dimen2 \vfil}
 \pagesofar}

Part A:  Abelson and Sussman, exercises 4.27 and 4.29.

Part B: In this lab exercise you will become familiar with the Logo programming
language, for which you'll be writing an interpreter in project 4.

To begin, type {\tt logo} at the Unix shell prompt --- {\bf not} from
Scheme!  You should see something like this:

{\prgex%
Welcome to Berkeley Logo version 3.4
?
}

The question mark is the Logo prompt, like the {\tt >} in Scheme.  (Later, in
some of the examples below, you'll see a {\tt >} prompt from Logo, while in
the middle of defining a procedure)

1.  Type each of the following instruction lines and note the results.  (A few
of them will give error messages.)  If you can't make sense of a result, ask
for help.

\twocol
\small
{\prgex\hfuzz=20pt%
print $2 + 3$

print $2+3$

print sum $2 3$

print (sum $2 3 4 5$)

print sum 2 3 4 5

$2+3$

print "yesterday

print "julia"

print revolution

print [blue jay way]

show [eight days a week]

show first [golden slumbers]

print first bf [she loves you]

pr first first bf [yellow submarine]

to second :stuff
output first bf :stuff
end

second "something

print second "piggies

pr second [another girl]

pr first second [carry that weight]
pr second second [i dig a pony]

to pr2nd :thing
print first bf :thing
end

pr2nd [the 1 after 909]

print first pr2nd [hey jude]

repeat 5 [print [this boy]]

if $3 = 1+1$ [print [the fool on the hill]]

print ifelse 2=1+1  \~{ }
      [second [your mother should know]] \~{ }
      [first "help]

print ifelse $3=1+2 $\~{ }
      [strawberry fields forever] \~{ }
      [penny lane]

print ifelse $4=1+2 $\~{ }
      ["flying] \~{ }
      [[all you need is love]]
}

\onecol
Continued on next page...

\vfill\eject

% \voffset=-1.5in
%\vsize=9.5in

Lab Assignment 7.1 continued...

\twocol
\small
{\prgex\hfuzz=20pt%
to greet :person
say [how are you,]
end

to say :saying
print sentence :saying :person
end

greet "ringo

show map "first [paperback writer]

show map [word first ? last ?] \~{ }
         [lucy in the sky with diamonds]

to who :sent
foreach [pete roger john keith] "describe
end

to describe :person
print se :person :sent
end

who [sells out]

print :bass

make "bass "paul

print :bass

print bass

to bass
output [johnny cymbal]
end

print bass

print :bass

print "bass

to countdown :num
if :num=0 [print "blastoff stop]
print :num
countdown :num-1
end

countdown 5

to downup :word
print :word
if emptyp bl :word [stop]
downup bl :word
print :word
end

downup "rain

;;;; The following stuff will work
;;;; only on an X workstation:

cs

repeat 4 [forward 100 rt 90]

cs

repeat 10 [repeat 5 [fd 150 rt 144] rt 36]

cs repeat 36 [repeat 4 [fd 100 rt 90]
              setpc remainder pencolor+1 8
              rt 10]

to tree :size
if :size < 3 [stop]
fd :size/2
lt 30 tree :size*3/4 rt 30
fd :size/3
rt 45 tree :size*2/3 lt 45
fd :size/6
bk :size
end

cs pu bk 100 pd ht tree 100
}
\normalsize
\onecol

\bigskip

2. Devise an example that demonstrates that Logo uses dynamic scope
rather than lexical scope.
Your example should involve the use of a variable
that would have a different value if Logo used lexical scope.
Test your code with Berkeley Logo.

\bigskip

3.  Explain the differences and similarities among the Logo operators
{\tt "} (double-quote), {\tt [~]} (square brackets), and {\tt :}~(colon).

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


\evenweek{7.2}{8/8}{8/9}

1.  Abelson and Sussman, exercises 4.35 and 4.38.

2.  In this exercise we learn what a {\it continuation\/} is.
Suppose we have the following definition:

{\prgex%
(define (square x cont)
  (cont (* x x))
}

Here {\tt x} is the number we want to square, and {\tt cont} is
the procedure to which we want to pass the result.  Now try these
experiments:

{\prgex%
> (square 5 (lambda (x) x))

> (square 5 (lambda (x) (+ x 2)))

> (square 5 (lambda (x) (square x (lambda (x) x))))

> (square 5 display)

> (define foo 3)
> (square 5 (lambda (x) (set! foo x)))
> foo
}

Don't just type them in -- make sure you understand why they work!
The nondeterministic evaluator works by evalutating every expression
with {\it two\/} continuations, one used if the computation succeeds,
and one used if it fails.

{\prgex%
(define (reciprocal x yes no)
  (if (= x 0)
      (no x)
      (yes (/ 1 x))))

> (reciprocal 3 (lambda (x) x) (lambda (x) (se x '(cannot reciprocate))))

> (reciprocal 0 (lambda (x) x) (lambda (x) (se x '(cannot reciprocate))))
}

\mag1

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

\oddweek{8.1}{8/13}{8/14}

Abelson and Sussman, exercises 4.55 and 4.62:

\medskip

4.55: Give simple queries that retrieve the following information
from the data base:

All people supervised by Ben Bitdiddle;

The names and jobs of all people in the accounting division;

The names and addresses of all people who live in Slumerville.

\bigskip

4.62: Define rules to implement the {\tt last-pair} operation of exercise
2.17, which returns a list containing the last element of a nonempty list.  Check
your rules on queries such as

{\prgex%
(last-pair (3) ?x)
(last-pair (1 2 3) ?x)
(last-pair (2 ?x) (3))
}

Do your rules work correctly on queries such as {\tt (last-pair~?x~(3))}?

\bigskip

For the lab exercises and the homework problems
that involve writing queries or rules,
test your solutions using the query system.
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.
\end{document}
%\bye
