Compiling with Continuations(swatson555.github.io)
swatson555.github.io
Compiling with Continuations
https://swatson555.github.io/posts/2025-09-16-compiling-with-continuations.html
25 comments
It was very odd to start a “review” of a book from 1992 by criticizing it for lacking all the things you think a book published in 2025 should have. And then searching GitHub for code related to it, like TFA is expecting this to be something widely read as an introduction. TFA never considers who the target audience for the book was—in 1992, hardly a year when books about compilation techniques were looking to reach a wider audience (like Nyquist’s book Crafting or something).
Beowulf really doesn’t stand up to the Marvel franchise.
Alternatively, OP might have a bit of learning still to do.
Alternatively, OP might have a bit of learning still to do.
I've implemented my lisp/scheme based on Three Implementation Models for Scheme and also Lisp in Small Pieces. Both make a CPS transformation, which, after finally wrapping my head around it, is great for many things. For example it makes implementing async/await very easy (without implementing call/cc which I find too powerful). I use them a lot since I use the language for scripting games, where asynchronous structures really shine.
I wrote my lisp as a modified explicit control evaluator from SICP because I wanted to avoid transforming the code at all.
> Three Implementation Models for Scheme
This was a good read, thank you for the reference.
> call/cc which I find too powerful
Why do you think that? Do you have the same opinion about delimited continuations?
> Three Implementation Models for Scheme
This was a good read, thank you for the reference.
> call/cc which I find too powerful
Why do you think that? Do you have the same opinion about delimited continuations?
Good question, but I'm not yet experienced enough in language design to give a coherent answer. And I'm not very familiar with delimited continuations. But I think it boils down to keeping the VM simple. Now it's just all closures, and I can focus on optimizing closures. Adding first class continuations would reauire me to also optimize those. Also having continuations makes optimizing closures harder, since it prevents certain assumptions. As long as closures and CPS enable everything I need, I'm not tempted to add another, more powrful structure.
> The book has no exercises. This positions it awkwardly in the broader perspective of compiler study. It’s as if it’s a book that isn’t meant to be studied or understood, or perhaps it just doesn’t care.
I bought it because it demonstrated how to cps-transform code, which was my goal. I think it delivered.
For a "broader perspective", see the follow-up papers:
FWIW, after I implemented CPS this way, I eventually switched to ANF for typing reasons. I'm a bit of a beginner at type inference and could not assign a meaningful type to the extra term ("continuation") that CPS produces (and which ANF does not).
I bought it because it demonstrated how to cps-transform code, which was my goal. I think it delivered.
For a "broader perspective", see the follow-up papers:
Compiling with Continuations, Continued (2007) (Cited by 154)” “The Essence of Compiling with Continuations (1993) (Cited by 806)” “Compiling with continuations, or without? whatever. (2019) (Cited by 34)”
FWIW, after I implemented CPS this way, I eventually switched to ANF for typing reasons. I'm a bit of a beginner at type inference and could not assign a meaningful type to the extra term ("continuation") that CPS produces (and which ANF does not).
I remember reading it and taking some inspiration for my thesis work.
CPS is quite useful for abstract interpretation when doing flow-based type-inference systems since the continuation just becomes another value to track.
CPS is quite useful for abstract interpretation when doing flow-based type-inference systems since the continuation just becomes another value to track.
> Doing a search for source code on Github reveals basically nothing. No blog posts. No source code repositories. Nothing.
If nobody ever implemented it in C, it's questionable whether it ever happened at all.
If nobody ever implemented it in C, it's questionable whether it ever happened at all.
I learned a lot from implementing this book. Compiler was in OCaml. Runtime was in C (used as a glorified assembly).
> Compiler was in OCaml
Not exactly a common language...
I don't have a math or computer science background so the more academic publications are almost always quite unreadable to me. I learn a lot by exploring the source code of existing virtual machines instead, and most are written in systems languages.
Sometimes much smarter people than I randomly decide to write articles that democratize access to very complex areas of programming language development. Examples:
https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga...
https://www.wingolog.org/archives/2010/02/26/guile-and-delim...
Not exactly a common language...
I don't have a math or computer science background so the more academic publications are almost always quite unreadable to me. I learn a lot by exploring the source code of existing virtual machines instead, and most are written in systems languages.
Sometimes much smarter people than I randomly decide to write articles that democratize access to very complex areas of programming language development. Examples:
https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga...
https://www.wingolog.org/archives/2010/02/26/guile-and-delim...
It’s an extremely common language to write compilers in. The original Rust compiler was written in it for exemple.
This is a book about ML, not C.
For C you can look at the old Perl6 VM, Parrot which compiled to CPS until v2.7, where they destroyed CPS and went conventional and slow.
For C you can look at the old Perl6 VM, Parrot which compiled to CPS until v2.7, where they destroyed CPS and went conventional and slow.
Have been many, for the book the post is reviewing, eg.
https://github.com/abeln/cc
Blogger just didn't look hard enough (or doesn't know that search on GitHub is crippled, for reasons)
https://github.com/abeln/cc
Blogger just didn't look hard enough (or doesn't know that search on GitHub is crippled, for reasons)
Github is not the universe.
The review doesn't mention branch prediction. Call/ret instructions work really well with branch predictors. Lots of jumps (to continuations) might not work quite as well.
From the review (discussing "practical applications of continuations"):
> Was it influential to the field of computer science?
Call/cc was fairly popular in the North West of the US (maybe California too) among Lisp and Scheme people. Compiling them well on real machines was definitely a topic worth investigating at the time.
https://en.wikipedia.org/wiki/Call-with-current-continuation
Call/cc has since (thankfully) become a lot less popular.
I liked the book a lot when I read it (2-3 decades ago) but it didn't seem relevant in the slightest if you just didn't care about call/cc.
From the review (discussing "practical applications of continuations"):
> Was it influential to the field of computer science?
Call/cc was fairly popular in the North West of the US (maybe California too) among Lisp and Scheme people. Compiling them well on real machines was definitely a topic worth investigating at the time.
https://en.wikipedia.org/wiki/Call-with-current-continuation
Call/cc has since (thankfully) become a lot less popular.
I liked the book a lot when I read it (2-3 decades ago) but it didn't seem relevant in the slightest if you just didn't care about call/cc.
> Call/ret instructions work really well with branch predictors. Lots of jumps (to continuations) might not work quite as well.
On x86, the use of paired call/return is conflated with usage of the stack to store activation records. On AArch64, indirect branches can be marked with a hint bit indicating that they are a call or return, so branch prediction can work exactly the same with activation records elsewhere.
On x86, the use of paired call/return is conflated with usage of the stack to store activation records. On AArch64, indirect branches can be marked with a hint bit indicating that they are a call or return, so branch prediction can work exactly the same with activation records elsewhere.
CPS and call/cc aren’t the same thing though they are close.
CPS is an intermediate form that a compiler can use to reason about a program. You could argue that using this form makes it easier to implement call/cc, but I don’t think that’s really true.
I vaguely recall that CPS makes it possible to reason about stack disciplined calls, if you want to compile to call/ret instructions.
But whatever, it really doesn’t matter. CPS is quite dead as an IR. SSA won
CPS is an intermediate form that a compiler can use to reason about a program. You could argue that using this form makes it easier to implement call/cc, but I don’t think that’s really true.
I vaguely recall that CPS makes it possible to reason about stack disciplined calls, if you want to compile to call/ret instructions.
But whatever, it really doesn’t matter. CPS is quite dead as an IR. SSA won
CPS is fairly dead as an IR, but the (local) CPS transform seems more popular than ever with languages implementing "stackless" control effects.
As far as functional IRs go, I would say SSA corresponds most directly to (a first-order restriction of) ANF w/ join points. The main difference being the use of dominance-based scoping rules, which is certainly more convenient than juggling binders when writing transformations. The first-order restriction isn't even essential, e.g. https://compilers.cs.uni-saarland.de/papers/lkh15_cgo.pdf.
If you're interested in an IR that can express continuations (or evaluation contexts) in a first-class way, a much better choice than CPS is an IR based on the sequent calculus. As I'm sure you know (since you work with one of the coauthors), this was first experimented with in a practical way in GHC (https://pauldownen.com/publications/scfp_ext.pdf), but there is a paper in this year's OOPSLA (https://dl.acm.org/doi/10.1145/3720507) that explores this more fundamentally, without the architectural constraint of being compatible with all of the other decisions already made in GHC. Of course, one could add dominance scoping etc. to make an extension of SSA with more symmetry between producers and consumers like the classical sequent calculus.
As far as functional IRs go, I would say SSA corresponds most directly to (a first-order restriction of) ANF w/ join points. The main difference being the use of dominance-based scoping rules, which is certainly more convenient than juggling binders when writing transformations. The first-order restriction isn't even essential, e.g. https://compilers.cs.uni-saarland.de/papers/lkh15_cgo.pdf.
If you're interested in an IR that can express continuations (or evaluation contexts) in a first-class way, a much better choice than CPS is an IR based on the sequent calculus. As I'm sure you know (since you work with one of the coauthors), this was first experimented with in a practical way in GHC (https://pauldownen.com/publications/scfp_ext.pdf), but there is a paper in this year's OOPSLA (https://dl.acm.org/doi/10.1145/3720507) that explores this more fundamentally, without the architectural constraint of being compatible with all of the other decisions already made in GHC. Of course, one could add dominance scoping etc. to make an extension of SSA with more symmetry between producers and consumers like the classical sequent calculus.
The C in CPS and the cc in call/cc are exactly the same thing.
It’s a continuation. You don’t need to express your program in continuation passing style to use continuation which is why call/cc exists.
The idea of continuation is interesting in and of itself independently of if your compiler uses CPS because continuation as a concept is useful. It appears in effect system for exemple.
Apple book is very good by the way. It gives a very hand on overview of how to implement a compiler in a functional style and neatly introduces some quite complex ideas. To me it’s amongst the books you can’t regret reading also it’s quite short and easy which helps. Timeless classic like Peyton Jones The implementation of functional programming languages and is great introduction to lambda calculus and presentation of how to implement a type checker in Miranda.
It’s a continuation. You don’t need to express your program in continuation passing style to use continuation which is why call/cc exists.
The idea of continuation is interesting in and of itself independently of if your compiler uses CPS because continuation as a concept is useful. It appears in effect system for exemple.
Apple book is very good by the way. It gives a very hand on overview of how to implement a compiler in a functional style and neatly introduces some quite complex ideas. To me it’s amongst the books you can’t regret reading also it’s quite short and easy which helps. Timeless classic like Peyton Jones The implementation of functional programming languages and is great introduction to lambda calculus and presentation of how to implement a type checker in Miranda.
It might be a cool book but it describes an outdated way to write compilers, even if you’re writing compilers for functional languages
What does that mean?
The book introduces how to turn a program to CPS, why you can and how that allows to compile. That’s interesting in and of itself as a way to conceptualise how a program computation flows work and what it means for the construction of functional programs.
It was never a popular way to write compilers but academic books are not tutorial. That never was the point.
The book introduces how to turn a program to CPS, why you can and how that allows to compile. That’s interesting in and of itself as a way to conceptualise how a program computation flows work and what it means for the construction of functional programs.
It was never a popular way to write compilers but academic books are not tutorial. That never was the point.
CPS is not that different from SSA.
https://bernsteinbear.com/assets/img/kelsey-ssa-cps.pdf
https://bernsteinbear.com/assets/img/kelsey-ssa-cps.pdf
They are so extremely and utterly different.
CPS is an AST form with first class functions that don’t return. CPS is highly opinionated about how control flow is represented and not very opinionated about how data flow is represented (maybe it’s just variable names you resolve, maybe it’s data flow).
SSA is a data flow graph with a way to express looping. SSA isn’t very opinionated about control flow and different SSA implementations do it differently.
That paper is just saying that you can transform between the two. So what. Of course you can; you can transform between any Turing complete languages and that doesn’t make them “not that different” and definitely not the same.
CPS is an AST form with first class functions that don’t return. CPS is highly opinionated about how control flow is represented and not very opinionated about how data flow is represented (maybe it’s just variable names you resolve, maybe it’s data flow).
SSA is a data flow graph with a way to express looping. SSA isn’t very opinionated about control flow and different SSA implementations do it differently.
That paper is just saying that you can transform between the two. So what. Of course you can; you can transform between any Turing complete languages and that doesn’t make them “not that different” and definitely not the same.
> Call/cc has since (thankfully) become a lot less popular.
Delimited continuations are the state of the art now, aren't they?
Delimited continuations are the state of the art now, aren't they?
Dunno. I really dislike continuations (but like Appel's book(s)) so I haven't kept up. Also, Oleg has a reputation for invention type mountains for lots of molehill problems so I'm naturally inclined to dismiss his ideas pretty much out of hand.