Advanced Methods in Programming Languages (201-2-4411-01)

## Exam Solution

```;; QUESTION 1 (CPS):

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

;; QUESTION 3 (STREAMS):

(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)
'ok
(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)
the-null-stream
(cons-stream (f (stream-car s)) (stream-map f (stream-cdr s)))))

(define (interleave s1 s2)
(if (stream-null? s1)
s2
(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)
i
(a-bag item)))))

(define (delete-all element a-bag)
(lambda (item)
(if (eq? item element)
0
(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)

```