name resolution

Sub-cards (0)Archived
Comments (3)

GitHub’s stack graphs


Avoid reallocation in name resolution.

GHC’s renamer takes a parsed syntax tree as input and produces (allocates) a renamed syntax tree, where every name has been assigned a unique identifier.

In an imperative language (with mutable data structures) we could preallocate a field in the AST for those unique identifiers, and name resolution would fill it in. I bet we could also do that in Haskell using lazy evaluation.

Profile picture

The size of the AST in memory is probably linear in the size of the input string.

So we can preallocate a contiguous chunk of memory for it even before parsing.