Problem Set 7 Answers, CS 257

Due 9pm Tue December 2, 1997
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

      (define (sublist lis)
  (aux lis 0))

(define (aux lis subtotal)
  (if (null? lis)
      subtotal
      (aux (cdr lis)
      (+ (car lis) subtotal))))

    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)

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

(define (aux f lis end-o-result)
  (if (null? lis)
      end-o-result
      (aux f
	   (cdr lis)
	   (cons (f (car lis))
		 end-o-result))))

  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

    ;;; Use delegation and prototypes to define a hierarchy of animals

;;; Utilities used

(define (send obj selector . args)
  (apply obj obj selector args))

(define (delegate obj delegee selector . args)
  (apply delegee obj selector args))

(define (make-instance-with-sex delagee sex)
  (lambda (self selector . args)
    (cond ((equal? selector 'sex) sex)
	  (else (apply delegate self delagee selector args)))))

;;; All the leaf animal objects should respond to each of the
;;; following messages:
;;;
;;; has-thumbs?
;;; biped?
;;; slimy?
;;; hairy?
;;; eye-count
;;; enormous?
;;; sound
;;; sex
;;; flies?
;;; lays-eggs?

;;; You should include a generic
;;;
;;; animal object, 
;;; amphibian object, 
;;; mamal object, 
;;; reptile object, 
;;; primate object, and
;;; an object for each particular species.



;;; upper levels of evolutionary hierarchy

(define animal
  (lambda (self selector . args)
    (cond ((equal? selector 'has-thumbs?) #f)
	  ((equal? selector 'biped?) #f)
	  ((equal? selector 'slimy?) #t)
	  ((equal? selector 'hairy?) #f)
	  ((equal? selector 'eye-count) 2)
	  ((equal? selector 'enormous?) #f)
	  ((equal? selector 'flies?) #f)
	  ((equal? selector 'lays-eggs?) #t)
	  (else (error "unhandled message ~A to ~A" selector self)))))

(define amphibian
  (lambda (self selector . args)
    (cond (else (apply delegate self animal selector args)))))

(define reptile
  (lambda (self selector . args)
    (cond ((equal? selector 'slimy?) #f)
	  (else (apply delegate self animal selector args)))))

(define mammal
  (lambda (self selector . args)
    (cond ((equal? selector 'hairy?) #t)
	  ((equal? selector 'slimy?) #f)
	  ((equal? selector 'lays-eggs?) #f)
	  (else (apply delegate self reptile selector args)))))

(define primate
  (lambda (self selector . args)
    (cond ((equal? selector 'has-thumbs?) #t)
	  (else (apply delegate self mammal selector args)))))

;;; individual species (for our purposes)

(define dog
  (lambda (self selector . args)
    (cond ((equal? selector 'sound) 'woof)
	  (else (apply delegate self mammal selector args)))))

(define elephant
  (lambda (self selector . args)
    (cond ((equal? selector 'sound) 'trumpet)
	  ((equal? selector enormous?) #t)
	  (else (apply delegate self mammal selector args)))))

(define frog
  (lambda (self selector . args)
    (cond ((equal? selector 'sound) 'ribbit)
	  (else (apply delegate self amphibian selector args)))))

(define toad
  (lambda (self selector . args)
    (cond ((equal? selector 'sound) 'croak)
	  (else (apply delegate self amphibian selector args)))))

(define pig
  (lambda (self selector . args)
    (cond ((equal? selector 'sound) 'oink)
	  (else (apply delegate self mammal selector args)))))

(define snake
  (lambda (self selector . args)
    (cond ((equal? selector 'sound) 'hiss)
	  (else (apply delegate self reptile selector args)))))

(define chimp
  (lambda (self selector . args)
    (cond ((equal? selector 'sound) 'ook-ook)
	  (else (apply delegate self primate selector args)))))

(define human
  (lambda (self selector . args)
    (cond ((equal? selector 'bipid?) #t)
	  ((equal? selector 'sound) 'yak-yak-yak) 
	  (else (apply delegate self primate selector args)))))

;;; Instances - particular animals - be sure to handle SEX

(define fido
  (make-instance-with-sex dog 'male))

(define fifi
  (make-instance-with-sex dog 'female))

(define dumbo
  (lambda (self selector . args)
    (cond ((equal? selector 'flies?) #t)
	  ((equal? selector 'sex) 'male)
	  ((equal? selector 'enormous?) #f)
	  (else (apply delegate self elephant selector args)))))

(define gertrude
  (make-instance-with-sex elephant 'female))

(define kermit
  (make-instance-with-sex frog 'male))

(define mrs-piggy
  (make-instance-with-sex pig 'female))

(define tony
  (make-instance-with-sex toad 'male))

(define siddhartha
  (make-instance-with-sex snake 'male))

(define fiona
  (make-instance-with-sex chimp 'female))

(define barak
  (lambda (self selector . args)
    (cond ((equal? selector 'slimy?) 'very)
	  ((equal? selector 'sex) 'male)
	  (else (apply delegate self human selector args)))))

;;; Testing functions

;;; These are all the low-level instances:

(define everyone (list fido fifi dumbo gertrude kermit
		       mrs-piggy tony siddhartha fiona barak))

(define (all-props obj)
  (list 'has-thumbs? (send obj 'has-thumbs?)
	'biped?      (send obj 'biped?)
	'slimy?      (send obj 'slimy?)
	'hairy?      (send obj 'hairy?)
	'eye-count   (send obj 'eye-count)
	'enormous?   (send obj 'enormous?)
	'sound       (send obj 'sound)
	'sex         (send obj 'sex)
	'flies?      (send obj 'flies?)
	'lays-eggs?  (send obj 'lays-eggs?)))

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

    (define (foo x)
  (l1 x '()))

(define (l1 x y)
  (if (null? x)
      y
      (l1 (cdr x) (cons (car x) y))))
Turn in this problem set by running the program ~barak/bin/submit file.scm

The file should be legal scheme code, with comments indicating which fragment of code corresponds to which problem.

You are allowed to make corrections, because the last submit command supersedes all previous submissions.

Turn in the call graph for problem 2 by either (1) handing it in before class, (2) slipping it under the door to FEC 355C, or (3) submitting a postscript file which we can print.

Barak Pearlmutter <bap@cs.unm.edu>