Write your name in the top right-hand corner of this page. This exam is worth 110 points. You have two hours to answer eight (or nine) questions. Show your work to receive partial credit. Good luck!
+ is primitive. All other procedures
are potentially recursive and must take continuations.
(define add7
(let ([curry (lambda (f)
(lambda (x)
(lambda (y)
(f x y))))]
[plus (lambda (x y)
(+ x y))])
(lambda (x)
(((curry plus)
x)
7))))
Solution:
(define add7
(let ([curry (lambda (f k2)
(k2 (lambda (x k3)
(k3 (lambda (y k4)
(f x y k4))))))]
[plus (lambda (x y k5)
(k5 (+ x y)))])
(lambda (x k1)
(curry plus
(lambda (v1)
(v1 x
(lambda (v2)
(v2 7 k1))))))))
(+ 1
(+ 10
(call/cc
(lambda (exit)
(+ 100 (exit 100))))
1000)
10000)
Solution: 11111
(let ([n (+ 3 (call/cc
(lambda (exit)
(exit (exit 6)))))])
(if (= n 12)
(call/cc
(lambda (new-exit)
(- (new-exit n) 6)))
n))
Solution: 9
fib takes a number n
and returns the n-th fibonacci number.
(define fib
(lambda (n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2))))))
(fib 5) ==> 5
(fib 6) ==> 8
(fib 7) ==> 13
fib into
continuation-passing style by defining the procedure
fib-cps which takes a number n,
and a continuation k. Redefine the procedure
fib so that it calls fib-cps
with a proper initial continuation.
You may assume that the procedures
<, +, and -
are primitive.
(define fib
(lambda (n)
(fib-cps n (lambda (v) v))))
(define fib-cps
(lambda (n k)
(if (< n 2)
(k n)
(fib-cps (- n 1)
(lambda (v)
(fib-cps (- n 2)
(lambda (v2)
(k (+ v v2)))))))))
fib-cps called fib-ri, and
represent your continuations as records. Redefine
fib so that it calls fib-ri
with a proper initial continuation.
Solution:
(define fib
(lambda (n)
(fib-ri n (make-final-k))))
(define fib-ri
(lambda (n k)
(if (< n 2)
(apply-k k n)
(fib-ri (- n 1) (make-fib1-k n k)))))
(define make-final-k
(lambda ()
(list 'final-k)))
(define make-fib1-k
(lambda (n k)
(list 'fib1-k n k)))
(define make-fib2-k
(lambda (v k)
(list 'fib2-k v k)))
(define apply-k
(lambda (k v)
(record-case k
(final-k () v)
(fib1-k (n k)
(fib-ri (- n 2) (make-fib2-k v k)))
(fib2-k (v2 k)
(apply-k k (+ v2 v))))))
fib-ri so that it passes its
arguments in registers. Call the new program
fib-reg (which should take zero arguments).
Redefine fib so that it sets up the
registers properly for the call to fib-reg,
and returns the answer.
Solution:
(define fib
(lambda (n)
(set! n-reg n)
(set! k-reg (make-final-k))
(fib-reg)))
(define fib-reg
(lambda ()
(if (< n-reg 2)
(begin
(set! v-reg n-reg)
(apply-k))
(begin
(set! k-reg (make-fib1-k n-reg k-reg))
(set! n-reg (- n-reg 1))
(fib-reg)))))
(define apply-k
(lambda ()
(record-case k-reg
(final-k () v-reg)
(fib1-k (n k)
(set! k-reg (make-fib2-k v-reg k))
(set! n-reg (- n 2))
(fib-reg))
(fib2-k (v2 k)
(set! k-reg k)
(set! v-reg (+ v2 v-reg))
(apply-k)))))
(define v-reg 'ignored)
(define k-reg 'ignored)
(define n-reg 'ignored)
(local ([x 1] [y 2])
(let ([a x] [b y] [c (+ x y)])
(set! a (+ a a))
(set! b (+ b b))
(set! b (+ c c))
(printf "~s ~s ~s , ~s ~s" a b c x y)))
Assume local is like let, but always uses
call-by-value.
Solution:
(let ([x 1] [n 10])
(let ([add-x (lambda (n) (+ x n))])
(let ([x 100] [n 1000])
(add-x n))))
Solution:
public class Main {
public static void main(String args []) {
Furniture f = new Furniture();
Table t = new Table();
Table c = new CoffeTable();
f.place(0,0);
t.place(0,0);
c.place(0,0);
t.placeAndDestroy(0,0);
c.placeAndDestroy(0,0);
c.destroy();
}
}
class Furniture {
public void place(int x, int y) {
System.out.println("This furniture is in a new place");
}
public void destroy() {
System.out.println("This furniture no longer exists");
}
}
class Table extends Furniture {
public void place(int x, int y) {
System.out.println("This table is in a new place");
}
public void placeAndDestroy(int x, int y) {
this.place(x,y);
super.destroy();
}
public void destroy() {
System.out.println("This table no longer exists");
}
}
class CoffeTable extends Table {
public void place(int x, int y) {
System.out.println("This coffe table is in a new place");
}
}
Solution:
This furniture is in a new place This table is in a new place This coffe table is in a new place This table is in a new place This furniture no longer exists This coffe table is in a new place This furniture no longer exists This table no longer exists
Statement --> IterationStatement IterationStatement --> do Statement while ( Expression ) ;
Solution: (changes marked with <strong>)
(define program?
(grammar program
...
(statement
(report-if-bad 'statement
(alt select-statement jump-statement iteration-statement block expression)))
(iteration-statement (lst 'dowhile statement expression))
...))
(define stmt-keywords '(begin if return dowhile))
(define check-stmt
(lambda (stmt tenv)
(if (stmt-is-exp? stmt)
(mvlet (((type exp) (check-exp stmt tenv))) exp)
(record-case stmt
...
(dowhile (body-stmt test-exp)
(mvlet (((test-type test-exp) (check-exp test-exp tenv)))
(match-types test-type 'boolean)
(list 'dowhile (check-stmt body-stmt tenv) test-exp)))))))
for-loop works in a similar
way to the for statement in C.
(define for-loop
(lambda (start end body)
(call/cc
(lambda (break)
(letrec
([loop
(lambda (i)
(if (< i end)
(begin
(body i break)
(loop (add1 i)))))])
(loop start))))))
An example using this function could be: using for-loop
| output | equivalent C program |
|---|---|---|
(for-loop 0 10
(lambda (i break)
(cond
[(= i 7) (break)]
[(odd? i)
(printf "i=~s o" i)]
[else
(printf "i=~s e" i)])
(newline)))
|
i=0 e i=1 o i=2 e i=3 o i=4 e i=5 o i=6 e |
for (i=0; i<10; i++) {
if (i == 7)
break;
else if (odd(i))
printf("i=%d o", i);
else
printf("i=%d e", i);
printf("\n");
}
|
Now you want to extend for-loop to allow for
continue in the body of the function, which
exits the current iteration and continue with the next one.
using for-loop
| output | equivalent C program |
|---|---|---|
(for-loop 0 10
(lambda (i break continue)
(cond
[(= i 7) (break)]
[(odd? i)
(printf "i=~s o" i)]
[else
(printf "i=~s e" i)])
(if (= i 3) ; if i==3, don't
(continue)) ; print newline
(newline)))
|
i=0 e i=1 o i=2 e i=3 oi=4 e i=5 o i=6 e |
for (i=0; i<10; i++) {
if (i == 7)
break;
else if (odd(i))
printf("i=%d o", i);
else
printf("i=%d e", i);
if (i == 3)
continue;
printf("\n");
}
|
Solution:
(define for-loop
(lambda (start end body)
(call/cc
(lambda (break)
(letrec
([loop
(lambda (i)
(if (< i end)
(begin
(call/cc
(lambda (continue)
(body i break continue)))
(loop (add1 i)))))])
(loop start))))))