Advanced Methods in Programming Languages (201-2-4411-01)
Exam Solution - Spring 2001 - Michael Elhadad

Exam Solution


(define (compose-list$ fs k)
  (if (null? fs)
    (k (lambda (x k1) (k1 x)))
    (compose-list$ (cdr fs)
                   (lambda (f-cdr)
                     (k (lambda (x k1)
                          (f-cdr x (lambda (cdrfx)
                                     ((car fs) cdrfx k1)))))))))


(define stream-car car)
(define stream-cdr (lambda (s) (force (cdr s))))
(define the-null-stream '())
(define stream-null? null?)
(define (print-n n s)
  (if (= n 0)
    (begin (print (stream-car s))
           (print-n (- n 1) (stream-cdr s)))))
(define (integers n)
  (cons-stream n (integers (+ n 1))))

(define (stream-map f s)
  (if (stream-null? s)
    (cons-stream (f (stream-car s)) (stream-map f (stream-cdr s)))))

(define (interleave s1 s2)
  (if (stream-null? s1)
    (cons-stream (stream-car s1)
                 (interleave s2 (stream-cdr s1)))))

(define (star r)
  (letrec ((star2 (lambda (rr)
                    (cons-stream (stream-car rr)
                                 (interleave (stream-cdr rr)
                                             (star2 (pairs r rr)))))))
    (cons-stream '() (star2 (stream-map list r)))))

(define (pairs s t)
  (cons-stream (cons (stream-car s) (stream-car t))
               (interleave (stream-map
                            (lambda (x)
                              (cons (stream-car s)  x)) (stream-cdr t))
                           (pairs (stream-cdr s) t))))


;; PART 1: Procedural Representation
;; The tricky part is the delete operation
;; The representation is:
;; A bag is a function of one argument that returns the number of
;; occurences of the argument in the bag.

;; The other delicate point was to handle 2 accessors (is-empty? and
;; is-in?).  You can use message passing or use a simple encoding of
;; empty-bag with a singleton;  I show here the singleton.

(define the-empty-bag
  (lambda (item) 0))

(define (is-empty? bag)
  (eq? bag the-empty-bag))

(define (make-empty-bag)
  the-empty-bag)          ;; NOT lambda so that eq? works.

(define (is-in? element a-bag)
  (> (a-bag element) 0))

(define (insert element a-bag)
  (lambda (item)
    (if (eq? item element)
      (+ 1 (a-bag item))
      (a-bag item))))

(define (delete element a-bag)
  ;; The computation can be "compiled" at construction time.
  (let* ((n (a-bag element))
         (i (if (= n 0) 0 (- n 1))))
    (lambda (item)
      (if (eq? item element)
        (a-bag item)))))

(define (delete-all element a-bag)
  (lambda (item)
    (if (eq? item element)
      (a-bag item))))

;; The record encoding was very easy.
;; A record encoding based on the same idea as the procedural
;; encoding would use a list of records (item number-of-occurences)