Problem Set 7, CS 257

Beware of mathematicians and all those who make empty prophecies. The danger already exists that the mathematicians have made covenant with the devil to darken the spirit and to confine man in the bonds of hell.

-St. Augustine

1. Write tail-recursive solutions for each of the following problems.
   1. Define sumlist which, given a list of numbers, returns the sum of the numbers in the list.

      Examples:

      (sumlist '())                     ; 0
      (sumlist '(1 2 3 4 5 6 7 8 9))    ; 45
      

   2. Define using recursion the higher order function map-reverse, which could be defined with

      (define (map-reverse f lis)
        (reverse (map f lis)))
      

      Examples:

      (map-reverse car '((a b) (c d) (e f) (g h))) ; (g e c a)
      (map-reverse - '(1 -2 3 -4 5))               ; (-5 4 -3 2 -1)
      

2. Consider

   (define (foo x y)
     (cond ((null? x) y)
           ((pair? x) (foo (car x)
                           (foo (cdr x) y)))
           (else (cons x y))))
   

   Draw the call graph of (foo '(((a) b) c d) '(e f)). Use the return arrows to indicate all tail recursion. Note that foo calls itself twice: once tail-recursively and the other time non-tail-recursively.

3. Use delegation and prototypes to define a hierarchy of animals, including Fido and Fifi (male and female dogs); Dumbo and his mother Gertrude (elephants, but Dumbo is atypical in that he's small and flies); Kermit the frog; Mrs-Piggy, a pig; Tony the toad; Siddhartha the Snake; Fiona the chimpanzee; and Barak the human.

   You should include a generic animal object, amphibian object, mamal object, reptile object, primate object, and an object for each particular species. All the final animal objects should respond to each of the following messages:

   has-thumbs?, biped?, slimy?, hairy?, eye-count, enormous?, sound, sex, flies?, lays-eggs?.

   Put all methods as high up the hierarchy as possible, overriding them as necessary.

   Examples:

   (send dumbo 'flies?)                   ; #t
   (send barak 'flies?)                   ; #f
   (send barak 'eye-count)                ; 2
   (send kermit 'has-thumbs?)             ; #f
   (send fiona 'lays-eggs?)               ; #f
   (send kermit 'lays-eggs?)              ; #t
   (send fifi 'enormous?)                 ; #f
   (send gertrude 'enormous?)             ; #t
   (send mrs-piggy 'sex)                  ; female
   

4. Convert the following code into Scheme with tail-recursive procedure calls instead of assignments and gotos.

   foo(x)
   {
     list y = empty_list;
   
    l1:
     if (x == empty_list) return y;
   
     y = cons( car(x), y);
     x = cdr(x);
     goto L1;
   }