It's not true that you need to use CPS to implemented first-class continuations. There are plenty of slow ways to do it, and even if you want to be fast you can do multiple different things. Dybvig describes a number of options in his thesis: https://www.cs.unc.edu/xcms/wpfiles/dissertations/dybvig.pdf
Sam will definitely know more about this than I will, so if he contradicts me, listen to him.
If I am not mistaken, the racket language does not convert to CPS during compilation. Instead, when you want to get the continuation, I think you just get a pointer to the stack frame that you want. All I know for sure is that it uses something called a-normal form, which is kind of like SSA in some ways, and that the continuation is 2x 64/32-bit words depending on your architecture.
Very true but the other side of this is first class continuations are no worse than compiling try-catch semantics, and hygienic macros are still just macros so the complexity is kept simple (sort of. maybe simple isn't always so simple).
The other thing that makes languages like scheme difficult to compile are those closures. In fact, the book, the implementation of functional programming languages, Jones (1987) didn't do it at all! No closure conversion at all. They just compiled to a letrec in the g-machine.
As far as compiling continuations goes, sequent calculus (specifically as a compiler IR) is an interesting research direction. See Grokking the Sequent Calculus (Functional Pearl) from ICFP 2024: https://dl.acm.org/doi/abs/10.1145/3674639
"This becomes clearer with an example: When we want to evaluate the expression (2 + 3) ∗ 5,
we first have to focus on the subexpression 2 + 3 and evaluate it to its result 5. The remainder
of the program, which will run after we have finished the evaluation, can be represented with
the evaluation context □ ∗ 5. We cannot bind an evaluation context like □ ∗ 5 to a variable in
the lambda calculus, but in the λμ~μ-calculus we can bind such evaluation contexts to covariables.
Furthermore, the μ-operator gives direct access to the evaluation context in which the expression
is currently evaluated.
Having such direct access to the evaluation context is not always necessary for a programmer who wants to write an application, but it is often important for compiler implementors who write optimizations to make programs run faster. One solution that compiler writers use to represent evaluation contexts in the lambda calculus is called continuation-passing style. In continuation-passing style, an evaluation context like □ ∗ 5 is represented as a function λ x . x ∗ 5. This solution works, but the resulting types which are used to type a program in this style are arguably hard to understand. Being able to easily inspect these types can be very valuable, especially for intermediate representations, where terms tend to look complex. The promise of the λμ~μ-calculus is to provide the expressive power of programs in continuation-passing style without having to deal with the type-acrobatics that are usually associated with it."
"In some sense the Sequent Calculus (SC) is quite similar to a CPS based IR. To sum up the benefits of SC over CPS in two concepts, I would say: Symmetry and non-opaque continuations.
Symmetry: A lot of pairs of dual concepts are modelled very naturally and symmetrically in SC: call-by-value and call-by-name, data types and codata types, exception based error handling and Result-type error handling, for example.
Non-Opaque continuations: Instead of continuations in CPS which are just a special kind of function whose internals cannot be inspected (easily), SC introduces consumers whose internal structure can be inspected easily, for example when writing optimization passes."
There's an OOPSLA paper (referred to from the link starting that thread) from this year with 2 of the same authors that goes into more detail about using it as a compiler IR: https://dl.acm.org/doi/10.1145/3720507
Bug: The `list-iter` function presented assumes that an empty list is false. While that's the case in Common Lisp, it isn't in Scheme (and hasn't been in a very long time; iirc in early versions it was optional behavior).
Speaking from personal experience, Scheme looks deceptively simple but it is one of the hardest languages to write a compiler for.
I say this mainly because of 2 things:
1. Hygienic Macros (You practically have a whole another language inside the language)
2. First Class Continuations (There is no good way to achieve this other than doing a CPS transform on the AST)
It's not true that you need to use CPS to implemented first-class continuations. There are plenty of slow ways to do it, and even if you want to be fast you can do multiple different things. Dybvig describes a number of options in his thesis: https://www.cs.unc.edu/xcms/wpfiles/dissertations/dybvig.pdf
Sam will definitely know more about this than I will, so if he contradicts me, listen to him.
If I am not mistaken, the racket language does not convert to CPS during compilation. Instead, when you want to get the continuation, I think you just get a pointer to the stack frame that you want. All I know for sure is that it uses something called a-normal form, which is kind of like SSA in some ways, and that the continuation is 2x 64/32-bit words depending on your architecture.
CPS transforms are not the only way; if you translate the scheme to bytecode for a virtual machine, the call stack and IP can be reified.
But yes, for a compiler specifically, you need a CPS transformation
CPS transformation is a good thing to do anyway, no? Then CPS your CPS and you have delimited continuations.
Go straight for delimited continuations, which give you global ones for free.
Oh. I meant not using call/cc, but by doing local CPS transformations. This is the simple way, but has limitations with dynamic uses of reset.
A direct implementation is harder, but probably more useful.
Very true but the other side of this is first class continuations are no worse than compiling try-catch semantics, and hygienic macros are still just macros so the complexity is kept simple (sort of. maybe simple isn't always so simple).
The other thing that makes languages like scheme difficult to compile are those closures. In fact, the book, the implementation of functional programming languages, Jones (1987) didn't do it at all! No closure conversion at all. They just compiled to a letrec in the g-machine.
As far as compiling continuations goes, sequent calculus (specifically as a compiler IR) is an interesting research direction. See Grokking the Sequent Calculus (Functional Pearl) from ICFP 2024: https://dl.acm.org/doi/abs/10.1145/3674639
"This becomes clearer with an example: When we want to evaluate the expression (2 + 3) ∗ 5, we first have to focus on the subexpression 2 + 3 and evaluate it to its result 5. The remainder of the program, which will run after we have finished the evaluation, can be represented with the evaluation context □ ∗ 5. We cannot bind an evaluation context like □ ∗ 5 to a variable in the lambda calculus, but in the λμ~μ-calculus we can bind such evaluation contexts to covariables. Furthermore, the μ-operator gives direct access to the evaluation context in which the expression is currently evaluated.
Having such direct access to the evaluation context is not always necessary for a programmer who wants to write an application, but it is often important for compiler implementors who write optimizations to make programs run faster. One solution that compiler writers use to represent evaluation contexts in the lambda calculus is called continuation-passing style. In continuation-passing style, an evaluation context like □ ∗ 5 is represented as a function λ x . x ∗ 5. This solution works, but the resulting types which are used to type a program in this style are arguably hard to understand. Being able to easily inspect these types can be very valuable, especially for intermediate representations, where terms tend to look complex. The promise of the λμ~μ-calculus is to provide the expressive power of programs in continuation-passing style without having to deal with the type-acrobatics that are usually associated with it."
A brief summary of the SC-as-a-compiler-IR vs. CPS from one of the authors of the paper: https://types.pl/@davidb/115186178751455630
"In some sense the Sequent Calculus (SC) is quite similar to a CPS based IR. To sum up the benefits of SC over CPS in two concepts, I would say: Symmetry and non-opaque continuations.
Symmetry: A lot of pairs of dual concepts are modelled very naturally and symmetrically in SC: call-by-value and call-by-name, data types and codata types, exception based error handling and Result-type error handling, for example.
Non-Opaque continuations: Instead of continuations in CPS which are just a special kind of function whose internals cannot be inspected (easily), SC introduces consumers whose internal structure can be inspected easily, for example when writing optimization passes."
There's an OOPSLA paper (referred to from the link starting that thread) from this year with 2 of the same authors that goes into more detail about using it as a compiler IR: https://dl.acm.org/doi/10.1145/3720507
Use someone else's implementation of the macro stuff and focus on the compiler.
This is part two of a seminar series:
https://people.csail.mit.edu//jhbrown/scheme/
Bug: The `list-iter` function presented assumes that an empty list is false. While that's the case in Common Lisp, it isn't in Scheme (and hasn't been in a very long time; iirc in early versions it was optional behavior).
Slides author here. Thanks for flagging that. I'll fix it before I give the talk again, most likely in 2044 :)
Don't feel compelled to rush into giving it again that soon just because it got shared on HN.
FYI, all the links in your bio 404.
You should all have a look at Oleg Kiselyov's speech about continuations at Dan Friedman's 60th birthday. That is some next level shit.
Thanks for the heads up.