Solution for Exam - Spring 2000 - Michael Elhadad

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

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

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.

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

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

(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

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

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