Com S 342 --- Principles of Programming Languages

		 HOMEWORK 1: INDUCTION and RECURSION
		  (File $Date: 1995/08/31 02:56:11 $)

Due:  problems 0,5-6,8, and 10 in your discussion section, September 1;
      12 and 14 at the beginning of class, September 6.

In this homework, you will learn (or recall what you know)
about induction and recursion.  All code is to be written in Scheme,
using the exact procedure names specified in the problem
descriptions.  For code hand in *both* your printout of the code
and a transcript of testing.  See the directory $PUB/data/hw1 for test data
for each coding problem.  (Recall that $PUB means /home/cs342/public.)

The section headings below give the readings related to the problems.
(Please read them!)

0. (5 points)
   What is your background in Scheme?
     a. more than one course using Scheme
     b. one course using Scheme (e.g., Com S 227)
     c. one course using LISP, but not Scheme
     d. experience using LISP
     e. no prior experience with Scheme or LISP

ESSENTIALS OF PROGRAMMING LANGUAGES: Section 2.1

1. (5 points, extra credit)
   Do exercise 2.1.1 in the text.  (This can be handwritten)

2. (5 points, extra credit)
   Do exercise 2.1.2 in the text.  (This can be handwritten)

3. (suggested practice)
   Do exercise 2.1.3 in the text.

4. (15 points, extra credit)
   Do exercise 2.2.1 in the text.

5. (5 points)
   Do exercise 2.2.2 in the text.  (This can be handwritten)

6. (5 points)
   Do exercise 2.2.3 in the text.  (This can be handwritten)

7. (suggested practice)
   Do exercise 2.2.4 in the text.

8. (5 points)
   Do exercise 2.2.5 in the text.  You only have to use map once
   in your code.

   After doing your own testing on the procedure subst you wrote,
   you can test your code as follows, if you are using the Com S machines,
   and have the directory $PUB/bin (/home/cs342/public/bin) in your PATH.
   Start the interpreter, scm342, by typing at the shell prompt
   (you have to be in your own directory for this):
	scm342
   Then start a transcript:
	(transcript-on "hw1-8.out")
   Then execute our test by typing:
	(test-hw1 "subst")
   (If you get errors that appear to be in our files, they are probably
   problems in your code...)
   You can also add your own test cases to the output by running them
   now if you want.
   Now if you are satisfied, you can stop by typing to Scheme:
	(transcript-off)
	(exit)
   Print the file hw1-8.out and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code
   (as in homework 0).

   If you aren't on the Com S machines, see the directions in
   $PUB/homework/hw1.tst/README.

9. (5 points, extra credit)
   Do exercise 2.2.6 in the text.

10. (25 points (5 points each))
   Do exercise 2.2.7 in the text, parts 2, 3, 4, 5, and 8.

   After doing your own testing on the procedures you wrote,
   you can test your code as follows, if you are using the Com S machines,
   and have the directory $PUB/bin (/home/cs342/public/bin) in your PATH.
   Start the interpreter, scm342, by typing at the shell prompt
   (you have to be in your own directory for this):
	scm342
   Then start a transcript and run the tests by typing to Scheme:
	(transcript-on "hw1-10.out")
	(test-hw1 "invert")
	(test-hw1 "list-index")
	(test-hw1 "vector-index")
	(test-hw1 "ribassoc")
	(test-hw1 "swapper")
   (If you get errors that appear to be in our files, they are probably
   problems in your code...)
   You can also add your own test cases to the output by running them
   now if you want.
   Now if you are satisfied, you can stop by typing to Scheme:
	(transcript-off)
	(exit)
   Print the file hw1-10.out and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code
   (as in homework 0).

   If you aren't on the Com S machines, see the directions in
   $PUB/homework/hw1.tst/README.

11. (suggested practice)
   Do exercise 2.2.7 in the text, parts 7 and 9.

12. (30 points (10 points each))
   Do exercise 2.2.8 in the text, parts 1, 3, and 4.

   Test your code as described above for problem 10.

13. (suggested practice)
   Do exercise 2.2.8 in the text, parts 2 and 5.

14. (30 points (15 points each))
   Do exercise 2.2.9 in the text, parts 2 and 4.

   Test your code as described above for problem 10.

15. (suggested practice)
   Do exercise 2.2.9 in the text, parts 1, 3, 5, and 6.