Com S 227 --- Introduction to Computer Programming

			 HOMEWORK 9: MUTATION
		 (File $Date: 1993/11/30 21:11:06 $)

Due: (everything (Dec 8))

In the part of chapter 11 (we skipped chapter 10) that we will discuss
this year you will learn how to use the assignment statement, Scheme's set!.
We will see how to write loops using set! to change variables,
and how to abstract such loops using while-proc (similar to the while loops
in other languages).  We will also see how to do something that would be
nearly impossible without mutation: memoization of functions.

All the directions from homework 2 apply to this homework.
In particular, remember to hand in labeled printouts for procedures,
and transcripts showing your testing.


SECTION 11.2, ASSIGNMENT AND STATE

1. (0 points; suggested practice)
What are the results of the following expressions?  Why does Scheme give
those results?
	(let ((x 2));; (a)
	  (writeln x)
	  (let ((x 'hmm))
	    (writeln x) (set! x 'inside) (writeln x))
	  (writeln x))

	(letrec ((du (lambda (x);; (b)
		       (writeln x)
		       (if (not (zero? x))
			   (begin
			     (set! x (sub1 x))
			     (du x)
			     (writeln x))))))
	  (du 4))

2. (0 points; suggested practice)
What happens when you give Scheme the following?
	(begin
	  (define foo 3)
	  (writeln foo)
	  (let ((bar 4))
	    (define foo 5)
	    (writeln foo))
	  (writeln foo))
What does this tell you about the difference between define and set!?


PAGES 353-354, IMPERATIVE-STYLE PROGRAMMING WITH WHILE-PROC AND SET!

In this section you will write procedures using while-proc.
A ``procedure written using while-proc'' should avoid the use
of vector-generator, and instead use make-vector, vector-set!, set!, and 
while-proc (program 11.8, which you can get by loading "ch11.ss").
For example, the following procedure is a version of program 9.5, on page 272,
that uses while-proc

	(load-from-lib "ch11.ss")
	
	(define vector-stretch-while
	  ; TYPE: vector, integer -> vector
	  (lambda (vec new-size)
	    ; ENSURES: result is a new copy of vec, but having size new-size,
	    ; result filled with () if bigger
	    (let ((size (vector-length vec))
	          (res (make-vector new-size))
	          (i 0))
	      (while-proc (lambda () (< i new-size))
	             ; INVARIANT: i <= new-size and for all 0 <= j < i,
	             ; the jth element of res is correctly filled in
	             (lambda ()
	               (if (< i size) 
	                   (vector-set! res i (vector-ref vec i))
	                   (vector-set! res i '()))
	               (set! i (add1 i))))
	      res)))

4. (5 points)
Write a version of the successive-powers procedure, in exercise 9.1,
using while-proc.

5. (10 points)
Write a version of multiply-by-scalar using while-proc.
(Hint, you can do this by writing a while-proc loop version of
vector-map.)  For example, consider the following transcript.

	> (define my-vec (vector 1 2 3))
	> my-vec
	#(1 2 3)
	> (multiply-by-scalar 7 my-vec)
	#(7 14 21)
	> my-vec
	#(1 2 3)

6. (5 points)
Write a version of vector-generator (see program 9.21) using while-proc.

7. (0 points; suggested practice)
Write a version of matrix-product (see program 9.38) using while-proc.

8. (10 points)
Write a version of program 5.4 on page 139 using while-proc.
That is, instead of using the letrec and tail recursion, use a call
to while-proc and use set!.  Test your program to see that it
correctly computes factorials.

9. (0 points; suggested practice)
Write a version of program 4.24 (fib-it) on page 124 using while-proc.
(Hint, you will need two variables.)

10. (10 points)
You may have noticed that many of the while loop procedures,
especially those that work with vectors share a similar structure.
This looping structure is called a ``for loop'',
because in many programming languages there is a statement called ``for''
that does this.  Write a procedure ``from-to'' that takes
two numbers ``from'' and ``to'' and returns a procedure that
takes a procedure, ``one-step'', of type (-> (number) void),
and which returns nothing.
The call ((from-to n m) p) should execute, in order,
	(p n), (p n+1), ..., (p m).
For example, consider the following transcript.

	> (begin
           ((from-to 0 4) (lambda (x) (display x) (display ", ")))
           (newline))
	0, 1, 2, 3, 4, 
	> ((from-to 4 4) (lambda (x) (writeln (* x x))))
	16
	> ((from-to 4 0) (lambda (x) (writeln "you goofed")))
	>

11. (0 points; suggested practice)
Rewrite the problems above that used while-proc using from-to.

12. (10 points)
Write vector-generator using from-to.
Be sure to test it and check that it is returning a vector with the
exact number of elements specified.

13. (0 points; suggested practice)
Write a procedure ``from-to-by''
that takes three numbers from, to, and by,
and returns a procedure that takes a procedure one-step
of type (-> (number) void), and which returns nothing.
The call ((from-to-by n m b) p) should execute, in order,
	(p n), (p n+b), ..., (p m), if m = n + k * b for some natural number k.
If there is no such ``k'', then the last call of p should be
(p x), where x = n + k'*b and k' is the smallest natural number
such that if b is positive, then n+(k'+1)*b is larger than m,
or if b is negative, then n+(k'+1)*b is smaller than m.
Note that (from-to-by n m 1) is equivalent to (from-to n m).
For example, consider the following transcript.

	> (begin
	    ((from-to-by 4 0 -1) (lambda (x) (display x) (display ", ")))
	    (newline))
	4, 3, 2, 1, 0, 
	> ((from-to-by 4 4 3) (lambda (x) (writeln (* x x))))
	16
	> (begin
            ((from-to-by 4 12 3) (lambda (x) (display x) (display ", ")))
	    (newline))
	4, 7, 10, 
	>

14. (0 points; suggested practice only)
Do exercise 11.9.

15. (0 points; suggested practice only)
Do exercise 11.10.  Check your answer on the computer.

16. (0 points; suggested practice only)
Rewrite the ``display-tower-of-hanoi'' program (program 6.10),  using set!,
while-proc, and 3 variables: left, center, and right, to hold the
number of disks on the corresponding post.
After each move print the state in a form such as:
	left: 3 center: 0 right: 2 
So that the output is a series of lines of this form.
For example, (display-tower-of-hanoi 2) would print the following.
	left: 2 center: 0 right: 0
	left: 1 center: 1 right: 0
	left: 0 center: 1 right: 1
	left: 0 center: 0 right: 2

PAGES 344-351, MEMOIZATION

In this section you can use either a functional or an imperative
style as you see fit.

17. (0 points; suggested practice)
Do exercise 11.1 on page 349.  This is to show how memoizing works.

18. (10 points)
Do exercise 11.2 (pascal-triangle).


19. (6 points)
Do exercise 11.3.  The procedure timer (program 10.19) is found in
/home/cs227/lib/timer.ss. If you use some other Scheme instead of
Chez Scheme, see the comments in the file.


20. (4 points)
Do exercise 11.4.


21. (10 points)
Do exercise 11.5.


22. (10 points)
Do exercise 11.6.

23. (12 points)
Do exercise 11.7.


SECTION 11.3, BOX-AND-POINTER REPRESENTATION OF CONS CELLS

We won't be doing this section this semester.  But you may want to read
it to find out how lists are implemented by Scheme.
Note that exercises 11.20 through 11.26 explain a theoretical model
of computers, called ``Turing machines.''  They are named after the late
Alan Turing, who used them do prove that there are some programs that
are easy to specify, but which cannot be programmed!  The proof itself
is not contained in the exercises, but the idea that such simple Turing
machines can compute anything computable is explored.
 You will see more of Turing machines if you take Computer Science 331.


COURSE SUMMARY

24. (0 points; suggested practice only)
Compare the programs you have written using the imperative style
and while loops to those written using functional style.
Realizing that you may prefer the style you are best acquainted with,
can you see any advantages and disadvantages to these styles?
Which would you use of the final exam, given a choice?
Why do you think that many programming languages only support
an imperative style?

25. (0 points; suggested practice only)
Take a longer program that you wrote this semester, for example one from
chapters 5 or 6, and produce two versions.
One version that is the most elegant you can produce,
and another that is the least elegant you can produce.
The bad version must still work and must be correctly formatted;
the idea is not to make it hard to understand,
but to do everything the hard way instead of using abstraction.

26. (0 points; suggested practice only)
Go back over your homeworks and collect the ones that would be useful to
you in the future, assuming that you are to write more Scheme programs.
Add comments as necessary so you can understand them a year from now.


CHAPTER 12, OBJECT-ORIENTED PROGRAMMING

Chapter 12 is interesting as a combination of all the ideas of previous
chapters.  This chapter also contains some of the data structures you
will see (in different guise) in Com S 228.
If you have time, the exercises in chapter 12 will help you get
an idea of what object-oriented programming is like.
You will see more of object-oriented programming in Com S 228
and other classes.


THE REST OF THE BOOK

Someday, you might enjoy exploring in the rest of the book.
Chapters 12 and 13 are an obvious place to start.
Chapter 14 shows you how to define your own special forms.
Chapter 15 shows a very interesting application of the techniques
in chapter 14: streams.  Streams can be used for input and output,
but more than that they can represent ``infinite data structures''.
Chapters 16 and 17 (which can be read before 14 and 15)
explore an extremely powerful and deep idea about control.
It can be used to do things like exception handling, and much more.

After that you might want to read some of the suggestions in our handout
``How to become a Computing Professional''.  Suggest them to your friends
and family as gift ideas!