Continuation Passing Style and the Y combinator

Having written both imperative and having written a lot of FP code in Scheme, I somehow find the passing of lambdas to be more readable by now. I think it is a matter of individual taste or matter of what one has used a lot recently. I like to be able to minimalize the things I need to keep in mind at one moment. The lambdas are in themselves sort of units of code, which I can look at separately, without considering the path, how the execution of the code gets there. They do not have side-effects except for printing something (lets not be too strict, but yes OK that's a side-effect as well, but it has to live somewhere). If only I give these lambdas to other procedures in the right places, then if the lambda is correct, the whole will work correctly. I can focus on that one lambda or generalized I can focus on that one expression, instead of keeping the surrounding code in mind. Such kind of style makes it simple to copy paste expressions and be sure, that they work the same in a different place. For which I actually like the parentheses a lot (again an individual preference), because they are natural markers for start and end of an expression and I can have a key binding, which allows me to copy, cut, wrap, replace, whatever, that expression. This also applies to forms like lets or bindings introduced in lets, so even smaller parts than whole expressions. Basically ease of code editing.

I remember trying to grok Sussman's pattern matching code for 6.001. IIRC this was written in CPS or CPS-like way. It seemed very foreign at the time, but when I finally thought I got it, it made sense. I don't find search & backtracking easy no matter what one does, but as you say, continuations + good discipline makes it easier to focus on one thing at a time.

I tried to implement async/await in javascript staying closer to CPS form without the extra caching layers and state machines (without the promises) that normally wrap every async calls. https://www.npmjs.com/package/casync I use it all the time. Except for the lack of language level tooling (that you get with promise wrapped async/await), it works quite well and it's faster than native async/await. I wish something like it would be integrated in the language.

Very cool! I was always wondering why a single-threaded language doesn't transform async/await into a "callback heaven" under the hood. It should be much easier than what Rust did to garbage collection.

Exceptions kind of muck with things, since you want to be able to establish handlers further up the stack. Compiling async/await to callbacks means also compiling exceptions down to a different mechanism, which makes it difficult to get a stack trace and so on.

Note that casync gives you somewhat ok stack traces (with language level support it could be better) for example: const {casync} = require('./casync.js'); let inner=casync(function*(next){ throw new Error("test err"); }); let outer=casync(function*(next){ yield inner(next); }); outer((err)=>{throw err;}); Gives you Error: test err at /home/benoit/Documents/casync/errorTest.js:4:8 at Generator.next (<anonymous>) at doNext (/home/benoit/Documents/casync/casync.js:26:12) at next (/home/benoit/Documents/casync/casync.js:44:5) at /home/benoit/Documents/casync/casync.js:49:3 at /home/benoit/Documents/casync/errorTest.js:8:8 at Generator.next (<anonymous>) at doNext (/home/benoit/Documents/casync/casync.js:26:12) at next (/home/benoit/Documents/casync/casync.js:44:5) at /home/benoit/Documents/casync/casync.js:49:3 If you skip the lines inside casync which are in most case irrelevant you get: Error: test err at /home/benoit/Documents/casync/errorTest.js:4:8 at /home/benoit/Documents/casync/errorTest.js:8:8

Can a Decent Compiler convert direct style to CPS under the hood so to have the best of both worlds? Let's say we return Result<Integer> for the lookup and then pattern match for error or result. A compiler would be able to create two callbacks based on the match arms and change the lookup interface to accept them.

Yes. Check out the book "Compiling with Continuations" by Andrew Appel. Not only can a compiler "convert direct style to CPS under the hood," it's one of the more efficient and effective ways to implement a compiler. At a high level, CPS provides an intermediate form that's well suited to transformation into machine-oriented forms like machine code and bytecode, but is still high-level enough to be able to support both human and automated reasoning. Also see the paper, "A Correspondence between Continuation Passing Style and Static Single Assignment Form"[1] which describes the equivalence between SSA, commonly used in imperative language compilers, and CPS. This is one of the many cases where a well-motivated functional solution turns out to be one of the better solutions to a problem, to the point that a version of it is used even in imperative contexts. [1] https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/k...

Cool, I'll check them out. If it is "one of the more efficient and effective ways to implement a compiler", are we aware of any non-functional languages that use this style in their compilers? Asking since most compilers use LLVM and LLVM is in SSA form.

The insight in the Kelsey paper I linked is that SSA and CPS are essentially equivalent. SSA is more or less CPS expressed at a kind of lower level, more like a bytecode. So one answer to the question is that all SSA compilers are already using a form of CPS. If you wanted to use traditional CPS explicitly, you'd need a transformation step that converts the imperative source code into a more functional intermediate form so that it can be CPS'd. There might be benefits to that, since CPS can be easier to analyze than SSA. But I'm not aware of any real imperative compilers that do it. There's been academic work on it, like: https://arxiv.org/abs/1202.3247 One of the potential benefits is covered in that paper: the ability to prove correctness of the transformations. That kind of thing is easier to do given the mathematical tractability of CPS, due to its connection to lambda calculus.

CPS is a tool in the box of language theorists and compiler authors (although I don't know if any non-prototype actually uses CPS). IIRC it is mostly a convenient alternative to SSA. So yes, a compiler can transform your code into CPS to make some other passes simpler. Just an example from my own research: Say your program has the form of a long prelude followed by a tight loop. The loop cannot easily be changed, but the prelude can (think of languages like prolog, the prelude sets up the model, the loop solves it). At some point during the prelude you want to say: "For now, do this, but if x happens inside the loop, come back here, do that and then go back into the loop!" (e.g., your solver found a solution and you want to add/remove/change predicates). This is conveniently expressed as taking a continuation and passing it into the loop, which continues it when necessary.

And it's noteably slow due to it; c.p.s. made sense at that time, but modern hardware takes advantage of the existence of a stack much more aggressively. Chicken Scheme also uses it with a novel approach that allows the C stack to become the garbage collector which is still relatively fast as far as I heard.

Tragically, this blog post is not using the words "continuation passing style" to refer to CPS. If you read it you will see that the author is talking about a "style" of code which involves passing multiple lambdas to a function. Why he thinks it is a good idea to refer to this idiom as "continuation passing style" is anybody's guess. It is not CPS. His usage is confusing and to me it seems most likely that he just wants to be seen using a fancy ten-dollar technical term with the ring of prestige. Basically, the kind of blog post that wastes the time of unsuspecting readers.

You are mistaken. This is exactly continuation passing style. The two arguments `if-found` and `if-not-found` are continuations of `lookup`. Note that their invocations are in tail position within lookup.

Yes, as others said. What's more: you could also interpret the typical stack based execution in machine code as a special CPS style execution: only the order is strictly LIFO so that the continuations can be allocated on the stack. I.e., the continuation object for a function call is simply the function call's stack frame. Everything is there: 'contuation address' is in there: the return address, i.e., the 'ret' instruction, which is just a computed branch in the end, implements the invocation of the continuation, and it passes it the return value as a parameter. Sure, the compiler does need to be careful about the stack pointer manipulation, but the analogy is close enough. This can very easily be changed to a heap-based allocation of 'stack frames'. The compiler can also optimise and do some continuation allocations on the stack when it knows it will run out of lifetime after the call, or on the heap, just by the right setup of the frame pointer. And the compiler may even do tail call optimisations from this, so even with CPS, you get O(1) memory usage if the code is recognised to allow that. Even more, if the heap is compressed, and a heap allocation is as easy as incrementing a pointer, then the stack pointer could be reinterpreted to point to the end of the continuation heap (careful with deallocations in this case, of course), so just a heap and no stack, the runtime system would not even need more pre-defined registers than a normal stack based execution and instructions that implicitly increment the stack pointer could be used to fill the next continuation object -- it would look exactly like constructing a stack frame. It's all connected.

First of all, I don't think you should program in CPS yourself but use proper language support if it's available. Otherwise just leave it at that. Code is read much more often than written. You also don't use Church-Encoding or De-Bruijn variables if you can avoid it. Secondly, what's the point when you have to inline? If your function would return an optional and you inline it, you would get the same effect from any decent compiler.

If your language has do-notation or something like it, then CPS can be quite readable. With the syntax: cps { let! x = doThisThing let y = x * 2 + 3 let! z = doOtherThing y return z + 1 } Without the syntax: doThisThing.Then(fun x -> let y = x * 2 + 3 doOtherThing(y).Then(fun z -> z + 1 ) )

Proper language support? But it's CPS passing functions rather than returning values, no? So lookup( "key", table, result => { ... }, error => { ... } ) or lookup( "key", table ).then(result => { ... }) .then(next_result => { ... }) .catch(error => { ... }) Or do you mean, one optimised for performance?

In "On Lisp," there's a chapter where pg explains how to write continuation-style passing macros without sacrificing readability. I used it to implement nondeterministic backtracking in python, and it worked. No coroutines, no language support, just macros and locally-captured continuations. (I'm a bit too tired to figure out how this relates to your question, but I'm pretty certain it's related.) Here's the whole chapter as an imgur album: https://imgur.com/a/ccv4Q9o It's hard to see from that chapter alone why it's so powerful, but later chapters implement a variety of wonderful things with these abstractions: a process scheduler, language analysis, and other nondeterministic things. It was neat playing with it on real algorithms in python, rather than being consigned to obscure-lisp-impelmentation hell: https://twitter.com/theshawwn/status/1373239490660069379 Basically, it's similar to your lookup.then.then.catch example, but the macros automate all of the code generation. It's also not quite the same thing as async-await, nor coroutines; there are some subtle, interesting differences.

I am working the examples in the new book Software Design for Flexibility both in Scheme and Python. I agree with you that it is good to carry practices from Lisp languages to Python, when we must use Python.

Glad you asked. Like this: https://github.com/shawwn/pymen/blob/68b66dccc96910869ab370d... (=defun choose-bind-test () (choose-bind x '(0 1 2 3 4 5 6 7 8 9) (write (str x)) (if (= x 6) x (fail)))) If it's confusing why it looks like Lisp, it's because it's a self-hosted Lisp that runs entirely in Python. (Basically, there's no "runtime" -- it uses native python constructs, and all of the code compiles directly to real python.) What does the python look like? Well: https://github.com/shawwn/pymen/blob/12753ebb1251970f29eb04e... setenv("choose-bind-test", macro=__choose_bind_test__macro1) def L_61choose_bind_test(L_42cont42=None): def __f73(x=None): write(L_str(x)) if x == 6: return x else: return L_61fail(L_42cont42) __L_42cont428 = __f73 return L_61choose(__L_42cont428, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) As you can see, macros do an incredible amount of work under the hood. This code is reminiscent of the parent comment's try.then.then.catch example, yet the source code is wonderfully readable. Thus, lisp's power. If you want to play around with it: git clone https://github.com/shawwn/pymen cd pymen git checkout ml # optionally, brew install rlwrap rlwrap bin/pymen > (load "lib/onlisp.l") > (choose-bind-test) 0123456 Note, I didn't invent this technique. This is courtesy of Scott Bell's Lumen lisp: https://github.com/sctb/lumen I "merely" ported it to Python, and a few billion other things over the years. The specific example listed in the tweet was made using this: (=defun path (node1 node2) (if (null? (neighbors node1)) (fail) (in node2 (neighbors node1)) (=values (list node2)) (=bind (n) (choose (neighbors node1)) (=bind (m) (path n node2) (=values `(,n ,@m)))))) (defconst nodes* (obj a: '(b d) b: '(c) c: '(a) d: '(e) e: '())) (def neighbors (n) (get nodes* n)) Which you can run like this: > (print (str (path 'a 'e))) ("d" "e") > (print (str (fail))) ("b" "c" "a" "d" "e") > (print (str (fail))) ("b" "c" "a" "b" "c" "a" "d" "e") > (print (str (fail))) ("b" "c" "a" "b" "c" "a" "b" "c" "a" "d" "e") The (print (str ...)) stuff is because otherwise it would pretty-print the actual python objects, which are dictionaries. It's a bit harder to read. > (fail) {0: 'b', 1: 'c', 2: 'a', 3: 'b', 4: 'c', 5: 'a', 6: 'b', 7: 'c', 8: 'a', 9: 'b', 10: 'c', 11: 'a', 12: 'd', 13: 'e'} As you can see, lists are represented as dicts, not cons cells. So, to sum up, Lisp is so powerful that I was able to port pg's On Lisp examples with almost no modification whatsoever, directly into Python. These examples are almost verbatim from the book. (There are more in the github links above.) Since this will be my last chance to demonstrate this for some time, I close with an example of the "ballet" from On Lisp, where multiple processes are collaborating together to reach some goal: (program ballet () (fork (visitor 'door1) 1) (fork (host 'door1) 1) (fork (visitor 'door2) 1) (fork (host 'door2) 1)) expands into: setenv("ballet", macro=__ballet__macro1) def L_61ballet(L_42cont42=None): global L_42procs42 L_42procs42 = None ____x179 = ["visitor", ["quote", "door1"]] def __f60(__id39=None): L_61visitor(L_42cont42, "door1") return pick_process() L_42procs42 = join([make_proc(state=__f60, pri=1)], L_42procs42) ____x183 = ["host", ["quote", "door1"]] def __f61(__id40=None): L_61host(L_42cont42, "door1") return pick_process() L_42procs42 = join([make_proc(state=__f61, pri=1)], L_42procs42) ____x187 = ["visitor", ["quote", "door2"]] def __f62(__id41=None): L_61visitor(L_42cont42, "door2") return pick_process() L_42procs42 = join([make_proc(state=__f62, pri=1)], L_42procs42) ____x191 = ["host", ["quote", "door2"]] def __f63(__id42=None): L_61host(L_42cont42, "door2") return pick_process() L_42procs42 = join([make_proc(state=__f63, pri=1)], L_42procs42) while True: L_print("looping") time.sleep(0.5) if not is63(pick_process()): break return catch(L_42halt42) Notice the incredible amount of leverage you get from macros. Most programmers simply go ahead and write that kind of callback-hell-style code in other languages. Bugs become very difficult to spot. Here, you don't need to.

Chicken Scheme implements R5RS Scheme using the continuation passing style underneath ("Cheney on the MTA"), so it is never strictly exposed to the programmer (no syntax changes), whilst giving them the performance improvements and making call/cc macros practically free. That's what I would call first class language support.

I found one can program in that style in Python as well. I am not sure whether it is usually a good idea....

Hmmm. I think this is yet another example of how the various programming communities have difficulty talking with each other. This "continuation passing style" with a Decent Compiler™ has been well known to the C++ community, to the point where the C++ community commonly exclaims that sort() is faster than qsort(). sort() is a template function, which means that the compiler will generate a "new sort" each time you pass in an argument. And much care has been put forth to ensure that the parameter function can easily be inlined by the compiler. Not quite 100%: sort() is a simple function and not a proper continuation. But still, I've seen C++ inline lambdas before. ----------- Of course, in the Lisp / Functional land, its all called "Continuation passing style". C# may call it async style. Javascript may call it callbacks. ----------- It should also be noted that compiler theory also calls things "continuation passing style" (in contrast to Single Static Assignment). Compilers need to "normalize" the code into a certain form (SSA: where all variables have ONE assignment max is probably more popular today. But Continuation Passing Style is proven to be an equivalent, and alternative, means of normalizing). I clicked expecting SSA vs Continuation Passing Style. Turns out its the "other" continuation passing style being discussed here.

Two smaller disagreements and a note: > We take a branch and return the "key not found" value. But now the caller tests the return value against "key not found" and it, too, takes a branch. We only take the true branch in the caller if the true branch was taken in the callee and we only take the false branch in the caller if the false branch was taken in the callee. In essence, we are branching on the exact same condition twice. If we can inline the lambdas, we can inline the lookup. In that case, the sufficiently smart compiler can just as easily tell we're doing "variable = a if test else b; if (variable == a) x else y" and optimize to "if (test) x else y". > It's a bit vacuous to observe that an inlined function performs better. Not necessarily - inlining a cold-path function can blow the instruction cache for no speed benefit. For instance, if the key is almost always going to be found, you may not want to inline the "key not found" lambda on performance grounds. Instead, you should allow the lookup function to assure the compiler that it won't leak its lambda arguments, at which point the closure allocation can be replaced with a stack pointer. > Unfortunately, we cannot declare answer to be an integer because it might be the "key not found" value. Alternatively, we might decide to reserve a special integer to indicate "key not found". The answer can then be declared an integer, but there is now a magic integer that cannot be stored in the table. In a language with sumtypes: (Value | :notFound) lookup(Key key) { ... } This can be optimized by the compiler to a "special integer" if the Value type doesn't cover the entire integer range. (I believe Rust does this.)

This won't be a very deep answer, but to connect with the original post, programming in CPS is more closely related to delimited continuations than call/cc is because the continuations are just ordinary functions in the host language, unlike call/cc continuations which are a bit more complex. As for why delimited continuations are not more popular, many people find shift/reset a bit difficult to program with. In particular the type systems for them are a bit odd and some variants like prompt/control don't have nice type systems for them. Currently, the closely related notion of (algebraic) effect handlers is quite popular in the functional language design community as something quite similar in expressive power but more intuitive for programming and with very natural typing. The Koka language has a lot of nice introductory resources if you are interested in learning more: https://github.com/koka-lang/koka . There's even a serious proposal for adding something based on these to webassembly: https://github.com/effect-handlers/wasm-effect-handlers .

call/cc can be built entirely out of CPS and closures of indefinite extent (i.e., allocated on the heap). Using CPS with closures of dynamic extent (i.e., allocated on the stack, either explicitly, or because that's all you get, or because the compiler is smart enough to figure out that these closures don't leak out) is a lot more like delimited continuations (but easier to use).

CPS is used as an intermediate representation. I have never seen anyone programming in CPS. You program in any style you want, the code is converted to CPS, then compiler works on CPS.

> I have never seen anyone programming in CPS. Perhaps you've heard of "Javascript callback hell", or maybe even witnessed it first-eye? That's essentially CPS, written manually--one of the driving forces for inventing async/await was to return back to writing the programs in direct style and letting the compiler do the CPS transformation at specified points.

I think the author is specifically talking about those cases where performance really matters. You could still have callback hell, but a lot less so. As an aside, there is an alternative: passing a default value. This is Swift syntax: let favoriteIceCream = [ "Paul": "Chocolate", "Sophie": "Vanilla" ] let result = favoriteIceCream["Charlotte", default: "Unknown"]

You do it in Javascript and they call it "Callback hell", do it in LISP and it is "Continuation passing style".

That's because most JS developers don't know how to organize async code (surprising, I know) so they end up building a ball of spaghetti and then claim it's the callbacks fault rather than their own architecture.

watsonyoublituff.blogspot.com

Source: https://news.ycombinator.com/item?id=26800745

Share this post