These exercises are due at the beginning of class on Tuesday, February 25. In each case, you should submit the source code for your procedure and also show what happens when your procedure is invoked, in enough different cases to satisfy me that it works as described.

The source code for your procedures should be accompanied by comments explaining what the procedures do and (unless this is quite obvious) how they do it. In writing the comments, assume that you are addressing an intelligent outsider who already knows some Scheme but has not read the assignment and needs to know what the procedure is for. You should also include your name, the date, and the occasion for which the code was written in a comment at the beginning of your file.

I'd like you to send your exercises to me by e-mail. When you're ready to turn something in, run the submit program to create a log file. The handout on submit will remind you of how to do this. Then use the elm program to mail the file to me, as described in the handout on mailing files.

1. Flat recursion.

Design, write, and test a Scheme procedure substitute that takes three arguments -- template, which should be a list, and old and new, which might be values of any type -- and returns a list just like template except that new has been substituted for every element of template that is equal to old (as determined by the equal? predicate). For example:

(substitute '(0 1 2 0 1 2 0 1 2) 0 3) ===> (3 1 2 3 1 2 3 1 2)
(substitute '((a b) (b a) (a) (a b)) '(a b) 'c) ===> (c (b a) (a) c) 
(substitute '(alpha beta) 'gamma 'delta) ===> (alpha beta)
(substitute '(a a a) 'a '(1 2)) ===> ((1 2) (1 2) (1 2))

In designing this procedure, you should consider such issues as what should happen if the template argument is the empty list and whether you want to include a precondition test. In testing the procedure, you will want not only to try the four cases shown here, but to invent and check out a variety of special cases that confirm that everything in your procedure works correctly.

2. Recursion on two lists.

Design, write, and test a Scheme procedure maximize that takes two lists of real numbers as arguments, compares the numbers that are in corresponding positions on the two lists, and returns a single list containing at each position the larger of the numbers compared for that position:

(maximize '(1 2 3 4 5) '(5 4 3 2 1)) ===> (5 4 3 4 5)
(maximize '(-3 -8 12 0 6 -4) '(-7 3 9 6 6 -2)) ===> (-3 3 12 6 6 -2)
(maximize '(5 5 5) '(4 4 4)) ===> (5 5 5)

If the given lists are of different lengths, the result should always be as long as the longer of them, and the longer list should provide the result value for any position after the end of the shorter list:

(maximize '(1 2 3 4 5) '(8 7 6)) ===> (8 7 6 4 5)
(maximize '(-3 4) '(3 2 -7)) ===> (3 4 -7)
(maximize '(-1 -1 -1 -1) '()) ===> (-1 -1 -1 -1)

3. Mutual recursion.

Design, write, and test two Scheme procedures, up-sum and down-sum, each of which takes a list of numbers as its only argument. The up-sum procedure should add its first element to the down-sum of all of its subsequent elements, or return 0 if it is given an empty list. The down-sum procedure should subtract its first element from the up-sum of all of its subsequent elements, or, again, return 0 if its argument is the empty list.

For extra credit, describe what these procedures compute without defining them recursively.

This document is available on the World Wide Web as

http://www.math.grin.edu/courses/Scheme/spring-1997/exercise-1.html