<h2>Motivation</h2>
<p>CPS(Continuation-Passing Style), SSA(Static Single Assignment), ANF(A-Normal Form) are three common forms of IR(Intermediate Representation).</p>
<p>I find it very convenient to describe and rewrite complex control flow across functions in CPS, so I'm rewriting my intermediate representation to CPS form now.</p>
<p>But it seems that very few compilers use CPS as IR, as far as I know only <code>Chez</code>.</p>
<ul>
<li>As a backend for many procedural languages, <code>LLVM</code> and <code>GCC</code> uses SSA.</li>
<li><code>HotSpot VM</code>, a mainstream implementation of the OOP language Java, also uses SSA.</li>
<li><code>GHC</code>, as the backend of the pure functional language Haskell, does not adopt CPS as IR.</li>
</ul>
<h2>Question</h2>
<p>So I wonder if there is any weakness in pure CPS that is causing people to abandon CPS.</p>
<h2>Related</h2>
<ul>
<li><a href="https://langdev.stackexchange.com/questions/1441/what-are-the-disadvantages-of-using-ssa-form">What are the disadvantages of using SSA form?</a></li>
</ul>

<intermediate-representation><continuation-passing-style>
What are the disadvantages of using CPS form?
CC BY-SA 4.0
2023-07-06T23:13:30.070Z
CPS is more or less `goto`, and is rather hard to analyse. Not sure how that affects using it for IR though
Bergi
CC BY-SA 4.0
2023-07-07T01:32:53.973Z
@Bergi No, the equivalent of `goto` is `call/cc`
Aster
CC BY-SA 4.0
2023-07-07T01:45:50.787Z
For Haskell, the laziness is probably more important than the purity when it comes to IR design. It doesn't have the usual notions of "control flow".
hugomg
CC BY-SA 4.0
2023-07-07T13:27:26.290Z
Would C interop be a problem? C error handling is already non-idiomatic in basically every other language, but I'm not sure how to reconcile the way C's `return` works with CPS.
Bbrk24
<p>The widely used SSA is <a href="https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/kelsey-ssa-cps.pdf" rel="nofollow noreferrer">equivalent</a> to a restricted subset of CPS, so one can argue that CPS is indeed very popular.</p>
<p>For the more generic and unrestricted CPS, it is not practical for most languages as there's runtime cost for converting all your function calls to continuation-passing style, so restricting the CPS/SSA conversion to only function local scope makes sense.</p>
<p>Scheme implementations use a full CPS mainly because continuations are first class and mandatory anyway, so it worth paying the performance penalty for having them.</p>

CC BY-SA 4.0
2023-07-09T11:07:02.833Z
2023-07-09T11:07:02.833Z
SK-logic
CC BY-SA 4.0
2023-07-10T02:50:48.493Z
The runtime overhead is not justified, can a language produce different assembly or bytecode because it uses a different IR?
Aster
<p>Historically, the first significant compiler to use CPS was Rabbit, for Scheme, in 1978.  This allowed all function calls to become tail calls at the end of blocks, and proved that a Lisp dialect with lexical scoping could be efficient.  Both ANF and SSA came later, and <a href="https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/kelsey-ssa-cps.pdf" rel="noreferrer">there are algorithms to convert between them and a powerful-enough subset of CPS,</a> so compilers choose whichever one is more convenient to work with.</p>
<p>Scheme is a functional language, and this form has mostly been used for functional languages.  It is a better fit for functional languages, where undergrads typically learn how to transform functional code by hand, by turning the function calls inside-out, than for the control structures of imperative languages, whose functions might not even support tail-call optimization.  For these, it is more intuitive to transform blocks into a control graph, and transform blocks into phi-functions if necessary.</p>
<p>Cong <em>et al.</em> wrote <a href="https://www.cs.purdue.edu/homes/rompf/papers/cong-icfp19.pdf" rel="noreferrer">a paper in 2019</a> going over the reasons why CPS, ANF and SSA have gone in and out of style.  They say of CPS:</p>
<blockquote>
<p>In these compilers, many optimizations can be described as a sequence of full <em>β</em> and <em>η</em> steps, which are always <em>sound</em> and often come with <em>shrinking guarantees</em>. While this is a direct benefit obtained from explicit continuations, they may as well make it harder to recover specific information from the source program. An instance of this is the uniform representation of ordinary functions and continuations as jumps. Since the latter are guaranteed not to escape, a compiler must avoid allocating closure records for them.</p>
</blockquote>
<p>They say of ANF, which wasn’t as widely-used in real compilers,</p>
<blockquote>
<p>Since an ANF-based IR remains in direct style, we can more easily identify parts of the program that are subject to optimization. Nevertheless, ANF suffers from two problems that would not arise in CPS. First, ANF is not closed under reduction, and hence requires an additional re-normalization step for subsequent optimizations. Second, ANF lacks a facility for modeling jumps, which is crucial for converting recursive functions into loops, and for representing <em>join points</em> that arise in case-like constructs.</p>
</blockquote>
<p>Andrew Kennedy <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2007/10/compilingwithcontinuationscontinued.pdf" rel="noreferrer">wrote about the disadvantages of ANF relative to CPS in more detail in 2007.</a></p>
<p>You mention GHC, which is a very well-documented example.  So let’s look at some of that history.</p>
<p>GHC first <a href="https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/cps" rel="noreferrer">used CPS to get an IR called C-- or Cmm </a> (“In a word, it does CPS conversion.  All right, that’s two words.”), and then converts it to <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/1998/09/comp-by-trans-scp.pdf" rel="noreferrer">an intermediate language named Core</a>, which then outputs LLVM or C.  Core, as described on page 4, is essentially equivalent to SSA, although, due to how it is generated, has lambdas rather than blocks or φ-functions.  Indeed, you can use <a href="https://discourse.haskell.org/t/ghc-core-stg-and-cmm-views-on-compiler-explorer/4494" rel="noreferrer">the Godbolt compiler explorer to display either of these intermediate representations.</a></p>
<p>In 2017, GHC <a href="https://dl.acm.org/doi/pdf/10.1145/3062341.3062380" rel="noreferrer">was reworked to use what Maurer <em>et al.</em> describe</a> as “a modest extension to a direct-style λ-calculus intermediate language, namely adding join points.”  The motivation for this is explained in section 2 of the paper, and has to do with preserving information needed to optimize case expressions.  In section 8, “Why Not Use Continuation-Passing Style?” Maurer <em>et al.</em> list several reasons which I’ll summarize here.</p>
<blockquote>
<ul>
<li>Direct style is, well, more direct. Programs are simply easier to understand, and the compiler’s optimizations are easier to follow. [...]</li>
<li>The translation into CPS encodes a particular order of evaluation, whereas direct style does not. That dramatically inhibits code-motion transformations.  [...]</li>
<li>Some transformations are much harder in CPS. For example, consider common sub-expression elimination (CSE). [...]</li>
<li>[...] nested function applications are more difficult to spot. Also, rule matching is simply easier to reason about when the rules are written in more-or-less the same syntax as the intermediate language, but CPS makes radical changes compared to the source language.</li>
</ul>
</blockquote>
<p>The join-point optimizations can be done in CPS instead.  For example,  <a href="https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/contification.pdf" rel="noreferrer">Fluct and Weeks in 2001 had a very similar treatment of join points, but in CPS rather than SSA.</a></p>
<p>Another motivation that these authors so far have barely mentioned, if at all, is to be able to use the LLVM or GCC backends, both of which take SSA.  <a href="http://l-lang.org/blog/CPS-to-LLVM-SSA-conversion-in-literate-programming/" rel="noreferrer">Some compiler projects which start with a CPS IR</a> therefore convert it to SSA, which is straightforward, for the sake of interfacing with LLVM.</p>
<p>One interesting wrinkle that I have not seen much discussion of in this literature is the <code>async</code> or <code>yield</code> <a href="https://vkontech.com/exploring-the-async-await-state-machine-main-workflow-and-state-transitions/" rel="noreferrer">state machines of C#</a>, which have a great deal of resemblance to CPS.  It might therefore be a more natural fit for them.</p>

CC BY-SA 4.0
2023-07-10T04:16:33.323Z
2023-07-10T04:58:20.887Z
2023-07-10T04:58:20.887Z
Davislor
CC BY-SA 4.0
2023-07-10T09:42:49.320Z
I don't think it is necessary to use a state machine. If all CPS forms are used, only call/cc is required.
And compared to the State Machine, it is better to say that it is a Continuation Map.
Aster
CC BY-SA 4.0
2023-07-10T15:19:19.720Z
@Aster CPS would be an alternative to what C# currently does, or CPS transformation during compilation might be an efficient way to implement what it does now. Generators in particular are very similar to the lazily-evaluated thunks of lists in Haskell.
Davislor
# What are the disadvantages of using CPS form?
Posted by: username_0 on 2023-07-06
## Motivation

CPS(Continuation-Passing Style), SSA(Static Single Assignment), ANF(A-Normal Form) are three common forms of IR(Intermediate Representation).

I find it very convenient to describe and rewrite complex control flow across functions in CPS, so I'm rewriting my intermediate representation to CPS form now.

But it seems that very few compilers use CPS as IR, as far as I know only `Chez`.

* As a backend for many procedural languages, `LLVM` and `GCC` uses SSA.
* `HotSpot VM`, a mainstream implementation of the OOP language Java, also uses SSA.
* `GHC`, as the backend of the pure functional language Haskell, does not adopt CPS as IR.

## Question

So I wonder if there is any weakness in pure CPS that is causing people to abandon CPS.

## Related

* [What are the disadvantages of using SSA form?](https://langdev.stackexchange.com/questions/1441/what-are-the-disadvantages-of-using-ssa-form)
**Tags:** intermediate-representation continuation-passing-style
> **Comments:**
> **username_1**: CPS is more or less `goto`, and is rather hard to analyse. Not sure how that affects using it for IR though  
> **username_0**: @Bergi No, the equivalent of `goto` is `call/cc`  
> **username_2**: For Haskell, the laziness is probably more important than the purity when it comes to IR design. It doesn't have the usual notions of "control flow".  
> **username_3**: Would C interop be a problem? C error handling is already non-idiomatic in basically every other language, but I'm not sure how to reconcile the way C's `return` works with CPS.  
---
## 2 answers
### Answer by username_5 on 2023-07-10. Score: 8
Historically, the first significant compiler to use CPS was Rabbit, for Scheme, in 1978. This allowed all function calls to become tail calls at the end of blocks, and proved that a Lisp dialect with lexical scoping could be efficient. Both ANF and SSA came later, and [there are algorithms to convert between them and a powerful-enough subset of CPS,](https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/kelsey-ssa-cps.pdf) so compilers choose whichever one is more convenient to work with.

Scheme is a functional language, and this form has mostly been used for functional languages. It is a better fit for functional languages, where undergrads typically learn how to transform functional code by hand, by turning the function calls inside-out, than for the control structures of imperative languages, whose functions might not even support tail-call optimization. For these, it is more intuitive to transform blocks into a control graph, and transform blocks into phi-functions if necessary.

Cong *et al.* wrote [a paper in 2019](https://www.cs.purdue.edu/homes/rompf/papers/cong-icfp19.pdf) going over the reasons why CPS, ANF and SSA have gone in and out of style. They say of CPS:

> In these compilers, many optimizations can be described as a sequence of full *β* and *η* steps, which are always *sound* and often come with *shrinking guarantees*. While this is a direct benefit obtained from explicit continuations, they may as well make it harder to recover specific information from the source program. An instance of this is the uniform representation of ordinary functions and continuations as jumps. Since the latter are guaranteed not to escape, a compiler must avoid allocating closure records for them.

They say of ANF, which wasn’t as widely-used in real compilers,

> Since an ANF-based IR remains in direct style, we can more easily identify parts of the program that are subject to optimization. Nevertheless, ANF suffers from two problems that would not arise in CPS. First, ANF is not closed under reduction, and hence requires an additional re-normalization step for subsequent optimizations. Second, ANF lacks a facility for modeling jumps, which is crucial for converting recursive functions into loops, and for representing *join points* that arise in case-like constructs.

Andrew Kennedy [wrote about the disadvantages of ANF relative to CPS in more detail in 2007.](https://www.microsoft.com/en-us/research/wp-content/uploads/2007/10/compilingwithcontinuationscontinued.pdf)

You mention GHC, which is a very well-documented example. So let’s look at some of that history.

GHC first [used CPS to get an IR called C-- or Cmm](https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/cps)  (“In a word, it does CPS conversion. All right, that’s two words.”), and then converts it to [an intermediate language named Core](https://www.microsoft.com/en-us/research/wp-content/uploads/1998/09/comp-by-trans-scp.pdf), which then outputs LLVM or C. Core, as described on page 4, is essentially equivalent to SSA, although, due to how it is generated, has lambdas rather than blocks or φ-functions. Indeed, you can use [the Godbolt compiler explorer to display either of these intermediate representations.](https://discourse.haskell.org/t/ghc-core-stg-and-cmm-views-on-compiler-explorer/4494)

In 2017, GHC [was reworked to use what Maurer *et al.* describe](https://dl.acm.org/doi/pdf/10.1145/3062341.3062380) as “a modest extension to a direct-style λ-calculus intermediate language, namely adding join points.” The motivation for this is explained in section 2 of the paper, and has to do with preserving information needed to optimize case expressions. In section 8, “Why Not Use Continuation-Passing Style?” Maurer *et al.* list several reasons which I’ll summarize here.

> * Direct style is, well, more direct. Programs are simply easier to understand, and the compiler’s optimizations are easier to follow. [...]
> * The translation into CPS encodes a particular order of evaluation, whereas direct style does not. That dramatically inhibits code-motion transformations. [...]
> * Some transformations are much harder in CPS. For example, consider common sub-expression elimination (CSE). [...]
> * [...] nested function applications are more difficult to spot. Also, rule matching is simply easier to reason about when the rules are written in more-or-less the same syntax as the intermediate language, but CPS makes radical changes compared to the source language.

The join-point optimizations can be done in CPS instead. For example, [Fluct and Weeks in 2001 had a very similar treatment of join points, but in CPS rather than SSA.](https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/contification.pdf)

Another motivation that these authors so far have barely mentioned, if at all, is to be able to use the LLVM or GCC backends, both of which take SSA. [Some compiler projects which start with a CPS IR](http://l-lang.org/blog/CPS-to-LLVM-SSA-conversion-in-literate-programming/) therefore convert it to SSA, which is straightforward, for the sake of interfacing with LLVM.

One interesting wrinkle that I have not seen much discussion of in this literature is the `async` or `yield` [state machines of C#](https://vkontech.com/exploring-the-async-await-state-machine-main-workflow-and-state-transitions/), which have a great deal of resemblance to CPS. It might therefore be a more natural fit for them.
> **Comments:**
> **username_0** (2023-07-10): I don't think it is necessary to use a state machine. If all CPS forms are used, only call/cc is required.
And compared to the State Machine, it is better to say that it is a Continuation Map.  
> **username_5** (2023-07-10): @Aster CPS would be an alternative to what C# currently does, or CPS transformation during compilation might be an efficient way to implement what it does now. Generators in particular are very similar to the lazily-evaluated thunks of lists in Haskell.  
---
### Answer by username_4 on 2023-07-09. Score: 3
The widely used SSA is [equivalent](https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/kelsey-ssa-cps.pdf) to a restricted subset of CPS, so one can argue that CPS is indeed very popular.

For the more generic and unrestricted CPS, it is not practical for most languages as there's runtime cost for converting all your function calls to continuation-passing style, so restricting the CPS/SSA conversion to only function local scope makes sense.

Scheme implementations use a full CPS mainly because continuations are first class and mandatory anyway, so it worth paying the performance penalty for having them.
> **Comments:**
> **username_0** (2023-07-10): The runtime overhead is not justified, can a language produce different assembly or bytecode because it uses a different IR?  
---
