prog

frontpage - thread list - new thread - preferences - ?

Inverse Recursion?

2 2020-05-13 07:22

CPS is just making the call stack explicit. It should be clear once you defunctionalze a CPS transformed program.

3 2020-05-13 17:55

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

9