Com S 342 --- Principles of Programming Languages

                 HOMEWORK 2: INDUCTION and RECURSION
                  (File $Date: 2006/11/13 22:08:55 $)

Due: problems 1-7,9 on Tuesday, September 12, 2006.

In this homework, you will learn about higher-order procedures, syntax
abstraction, and a bit more about recursion.

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 problems, 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/hw2 for test data for each
coding problem, as described in homework 1.  (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!)


STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, SECTION 1.3
(http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3)

1. (5 points) [average3-c]
   Define a curried version of the following procedure,
   call it average3-c, and also write a deftype for it.

   (deftype average3 (-> (number number number) number))
   (define average3
     (lambda (a b c)
       (/ (+ a b c) 3)))

   Test your code by executing the following.

        (test-hw2 "average3-c")

   You can check the syntax and typing by using the "Check Syntax" and
   "Type Check" buttons in DrScheme.

   Remember, for this and all of the following coding problems, you
   must hand in both a printout of your code file.  Be sure to include
   statements at the top of your code file identifying yourself, as
   described in previous homeworks.

2. (5 points) [average-9-42]
   Using your solution from problem 1, define a procedure,

      (deftype average-9-42 (-> (number) number))

   that takes a number, c, and returns the average
   of 9, 42, and c. For example,

     (average-9-42 0) ==> 17
     (average-9-42 3) ==> 18

   Test your code by executing the following.

        (test-hw2 "average-9-42")

   Important: your solution must use average3-c from the previous
   problem.  You will get zero points if your solution's code does not
   depend on average3-c.

STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, SECTIONS 1.1.6
(http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html#%_sec_1.1.6)
REVISED^5 REPORT ON THE ALGORITHMIC LANGUAGE SCHEME, section 4.2
CODE EXAMPLES PAGE
(http://www.cs.iastate.edu/~cs342/lib342/code-examples.html#SyntacticAbstraction)

3. (10 points) [occurs-twice? using "and" and "or"]
   Write the procedure occurs-twice? from homework 1, problem 5 without
   using #t and #f, but using "and" and "or".

   Test your code by executing the following:

        (test-hw2 "occurs-twice")

4. (5 points) [example of syntactic sugar]
   Give an example of a statement or expression in Java or C++ that is a
   syntactic sugar.  State what language you are giving an example
   from.  Explain by a simple example how to desugar this statement or
   expression.

THE LITTLE SCHEMER, Chapters 2-5
FOLLOWING THE GRAMMAR
(handout at http://www.cs.iastate.edu/~cs342/docs/follow-grammar.pdf)

5. (20 points) [Following the grammar for flat lists]
   For each of the following, say whether the procedure has a correct
   outline that follows the grammar for flat lists, and if not,
   briefly explain what the problem is with that procedure
   (why it does not follow the outline).

   (Note: you don't have to judge whether these are correct or not,
   and you aren't expected to run them.)

     ;; (a) 
     (define talents-of
       (lambda (people)
          (cond
            ((null? people) '())
            (else (cons (talent (car people))
                        (talents-of (cdr people)))))))

     ;; (b)
     (define talents-of
       (lambda (people)
          (cons (talent (car people))
                (talents-of (cdr people)))))

     ;; (c)
     (define talents-of
       (lambda (people)
          (cond
            ((null? people) '())
            (else (talent (car people))
                  (talents-of (cdr people))))))

     ;; (d)
     (define talents-of
       (lambda (people)
          (if (null? people)
              (list)
              (cons (talent (car people))
                    (talents-of (cdr people))))))

     ;; (e)
     (define talents-of
       (lambda (people)
          (if (null? people)
              (list)
              (begin (cdr people)
                     (define first-talent (car people))
                     (cons (talent first-talent)
                           (talents-of people))))))

     ;; (f)
     (define talents-of
       (lambda (people)
          (if (null? people)
              people
              (cons (talent (car people))
                    (talents-of (cdr people))))))
     ;; (g)
     (define talents-of
       (lambda (people)
          (cond
            ((null? people) '())
            (else (talents-of (talent (car people))
                              (cdr people))))))

6. (20 points) [Following the grammar for flat lists 2]
   For each of the following, say whether the procedure has a correct
   outline that follows the grammar for flat lists, and if not,
   briefly explain what the problem is with that procedure
   (why it does not follow the outline).

   (Note: you don't have to judge whether these are correct or not,
   and you aren't expected to run them.)

     ;; (a) 
     (define rhymes-with
       (lambda (sought words)
          (if (null? words)
              '()
              (append
               (if (not (rhyme? sought (car words)))
                   '()
                   (list (car words)))
               (rhymes-with sought (cdr words))))))

     ;; (b)
     (define rhymes-with
       (lambda (sought words)
          (if (null? words)
              (list)
            (if (not (rhyme? sought (car words)))
                (rhymes-with sought (cdr words))
                (cons (car words)
                      (rhymes-with sought (cdr words)))))))

     ;; (c)
     (define rhymes-with
       (lambda (sought words)
          (cond
            ((null? words) '())
            (else (cond
                    ((not (rhyme? sought (car words)))
                     (rhymes-with sought (cdr words)))
                    (else (cons (car words)
                                (rhymes-with sought (cdr words)))))))))

     ;; (d)
     (define rhymes-with
       (lambda (sought words)
          (cond
            ((null? words) '())
            (else (cdr words)
                  (cond
                    ((not (rhyme? sought (car words)))
                     (rhymes-with sought words))
                    (else (cons (car words)
                                (rhymes-with sought words))))))))

     ;; (e)
     (define rhymes-with
       (lambda (sought words)
          (cond
            ((rhyme? sought (car words))
             (cons (car words)
                   (rhymes-with sought (cdr words))))
            (else 
             (rhymes-with sought (cdr words))))))

     ;; (f)
     (define rhymes-with
       (lambda (sought words)
          (cond
            ((null? words) words)
            (else (cond
                    ((not (rhyme? sought (car words)))
                     (rhymes-with sought (cdr words)))
                    (else (cons (car words)
                                (rhymes-with sought (cdr words)))))))))

     ;; (g)
     (define rhymes-with
       (lambda (sought words)
          (cond
            ((null? words) '())
            ((rhyme? sought (car words))
             (cons (car words)
                   (rhymes-with (cdr words))))
            (else
             (rhymes-with cdr words)))))

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

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

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

9. (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-hw2 "append-all")