Howdy! I’m a relative OCaml newcomer, and I’m writing a compiler in it. My AST data type has the following interesting problem: there are some nodes in the AST that can appear under several sorts of circumstances but which are not valid in all of them. For example, in this language, a variable def…

Sounds like an interesting problem–when I worked on a compiler in OCaml my AST was not repetitive enough, I guess, for this to be an issue. I do run into this sort of thing (if I’m understanding you correctly) with errors returned by functions. In that case I use polymorphic variants. Maybe for you…

Ah, but the problem with using polymorphic variants is I get even less typechecking. I can make mistakes unless I’m really careful about how I craft my code (rather than excluding them if I am thoughtful about how I craft my types). It would, however, allow me to re-use code, as you note, which woul…

Hm, I really don’t know what you mean by getting even less typechecking when using polymorphic variants. You should be specifying the types that the various nonterminals are parsed to, in which case you get at least as strong typechecking with polymorphic variants as with regular variants.

Take the case where I do a default match against a polymorphic variant. The compiler can’t tell what the full set of legal variants under the circumstances might be. If I then have a typo in naming a variant somewhere, it won’t catch it. Or am I mistaken?

Oh, I see. Well, when you use regular variants you’re implicitly specifying the type of the parameter (because a particular variant name belongs to one type). With polymorphic variants you need to add the type annotation on the parameter explicitly. If you don’t, though, you’re right that you might …

Did you try with GADT ? Here is a toy example : type 'a expr = | Lit : int -> int expr | Add : (int expr * int expr) -> int expr (* we can only add int expression *) | IsZ : int expr -> bool expr (* we can only compare to zero an int expression *) | If : (bool expr *'a expr * 'a expr) -> 'a expr (*…

[image] perry: One ugly way to do this would be to break up the definition type into its constituent variants, create two new variants, one at the top level and one at the function level, that will only wrap the kinds of definitions allowed at that level, so one would only allow function definit…

I’d like to have the type system give stronger assurances that if a parse tree can be expressed, it is valid. This is really tough to do in the general case. It is possible to abuse GADTs to express properties such as well-typedness and well-scopedness at the type level, but for real languages th…

Of course, I forgot to mention it, but the best way to fix your problem is obviously to allow function declarations within function declarations :slight_smile:

Best way to structure an algebraic data type for ASTs?

Learning

Chimrod July 26, 2018, 6:55am 18

You can take a look to the tagless final method which can give you a different way to structure your type.

Topic		Replies	Views
Mapping GADT AST node to list of it's children not allowed by compiler? Learning compiler , gadt , polymorphism , ast	3	873	August 26, 2022
An AST typing problem Learning	7	2996	November 2, 2020
Trees that Grow: Extending and annotating the AST Learning	2	427	November 25, 2025
Is it feasible to write parsers without using polymorphic variants for AST representation? Learning	16	2204	April 25, 2018
Do I need polymorphic variants? Learning	18	5247	January 6, 2023

Best way to structure an algebraic data type for ASTs?

Related topics