@device(dover)
@make(6001)

@modify(excounter, numbered [Exercise @1], referenced [@1])

@PageHeading(left "6.001 -- Hewlett-Packard Summer 1985",
             center "@Value(Page)",
             right "Problem set 1")

@begin(center)
HEWLETT-PACKARD
Summer 1985

Problem Set 1

Originally Prepared As

MASSACHUSETTS INSTITUTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001 Structure and Interpretation of Computer Programs
Spring Semester, 1985; Problem Set 1
@end(center)
@blankspace(0.25 in)

@section(Homework Exercises)

Write up and hand in the following exercises from the text.

@begin(itemize)

@begin(multiple)
Exercise 1.1: Evaluation of expressions.

You may use the computer to
check your answers, but first do the evaluation by hand so as to get
practice with understanding Lisp.  Typing expressions such as these to the
interpreter and observing its behavior is one of the best ways of
learning about the language.  Experiment and try your own problems.
Though the examples shown are often indented and printed on several
lines for readability, an expression may be typed on a single line or
on several, and redundant spaces and carriage returns are ignored.  It
is to your advantage to format your work so that you (and others) can
easily read it.
@end(multiple)

@begin(multiple)
Exercise 1.2a (not in text):  Defining a simple procedure

The roots of the polynomial @a[Ax@+[2] + Bx + C] are given by @a[-B]
plus or minus the square root of @a[B@+[2]-4AC], times @a[1/2A].  If
the discriminant @a[B@+[2]-4AC] is greater than or equal to 0, the
roots are both real; otherwise the roots are complex with real part
@a[-B/2A].  Define a procedure @a[smallest-real-part] that takes the
coefficients @a[A], @a[B] and @a[C] as arguments and returns either
the real part of the roots (if they are complex), or else the real
root having the smaller absolute value.  Be sure that your procedure
continues to work if some of the coefficients or the discriminant are
zero (but you may assume that @a[A] is always nonzero).
@end(multiple)

Exercise 1.4:  A new definition of @a[IF]

Exercise 1.6:  Computing cube roots

@end(itemize)


@section(Laboratory Assignment: Graphing Epicycloids and Hypocycloids)

A substantial part of each problem set consists of a laboratory
assignment that should be done with the aid of the 6.001 computing
facility.  Performance on problem sets, and laboratories in
particular, is a major factor in determining grades for 6.001.
Remember that the laboratory room tends to get very crowded on the
nights before assignments are due, so it will be to your advantage to
complete your computer work early.

Before coming to the laboratory room, you should read the ``Chipmunk
Manual'' and you should bring it with you to use for reference.  You
should also glance through the ``Scheme Manual,'' but almost all of the
information you will need about the Scheme language itself has been
included in the text.

Each time you begin using one of the Chipmunk computers, you must
insert a floppy disk in the drive.  Each disk is identified by a name,
which is chosen by you at the time when you initialize the disk.  If
you place an uninitialized disk in the drive, the system will offer to
initialize it for you.  Before beginning work on the first assignment,
you should use the system to initialize your disk.  More information is
given in the Chipmunk Manual, in the section called ``starting and
leaving the system.''


This first laboratory assignment has been designed to be very
simple, so that you will have a chance to become familiar with the
Chipmunk system.

In this assignment, you are to experiment with simple procedures
that plot curves called epicycloids and hypocycloids.  These are
defined formally as follows.

Consider a circle of radius @a[b] and a disk of radius @a[a] rolling
on the circumference of the circle.  Consider a point @a[p] that rotates
with the disk at a distance @a[a1] from the center of the disk.  The
curve traced by this point as the disk rolls around the circle is
called an @i[epicycloid] if the disk if rolling around the outside of
the circle, and a @i[hypocycloid] if the disk is rolling around the
inside of the circle.

@begin(figure)
@blankspace(4 inches)
@caption(Constructing epicycloids and hypocycloids)
@end(figure)

If the equation of the circle is

@begin(example)
x@+[2] + y@+[2] = b@+[2]
@end(example)
then the locus of the point @a[p=(x,y)] can be described for the
epicycloid as follows:

@begin(example)
                 a              (a+b)
x(t) = (a+b) sin - t  -  a1 sin ----- t
                 b                b

                 a              (a+b)
y(t) = (a+b) cos - t  -  a1 cos ----- t
                 b                b
@end(example)

The corresponding equations for the hypocycloid@foot[Actually, the
equation for y(t) for the hypocycloid is incorrect.  The terms must
be added, not subtracted.  Unfortunately, we discovered this too late
to correct this problem set -- the questions are based on the formula
given here.] are
@begin(example)
                 a              (b-a)
x(t) = (b-a) sin - t  -  a1 sin ----- t
                 b                b

                 a              (b-a)
y(t) = (b-a) cos - t  -  a1 cos ----- t
                 b                b

@end(example)

We can graph epicycloids on the Chipmunk using the procedure
below.  The arguments to the procedure are the radii
@a[a] and @a[b] of the disk and the circle, the distance @a[a1] from
the center of the disk
to the plotted point, and a parameter @a[dt] that determines the
increment at which points are plotted.

@begin(programexample)
(define (epicycloid a b a1 dt)
  (define (horiz t)
    (- (* (+ a b) (sin (/ (* a t) b)))
       (* a1 (sin (/ (* (+ a b) t) b)))))
  (define (vert t)
    (- (* (+ a b) (cos (/ (* a t) b)))
       (* a1 (cos (/ (* (+ a b) t) b)))))
  (define (iter t)
    (draw-line-to (horiz t) (vert t))
    (iter (+ t dt)))
  (clear-graphics)                     ; clear the graphics screen
  (position-pen (horiz 0) (vert 0))    ; set graphics at initial point
  (iter 0))                            ; start drawing
@end(programexample)

The @a[epicycloid] procedure contains internally defined
procedures that compute the horizontal and vertical coordinates
corresponding to a given value of @a[t], and a procedure @a[iter]
that repeatedly draws lines connecting the points for
consecutive values of @a[t].  When @a[epicycloid] starts, it
clears the graphics screen and positions the graphics pen at the
initial point corresponding to @a[t=0] before calling @a[iter].
The primitive @a[draw-line-to], used by @a[iter], moves the
graphics pen to the indicated @a[x] and @a[y] coordinates, drawing a line
from the current point.

@begin(exercise)
Use the NMODE editor to type in the above
procedure definition.  (Subsequent laboratory assignments will
include large amounts of code, which will be made available for
you to load when you begin work on the assignment.  This time,
however, we are asking you to type in the definition yourself, so
that you will get used to the editor.)  Notice that the editor
automatically ``pretty prints'' your procedure as you type it in,
indenting lines to the position determined by the number of
unclosed left parentheses.  Notice also that, when you type a
right parenthesis, the matching left parenthesis is briefly
highlighted.  In the code above, words to the right of semicolons
are comments, and need not be typed.  After you have finished
entering the definition, saved the procedure on your disk in a
file named @a[ps1.scm].
@end(exercise)

@begin(exercise)
``Zap'' your procedure from the editor into Scheme,@foot{Use the
@c[send buffer] command (@c[shift]-k@-[7] on the Chipmunk keyboard).
This transmits the entire buffer to Scheme, and is the easiest thing
to use when you only have one or two procedures in your buffer.  With
larger amounts of code, it is better to use other ``zap'' commands,
which transmit only selected parts of the buffer, such as individual
procedure definitions.  For a description of these commands, see the
description of NMODE in the Chipmunk manual, under the heading
``Commands for use with Scheme.''} and run it with test values by
executing:

@begin(programexample)

(epicycloid 40 35 60 0.1)
@end(programexample)

(To execute the expression, type the expression and press the
@c[EXECUTE] key.)  To see the drawing, press the key marked
@c[GRAPHICS] at the upper right of the keyboard.  The Chipmunk system
enables you to view either text or graphics on the screen, or to see
both at once.  This is controlled by the keys marked @c[GRAPHICS] and
@c[ALPHA].  Pressing @c[GRAPHICS] shows the graphics screen
superimposed on the text.  Pressing @c[GRAPHICS] again hides the text
screen and shows only graphics.  @c[ALPHA] works similarly, showing
the text screen and hiding the graphics screen.

If the program runs correctly, it should draw the following figure:
@begin(figure)
@blankspace(4 inches)
@caption{Figure drawn by @a[(epicycloid 40 35 60 0.1)]}
@end(figure)

If you typed the program incorrectly, you will need to debug the
procedure and return to the editor to make corrections.

Observe that the @a[epicycloid] procedure does not terminate.  It will
keep running until you stop execution by typing control-G.  (The
@c[CONTROL] key at the upper left of the keyboard is used like a @c[SHIFT]
key.  To type control-G, hold down the @c[CTRL] key and press G.)
@end(exercise)

@begin(exercise)
Define a procedure @a[radius-scale] that takes
as argument a number @a[m], and calls @a[epicycloid] with @a[a]
equal to 30, @a[b] equal to 20, @a[a1] equal @a[m] times 60, and
@a[dt] equal to 0.1.

Explore the family of figures generated by @a[radius-scale] as @a[m]
varies smoothly from 0 to 1. Turn in two or three sketches showing how
the figures change, together with a listing of the procedure
@a[radius-scale].

In doing this problem, you can save typing by taking advantage of the
``line edit'' and ``recall'' features of Scheme.  Pressing the
@c[recall] key will redisplay the last Scheme expression evaluated.
This can then be edited using many of the NMODE edit commands.@foot{In
general, you can use all the edit commands that keep the cursor within
a single line.  An exception: Do not use @c[ctrl]-B if you want to
move the cursor to the left.  Use the left-arrow key.} For instance,
suppose you have just evaluated @a[(radius-scale 0.1)] and you now
want to evaluate @a[(radius-scale 0.2)].  You can press @a[recall],
use the arrow keys to move the cursor to the character to be changed,
make the edit, and finally press @c[execute] to evaluate the modified
expression.  @c[Recall] always redisplays the previous expression.
Once you have pressed @c[recall], you can repeatedly press
@c[ctrl-recall] to replace this by the next-to-last expression, the
expression before that, and so on, cycling through a ``ring buffer''
of saved expressions.
@end(exercise)

@begin(exercise)
A hypocycloid is similar in definition to an
epicycloid.  Using the editor, make a copy of your code for
@a[epicycloid], and modify it to implement a definition for
@a[hypocycloid].  Turn in a listing of the procedure.
@end(exercise)

@begin(exercise)
Investigate the family of hypocycloids generated with @a[a]=60,
@a[b]=30, @a[dt]=0.2, and
@a[a1] varying from 0 to 70. All these figures should have 3-fold
symmetry. Turn in sketches of some of the figures to indicate how
the shape varies as @a[a1] changes.
@end(exercise)

@begin(exercise)
Investigate the hypocycloids that are generated with @a[a]=60,
@a[a1]=60, @a[dt]=0.2, and @a[b] taking on values that are integer
multiples of 5 that are greater than 0 and less than 60.  Pay
particular attention to the symmetry of the figures.  (For example,
@a[b]=30 produces 3-fold symmetry and @a[b]=40 produces 4-fold
symmetry.)  Find a value of @a[b] that produces a figure with 5-fold
symmetry; with 11-fold symmetry.  What kind of symmetry is produced by
@a[b]=35?  Turn in a sketch of one of the more interesting figures
you discover.
@end(exercise)

@begin(exercise)
If we restrict @a[a] and @a[b] to be integers, then the epicycloid
will be completely drawn by the time that @a[t] reaches 2 times @a[b]
times pi. Explain why.  (In general, waiting until @a[t] reaches 2
times @a[b] times pi may cause the figure to be traced more than once.
The number of times that the figure will be retraced can be specified
in terms of @a[a] and @a[b].  You might think about how to do this.)
Modify the @a[epicycloid] program so that it stops when @a[t] becomes
greater than @a[b] times 2 pi.  (Let the procedure return 0 when it
stops).  This requires only a small modification to the @a[iter]
procedure.  In order to do this conveniently, in Scheme define @a[pi]
to be 3.14159.  Also define @a[2pi] to be a constant equal to twice
@a[pi].  Turn in a listing of your modified procedure, as well as the
expressions you type to Scheme to define @a[pi] and @a[2pi].
@end(exercise)

@begin(exercise)
(@i[Design problem]) The @a[epicycloid] procedure given above does a
lot of unnecessary computation.  Each time it plots a point, it
computes the sum of @a[a] and @a[b] four times.  In computing the
argument to @a[sin] and @a[cos] it multiplies @a[t] by a constant and
then divides the result by @a[b], rather than just multiplying by a
single constant that could have been computed just once at the
beginning of the plot.  It takes no advantage of the fact that many of
the same quantities, such as @a[(/ (* (+ a b) t) b)], are used in
computing both the @a[x] and the @a[y] coordinates.

Redesign the procedure to eliminate as many of these redundant
computations as you can.  (You may need to define extra internal
variables or procedures.)  Implement your design as a new procedure
@a[epicycloid1].  Test your procedure to verify that it draws the same
figures as does the original @a[epicycloid].  Does your modification
improve the speed by a noticeable amount?  (Use a wristwatch, or the
clock at the lower right of the screen, to determine approximate
timings.)  Turn in a listing of @a[epicycloid1], together with the
expressions you ran to make timing tests, and the comparative timings
for @a[epicycloid] and @a[epicycloid1].
@end(exercise)

@section(Adventures in Debugging)

During the semester, you will often need to debug programs that
you write.  This section contains an exercise that you
should work through @i[at the terminal] to acquaint you with some
of the features of Scheme to aid in debugging.  There is
nothing you need turn in for this part of the problem set, but we
strongly suggest that you do this exercise.   Learning to use the
debugging features will save you much grief on later problem
sets.

The file @a[ps1-debug.scm] is a short file that has been provided for
you to load into Scheme.  To do this, use the NMODE extended
command ``load problem set'' and specify that you want to load
the code for problem set 1.  This will make a copy of the file on
your disk.

The file contains three tiny procedures called @a[p1], @a[p2], and
@a[p3].  You can examine them using NMODE, but there is no need to do
that now -- you will see them later on, during debugging. Zap the
procedures into Scheme.  Now evaluate the expression @a[(p1 1 2)].
This should signal an error, with the message
@begin(programexample)
Wrong Number of Arguments 1
within procedure #[COMPOUND-PROCEDURE P2]
There is no environment available;
using the current read-eval-print environment.

2 Error->
@end(programexample)

Don't panic.  Beginners have a tendency, when they hit an error,
to quickly type @c[ctrl-G] or press @c[edit]. Then they stare at
their code in the editor until they see the what the bug is.
Indeed, the example here is simple enough so that you probably
can see the bug just by reading the code.  But don't do
this.  Let's instead see how Scheme can be coaxed into producing
some helpful information about the error.

First of all, there is the error message itself.  It tells you
that the error was caused by a procedure being called with 1
argument, which is the wrong number of arguments for that
procedure.  The next line tells you that the error occurred
within the procedure
@a[P2], so the actual error was that @a[P2] was called with 1
argument, which is the wrong number of arguments for @a[P2].

The other information about ``current environment,'' and
``read-eval-print environment'' you can ignore.  We will
learn about environments later in the semester.  Notice, however,
that the prompt now reads
@begin(programexample)
2 Error->
@end(programexample)
which is Scheme's way of indicating that you can now
evaluate expressions within the context of the error, and that
this context is ``at level 2,'' namely, one level down from the
``top level,'' which is the initial Scheme command level.

Unfortunately, the error message alone doesn't say where in
the code the error occurred.  In order to find out more, you need
to use the debugger.  To do this execute the expression @a[(debug)].

@paragraph(Using the debugger)

The debugger allows you to grovel around
examining pieces of the execution in progress, in order to learn
more about what may have caused the error.
When you typed @a[(debug)] just above, Scheme should have responded:
@begin(programexample)
Subproblem Level: 0  Reduction Number: 0
Expression:
(P2 B)
within the procedure P3
applied to (1 2)
Debugger

3 Debug-->
@end(programexample)

This says that the expression that caused the error was
@a[(P2 B)], evaluated within the procedure @a[P3], which was
called with arguments 1 and 2.  That's probably enough
information to let you fix the error, but let's pretend we need
more information, just to learn more about how the debugger works.

Ignore the stuff about Subproblem and Reduction numbers.  (You can
read about them in the Chipmunk manual.)  The prompt says that you are
in the debugger (at level 3, one down from the error level, which was
level 2).  At this point, you could type @c[ctrl]-G to exit the whole
mess and get back to Scheme's ``top level,'' but let's instead explore
the debugger.

The debugger differs from an ordinary Scheme command level, in
that you use single-keystroke commands, rather than typing expressions
and pressing @c[execute].

One thing you can do is move ``backwards'' in the evaluation
sequence, to see how we got to the point that signaled the error.
To do this, type the character @a[b].  Scheme should respond:
@begin(programexample)
Subproblem level: 1 Reduction number: 0
Expression:
(+ (P2 A) (P2 B))
within the procedure P3
applied to (1 2)

3 Debug-->
@end(programexample)
Remember that the expression evaluated to cause the error was @a[(P2
B)].  Now that we have moved ``back,'' we learn that this expression
was being evaluated as a subproblem of evaluating the expression
@a[(+ (P2 A) (P2 B))], still within procedure @a[P3] applied to 1
and 2.

Press @a[b] again, and you should see
@begin(programexample)
Subproblem Level: 2  Reduction Number: 0
Expression:
(+ (P2 X Y) (P3 X Y))
within the procedure P1
applied to (1 2)
@end(programexample)
which tells us that got to the place we just
saw above as a result of trying to evaluate an expression in
@a[P1].

Press @a[b] again and you should see a horrible mess.  What you
are looking at is some of the guts of the Scheme system -- the part
shown here is a
piece of the interpreter's read-eval-print program.  In general,
backing up from any error will eventually land you in the guts of
the system.  At this point you should stop backing up unless, of
course, you want to explore what the system looks like.  (Yes:
almost all of the system is itself a Scheme program.)

In the debugger, the opposite of @a[b] is @a[f], which moves you
``forward.'' Go forward until the point of the actual error,
which is as far as you can go.

Besides @a[b] and @a[f], there about a dozen debugger
single-character commands that perform operations at various
levels of obscurity.  You can see a list of them by typing @a[?]
at the debugger.  For more information, see the Chipmunk manual.

Hopefully, the debugger session has revealed that the bug was in
@a[P3], where the expression @a[(+ (P2 A) (P2 B))] calls @a[P2]
with the wrong number of arguments.@foot{Notice that the call
that produced the error was @a[(P2 B)], and that @a[(P2 A)] would
have also given an error.  This indicates that in this case
Scheme was evaluating the arguments to @a[+] in right-to-left
order, which is something you may not have expected. You should
never write code that depends for its correct execution on the
order of evaluation of the arguments in a combination.  The
``official definition'' of Scheme (whatever that means) does not
guarantee that that any particular order will be followed, nor
even that this order will be the same each time a combination is
evaluated.} You can type @c[ctrl]-G to return to the Scheme top level
interpreter.

@paragraph(The stepper)

Even with such a simple error, debugging was not so simple.
What do you expect?  After all, an error occurred and you
have to grovel through the mess.  An alternative debugging
strategy is to re-evaluate the expression that produced the error, only
this time to do the evaluation ``step by step,'' and observe the
precise point where the error happens.  The Scheme program that
lets you do this is called the @i[stepper].

Let's try to debug again, this time using the stepper.  Clear the
screen (by typing @c[ctrl]-L) and evaluate the expression
@begin(programexample)

(step '(p1 1 2))
@end(programexample)
Don't omit the quotation mark after @a[step].   (You'll learn
about what quotation is for when we get to Chapter 2.)

If you did this correctly, Scheme should type, halfway down the screen,
@begin(programexample)

(DEFINE (P1 X Y) (+ (P2 X Y) (P3 X Y)))
Stepping: (P1 1 2) Eval Combination
@end(programexample)

What you are seeing is the text of the procedure being evaluated,
namely @a[P1].  The next line tells you that the expression being
stepped that called this procedure is @a[(P1 1 2)] and that the
interpreter is at the point ``Eval combination'' which is the
point where the interpreter sets up to evaluate a
combination.  (Later in the semester, we will learn about the
various elements of the evaluation process.)  The cursor is
flashing at the beginning of the combination to be evaluated.

Type a space.  This proceeds the evaluation ``one step.''  Notice
that nothing much happens, except that the cursor moves to the
beginning of the right-hand inner combination, which is the next
thing the interpreter is going to work on.@foot{There's that right-to-left
evaluation order again.  See previous footnote.}

Type another space and the interpreter starts working on the
subexpressions of this combination, starting with the symbol @a[Y].
Accordingly, the stepper prints
@begin(programexample)

Eval Irreducible
Y has the value
2
@end(programexample)
telling you that @a[Y] was irreducible (no subexpressions) and
that it has the value 2.

Type another space and you will see that @a[X] has the value 1.
Another space shows the interpreter determining that @a[P3] is the
name of a procedure.
@begin(programexample)

P3 has the value
#[COMPOUND-PROCEDURE P3]
@end(programexample)

When you type another space, the message changes to show that the
interpreter is about to apply @a[P3] to the arguments 1 and 2.

You now have a choice: you can ask the stepper to do the
application in one step, or you can go step-by-step through the
application.

If you press space, the stepper will do the application in one step and
show the returned value.  Try this.

Ugh!  That signaled the error.  So we know that the error happens
while evaluating @a[(P3 1 2)].  We probably should have gone step
by step through this part of the evaluation.

So go back and try again.  Press @c[ctrl]-G, clear the screen,
execute
@begin(programexample)

(step '(p1 1 2))
@end(programexample)
and press space until you get back to the point where the
interpreter is about to apply @a[P3] to 1 and 2.

This time, instead of pressing the space bar, type @a[s].
The stepper should now show the application of the internal procedure:
@begin(programexample)

(DEFINE (P3 A B) (+ (P2 A) (P2 B)))
@end(programexample)

Another space will get to the application @a[(P2 B)], which gives
the error.

Notice that this is the same information we found with the
debugger above.  Only this time we are working ``forwards'' until
the error occurs instead of letting the error happen and then
working backwards.  Both of these techniques should be part of
your debugging repertoire.


@paragraph(For you amusement)

Edit @a[P3] to eliminate the error by calling @a[P2] with two
arguments each time.  (It doesn't matter what these
arguments are, so long as the applications don't produce errors.) 
Now step through the original call to @a[P1], and get to the point in
@a[P3] where the addition operator @a[+] is about to be applied
to 2 arguments.  If you were to type a space at this point, the
addition would be performed and the result shown.  But, instead
of typing a space, type an @a[s], and you will see some incredibly
obscure stuff.

What you are looking at are the internals of the addition
operation, implemented as a Scheme procedure.  You see, we lied
to you in lecture: @a[+] is not a primitive in the Scheme system
you are using.

The lesson to draw from this is not that we are liars, but that
the meaning of ``primitive'' must always be taken to be relative
a given level of detail at which one wants to look.  Since we
have more than enough material to cover this semester without
worrying about how the 6.001 Scheme system is implemented in
detail, it is convenient for us to consider @a[+] to be a primitive.

For fun, you can start stepping through the application of @a[+].
Each time you get to an internal application, type @a[s] to go
inside of it.  Eventually you will get to a ``real primitive.''
Of course, all that a ``real primitive'' is is something that the
stepper won't let you look inside of.  In terms of the assembly
language ``kernel'' of Scheme, a ``real primitive'' might be a
complex program made up of lots of instructions in assembly
language.  And any single assembly language instruction might be
a complex program written in microcode.

This illustrates a major idea that we will see thoughout 6.001: One
does @i[not] create complex systems by focusing on how to construct
them out of ultimate primitive elements.  Rather, one proceeds in
layers, erecting a series of levels, each of which is the
``primitives'' upon which the next level is constructed.