Factorial and Fibonacci in continuation passing style.

fac-fib-cps.scm

;; Convert a CPS function into a normal function by passing a
;; function, which returns just the argument, as a continuation to the
;; CPS function.
(define (ret x) x)
(define (cps f/k) (lambda (x) (f/k x ret)))

;; Some test values.
(define digits (list 0 1 2 3 4 5 6 7 8 9))

;; Factorial
(define (fac n)
  (if (= n 0)
      1
      (* n (fac (- n 1)))))

(map fac digits)

;; Factorial with continuation
(define (fac/k n k)
  (if (= n 0)
      ;; Instead of returning the value pass it to the continuation.
      (k 1)
      ;; Instead of multiping the f(n-1) with n calculate f(n-1) and
      ;; pass the result to a new continuation, which takes the result
      ;; as t0 and then multiply t0 with n and pass it to the original
      ;; continuation.
      (fac/k (- n 1) (lambda (t0)
                       (k (* n t0))))))

(map (cps fac/k) digits)

;; Fibonacci
(define (fib n)
  (cond ((= 0 n) 0)
        ((= 1 n) 1)
        ((= 2 n) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

(map fib digits)

;; Fibonacci with continuation
(define (fib/k n k)
  (cond ((= 0 n) (k 0))
        ((= 1 n) (k 1))
        ((= 2 n) (k 1))
        ;; First calculate f(n-1).
        (else (fib/k (- n 1)
                     ;; Pass it as t0 to a new continuation.
                     (lambda (t0)
                       ;; Then calculate f(n-2).
                       (fib/k (- n 2)
                              ;; Pass it as t1 to a new continuation.
                              (lambda (t1)
                                ;; Finally add t0 and t1 and pass it
                                ;; to the original continuation.
                                (k (+ t0 t1)))))))))

(map (cps fib/k) digits)