<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
          Com S 342 --- Principles of Programming Languages

   HOMEWORK 3: RECURSION OVER FLAT LISTS AND NUMBERS, AND INDUCTION
                  (File $Date: 2006/09/13 21:26:04 $)

Due: problems 1-3 at the beginning of class on Tues., Sept. 19, 2006.
     problems 8-12 at the beginning of class on Thurs., Sept. 21, 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.  Test using your own tests and
also use our tests, as described in homework 1.  For coding
problems hand in:

  - a printout of the code, and
  - if our tests reveals any errors with your code for that problem,
    then include a transcript showing a run of our tests.

That is, you only have to hand in output of your testing if it reveals
problems in your code (that you have not fixed).  We expect you to run
our tests for each problem, but since the output in the case where the
tests all pass is not very interesting, we will trust you to have done
this.  However,  you must hand in a transcript of your testing if your
code does *not* pass our tests perfectly, as this will alert us to the
problem and will help us assign partial credit.  If we find that your
code is not correct and the problem would have been revealed by our
testing, but you did not hand in test results showing
these probems, then you will receive 0 points for that problem.
You may also hand in a transcript that includes our tests if you wish.

Tests are in the directory $PUB/homework/hw3 for test data for each
coding problem.  (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 how to test at home.)

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. (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 from homework
   2 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")

2. (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")

3. (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")

4. (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")

5. (suggested practice) [sort]
   Do the sort parts of exercise 1.17 on p. 27 of the text.  You'll
   have to test this yourself.

6. (15 points; extra credit) [remove using append-map]
   Write remove (see pages 18-19 of the text) using append-map.

7. (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.

8. (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")

9. (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")

10. (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")


ESSENTIALS OF PROGRAMMING LANGUAGES: Section 1.1

The following problems are about syntactic derivations from grammars.

11. (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).

12. (5 points)   [Kleene * and +]
   Do exercise 1.2 on p. 7 in the text.

13. (suggested practice)  [syntactic derivation]
   Do exercise 1.3 on p. 7 in the text.