▲ | pizlonator 3 days 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 | |||||||||||||||||
▲ | cwzwarich 3 days ago | parent | next [-] | ||||||||||||||||
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. | |||||||||||||||||
▲ | StopDisinfo910 3 days ago | parent | prev | next [-] | ||||||||||||||||
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. | |||||||||||||||||
| |||||||||||||||||
▲ | peterfirefly 3 days ago | parent | prev [-] | ||||||||||||||||
CPS is not that different from SSA. | |||||||||||||||||
|