Com S 342 --- Principles of Programming Languages

	HOMEWORK 6: CONVENTIONAL INTERFACES AND SYMBOLIC DATA
		 (File $Date: 1999/11/14 17:18:45 $)

Due: problems 1-7, at beginning of class November 11, 1999.

In this homework you will learn about standard patterns for dealing
with lists in functional programming.  In particular you learn about
the use of the accumulate and filter procedures.  You'll also learn
a bit about symbolic data.

The section headings below give the readings related to the problems.

WHAT TO HAND IN

For code hand in *both* your printout of the code and a transcript of
testing.

Be sure the code has your name and section information in a comment at
the top as described in homework 0 at the top.  Although you may want
to write your code out by hand as practice for taking the tests, and
then type it in, please don't turn in handwritten code, unless the
problem specifically states otherwise.

*No* credit will be given for programming problems unless you also
hand in a transcript that includes test output.

For this homework, testing is left to you, and there are no test
harnesses.  This is because understanding how to use (and hence test)
these procedures is half of what we want you to learn.


SICP section 2.2.3

1. [the power of accumulate]
   (15 points) Using Scheme, do exercise 2.33 in the text.  Think about it
   first, then check your work using the Scheme interpreter.
   You can load the "accumulate" procedure by writing:
	(load-from-lib "accumulate.scm")

2. [accumulation on trees]
   (10 points) Using Scheme, do exercise 2.35 in the text.   Think about it
   first, then check your work using the Scheme interpreter.

3. [accumulate-n]
   (10 points) Using Scheme, do exercise 2.36 in the text.   Think about it
   first, then check your work using the Scheme interpreter.

4. [matrix operations]
   (15 points) Using Scheme, do exercise 2.37 in the text.    Think about it
   first, then check your work using the Scheme interpreter.

5. [fold-right and fold-left]
   (15 points) Do exercise 2.38 in the text in Scheme.    Think about it
   first, then check your work using the Scheme interpreter.  Don't
   forget the question at the end.
   You can load the "fold-right" and "fold-left" procedures by writing:
	(load-from-lib "fold-right.scm")
	(load-from-lib "fold-left.scm")

6. [eight queens puzzle]
   (30 points) Do exercise 2.42 in text using Scheme.
   Check your work using the Scheme interpreter.
   You can load the "flatmap" procedure by writing:
        (load-from-lib "flat-map.scm")
   You can load the "enumerate-interval" and "filter" procedures similarly.
   Some of the code you'll want for this problem is found in
   the file $PUB/sicp/ch2.scm (search for "EXERCISE 2.42").
   However, don't just load that file: just copy the code you want into
   a file.
   Hints: Think about the representation of boards first, that's part of
   the problem.  To see what the code that is provided is doing,
   think about the types first.  Then try making the safe? procedure
   a stub that always returns true, and try invoking
   queens for different small numbers; look at the order of the boards
   produced.  Note that for boards of size 2 and 3, there is no solution to
   the eight queens problem.  Also, if safe? returns #f always, then you'll
   get no answers.

SICP section 2.3.2

7. [deriv extensions]
   (15 points)  Do exercise 2.56 in the text using Scheme.
   Some of the code you'll want for this problem is found in
   the file $PUB/sicp/ch2.scm.

8. (extra credit) If you have done all of the above, you can do extra
credit in SICP sections 2.2.3 and 2.3.2 by selecting any of the exercises not
listed above that are found in those sections.  These problems will be
worth 10 points extra credit if done in Scheme, and 25 if done in
Java.  Be sure to hand in both your code and test output.  Extra
credit problems should be handed in separately from the other problems.
(We will be doing problems from 2.2.4 in a future homework,
so don't do those yet.)