4 ms·

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?

asplake 2y ago
“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.”
- fn-mote 2y ago
  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"?
Vosporos 2y ago
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://pauldownen.com/publications/anf-continued.pdf, https://www.reddit.com/r/ProgrammingLanguages/comments/13w3cw3/cps_vs_anf/jmd8op6/ https://www.reddit.com/r/ProgrammingLanguages/comments/13w3c... and https://langdev.stackexchange.com/a/2254 https://langdev.stackexchange.com/a/2254 (as well as https://www.college-de-france.fr/sites/default/files/media/document/2024-03/Leroy%202023-2024%20-%20S%C3%A9minaire%2022%20f%C3%A9vrier%20Kennedy.pdf https://www.college-de-france.fr/sites/default/files/media/d... as a bonus)
mrkeen 2y ago
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.
- fire_lake 2y ago
  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!
  - mrkeen 2y ago
    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.

asplake 2y ago

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

fn-mote 2y ago
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"?

Vosporos 2y ago

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://pauldownen.com/publications/anf-continued.pdf, https://www.reddit.com/r/ProgrammingLanguages/comments/13w3cw3/cps_vs_anf/jmd8op6/ https://www.reddit.com/r/ProgrammingLanguages/comments/13w3c... and https://langdev.stackexchange.com/a/2254 https://langdev.stackexchange.com/a/2254 (as well as https://www.college-de-france.fr/sites/default/files/media/document/2024-03/Leroy%202023-2024%20-%20S%C3%A9minaire%2022%20f%C3%A9vrier%20Kennedy.pdf https://www.college-de-france.fr/sites/default/files/media/d... as a bonus)

mrkeen 2y ago

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.

fire_lake 2y ago
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!
- mrkeen 2y ago
  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.