I’ve found this problem annoying each time writing an ast, thanks for writing it down!
I’ve started to use three types of asts: the untyped parsetree, the fully typed tree, and then the typed tree that I use for type inference that has extra type information that’s not useful after type inference. (polytypes rather than monotypes). It becomes a larger cost to make an additional IR for each of these: the Two-level type solution works well here.
Adam Chlipala, a legend in verification community, is first in the comment section. Made me wonder about author. Checked his CV. Neatest thing about his research was he interned at Galois, worked with Simon Peyton Jones, worked with Chlipala, and then SPJ again. Lucky dude. ;)
I’m glad I’m not the only person who finds defining an AST data structure annoying :P
I hadn’t heard of attribute grammars before. Those look pretty interesting - I like the idea of being able to have a different set of attributes that exist for each phase. Going to look into this a bit.
I’ve been playing with redex recently, and am curious how easily I can convert the model into a compiler. It allows you to very nicely define the type system with rewrite rules. No need for an AST data type.
This problem has been particularly annoying for GHC (I bet that might have something to do with why ezyang, a frequent GHC contributor, blogged about it in the first place). More recently, Shayan Najd has been implementing the Trees that Grow approach in GHC. If you haven’t heard about it, it is an interesting take on extensible and well-typed AST trees using type families.
Great description of this stuff. I’m familiar with attribute grammars from a linguistics context, and it would never have occurred to me to use them as a practical data structure. But it does make a lot of sense and now I’m curious what software has done that.
Discusses approaches to defining recursive data structures for which you need multiple versions, possibly tagged with different data each time. Slightly code-golf, but I found it useful for a non-PLT project I’m doing currently.
I’ve found this problem annoying each time writing an ast, thanks for writing it down!
I’ve started to use three types of asts: the untyped parsetree, the fully typed tree, and then the typed tree that I use for type inference that has extra type information that’s not useful after type inference. (polytypes rather than monotypes). It becomes a larger cost to make an additional IR for each of these: the Two-level type solution works well here.
Adam Chlipala, a legend in verification community, is first in the comment section. Made me wonder about author. Checked his CV. Neatest thing about his research was he interned at Galois, worked with Simon Peyton Jones, worked with Chlipala, and then SPJ again. Lucky dude. ;)
I’m glad I’m not the only person who finds defining an AST data structure annoying :P
I hadn’t heard of attribute grammars before. Those look pretty interesting - I like the idea of being able to have a different set of attributes that exist for each phase. Going to look into this a bit.
I’ve been playing with redex recently, and am curious how easily I can convert the model into a compiler. It allows you to very nicely define the type system with rewrite rules. No need for an AST data type.
This problem has been particularly annoying for GHC (I bet that might have something to do with why ezyang, a frequent GHC contributor, blogged about it in the first place). More recently, Shayan Najd has been implementing the Trees that Grow approach in GHC. If you haven’t heard about it, it is an interesting take on extensible and well-typed AST trees using type families.
Great description of this stuff. I’m familiar with attribute grammars from a linguistics context, and it would never have occurred to me to use them as a practical data structure. But it does make a lot of sense and now I’m curious what software has done that.
Discusses approaches to defining recursive data structures for which you need multiple versions, possibly tagged with different data each time. Slightly code-golf, but I found it useful for a non-PLT project I’m doing currently.