;;; CPS sum of a list
(define (sum x k)
(cond ((null? x) (k 0))
((pair? x)
(sum (cdr x)
(lambda (z) (k (+ (car x) z)))))
(else (error "contract violation"))))
;; testing, with an identity continuation
(sum () (lambda (x) x)) ; always test base case!
(sum '(1 2 3) (lambda (y) (display y)))
;; Let's do something with the sum of a list, too see how
;; continuations are handed through several function calls.
;; puts (sqr (sum lst))
;; In a CPS world, all functions take an extra argument for "and then do this", k.
;; They never return, so k is what they do last (on each path the execution might
;; take, if there are several (here there's only one, but see treesum below).
(define (sqr x k)
(k (* x x))) ; assuming * is inlined
(define (puts val k)
(k (display val)))
(define (print-squared-sum lst k)
(sum lst
(lambda (z) ; z is what sum(lst) is expected to compute, and hand to this continuation
(sqr z
(lambda (zz) ; zz is what sqr(z) is expected to compute, and hand to this continuation
(puts zz k))))))
; testing
(print-squared-sum '() (lambda (x) x))
(print-squared-sum '(1 2 3 4 2)
(lambda (x) x))
;;; CPS traversal of a tree
;;; Note that for a tree, both CAR and CDR may be trees, so we need to recurse
;;; on both (unlike in the linear list example above). So when writing CPS
;;; we will use a lambda continuation _twice_, to "schedule"/"pospone" both
;;; the task of summing up the left subtree (under CAR) and the right subtree
;;; (under CDR).
;;; See more discussion of this example in
;;; http://stackoverflow.com/questions/1888702/are-there-problems-that-cannot-be-written-using-tail-recursion
(define (treesum x k)
(cond ((null? x) (k 0))
((pair? x)
(treesum (car x)
(lambda (l) ; l will be what treesum computes on the (car x) subtree
(treesum (cdr x)
(lambda (r) ; r will be what treesum computes on the (cdr x) subtree
(k (+ l r))))))) ; and now we add the two, now that we have them
((number? x) (k x)) ;; what happens if we don't call k here? Find out!
(else (error "contract violation"))))
(treesum '() (lambda (x) x))
(treesum '(1) (lambda (x) x))
(treesum '(((1 ((2)))) 3 ((((4))))) (lambda (x) x))