It's interesting how diametrically opposed this is to my recent explorations ... and yet, this is far better than most if only because it points out some of the decisions that would be bad (or at least could be done differently) in production.
I've ranted extensively [1] about how badly interpreters (among adjacent topics) are often taught, because so often decisions are just abruptly made without explanation of the reasoning (or, often, even that a decision is being made!).
One thing I just added was that there are (at least) 6 "arities" (which really should not be called that) of bytecode/IR:
* stack output, stack input, stack input - though often a few instructions do take arguments (push, jump)
* accumulator output/input, 1 explicit input (usually a local variable or constant)
* belt output, belt input, 1 explicit input. The first argument is always the output of the previous instruction; the explicit argument (if not a constant) specifies the output of some previous instruction. Backwards jumps will require storing many variables to a prior part of the belt, but this is simple and useful for mini expression evaluators.
* explicit output/input, explicit input - common for machine code
* explicit output, explicit input, explicit input - common for machine code
* implicit output, explicit input, explicit input - an easy way to save space for SSA (though you can also use it with mutability), though there's weirdness for phis.
The author has mentioned ANF a few times but, from what I can tell, the likeness that they emphasise is really just the usual property of operands being atomic. This is a property used in many IRs, but I don't feel it's enough to describe Bril as being "an ANF language" - especially when you think about how tied ANF is to the functional compiler space.
The original ANF is actually looser than this in that it permits anonymous functions as arguments. In practice, there is no canonical variant of ANF that people really refer to, but most people usually mean a variant of ANF that doesn't permit this (which, to my knowledge, was first published in David Tarditi's PhD thesis). See this table from Appel's "Modern Compiler Implementation in ML" for the comparisons made in the functional IR space: https://i.imgur.com/17nfGMI.png.
Usually what people in the functional compiler space mean when they mention ANF is some variant of ANF (with Tarditi's restriction) that retains nested functions in a tree-like structure. The tree structure is important because it practically necessitates the extension of "join point"s within the tree structure (to act as local, second-class, continuations: to avoid duplicating evaluation contexts for multi-way branching constructs, without using functions for this purpose). It just so happens that you hoist ANF into a bunch of function bodies (which were once nested) and blocks (which were once join points), you can easily construct a control flow graph. However, you could also say that lambda calculus would be "in SSA" throughout all of this (as it is originally, then normalised into ANF, and then hoisted into a control flow graph) - it just isn't usually what people mean when they talk about an SSA IR (they tend to imply the existence of specific provisions for the splitting of live ranges at join points, be it a phi-like pseudo-instruction or block arguments).
All this is to say that ANF is very tied to literature about the compilation of functional languages and its related analysis and comparison with CPS (such as whether it's closed under beta-reduction, for example), such that I think we need to be a bit more precise about the expected shape and properties of IRs to differentiate them, rather than just expecting compiler engineers to know what you're talking about - and, indeed, agree with your description - when you describe something as "an ANF language".
> Bril’s SSA form needs a full rework, probably including an actual language extension along the lines of MLIR’s basic block arguments.
The linked MLIR documentation, in turn, credits Swift for that idea, but the earliest occurrence of phis as continuation arguments I know is in MLton. It’d be interesting to know where this idea comes from initially, because standard phis really are incredibly awkward.
This is super cool! It would be nice to have a simple C or Pascal frontend that generates Bril. Playing with optimization and code generation is a lot of fun, but it's hard to really dig into it without being able to test things on real-world, non-trivial code. You can use Clang and work in LLVM, of course, but that's an order of magnitude too complicated for an intro-level compilers course, IMHO.
I also like the decision to not have the IR always in SSA form. I think it helps you understand SSA form better to have to construct it, and you're going to have to eliminate SSA form anyway for any of the classic techniques for generating machine code.
o11c ·42 days ago
I've ranted extensively [1] about how badly interpreters (among adjacent topics) are often taught, because so often decisions are just abruptly made without explanation of the reasoning (or, often, even that a decision is being made!).
One thing I just added was that there are (at least) 6 "arities" (which really should not be called that) of bytecode/IR:
* stack output, stack input, stack input - though often a few instructions do take arguments (push, jump)
* accumulator output/input, 1 explicit input (usually a local variable or constant)
* belt output, belt input, 1 explicit input. The first argument is always the output of the previous instruction; the explicit argument (if not a constant) specifies the output of some previous instruction. Backwards jumps will require storing many variables to a prior part of the belt, but this is simple and useful for mini expression evaluators.
* explicit output/input, explicit input - common for machine code
* explicit output, explicit input, explicit input - common for machine code
* implicit output, explicit input, explicit input - an easy way to save space for SSA (though you can also use it with mutability), though there's weirdness for phis.
[1]: https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...
contificate ·42 days ago
The original ANF is actually looser than this in that it permits anonymous functions as arguments. In practice, there is no canonical variant of ANF that people really refer to, but most people usually mean a variant of ANF that doesn't permit this (which, to my knowledge, was first published in David Tarditi's PhD thesis). See this table from Appel's "Modern Compiler Implementation in ML" for the comparisons made in the functional IR space: https://i.imgur.com/17nfGMI.png.
Usually what people in the functional compiler space mean when they mention ANF is some variant of ANF (with Tarditi's restriction) that retains nested functions in a tree-like structure. The tree structure is important because it practically necessitates the extension of "join point"s within the tree structure (to act as local, second-class, continuations: to avoid duplicating evaluation contexts for multi-way branching constructs, without using functions for this purpose). It just so happens that you hoist ANF into a bunch of function bodies (which were once nested) and blocks (which were once join points), you can easily construct a control flow graph. However, you could also say that lambda calculus would be "in SSA" throughout all of this (as it is originally, then normalised into ANF, and then hoisted into a control flow graph) - it just isn't usually what people mean when they talk about an SSA IR (they tend to imply the existence of specific provisions for the splitting of live ranges at join points, be it a phi-like pseudo-instruction or block arguments).
All this is to say that ANF is very tied to literature about the compilation of functional languages and its related analysis and comparison with CPS (such as whether it's closed under beta-reduction, for example), such that I think we need to be a bit more precise about the expected shape and properties of IRs to differentiate them, rather than just expecting compiler engineers to know what you're talking about - and, indeed, agree with your description - when you describe something as "an ANF language".
Show replies
mananaysiempre ·42 days ago
The linked MLIR documentation, in turn, credits Swift for that idea, but the earliest occurrence of phis as continuation arguments I know is in MLton. It’d be interesting to know where this idea comes from initially, because standard phis really are incredibly awkward.
Show replies
rayiner ·41 days ago
I also like the decision to not have the IR always in SSA form. I think it helps you understand SSA form better to have to construct it, and you're going to have to eliminate SSA form anyway for any of the classic techniques for generating machine code.
fire_lake ·42 days ago
Now the main choices seem to be CPS (which is seeing a bit of a resurgence!) and SSA.
So why teach ANF?
Show replies