Bril: An Intermediate Language for Teaching Compilers

I thought that ANF is considered a dead-end?

Now the main choices seem to be CPS (which is seeing a bit of a resurgence!) and SSA.

So why teach ANF?

“I want students to feel the pain of working with non-SSA programs before the course introduces SSA. This frustration can help motivate why SSA is the modern consensus.”

ANF is very much not considered a dead-end. It is the opposite number of SSA from the Functional programming languages perspective. CPS overlaps with it but also has properties, like requiring whole-program transformation, that do not help with predicting the final shape of the program.

See https://pauldownen.com/publications/anf-continued.pdf, https://www.reddit.com/r/ProgrammingLanguages/comments/13w3c... and https://langdev.stackexchange.com/a/2254 (as well as https://www.college-de-france.fr/sites/default/files/media/d... as a bonus)

In case anyone else believed this was scarcasm, it is not. It is a direct and accurate quote from the article. Bril is not (always) SSA.

Here is a follow-up quote from the article.

> Unfortunately, this aftermarket SSA retrofit has been a huge headache. [...] I think my original design is fundamentally flawed; it was a mistake to treat phi semantically as “just another instruction” [...]. Bril’s SSA form needs a full rework [...]. It has been an interesting lesson for me that SSA comes with subtle design implications that are difficult to retrofit onto an existing mutation-oriented IL.

I don't know enough to know what to make of this and the accompanying bug reports. Perhaps just "stay away from Bril SSA"?

I attempted both when trying to implement a language, and I couldn't wrap my head around the typing of the term that CPS introduces, so I ended up going down the ANF road.

Appel has a book on compiling with CPS Compiling with Continuations. It’s implemented in SML so the types are front and center. Might be of use!

p225:

> However, having a typed CPS language would require the manipulation and reduction of types whenever B-reductions (and other transformations) are performed. Although this is certainly possible to do, it is painful enough that we have decided to avoided this approach.