Hello, I hadn't programmed for some time, so as review I worked through “The Little Schemer” over the last seven days. I've been attempting to contextualize some of the knowledge I've gained from that book. For example Y-combinator seems to be a function which results in the repeated partial evaluation of a function onto its self. I'm struggling a bit to contextualize CPS as mentioned in Chapter 8 though. I understand the concept, just not how it relates to other ideas presented .
In some ways it seems like the inverse of repeated partial evaluation on its self (recursion). Instead of perpetually applying a function to its self a new function is generated by repeatedly adding new arguements on top of every application. Are they actually inverses of one another, can every recursion on a continuation be represented without either? What even is the natural recursion on a continuation?
CPS is just making the call stack explicit. It should be clear once you defunctionalze a CPS transformed program.
>>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.
>>3
But!
If we talk about inversion, it does have a curious effect on data structures. Consider a function that sums the elements of a list of natural numbers.
(define (natsum l)
(cond
((null? l) 0)
(else (+ (car l) (natsum (cdr l))))))
(define (natsum-cps l k)
(cond
((null? l) (k 0))
(else (natsum-cps (cdr l) (lambda (v) (k (+ v (car l))))))))
(define (natsum-dispatch v k)
(match k
('Start v)
(('Cdr w k') (natsum-dispatch (+ v w) k'))))
(define (natsum-defun l k)
(cond
((null? l) (natsum-dispatch 0 k))
(else (natsum-defun (cdr l) `(Cdr ,(car l) ,k)))))Notice the data structures in natsum-dispatch! They really look like a list, don't they? Let's rewrite it using a simple list.
(define (natsum-aps a l)
(cond
((null? l) a)
(else (natsum-aps (+ a (car l)) (cdr l)))))
(define (natsum-?? l k)
(cond
((null? l) (natsum-aps 0 k))
(else (natsum-?? (cdr l) (cons (car l) k)))))As you can guess from the name, the dispatch function turned out to be the accumulator passing style version of the original function! Or you could call it iterative and name it Natsumi. This is possible because + is commutative. Otherwise, we would have something different here, and natsum-?? will give us a hint what. If you squint your eyes, you might recognize the accumulator passing style of reverse.
I cheated a little, if you try it on a tree traversing algorithm you will end up with something different but just as much fascinating.
Try doing the transformation yourself before looking at the next code snippet! This is what I got:
This is actually kinda crazy. I was really struggling to rewrite this function so I ended up thinking I might be able to cheat a little. I ended up rewriting this function iteratively, reversing the iteration of the helper function, and then inlining that function with some partial evaluation. I knew this process wouldn't work in the general case because reversing the iteration of the helper function while preserving meaning is not always trivial/possible:
(define (fib-cps n c)
(cond ((zero? n) 0)
((= n 1) ((c 1) 0))
(else (fib-cps (- n 1) (lambda (x) (lambda (y) ((c (+ x y)) x)))))))
(fib-cps 20 (lambda (x) (lambda (y) x)))
=> 6765I then read the remainder of your posts to discover you mention all of these things! I was completely unaware of defunctionalisation, which seems to be a very powerful explanatory device; it's like making a little mini-interpreter as needed for higher order functions. So if I understand correctly CPS functions are higher-order iterative function, which are isomorphic with normal iterative functions through (de)functionalisaton, and all recursive functions are in turn isomorphic with CPS functions because they can be rewritten (right?). CPS and iterative functions both make the stack explicit, and in this way iterative functions are just a special case of CPS functions where the continuation is not higher order, this is why iterative functions through TCO don't expand the stack. Anyway I appreciate the effort you've expended in these posts, they've really helped me out.
>>5
For the programmer, CPS moves the call stack from the stack to the heap. This way one can avoid stack overflows on huge recursive structures, at the cost of having to reverse the data structure. It also makes control explicit and gives a way to simulate having first-class continuations in languages that don't have them.
More importantly, it is in widespread use as an intermediate language in compilers and interpreters. If you are interested in the topic, and want to learn how to algorithmically transforms programs into CPS, EOPL has two great chapters on the topic.
As for isomorphism, I think you are a bit too generous. The result of transforming =natsum= was both the iterative function and the reversing function. In the case of summing the values of a list, we can skip the reversing because of the commutative property of addition. But this is the rare case, for almost any other function you will still have to use both. For example, the iterative Fibonacci function that you tried to transform into CPS is not the same as what we got as fib-cps by transforming the direct-style definition. It is an interesting topic and people have used these transformations to demonstrate some amazing things, like transforming proofs[0] or abstract machines[1], and it is pretty fun to play around with it. But I have no training in this field so I don't want to claim things that are actually not true.
[0] http://cedric.cnam.fr/~puechm/upside.pdf
[1] https://tidsskrift.dk/brics/article/download/21784/19215
I blurred the distinction between CPS and the defunctionalized version a little, I should be sleeping by now. Anyway, CPS is not really iterative since you carry the stack around.
>>6,7
I was confused over the definition of iterative evidently, my thought was that it was simply a function which kept state off the call stack and as a form other than a function. With this definition my thought on the isomorphism was not that every procedure has an iterative function that can be derived from it in the traditional since, but rather that a defunctionalize procedure seemed to be necessarily iterative because you translate all recursive calls into a datastructure which you pass around. This is incorrect, yet further insight gained, terminology is important.
Anyway, EOPL is on my virtual book shelf, and I plan on reading it eventually, although I'm not exactly sure when. I've decided to relearn a good bit from scratch so I'm currently working through “The Seasoned Schemer”, hopefully I'll finish by the end of next week. One thing that really interests me about continuations is there use in making composable hygienic macros, and as you mention as a translation phase of compilers/interpreters, I think I'm awhile away from these applications though.