<p>I'm working on a language that transpiles to Lua, and writing the transpiler in Kotlin. One problem I'm having is that I simply have too many AST types. I have an untyped AST, a typed AST, and a Lua pseudo-AST. I have considered adding an IR too. Additionally, a lot of these ASTs have duplicated fields. Most of the typed AST is identical to the untyped one with the exception of a <code>type</code> field. What strategies can I use to limit the amount of such code duplication?</p>

<implementation><abstract-syntax-tree>
How can I reduce the amount of AST duplication in my code?
CC BY-SA 4.0
2023-05-27T19:16:49.583Z
If you merge the untyped AST with the typed AST, you  can make the `type` field optional. That's what I do in my AST...
Hydroper
CC BY-SA 4.0
2023-06-13T12:51:17.157Z
Take a look at Nanopass framework (on top of Scheme), or specialised languages like https://github.com/combinatorylogic/mbase - where AST handling is a first-class feature. Kotlin and other OO languages are not really well suited for such things.
SK-logic
CC BY-SA 4.0
2023-08-18T03:31:47.250Z
I think this blog post is also a good resource on the question specifically, although maybe a bit light on details: http://blog.ezyang.com/2013/05/the-ast-typing-problem/
quiet_laika
<h3>Code generation</h3>
<p>This isn't always applicable, but AST-related boilerplate code can be generated from a more concise notion. This is what <a href="https://github.com/python/cpython/blob/main/Parser/Python.asdl" rel="noreferrer">Python does</a> (using the ASDL format). Your definition grammar could allow to specify AST subforms and variations in a more convenient manner.</p>
<p>I should, however, note that I'm not familiar with any existent DSL that would be capable of this, so you'll most likely have to write it yourself. Maybe use the Kotlin Annotation Processor to integrate that DSL into your existent code base more conveniently</p>

CC BY-SA 4.0
2023-05-27T20:12:19.337Z
2023-05-27T20:12:19.337Z
abel1502
<p>One strategy I have read about, but not implemented myself, is the &quot;Trees that Grow&quot; pattern:</p>
<ul>
<li><a href="https://www.microsoft.com/en-us/research/uploads/prod/2016/11/trees-that-grow.pdf" rel="noreferrer">Original paper</a></li>
<li><a href="https://gitlab.haskell.org/ghc/ghc/-/wikis/implementing-trees-that-grow/trees-that-grow-guidance" rel="noreferrer">GHC wiki overview of TTG</a>
<ul>
<li><a href="https://gitlab.haskell.org/ghc/ghc/-/wikis/implementing-trees-that-grow" rel="noreferrer">GHC wiki implementation notes</a></li>
</ul>
</li>
<li><a href="https://gist.github.com/maurobalbi/b2292c2fd6736827cd58142381ead2f9" rel="noreferrer">A small example that came up when I searched for TTG</a></li>
</ul>
<p>IIRC, the basic idea is that you design one AST type that takes a type parameter to control what &quot;decorations&quot; are available. You then use decorations to enhance the tree with additional information in various stages.</p>
<p>So, you might have <code>GenericAST&lt;DecorationType&gt;</code> and then define various stages of the AST as <code>PlainAST = GenericAST&lt;Nothing&gt;</code>, <code>ParserAST = GenericAST&lt;SourceLocation&gt;</code>, <code>TypeCheckerAST = GenericAST&lt;Type&gt;</code>, etc.</p>
<p>Making a type-extensible AST like this adds flexibility, but also introduces a lot of extra complexity in the AST implementation. Furthermore, the Trees that Grow pattern originates in Haskell, and I can't say off the top of my head if Kotlin might have some differences that make TtG difficult to implement.</p>

CC BY-SA 4.0
2023-05-27T22:32:10.690Z
2023-05-27T23:08:19.823Z
2023-05-27T23:08:19.823Z
quiet_laika
# How can I reduce the amount of AST duplication in my code?
Posted by: username_0 on 2023-05-27
I'm working on a language that transpiles to Lua, and writing the transpiler in Kotlin. One problem I'm having is that I simply have too many AST types. I have an untyped AST, a typed AST, and a Lua pseudo-AST. I have considered adding an IR too. Additionally, a lot of these ASTs have duplicated fields. Most of the typed AST is identical to the untyped one with the exception of a `type` field. What strategies can I use to limit the amount of such code duplication?
**Tags:** implementation abstract-syntax-tree
> **Comments:**
> **username_1**: If you merge the untyped AST with the typed AST, you  can make the `type` field optional. That's what I do in my AST...  
> **username_2**: Take a look at Nanopass framework (on top of Scheme), or specialised languages like https://github.com/combinatorylogic/mbase - where AST handling is a first-class feature. Kotlin and other OO languages are not really well suited for such things.  
> **username_3**: I think this blog post is also a good resource on the question specifically, although maybe a bit light on details: http://blog.ezyang.com/2013/05/the-ast-typing-problem/  
---
## 2 answers
### Answer by username_3 on 2023-05-27. Score: 8 | Accepted answer
One strategy I have read about, but not implemented myself, is the "Trees that Grow" pattern:

* [Original paper](https://www.microsoft.com/en-us/research/uploads/prod/2016/11/trees-that-grow.pdf)
* [GHC wiki overview of TTG](https://gitlab.haskell.org/ghc/ghc/-/wikis/implementing-trees-that-grow/trees-that-grow-guidance)
  + [GHC wiki implementation notes](https://gitlab.haskell.org/ghc/ghc/-/wikis/implementing-trees-that-grow)
* [A small example that came up when I searched for TTG](https://gist.github.com/maurobalbi/b2292c2fd6736827cd58142381ead2f9)

IIRC, the basic idea is that you design one AST type that takes a type parameter to control what "decorations" are available. You then use decorations to enhance the tree with additional information in various stages.

So, you might have `GenericAST` and then define various stages of the AST as `PlainAST = GenericAST`, `ParserAST = GenericAST`, `TypeCheckerAST = GenericAST`, etc.

Making a type-extensible AST like this adds flexibility, but also introduces a lot of extra complexity in the AST implementation. Furthermore, the Trees that Grow pattern originates in Haskell, and I can't say off the top of my head if Kotlin might have some differences that make TtG difficult to implement.
---
### Answer by username_4 on 2023-05-27. Score: 5
### Code generation

This isn't always applicable, but AST-related boilerplate code can be generated from a more concise notion. This is what [Python does](https://github.com/python/cpython/blob/main/Parser/Python.asdl) (using the ASDL format). Your definition grammar could allow to specify AST subforms and variations in a more convenient manner.

I should, however, note that I'm not familiar with any existent DSL that would be capable of this, so you'll most likely have to write it yourself. Maybe use the Kotlin Annotation Processor to integrate that DSL into your existent code base more conveniently
---
