Created
January 5, 2017 14:26
-
-
Save ceving/21fd465185eb6f006d466bc9cc261d37 to your computer and use it in GitHub Desktop.
Factorial and Fibonacci in continuation passing style.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment