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.
[5]