>>2
To expand on that. Let's consider a function to calculate the nth element of the Fibonacci sequence:
(define (fib n)
(cond
((zero? n) 0)
((= 1 n) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))))Now transform it into CPS. For the sake of simplicity, we assume that it is known that zero? and = both terminate and need not to be considered during the transformation. Try doing the transformation yourself before looking at the next code snippet! This is what I got:
(define (fib-cps n k)
(cond
((zero? n) (k 0))
((= 1 n) (k 1))
(else (fib-cps (- n 1)
(lambda (w) (fib-cps (- n 2)
(lambda (v) (k (+ w v)))))))))
(define (fib' n)
(fib-cps n (lambda (v) v)))It does look like building a pretty involved function, doesn't it?
Defunctionalization is the process of taking every closure and representing them with a structure that contains a unique label and the values it closes over. A function to dispatch on these structures is also added, and call sites that invoke functions from values are replaced with it. Here's the defunctionalized version:
(use-modules (ice-9 match))
(define (dispatch v k)
(match k
(('Id) v)
(('Kont1 n k') (fib-d (- n 2) `(Kont2 ,v ,k')))
(('Kont2 w k') (dispatch (+ v w) k'))))
(define (fib-d n k)
(cond
((zero? n) (dispatch 0 k))
((= 1 n) (dispatch 1 k))
(else (fib-d (- n 1) `(Kont1 ,n ,k)))))
(define (fib'' n)
(fib-d n '(Id)))Now it should be clear how simple CPS actually is.