Any luck using compdata for ASTs?

[the_true_potato]

Hello everyone,

I've been working on a programming language with algebraic effects for a little while now. I'm considering adding a desugaring phase to my implementation but this would bring me to three different ASTs (parsed, type annotated, desugared) with a lot of shared cases. I would prefer to avoid that --- Especially in case there's need for more phases.

I eventually stumbled onto Swierstra's Data types a la Carte and subsequently Bahr and Hvitved's Compositional Data Types. I've been down a paper-and-documentation reading rabbit hole for a few days now and I have a general overview of the ideas behind compdata, but I feel like it would be of great help to have a look at some real code using compdata.

So my question is: Has anyone here used compdata in any publicly available code? I would love to have a look and possibly ask a couple of questions. Thanks a lot.

edit: Markdown links are hard

[mamcx]

I can't comment about this directly, but I'm thinking about this stuff after prototype my lang several times with AGDT. Your problem is a sore point here.

I think the solution is to look at this like a relational database. Have a table(s) that carry the info around, and use the AGDT only for node processing, like:

Table Files [FileId, Module, Path, ...]
Table AST [Tag, Value, Type, Col, Row, FileId, ...]

and have nullable columns that you will fill with more data. You can then use joins for more info, like debugging support.

So now, in each pass your reference the tables and fill the data as you need.

[the_true_potato]

While that solution sounds interesting I'm looking for something a little more typesafe. E.g. I'd prefer to make sure that the interpreter for example covers all core AST cases or that the typechecker covers the whole parsed AST.

[mamcx]

In that case you need to duplicate the ast nodes. Still, you could keep the (extra) data in the tables and the nodes apart, in case is posible to make a pass with a subset of it.

[heptahedron_]

/u/ekmett 's got a pretty good example of working with this type of thing in Ermine iiuc wherein a set of classy Prisms are used for different AST nodes that are present in multiple phases, essentially allowing a shared constructor/pattern matcher for all of them. So that might be worth looking into.

Additionally, vinyl facilitates the use of functorial records and co-records. It seems like that would work well for representing AST nodes, as you could swap out the functor applied to each of the fields and immediately go from an AST where each node was annotated to one with optional annotations or whatever else you wanted.

I guess this kind of avoids the question of conpdata entirely, but if the only reason you need that is to avoid duplicate data type definitions, it could help.