Elegant AST model

Question

I am in the process of writing a toy compiler in scala. The target language itself looks like scala but is an open field for experiment.

After several large refactorings I can't find a good way to model my abstract syntax tree. I would like to use the facilities of scala's pattern matching, the problem is that the tree carries moving information (like types, symbols) along the compilation process.

I can see a couple of solutions, none of which I like :

• case classes with mutable fields (I believe the scala compiler does this) : the problem is that those fields are not present a each stage of the compilation and thus have to be nulled (or Option'd) and it becomes really heavy to debug/write code. Moreover, if for exemple, I find a node with null type after the typing phase I have a really hard time finding the cause of the bug.

• huge trait/case class hierarchy : something like Node, NodeWithSymbol, NodeWithType, ... Seems like a pain to write AND work with

• something completly hand crafted with extractors

I'm also not sure if it is good practice to go with a fully immutable AST, especially in scala where there is no implicit sharing (because the compiler is not aware of immutability) and it could hurt performances to copy the tree all the time.

Can you think of an elegant pattern to model my tree using scala's powerful type system ?

Answer 1

TL;DR I prefer to keep the AST immutable and carry things like type information in a separate structure, e.g. a Map, that can be referred by IDs stored in the AST. But there is no perfect answer.

You're by no means the first to struggle with this question. Let me list some options:

1) Mutable structures that get updated at each phase. All the up and downsides you mention.

2) Traits/cake pattern. Feasible, but expensive (there's no sharing) and kinda ugly.

3) A new tree type at each phase. In some ways this is the theoretically cleanest. Each phase can deal only with a structure produced for it by the previous phase. Plus the same approach carries all the way from front end to back end. For instance, you may "desugar" at some point and having a new tree type means that downstream phase(s) don't have to even consider the possibility of node types that are eliminated by desugaring. Also, low level optimizations usually need IRs that are significantly lower level than the original AST. But this is also a lot of code since almost everything has to be recreated at each step. This approach can also be slow since there can be almost no data sharing between phases.

4) Label every node in the AST with an ID and use that ID to reference information in other data structures (maps and vectors and such) that hold information computed for each phase. In many ways this is my favorite. It retains immutability, maximizes sharing and minimizes the "excess" code you have to write. But you still have to deal with the potential for "missing" information that can be tricky to debug. It's also not as fast as the mutable option, though faster than any option that requires producing a new tree at each phase.

Answer 2

I recently started writing a toy verifier for a small language, and I am using the Kiama library for the parser, resolver and type checker phases.

Kiama is a Scala library for language processing. It enables convenient analysis and transformation of structured data. The programming styles supported by the library are based on well-known formal language processing paradigms, including attribute grammars, tree rewriting, abstract state machines, and pretty printing.

I'll try to summarise my (fairly limited) experience:

• [+] Kiama comes with several examples, and the main contributor usually responds quickly to questions asked on the mailing list

• [+] The attribute grammar paradigm allows for a nice separation into "immutable components" of the nodes, e.g., names and subnodes, and "mutable components", e.g., type information

• [+] The library comes with a versatile rewriting system which - so far - covered all my use cases

• [+] The library, e.g., the pretty printer, make nice examples of DSLs and of various functional patterns/approaches/ideas

• [-] The learning curve it definitely steep, even with examples and the mailing list at hand

• [-] Implementing the resolving phase in a "purely function" style (cf. my question) seems tricky, but a hybrid approach (which I haven't tried yet) seems to be possible

• [-] The attribute grammar paradigm and the resulting separation of concerns doesn't make it obvious how to document the properties nodes have in the end (cf. my question)

• [-] Rumour has it, that the attribute grammar paradigm does not yield the fastest implementations

Summarising my summary, I enjoy using Kiama a lot and I strongly recommend that you give it a try, or at least have a look at the examples.

(PS. I am not affiliated with Kiama)