4 ms·

Compiling with Continuations

82 points by swatson741 1y ago

matheusmoreira 1y ago
> 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.
- gsf_emergency_2 1y ago
  Have been many, for the book the post is reviewing, eg. https://github.com/abeln/cc https://github.com/abeln/cc Blogger just didn't look hard enough (or doesn't know that search on GitHub is crippled, for reasons)
- enum 1y ago
  I learned a lot from implementing this book. Compiler was in OCaml. Runtime was in C (used as a glorified assembly).
  - matheusmoreira 1y ago
    > 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-garbage-collector/ https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga... https://www.wingolog.org/archives/2010/02/26/guile-and-delimited-continuations https://www.wingolog.org/archives/2010/02/26/guile-and-delim...
    - StopDisinfo910 1y ago
      It’s an extremely common language to write compilers in. The original Rust compiler was written in it for exemple.
- pjmlp 1y ago
  Github is not the universe.
- rurban 1y ago
  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.
peterfirefly 1y ago
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 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.
- pizlonator 1y ago
  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
  - StopDisinfo910 1y ago
    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.
mrkeen 1y ago
> 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: 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)” (...which TFA characterised as "parody") 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).
tikotus 1y ago
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.
- matheusmoreira 1y ago
  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?
  - tikotus 1y ago
    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.
dmvdoug 1y ago
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).
- antonvs 1y ago
  Beowulf really doesn’t stand up to the Marvel franchise. Alternatively, OP might have a bit of learning still to do.
whizzter 1y ago
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.

82 points by swatson741 1y ago

> 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.

gsf_emergency_2 1y ago
Have been many, for the book the post is reviewing, eg. https://github.com/abeln/cc https://github.com/abeln/cc Blogger just didn't look hard enough (or doesn't know that search on GitHub is crippled, for reasons)
enum 1y ago
I learned a lot from implementing this book. Compiler was in OCaml. Runtime was in C (used as a glorified assembly).
- matheusmoreira 1y ago
  > 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-garbage-collector/ https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga... https://www.wingolog.org/archives/2010/02/26/guile-and-delimited-continuations https://www.wingolog.org/archives/2010/02/26/guile-and-delim...
  - StopDisinfo910 1y ago
    It’s an extremely common language to write compilers in. The original Rust compiler was written in it for exemple.
pjmlp 1y ago
Github is not the universe.
rurban 1y ago
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.

peterfirefly 1y ago

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 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.

pizlonator 1y ago
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
- StopDisinfo910 1y ago
  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.

mrkeen 1y ago

> 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: 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)” (...which TFA characterised as "parody") 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).

tikotus 1y ago

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.

matheusmoreira 1y ago
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?
- tikotus 1y ago
  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.

dmvdoug 1y ago

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).

antonvs 1y ago
Beowulf really doesn’t stand up to the Marvel franchise. Alternatively, OP might have a bit of learning still to do.

whizzter 1y ago

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.