Com S 342 --- Principles of Programming Languages

                 HOMEWORK 2: INDUCTION and RECURSION
                  (File $Date: 2006/01/24 04:54:12 $)

Due: problems 1-6 on Tuesday, January 31, 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.
For code hand in *both* your printout of the code
and a transcript of testing.  See the directory $PUB/homework/hw2
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 how to test at home.)

*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!)


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 "Type Check"
   button in DrScheme.

   Remember, for this and all of the following coding problems, you
   must hand in both a printout of your code file and a transcript showing
   testing using our test data.  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".

   Hand in a printout of your code and a transcript of testing that
   includes our test cases, which you can execute using:

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