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

Question 1: call/cc

Question 1.1: Value returned by (call/cc call/cc)

The expression is evaluated at the toplevel loop of the interpreter. It passes the "current continuation" to call/cc. The current continuation is at this point the "toplevel loop" itself. The first reduction is therefore:
(call/cc call/cc) ==> (call/cc top)

where top is the continuation active at the toplevel loop, that is, the continuation that returns to the toplevel of the interpreter the value it is given. That is:
For all x, and for all context K: (K (top x)) ==> x

Now, (call/cc top) passes to top the current continuation, which is top. Therefore, the returned value is top itself.

Question 1.2: Stick

> (define (stick f flag k*)
       (lambda (arg)
         (call/cc (lambda (k)
                    (if (= flag 1)
                        (begin (set! flag 0) (set! k* k)))
                        (k* (f arg))))))
#<unspecified>
> (define s (stick fact 1 (lambda (x) x)))
#<unspecified>
> (define t (stick fact 1 (lambda (x) x)))
#<unspecified>
> (s 5)
120
> (+ (s 5) (s 4))
CASE 1: Interpreter evaluates left-to-right: (s 5) is evaluated first
120
CASE 2: Interpreter does not evaluate left-to-right: (s 4) is evaluated first
24
NOTE1: It is typical of processing of continuations that they are sensitive to
the order of evaluation (computation strategy).  This has become apparent when
processing the CPS transformation.

NOTE2: What stick does is return a continuation that computes the same value as
f but exits from any context in which it is invoked, and passes the result to the
context that was active the first time the continuation is invoked.

> (+ 8 (t 5))
128
> (t 5)
128

Question 2: Streams

Question 2.1: exp-terms

(exp-terms x) returns a stream that returns the values (x^n)/n! without doing redundant computations.

Note that the terms that are returned verify the equation:
s(n+1) = s(n) * x / (n + 1)


(define (exp-terms x)
  (letrec ((terms (lambda (an n+1)
                    (cons-stream an
                                 (terms (/ (* an x) n+1) (+ n+1 1))))))
    (terms 1 1)))

Note: solutions that invoke fact or power are obviously not efficient, since they recompute the multiplications for each term, instead of reusing the previous term.

Question 2.2: exp-approx

(exp-approx x) computes the partial sums of the terms (x^n)/n! (that is, sum(i=0..n, x^i/i!)).

(define (exp-approx x)
  (letrec ((sum-stream (lambda (sum s)
                         (cons-stream sum
                                      (sum-stream (+ sum (stream-car s))
                                                  (stream-cdr s))))))
    (sum-stream 0 (exp-terms x))))

Question 3: CPS

The tree BNF is:

<tree> ::= <number>
         | ( )
         | (<tree> . <tree>)

Question 3.1: treemax

(define (tree-max tree k)
  (cond ((number? tree) (k tree))
        ((null? tree) (k most-negative-number))
        (else (tree-max (car tree)
                        (lambda (carmax)
                          (tree-max (cdr tree)
                                    (lambda (cdrmax)
                                      (k (max carmax cdrmax)))))))))

The main question is: what should be returned for the empty tree? To grasp the answer, consider what should be returned if the question were:

the sum of all the nodes in the tree? 0
the product of all the nodes in the tree? 1

In general, given a combination method, the function should return the "neutral element" of the combination when applied to an empty tree. In the case of max, the neutral element is the smallest possible number. Call this "most-negative-number".

If such an element cannot be obtained from the scheme interpreter, then we can "simulate" it by defining a symbol 'most-negative-number, and defining an operator max-with-most-negative:

(define (max-with-most-negative x y)
  (cond ((eq? x 'most-negative-number) y)
        ((eq? y 'most-negative-number) x)
        (else (max x y))))

Question 3.2: replace-neg-by-max

The function replaces all negative numbers in a tree with the maximum element appearing in the tree - but performs only one pass over the tree. Naturally, the trick is that the necessary "second pass" is performed by a continuation that is built during the first pass.

(define (replace-neg-max tree k)
  (cond ((null? tree) (k 0 (lambda (max) '())))
        ((number? tree) (k tree (lambda (max) (if (< tree 0) max tree))))
        (else (replace-neg-max 
                (car tree)
                (lambda (carmax carmaker)
                  (replace-neg-max 
                   (cdr tree)
                   (lambda (cdrmax cdrmaker)
                     (k (max carmax cdrmax)
                        (lambda (max)
                          (cons (carmaker max)
                                (cdrmaker max)))))))))))

(define (rnm tree)
  (replace-neg-max tree (lambda (max maker) (maker max))))

Question 4: lexical-address

This was done in HW1.

Last modified 6 June 2000 Michael Elhadad