Com S 342 --- Principles of Programming Languages

   HOMEWORK 3: RECURSION OVER FLAT LISTS AND NUMBERS, AND INDUCTION
                  (File $Date: 2006/02/08 17:58:08 $)

Due: problems 1, 3-6 at the beginning of class on Tues., Feb. 7, 2006;
     problems 11, 12-15 at the beginning of class on Thurs., Feb. 9, 2006.

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/lib342/code-examples.html#Little2
    http://www.cs.iastate.edu/~cs342/lib342/code-examples.html#Little3
    http://www.cs.iastate.edu/~cs342/lib342/code-examples.html#SchemeProcedures
FOLLOWING THE GRAMMAR HANDOUT
    http://www.cs.iastate.edu/~cs342/docs/follow-grammar.pdf

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.  In our dialect of Scheme, Typedscm, ADTs are stored in
   modules, which export only what is listed in their "provides"
   clause.  See the documentation on Typedscm 

     http://www.cs.iastate.edu/~leavens/typedscm/typedscm.html

   in section 3.3, which has an explanation of modules, provide,
   require, and defrep. 

   In this problem, we give you some of the code for implementing sets
   as lists, and ask you to fill in the remaining code.  Our code is
   found in $PUB/homework/hw3/set-ops.scm, which is also available in
   the homework zip file for the course under
   collects/homework/hw3/set-ops.scm.  You need to read the code for
   the operations we provide to understand it.

   As noted in the code's `defrep' declaration

      (defrep (forall (T) (set-of T) (list-of T)))

   we represent sets (of some type T) by lists (of the same type).

   Our representation assumes that lists are represented
   *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.

   There is one additional complication in the code that we have
   provided for you.  That is, it won't type check or pass Scheme
   until you write something for your code.  In particular, our code
   for the procedure named `set' uses `set-add', which you are
   to write; so `set' won't work until you define `set-add'.

   Your task is to write a procedure for each of the following
   operations on sets (given with their types below).

    set-add : (forall (T) (-> (T (set-of T)) (set-of T)))
    set-remove : (forall (T) (-> (T (set-of T)) (set-of T)))
    set-union : (forall (T) (-> ((set-of T) (set-of T)) (set-of T)))
    set-minus : (forall (T) (-> ((set-of T) (set-of T)) (set-of T)))
    set-intersect : (forall (T) (-> ((set-of T) (set-of T)) (set-of T)))
    set-union-list : (forall (T) (-> ((list-of (set-of T))) (set-of T)))
    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.

   The following are examples illustrating these operations.
   In these examples, note that the expression 

      (set 2 3 1)

   evaluates to the set containing 1, 2 and 3.

   (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

   To start solving this problem, copy the file
   $PUB/homework/hw3/set-ops.scm to your directory, in Unix do:

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

   Note that your file must be called "set-ops.scm".

   In any case you want to start with the `set-ops.scm' code we have
   provided for you.  Then add your own procedure definitions at the
   appropriate places (after each corresponding deftype) as indicated
   in the file we provide.
   
   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.

   Hint: to incrmentally develop the procedures, start with by
   implementing set-add.  It may be helpful to either "stub out" the
   other procedures, or to change the provide at the beginning of the
   module so that it doesn't list all of the names, as in:

    (provide the-empty-set set-empty? set-size set set-member?
             set-one-elem set-rest set-subset? set-equal?
             set-add
             ;set-remove
             ;set-union
             ;set-minus
             ;set-intersect
             ;set-union-list
             ;set-union*
            )

   This works becuase commenting out a name from the provide list
   makes Scheme not demand a definition for it in the body of the
   module.  The provide list allows you to only implement set-add (in
   addition to the ones we have provided for you).  This is a good
   choice for testing at first. Note that when you implement the next
   one, say set-remove, you have to uncomment the corresponding name
   (set-remove) in the provide list, otherwise it won't be available
   when you try to test it.

   Hint: since modules are cached when you use (require ...), you
   need to press Run again, or restart DrScheme, if you make changes
   to the module that aren't reflected in your testing.  Save the file
   first!

   Important: To test your code, since set-ops is a module, you can't
   use the Scheme, "load" procedure, and the DrScheme "Run" button
   doesn't do the right thing either.  So you have to save your file,
   and then (press "Run" in DrScheme and then) use

     (require "set-ops.scm")

   in the interactions window to both load and import into the
   interactions window the exported definitions of the set-ops
   module.

   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 less than or equal to 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 1 'x '(y)) ==> (y)
     (insert-after 0 'x '(y)) ==> (y 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.
   In the following examples, we have formatted the output to show the
   result more clearly, but your output will not look the same (unless
   you use pretty-print); it is sufficient to just get the outputs
   that are equal? to those shown.

    (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.