aliquote

< a quantity that can be divided into another a whole number of time />

July 9, 2021

(…) the biggest stylistic change that’s happened in GHC recently, I think, is the move towards this “trees that grow” idea. Now, trees that grow, you can search for that keyword as a paper on my homepage about it, is a way to make sort of extensible data types using Haskell. This is really useful for Haskell’s abstract syntax tree. Haskell has a very large concrete syntax and so, correspondingly, has a large abstract syntax, that is the internal data type that describes Haskell programs after you’ve passed them has dozens of data types and hundreds of constructors and GHC then, during its renaming and type checking phase, decorates this tree with lots of additional stuff: types and scopes, and all sorts of extra stuff get gets added onto the tree. So, at first, we had a tree that was just GHC specific, but then we realized increasingly that other people would like to parse Haskell themselves for other purposes, so what we really wanted was a sort of base library that contained the core abstract syntax tree with its dozens of data types and hundreds of constructors and then some way for GHC to customize that tree, to add all its decorations and that’s the trees that grow idea and that lives off type families. We use both type families and data families quite extensively to power the trees that grow idea. It’s not what type families and data families were originally intended for, you can use them for all sorts of things, but it’s a major application within GHC, and it’s pushed a sort of stylistic change through the compiler. — Past and Present of Haskell: Interview with Simon Peyton Jones