next up previous contents index
Next: Explicit store Up: The transformer Previous: Continuation passing style

The engine transformation

We augment the CPS program to count operations. Later we will use the count to limit the number of operations that a program does. Instead of counting up, we count down, since by starting at some positive count, we can count down to zero, a fixed limit, and avoid having to pass a limit too.

1. (define (fib k fuel n)
2.   (if (< n 2)
3.       (k (- fuel 1) 1)
4.       (fib (lambda (fib-of-n-1 fuel)
5.              (fib (lambda (fib-of-n-2 fuel)
6.                     (k (+ fib-of-n-1 fib-of-n-2)
7.                        (- fuel 1)))
8.                   (- fuel 1)
9.                   (- n 2)))
10.            (- fuel 2)
11.            (- n 1))))

The counting of the operations is as follows. Notice that although < appears twice in the accounting, it will only be counted once since each count appears on a different conditional path.

The variable fuel is single threaded (also known as linear), which means that once a new value of fuel is computed, the old value is never re-used.


Erik Rauch
Sat May 8 16:42:57 EDT 1999