;; Continuations! Continuation-passing style CPS ;; On the history of continuations (you will see some familiar names in there!): ;; https://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/reynolds-discoveries.pdf ;; ;; also look at the slides 32--34 of ;; https://homepages.inf.ed.ac.uk/wadler/papers/papers-we-love/papers-we-love.pdf ;; These slides very succinctly explain the constraints on continuation functions! ;; The textbook explains continuations in Chapter 8.3, with a sketch of ;; relevant history in 8.1. You may skip 8.2 on Exceptions for now. ;; Continuations are best demonstrated in Scheme. Although it's absolutely possible ;; to do them in Lisp (see Paul Graham's OnLisp Chapter 20), quite a bit of syntax ;; is required to make them look natural. In Scheme, they start natural! ;; First, recall our recursive sum of list function. (define (sum lst) ; type is [num] -> num (if (null? lst) 0 ; [] (+ (car lst) ; pair? == CONS (sum (cdr lst))))) ;; The tail call-optimized (TCO) form pushes the work of adding into the second argument (define (sum-acc lst acc) (if (null? lst) acc ; [] ; pair? == CONS (sum-acc (cdr lst) (+ acc (car lst))))) (sum-acc '() 0) ; 0 (sum-acc '(1 2 3 4) 0) ; 10 ;; Now consider a recursive sum of a tree: (define (sum-tree tree) (cond ((null? tree) 0) ((atom? tree) tree) ; leaf, a scalar value, hopefully addable ((pair? tree) (+ (sum-tree (car tree)) ; CAR tree is a tree (sum-tree (cdr tree)))))) ; CDR tree is a tree too ;; We now have two invocations of sum-tree. The TCO accumulator form doesn't ;; seem to be possible, because there doesn't seem to be a natural way of passing ;; subtree sums around to calls that descend into other subtrees. ;; Luckily, this is where the idea of _continuations_ shines. Instead of an ;; accumulated value, we pass around an entire function that takes the ;; would-be return value and, when called, performs the remaining actions ;; such as traversing the rest of the tree and adding the passed-in value ;; to the newly computed value. (define (sum-tree-cps tree cont) ; cont: num -> num (cond ((null? tree) (cont 0)) ((atom? tree) (cont tree)) ; scalar value, hopefully addable ((pair? tree) (sum-tree-cps (car tree) ; descend into the left subtree ; (note the TCO position) ;; after sum-tree-cps on CAR is done, hand its returned value to ... ;; (lambda (l) (sum-tree-cps (cdr tree) ; continuation will descend ;; and after CDR subtree is done, hand it to .. ;; (lambda (r) ; into the rest of tree (cont (+ l r))))))))) ; add the left and right ; subtree sums & continue ;; Note that (1) all recursive calls for subtrees are in the TCO position ;; (2) the last call in each branch is to the continuation cont, no matter what happens ;; (3) the argument to the continuation function is the return value of its caller: ;; for example, (sum-tree-cps (car tree) .. would return l , and ;; (sum-tree-cps (cdr tree) .. would return r. These then must be ;; added, (+ l r), after which execution must continue. The ;; continuation function called at that point might be a (lambda (r) ..) ;; of a subtree one level up, or the final continuation passed ;; to the initial call to sum-tree-cps. ;; Note that the type of the continuation's input value _and_ its return value are one and the same, ;; i.e., the original function's return value. (define (flatten-cps tree cont) ; cont: list -> flat list (cond ((null? tree) (cont tree)) ((pair? tree) (flatten-cps (car tree) ; flatten car (lambda (l) (flatten-cps (cdr tree) (lambda (r) (cont (append l r))))))) ((atom? tree) (cont (list tree))))) ; the scalar leaf value gets wrapped in a cons cell, for ; type uniformity (continuations take a list, not a scalar) (flatten-cps '((((1))) (2) ((3) 5)) (lambda (x) x)) ; the final continuation here is just "return whatever given". ; It could be anything else, like printing this value ; (1 2 3 5) (define (sum-cps lst cont) ; cont: num -> num (if (null? lst) (cont 0) (sum-cps (cdr lst) (lambda (s) (cont (+ s (car lst))))))) (sum-cps '(1 2 3 4) (lambda (x) x)) ; 10 ;; The CPS style is universal and can be applied to any program. ;; (you can check a discussion of this at ;; http://stackoverflow.com/questions/1888702/are-there-problems-that-cannot-be-written-using-tail-recursion ;; To read about continuations in LISP, look at Chapter 20 of OnLisp. ;; Focus on the Scheme DFT example in 20.1 and step through it by adding ;; debug prints throughout the code, until you understand how it works. ;; You will need a working Scheme set-up for this; see ;; https://cosc59.gitlab.io/scheme/scheme-and-evolution-of-lisp.txt ;; Ch. 20.2 explains how continuations can be approximated in LISP. This ;; approximation is neither complete nor first-class as above in Scheme, ;; but stepping though it is quite useful as well. ;; Continuations are an idea that seems to have no "best" explanation. The ;; idea of making first-class functions on the fly out of large chunks of ;; existing code _with associated execution state_ was revolutionary in its ;; time, even though lambdas were already first-class and closures ;; were on-the-fly made-to-order functions that captured some existing storage ;; (cf. eLisp's make-closure you see in bytecode disassembly). ;; Scheme has another astonishing feature, CALL/CC, which makes a continuation ;; at a given point of the code, from the current environment and "the rest ;; of the code from this point on". This turns out to have all kinds of ;; uses, such as implementing equivalents of GOTOs and exceptions, and even ;; making Scheme code look like logical programming/SAT solving. We'll look ;; into these on Tuesday.