Com S 227 --- Introduction to Computer Programming

		 HOMEWORK 7: ABSTRACTING PROCEDURES
		 (File $Date: 1993/11/15 16:25:42 $)

Due: ((1-3 (Nov 5)) ((4-10 12-13) (Nov 12))
      ((16-20 22-24 27-30) (Nov 17)) ((31-34) (Dec 1))
      ((all extra credit problems) (Dec 3)))

In this homework you will learn how to use procedural abstractions of
common programming patterns, such as map and for-each,
and how to make up your own such procedural abstractions!
This will involve a review of much of the previous material in the course.

The basic and regular problems in this homework have been designed
for group work.  There are a few problems to check basic understanding, but
many of them require you to find several examples which you can abstract
from earlier in the course; for these problems you should be able
to pool your answers; for example, see problem 6 below.
You may want to read through a whole section of problems before solving
any of them, as this can save time searching.

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.

Testing for the problems in this homework is important, as it shows that
not only can you write code like in the book, but that you understand how
it works.  It's best if you make up at least one or two test cases on
your own. Be sure to include transcripts showing your test cases
for all problems.

SECTION 7.2 (EXCEPT PP. 197--201), PROCEDURES AS ARGUMENTS AND VALUES

This may be a good time to read ``The Little LISPer'', chapters 8 and 9,
which is on reserve at the library.  You can stop around the discussion
of curry-maker (p. 151 in my copy), or whenever you start to see even more
weird things than we've discussed in class.

1. (0 points; suggested practice only)
   Fill out a table of types as suggested in the ``Chapter 7'' section of
   the Make Your Own Scheme Reference Card handout.

2. (0 points; suggested practice)
   Do exercise 7.1 on page 202.

3. (5 points; basic)
   Do exercise 7.2.
   For example,
	((compose3 add1 add1 add1) 4) ==> 7

4. (0 points; suggested practice)
   Do exercise 7.4.  You should not use the procedure -, but you may use
   sub1 in your answer.

5. (0 points; suggested practice)
   Do exercise 7.5.
   In addition, write why each answer is what it is, in your own words.
   Use the computer to check your work, not to think for you.

6. (20 points)
   Find as many homework problems and exercises in the textbook in chapters 2-6
   that can be solved using map (and that are not mentioned in chapter 7 or
   in this homework) as you can.  Show how to solve each of them using map.
   Your grade will depend both on the correctness of your answer
   and how many occurrences you find out of those possible.

7. (0 points; suggested practice)
   Do exercise 7.6 in the book.

8. (0 points; suggested practice)
   Do exercise 7.7. You should assume that the second argument, ls,
   is non-empty.  Note that the last example returns #t as noted in the errata
   for the first printing.

9. (15 points)
a. Define a procedure ``red'' of type
	 (-> ((-> (T T) T) (non-empty-list T)) T)
   that takes a procedure ``proc'' and a non-empty list ``lst''
   as arguments. The behavior of red is characterized by the following
   equations, for all x, p, y, and l:
	(red p (cons x '())) = x
	(red p (cons x (cons y l))) = (p x (red p (cons y l)))
   For example,
	(red - '(3)) ==> 3
	(red - '(3 4 5)) = (- 3 (- 4 5)) = (- 3 -1) ==> 4
	(red max '(3 -4 5)) ==> 5
	(red (lambda (x y) (or x y)) '(#t #f #f #t)) ==> #t
b. Find or invent at least 4 examples of problems that could be solved using
   the procedure red, and show how to use red to solve them.

10. (15 points)
a. Do exercise 7.9.
b. Find or invent 5 examples of problems that could be solved using
   map2, and show to solve them using map2.

11. (10 points; extra credit only)
   Define a procedure, map-poly, that is takes a procedure f
   and a poly p as arguments, and returns a poly.  The procedure f
   must have type, (-> (term) poly), where a term is a monomial.
   The result is obtained by taking the results of applying f to each
   term of p, and adding the resulting polys.
   For example,
	(print-poly
	  (map-poly (lambda (trm)
	              (make-term (degree trm) (* 3 (leading-coef trm))))
                    (poly-cons 3 12.0
	              (poly-cons 2 -5.1 (poly-cons 0 2.2 the-zero-poly)))))
	=prints=> 36.0 x^3 + -15.3 x^2 + 6.6
	(print-poly
	  (map-poly (lambda (trm)
                      (make-term (add1 (degree trm)) (+ 3 (leading-coef trm))))
                    (poly-cons 3 12.0 (poly-cons 2 -5.1
                          (poly-cons 0 2.2 the-zero-poly)))))
	=prints=> 15.0 x^4 + -2.1 x^3 + 5.2 x
   Hint: you should pattern your answer after map.
   You may use p+ in your solution.  Load "ch5.ss" from the library.

11.5 (20 points; extra credit only)
a. What homework problems or exercises in chapter 2 or section 4.2 of the book
   cannot be handled by either map, reduce, red, or map2?
   (If all can be handled by map, reduce, red, or map2, then you should
   include those in your answers to the above problems, and write here that
   they all can be.)
b. Define a small set of procedures like map, reduce, red, or map2
   that can be used to solve all the other homework problems and exercises
   from chapter 2 and sections 4.2 of the book, and
c. and show how these procedures can be used to solve these problems.


SECTION 7.2, PP. 197 -- 201, UNRESTRICTED LAMBDA

12. (5 points)
   The Scheme procedure ``max'' can take any number of arguments.
   How is this defined?  To see how, define a procedure ``maximum'' that
   can take any number of arguments, and in your solution use ``max''
   as if it only took exactly 2 arguments.
   For example,
	(maximum 3) ==> 3
	(maximum 3 -5 4 9) ==> 9

13. (10 points)
   Do exercise 7.3.
   As a base case, for all values v,
	((compose-many) v) = v.
   That is, compose-many with zero arguments returns the identity function.
   You can think of the type of compose-many as
	(-> ((-> (datum) datum) ...) (-> (datum) datum))
   (a more accurate type requires a notion of recursive types.)

14. (5 points; extra credit only)
   Alonzo Typed has noticed that for non-empty lists,
   the procedure for-each is more general than necessary.
   To make a procedure for-each-non-empty,
   he copies the code from for-each, changes the name,
   and then changes the test from (null? ls) to (null? (cdr ls)).
   But now for-each-non-empty doesn't work.
   How would you fix it, keeping the test as (null? (cdr ls))?

15. (10 points; extra credit)
   Do exercise 7.10.  Note that the sentence following the faulty definition
   in the exercise should read as follows, with the bracketed words inserted:
   ``This program, as written, is incorrect, because
   [we would like] the two invocations of map
   within the definition ....''
   Note that there are three parts to this exercise
   map, ormap, and the question at the end.


SECTION 7.3, CURRYING

16. (5 points; basic)
   Curry the procedure expt to get a procedure expt-c,
   and use that to define  procedures power-of-2 and power-of-10
   that raise 2 and 10 to the exponent of their arguments, respectively.
   For example,
	((expt-c 2) 3) ==> 8
	((expt-c 3) 2) ==> 9
	((expt-c 10) 4) ==> 10000
	(power-of-2 5) ==> 32
	(power-of-10 4) ==> 10000

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

18. (0 points; suggested practice)
   Curry the procedure poly-value from Chapter 5 to get a procedure 
   ``poly-value-c'' and use it to define the procedures
   ``binary->decimal'' (see Program 5.17 on page 157),
   ``octal->decimal'' and ``hexadecimal->decimal''.

18. (0 points; suggested practice)
   Do exercise 7.14.

19. (0 points; suggested practice)
   Do exercise 7.15.

20. (5 points)
   Do exercise 7.16.

21. (5 points; extra credit only)
   Do exercise 7.17.

22. (7 points)
   Do exercise 7.18.

23. (16 points)
   Give 3 additional examples of procedures from chapters 2-6 of the text
   that could usefully be curried, besides those discussed in chapter 7 of
   the text and in this homework.  For each procedure:
a. state what procedure or procedures your curried procedure
   is a generalization of.
b. give the code for the curried procedure.
c. show how to use the curried procedure to accomplish what the original
   procedure(s) could do; that is, test it.

24. (0 points; suggested practice)
   Do exercise 7.19. Use the computer only to check your work,
   not to think for you.

25. (5 points; extra credit only)
   Do exercise 7.21. 

26. (extra credit; points below)
   John Backus was the principal scientist on the team that invented FORTRAN.
   In 1978 the Association for Computing Machinery gave him its highest award,
   the Turing Award.  In his influential Turing Award lecture,
   ``Can Programming Be Liberated from the von Neumann Style?
   A Functional Style and Its Algebra of Programs''
   (Communications of the ACM, Volume 21, Number 8, August 1978,
   pages 613--641), he gives reasons for abandoning languages like FORTRAN
   and for the kind of programming we have been doing in this chapter.
   (You might enjoy reading it; it's in the library.)
   In this problem you will explore the alternative language, called FP,
   which he proposed.

   One of the features of FP, in Scheme terms, is that every function
   takes one argument, which in the case of procedures like +,
   means that the argument is a list of 2 numbers.
a. (5 points; extra credit only)
   Write a procedure fp-ize that takes a Scheme function of 2 arguments,
   such as +, and returns the FP style function.
   For example,
	((fp-ize +) '(3 4)) ==> 7
	((fp-ize -) '(3 4)) ==> -1
   Define fp-ize so that the function signals an error if
   it is applied to a list that is not exactly 2 elements long.
   Use fp-ize to define procedures fp-plus, fp-times,
   and fp-minus to be the FP versions of the Scheme
   arithmetic procedures.

b.(5 points; extra credit only)
   What is the FP version of the compose function?

c. (5 points; extra credit only)
   In FP, many of the functions are curried.  For example,
   the reduction function, red is curried.
   But the function argument is an FP-style function.
   Thus ((red f) (list x y ...)) = (f (list x ((red f) (list y ...)))).
   How would you write the FP version of the red function?

d. (5 points; extra credit only)
   In FP Backus defined a function ``constr'' that takes a list of FP
   functions and turns it into a FP function that satisfies the following.
	((constr (list  f1 f2 ...)) x) = (list (f1 x) (f2 x) ...).
   How would you write the FP version of the constr function?

e. (10 points; extra credit only)
   How would you write a matrix product procedure using FP conventions?
   For example,
	(mat-prod '(((1 2 3) (4 5 6))
	             ((7 8) (9 10) (11 12) (13 14))))
	 ==> ((25 28) (73 82))


SECTION 7.4, PROCEDURAL ABSTRACTION OF FLAT RECURSION

27. (5 points; basic)
   Do exercise 7.22.
   
28. (5 points)
   Do exercise 7.23.

29. (0 points; suggested practice)
   Do exercises 7.24 and 7.25

30. (10 points)
   Find at least four (4) problems or exercises from chapters 2-6
   that can be solved using flat-recur, that are not mentioned in chapter 7
   or as problems in this homework.  (You can use some of the examples you
   found for other problems in this homework, however.)  Show how to solve
   them using flat-recur.


SECTION 7.5, PROCEDURAL ABSTRACTION OF DEEP RECURSION

   Note that in this section, instead of the procedure deep-recur
   described in the book, you should use the procedure deep-recur-abs.
   The code for this is in the file ``/home/cs227/lib/deep-recur-abs.ss''.

31. (20 points)
   Do exercises 7.26 and 7.27.  You are to write a total of 4 procedure
   definitions for this problem as described in the exercises.
   Your definitions for 7.26 should look like the code we have been writing
   in class for deep recursion, instead of the code in the book.
   You should think of the procedure ``remove-all-c''
   as a procedure that takes a symbol and a tree of symbols as its arguments.
   Use deep-recur-abs.

32. (20 points)
   Solve 3 problems from the homework in sections 4.3 or 4.4 of the book,
   or exercises from those sections of the book using deep-recur-abs.

33. (5 points)
   Define flat-recur using deep-recur-abs.

34. (20 points)
a. Find an set of at least three (3) similar programs or exercises in the text
   from chapters 2-6, which demonstrate a programming pattern
   that is *not* captured by flat-recur or by deep-recur-abs.
b. Briefly argue why these problems cannot be adequately solved
   using deep-recur-abs or flat-recur.
c. Write something like deep-recur-abs and flat-recur that is a procedural
   abstraction of the pattern used to solve those problems, and then
d. use it to solve at least 3 of the original problems.

35. (up to 40 points; extra credit only)
   If you found more than one pattern to abstract in the previous problem,
   do the same things as asked for in problem 34 here.
   You'll get up to 10 points for each different pattern you abstract.
   Do all the parts of problem 34 for each of these.


CHAPTER 8, SETS AND RELATIONS

We are not going to cover chapter 8 in class this semester.
But there are many interesting exercises in that chapter.
Besides their intrinsic interest, these exercises will increase your
mathematical sophistication, and thus may help you in math and computer
classes (such as Com S 330).
(You may want to do them when you take such a class.)

36. (0 points; suggested practice only)
   Read chapter 8.  This will help you understand lambda.
   You might also want to read chapter 8 of the Little LISPer.

37. (many points; extra credit only)
   Do one or more of the following exercises, for the extra credit listed.

   8.1 (4 points), 8.2 (4 points), 8.3 (5 points), 8.4 (8 points),
   8.5 (10 points), 8.6 (5 points), 8.8 (10 points),
   8.9 (4 points), 8.10 (5 points), 8.12 (10 points), 8.13 (1 point),
   8.14 (2 points), 8.15 (5 points), 8.17 (5 points), 8.18 (5 points),
   8.19 (5 points), 8.20 (10 points), 8.21 (5 points), 8.22 (5 points).

   Your solutions should be clearly written with good style, clearly labeled,
   and clearly tested (to be easier on your TA).  Note that you should,
   as you do these concentrate on the functional style described in chapter 8,
   not just getting the right answer.