I've spent some time looking into how other compilers handle their ASTs to see if there is something we could learn or improve our current design. I'm listing my findings here and make a few suggestions to hopefully get some feedback/discussion from you folks :)

Current shortcomings

I'll start out motivating this disussion by talking about some of the shortcomings/problems I ran into with our current AST types.

• A lot of functions that operate on our AST are partial, because only subsets of the available constructors can appear in certain stages of compilation.

• We don't have "record" labels for our AST datatypes, because they would be partial accessors, since our datatypes are huge sums. This means one needs a lot of lookups in the documentation when pattern matching, and all the pattern matches have to be updated when new fields are added. (The recent SourceSpan addition PRs from Gary are a good example of the problems this causes)

• There's no way for our AST nodes to refer to another node that is a parent or higher up in the hierarchy. This is fine when doing the kind of desugaring top-down traversals we do in the compiler, but it doesn't work as well if I find a node in the hierarchy (for example by matching on a source position) and now try to collect data starting from that node

• Our AST lacks the ability to accurately describe the source it was parsed from (because some desugarings already happen during parsing). This means our AST is not well suited to writing a formatter or other tooling that tries to operate on the AST and translate the results back into source code.

Proposals/Potential changes

I'll now outline some of the modifications I've thought of, that could solve/make it easier to solve some of the problems I outlined.

Extract our individual variants into their own datatypes

I did a similar transformation for IDE's data types and it makes it possible to have record accessors and helper functions that operate on these types with a proper signature.

Eg:

data Declaration 
  = TypeDeclaration SSpan Ident Type 
  | ...

pprintTypeDeclaration :: (SSpan, Ident, Type) -> Text

-- vs:

data Declaration 
  = DTypeDeclaration TypeDeclaration 
  | ...
data TypeDeclaration = TypeDeclaration
  { tdSpan :: SSPan
  , tdIdentifier :: Ident
  , tdType :: Type
  }

pprintTypeDeclaration :: TypeDeclaration -> Text

While this involves a fair bit of boilerplate it makes it easier to pass around proof that a certain pattern match has already been done. It also makes it easier to build sums for subsets of all the different Declarations, and still allows me to use the utility functions defined for individual Declarations. In IDE's code the boilerplate pain is mitigated by using Prisms, which would increase the barrier of entry for new contributors. Maybe something could be done with patterns instead.

Introduce a node index

Concretely this should be a (memory efficient) key which allows us to refer to nodes in the parsed ASTs with a global lookup table to get a hold of these nodes.

I've recently experimented with the depth first index (inspired by a paper I recently read: AST Indexing). If we additionally collect the number of descendants for each node we'd get a data structure that would be a lot faster for some of the linting passes we do on top.

The DFI doesn't "survive" our desugaring passes though, as we change the structure of the AST. If we wanted to keep some kind of index all the way through the type checking process we'd either need some kind of globally unique key (through a SupplyT which is available through the entire compilation), UUIDs, or we'd need to be really smart about updating the DFIs as we desugar. The DFI and descendant count would ideally be stored with the node, which would be a potential candidate for something to fit in a type parameter slot.

Add new constructors for some of our source constructs

For example we have an Abs constructor which represents a lambda of a single argument. During parsing we turn \x y -> ... into Abs x (Abs y ...) which makes it indistinguishable from \x -> \y -> .... I think we should either augment Abs to take multiple arguments or (my preferred solution) add a MultiAbs constructor. There are a few more cases of this around record sugar.

Now for a couple of observations about other ASTs

AST Design

Clang

Clang uses inheritance heavily and has a "God object" in the ASTContext, which eg. has a method called getParents, which handles the reverse lookup for nodes.

Rust

The primary observation I made here, is that Rust uses Visitors extensively (just like Clang), which was surprising, because I thought that pattern would be tied to OO. Our equivalent are the Traversals.

Elm

Elm has three different ASTs. One after parsing, one after renaming/desugaring and one after optimizing. We use our first AST representation for both the parsing as well as the renaming/desugaring.

Strings

Rust and Clang

Both Rust as well as Clang have a singleton which manages source files and maps locations to strings. They then store the offsets in the AST nodes instead, to keep their size small.

GHC's FastString

GHC also eschews ByteString/Text for storing Text in the AST and uses its own FastString instead, which is a hash consed String implementation (in short, a global shared hashmap from Strings to hashes, where only the hashes are stored in the nodes and then looked in the global map, thus reducing the memory required for storing the same string over and over, while keeping fast equality comparisons without lookups). It's noteworthy that the FastString type caused issues for GHC, because of the global shared nature of the backing hashmap, when they tried to parallelize the compiler (See Crime Doesn't Pay).

Elm

Elm uses Text in its Nodes, just like we do.

I have a lot more observations about the other ASTs, but I think they just add noise for now. I'm happy to write them down once we focus on a specific topic.