Com S 342 --- Principles of Programming Languages

   HOMEWORK 3: RECURSION OVER FLAT LISTS AND NUMBERS, AND INDUCTION
		  (File $Date: 2005/02/09 20:27:32 $)

Due: problems 1, 3-6, 11 at the beginning of class on Tues., Feb. 8, 2005;
     problems 12-15 at the beginning of class on Thurs., Feb. 10, 2005.

In this homework, you will learn more about recursion over flat lists,
higher-order procedures, recursion over numeric data, and grammars.

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/homework/hw3
for test data for each coding problem, as described in problem 7 below.
(Recall that $PUB means /home/course/cs342/public/.)
This applies even if you aren't using the Com S machines.
(If you're not, see the course web page for hints.)

*No* credit will be given for Scheme programming problems unless you also
hand in a transcript that includes our tests.

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

ESSENTIALS OF PROGRAMMING LANGUAGES: pages 1-19 (you can skim section 1.1)
THE LITTLE SCHEMER, CHAPTER 3
CODE EXAMPLES WEB PAGE,
    http://www.cs.iastate.edu/~cs342/code-examples.shtml#Little2
    http://www.cs.iastate.edu/~cs342/code-examples.shtml#Little3
    http://www.cs.iastate.edu/~cs342/code-examples.shtml#Procedures
$PUB/docs/follow-grammar-flat.txt

This first set of problems is about recursion over flat lists, and
some of the problems involve interesting uses of Scheme's procedure
mechanisms.  (You may also want to refer to the Revised^5 Report on
Scheme for details about procedures.)

1. (5 points)   [change to remove-first]
   Do exercise 1.8 on p. 18 in the text (which means the Essentials of
   Programming Languages, second edition book). 

2. (suggested practice)  [change to remove]
   Do exercise 1.9 on p. 19 in the text.

3. (10 points) [append-all]
   Write a procedure, append-all, whose type is given by the following
   deftype: 

     (deftype append-all
        (forall (T)
           (-> ((list-of (list-of T))) (list-of T))))

   The procedure append-all takes a list of lists, ll, and returns a
   list of all the lists in ll appended together in the same order in
   which they appear in ll.  In your solution's code you may only use
   Scheme's append procedure with two (2) arguments.

   The following are examples.

    (append-all '())
      ==> ()
    (append-all '((3 7 10) (20 25 30) (5 4 3)))
      ==> (3 7 10 20 25 30 5 4 3)
    (append-all '((20 25 30) (5 4 3)))
      ==> (20 25 30 5 4 3)
    (append-all '((l i k) (e) (t h i s) () (o k)))
      ==> (l i k e t h i s o k)

   After doing your own testing you must test your code using:

	(test-hw3 "append-all")

   Print a transcript of your testing, and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code.

4. (10 points) [append*]
   Write a Scheme procedure, append*, whose type is:

      (forall (T)
        (-> ((list-of T) ...) (list-of T)))

   that takes 0 or more argument lists and returns a list of all these
   argument lists appended together in the same order.  In your
   solution's code you may only use Scheme's append procedure with two
   (2) arguments.  You may use the append-all procedure if you wish as
   well.  The following are examples.

    (append* )
      ==> ()
    (append* '(3 7 10) '(20 25 30) '(5 4 3))
      ==> (3 7 10 20 25 30 5 4 3)
    (append* '(20 25 30) '(5 4 3))
      ==> (20 25 30 5 4 3)
    (append* '(l i k) '(e) '(t h i s) '() '() '(o k) '())
      ==> (l i k e t h i s o k)

   After doing your own testing you must test your code using:

	(test-hw3 "appendstar")

   Print a transcript of your testing, and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code.

5. (20 points) [append-map]
   Write a procedure, 

    append-map : (forall (S T)
                   (-> ((-> (S) (list-of T)) (list-of S))
                       (list-of T))))

   such that (append-map f (list e1 e2 ...)) is the list that results
   from appending the results of (f e1), (f e2), and so on.
   That is, append-map should satisfy the equation:

     (append-map f (list e1 e2 ...)) = (append* (f e1) (f e2) ...).

   The following are examples.

    (append-map (lambda (x) (list x))
                '(copies the argument list))
      ==> (copies the argument list)
    (append-map (lambda (x) (list x))
                '())
      ==> ()
    (append-map (lambda (n) (if (= n 3) '() (list n)))
                '(3 4 2 3 7))
      ==> (4 2 7)
    (append-map (lambda (x) (list x 7 (+ x 1)))
                '(5 4 1 2 100 50 10 3))
      ==> (5 7 6 4 7 5 1 7 2 2 7 3 100 7 101 50 7 51 10 7 11 3 7 4)
    (append-map (lambda (x) (list (list x 7 (+ x 1))))
                '(5 4 1))
      ==> ((5 7 6) (4 7 5) (1 7 2))
    (append-map (lambda (x) (if (= 5 x) '() (list (list x 7 (+ x 1)))))
                '(5 4 1))
      ==> ((4 7 5) (1 7 2))

   After doing your own testing, you must test your code using:

	(test-hw3 "append-map")

   Print a transcript of your testing, and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code.

6. (35 points) [set-ops]
   In this problem you will write procedures to operate on the ADT of sets.
   We will implement sets as lists, as noted in the `defrep'
   declaration below.  (The defrep declaration is just a way to tell
   the type system how sets are represented.)
   However, we will use lists *without* duplicate elements.
   Duplicates are defined by Scheme's `equal?' operation; that is, we
   consider x to be a duplicate of y if (equal? x y) is true.
   To get you started, here are some operations on sets with
   that representation.  (Note that `set' uses `set-add', which you are
   to write; so it won't work until you define `set-add'.)

    (defrep (forall (T) (set-of T)) (forall (T) (list-of T)))
    
    (deftype the-empty-set (forall (T) (set-of T)))
    (define the-empty-set '())
    
    (deftype set-empty? (forall (T) (-> ((set-of T)) boolean)))
    (define set-empty?
      (lambda (s)
        ;; ENSURES: result is true just when s is empty
        (null? s)))
    
    (deftype set-size (forall (T) (-> ((set-of T)) number)))
    (define set-size
      (lambda (s)
        ;; ENSURES: result is the number of elements in s
        (length s)))
    
    (deftype set (forall (T) (-> (T ...) (set-of T))))
    (define set
      (lambda args
        ;; ENSURES: result is a set containing just the elements in args
        (if (null? args)
            the-empty-set
            (set-add (car args) (apply set (cdr args))))))
    
    (deftype set-member? (forall (T) (-> (T (set-of T)) boolean)))
    (define set-member?
      (lambda (e S)
        ;; ENSURES: result is true just when e is equal? to some element of S
        (and (not (set-empty? S))
             (or (equal? e (car S))
                 (set-member? e (cdr S))))))
    
    (deftype set-one-elem (forall (T) (-> ((set-of T)) T)))
    (define set-one-elem
      (lambda (s)
        ;; REQUIRES: s is not empty
        ;; ENSURES: result is a member of s
        (car s)))
    
    (deftype set-rest (forall (T) (-> ((set-of T)) (set-of T))))
    (define set-rest 
      (lambda (s)
        ;; REQUIRES: s is not empty
        ;; ENSURES: result is the largest subset of s that does not contain
        ;;          the element (set-one-elem s)
        (cdr s)))
    
    (deftype set-subset? (forall (T) (-> ((set-of T) (set-of T)) boolean)))
    (define set-subset?
      (lambda (S1 S2)
        ;; ENSURES: result is true just when S1 is a subset of S2,
        ;;          or equal to S2.  Membership is determined by equal?
        (or (set-empty? S1)
            (and (set-member? (set-one-elem S1) S2)
                 (set-subset? (set-rest S1) S2)))))
    
    (deftype set-equal? (forall (T) (-> ((set-of T) (set-of T)) boolean)))
    (define set-equal?
      (lambda (S1 S2)
        ;; ENSURES: result is true just when S1 and S2 contain
        ;;          the same elements. Membership is determined by equal?
        (and (set-subset? S1 S2)
             (set-subset? S2 S1))))

  Your task is to write a procedure for each of the following
  operations on sets (whose deftypes are given below).

    (deftype set-add
      (forall (T) (-> (T (set-of T)) (set-of T))))
    (deftype set-remove
      (forall (T) (-> (T (set-of T)) (set-of T))))
    (deftype set-union
      (forall (T) (-> ((set-of T) (set-of T)) (set-of T))))
    (deftype set-minus
      (forall (T) (-> ((set-of T) (set-of T)) (set-of T))))
    (deftype set-intersect
      (forall (T) (-> ((set-of T) (set-of T)) (set-of T))))
    (deftype set-union-list
      (forall (T) (-> ((list-of (set-of T))) (set-of T))))
    (deftype set-union*
      (forall (T) (-> ((set-of T) ...) (set-of T))))

   The operation `set-add' inserts an item into a set,
   `set-remove' takes an item out of a set (or returns its set
   argument unchanged if the element argument was not in the set argument),
   `set-union' returns the union of its two arguments as a set
   (i.e., without duplicates),
   `set-minus' returns the set of all elements such that every element
   of the result is an element of the first set argument, but no
   element of the result is an element of the second set argument,
   `set-intersect' returns the set of elements that are elements of both sets,
   `set-union-list' gives the union of all the sets in its argument list,
   and `set-union*' is the variable argument version of set-union-list.
   Note that the expression 

      (set 2 3 1)

   evaluates to the set containing 1, 2 and 3.  The code for
   procedure set is given above.  The following are examples
   illustrating these operations.

   (set-equal? (set-add 1 (set 2 3)) (set 1 2 3)) ==> #t
   (set-equal? (set-add 1 (set 2 3 1)) (set 1 2 3)) ==> #t

   (set-equal? (set-remove 1 (set 2 3 1)) (set 3 2)) ==> #t
   (set-equal? (set-remove 1 (set 2 3 4 8)) (set 3 2 4 8)) ==> #t

   (set-equal? (set-union (set 'a 'b) (set 'c 'd))
               (set 'a 'b 'c 'd)) ==> #t
   (set-equal? (set-union (set 'a 'b 'c) (set 'c 'd))
               (set 'a 'b 'c 'd)) ==> #t

   (set-equal? (set-minus (set 'a 'b) (set 'c 'd))
               (set 'a 'b)) ==> #t
   (set-equal? (set-minus (set 'a 'b 'c) (set 'c 'a 'd))
               (set 'b)) ==> #t

   (set-equal? (set-intersect (set 'a 'b) (set 'c 'd))
               the-empty-set) ==> #t 
   (set-equal? (set-intersect (set 'a 'b 'c) (set 'c 'a 'd))
               (set 'a 'c)) ==> #t 

   (set-equal? (set-union-list (list (set 'a 'b) (set 'c 'd)))
               (set 'a 'b 'c 'd)) ==> #t
   (set-equal? (set-union-list
                   (list (set 'a) (set 'b 'c) (set 'c 'a)))
               (set 'a 'b 'c)) ==> #t

   (set-equal? (set-union* (set 'a 'b) (set 'c 'd) (set))
               (set 'a 'b 'c 'd)) ==> #t
   (set-equal? (set-union* (set 'a) (set 'b 'c) (set 'c 'a))
               (set 'a 'b 'c)) ==> #t
   (set-equal? (set-union* ) (set )) ==> #t

   Make a file `set-ops.scm' containing the code we have provided
   above, and your own procedure definitions.  You should start by
   copying the file $PUB/homework/hw3/set-ops.scm to your directory:

	cp $PUB/homework/hw3/set-ops.scm .

   In your solution you may not modify any of the provided procedures.

   Hint: these are really just a bunch of list recursion problems.

   Hint: To save yourself time, you should write and test each of your
   procedures one by one.  It really will save time to test your code
   yourself; just trying to run our test cases will be frustrating,
   because you won't have much idea of what went wrong.

   After doing your own testing, you must test your code using:

	(test-hw3 "set-ops")

   Print a transcript of your testing, and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code.

7. (suggested practice) [merge]
   Do exercise 1.16 on p. 26 in the text, part 5 [merge].  You should
   assume that the argument lists are sorted in ascending order.  The
   type of merge is given by the following.

     (deftype merge
        (-> ((list-of number) (list-of number)) (list-of number)))

   After doing your own testing, you must test your code using:

	(test-hw3 "merge")

   Print a transcript of your testing, and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code.

8. (suggested practice) [sort]
   Do the sort parts of exercise 1.17 on p. 27 of the text.  You'll
   have to test this yourself.

9. (15 points; extra credit) [remove using append-map]
   Write remove (see pages 18-19 of the text) using append-map.  Hand
   in a printout of your code and testing.

10. (10 points; extra credit) [remove-first using append-map]
   Can you write remove-first easily using append-map?  If so, do it;
   if not, explain why you can't.


THE LITTLE SCHEMER, CHAPTER 4

The following problems involve recursion over the non-negative integers.

11. (20 points) [insert-after]
   Write a procedure

        insert-after : (forall (T) (-> (number T (list-of T)) (list-of T)))

   such that (insert-after n new ls) returns a list that is just like ls,
   except that it has new in position n+1.  Positions are zero-based.
   If ls has a length strictly less than n, then ls is returned.  You
   may assume that n is a non-negative integer.  For example:

     (insert-after 0 'x '()) ==> ()
     (insert-after 1 'x '()) ==> ()
     (insert-after 0 'x '(z e r o b a s e d)) ==> (z x e r o b a s e d)
     (insert-after 1 'x '(z e r o b a s e d)) ==> (z e x r o b a s e d)
     (insert-after 2 'y '(z e r o b a s e d)) ==> (z e r y o b a s e d)
     (insert-after 3 '- '(z e r o b a s e d)) ==> (z e r o - b a s e d)
     (insert-after 2 '- '(e r o b a s e d)) ==> (e r o - b a s e d)
     (insert-after 1 '- '(r o b a s e d)) ==> (r o - b a s e d)
     (insert-after 0 '- '(o b a s e d)) ==> (o - b a s e d)

   After doing your own testing, you must test your code using:

	(test-hw3 "insert-after")

   Print a transcript of your testing, and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code.

12. (15 points) [iterate]
   Write a procedure,

      iterate : (forall (T) (-> ((-> (T) T) number)
                                (-> (T) T)))

   such that (iterate f 0) is the identity function,
   so that, for all x, 

       ((iterate f 0) x) = x

   and so that for integers n > 0, (iterate f n) is that function that
   applies f n times to its argument.  That is,
   for all n > 0, and for all x,

       ((iterate f n) x) = (f ((iterate f (- n 1)) x)).

   For example:

     ((iterate (lambda (n) (+ n 1)) 4) 100) ==> 104
     ((iterate (lambda (n) (+ n 1)) 3) 100) ==> 103
     ((iterate (lambda (n) (+ n 1)) 3) 5) ==> 8
     ((iterate (lambda (n) (+ n 1)) 1) 5) ==> 6
     ((iterate (lambda (n) (+ n 1)) 0) 5) ==> 5
     ((iterate (lambda (n) (* n n)) 3) 5) ==> 390625
     ((iterate (lambda (n) (* n n)) 2) 5) ==> 625
     ((iterate (lambda (n) (* n n)) 1) 5) ==> 25
     ((iterate (lambda (ls) (cons 1 ls)) 8) '(2 3))
         ==> (1 1 1 1 1 1 1 1 2 3)
     ((iterate (lambda (ls) (cdr ls)) 7) '(0 1 2 3 4 5 6 7 8 9))
         ==> (7 8 9)
     ((iterate (lambda (ls) (cons (+ 1 (car ls)) ls)) 6) '(0))
         ==> (6 5 4 3 2 1 0)
     ((iterate (iterate (lambda (n) (+ n 1)) 5) 6) 1)
         ==> 31
     ((iterate (iterate (lambda (n) (* n n)) 2) 3) 2)
         ==> 18446744073709551616

   After doing your own testing, you must test your code using:

	(test-hw3 "iterate")

   Print a transcript of your testing, and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code.

13. (25 points) [board]
   Write a procedure, board, whose type is given by the following.
     
      (deftype board (-> (number) (list-of (list-of symbol))))

   When board is called with a non-negative integer, size, it returns
   a list containing size lists, each of which is of length size.
   These inner lists each contain only the symbols b
   (representing black squares) and w (representing white squares) so
   that the alternations across all the lists created form a
   chess-board pattern.  The result always has the
   symbol b as the first element of the first sublist, if any.
   For example: 

    (board 0) ==> ()
    (board 1) ==> ((b))
    (board 2) ==> ((b w)
                   (w b))
    (board 3) ==> ((b w b)
                   (w b w)
                   (b w b))
    (board 4) ==> ((b w b w)
                   (w b w b)
                   (b w b w)
                   (w b w b))
    (board 8) ==> ((b w b w b w b w)
                   (w b w b w b w b)
                   (b w b w b w b w)
                   (w b w b w b w b)
                   (b w b w b w b w)
                   (w b w b w b w b)
                   (b w b w b w b w)
                   (w b w b w b w b))

   Hint: this problem involves a nested numeric recursion (reflected
   in the nested lists of its output).  For that reason you should use
   several helping procedures, and give yourself examples for each of
   these helping procedures.  Test your helpers first, before testing
   the whole solution.

   After doing your own testing, you must test your code using:

	(test-hw3 "board")

   Print a transcript of your testing, and hand that in with your printout
   of the code.  Be sure your name appears in a comment in your code.


ESSENTIALS OF PROGRAMMING LANGUAGES: Section 1.1

The following problems are about syntactic derivations from grammars.

14. (5 points) [syntactic derivation]
   Write a syntactic derivation that proves (3 . (4 . (2 . ())))
   is a list of numbers, using the first grammar on page 4 in the text
   (i.e., in Essentials of Programming Languages, second edition).

15. (5 points)   [Kleene * and +]
   Do exercise 1.2 on p. 7 in the text.

16. (suggested practice)  [syntactic derivation]
   Do exercise 1.3 on p. 7 in the text.