I have a core IR that compiles to a ministg. I originally started with the Core defined in “Implementing Functional Languages: a tutorial” and later modified it to ape core (system F etc). Looking at papers like “compiling without continuations” you have an IR that is strongly normalized to ANF (ie App Expr Atom) which is contrary to ghc’s core which does not have this invariant. Is there an advantage to not being strongly normalized or was core not originally intended to be ANF?
1 Like
Not App Atom Atom?
One thing that SPJ told me is that it that it’s harder to apply some transformations if you’re in ANF, for example optimize let ys = map f xs in map g ys to map (g . f) xs. If it’s already in the form map g (map f xs) then it’s easier because you can just pattern match on it rather than having to deal with substitutions.
1 Like
Good catch, I was referring to App Expr Atom but yes it is wrong to call it strongly normalized. I mean more normalized than simply App Expr Expr. To make my question more clear it would be why do the papers limit the argument in an application to be an atom? Rather than declare it to be App Expr Expr like ghc does?
IIRC, GHC Core used to be in ANF back in the 90s. But many many of the let bindings introduced only ever had one occurrence. Every name introduced comes with an overhead when maintaining what names are in scope. Also every pass that introduces new subexpressions needs to allocate unused names, for which you need to know what is in scope.
Since ANF is only needed when fixing evaluation order, the conversion to ANF is only done immediately before translation to STG in a pass named CorePrep. Check GHCs output with -ddump-prep.
That said, as a consumer I like ANF. As a producer (I.e. optimisation pass), not so much.
6 Likes