This is a great example! It’s relevant to my work too: I have an RPython implementation that I want to make generic, so that other interpreters can use it, but it’s too tightly tied to a single interpreter’s classes.

So, Najd & Peyton Jones call this the “tree decoration problem.” Great name! Their attempt at solving it is called Trees that Grow and there’s a plan for implementing it in GHC. A closely-related problem, the “AST typing problem,” shows up here and has discussion at Lambda The Ultimate, from Yang, and from McKenna; note that we aren’t putting types on ASTs, but putting types on logic variables which are “interpreted” by generic traversals.

I cheat the problem in multiple ways. In RPython for Monte, there are no types; instead, objects guard each other, and are referred to with generic fat pointers to objects. In RPython for Cammy, I hand-wrote a specialized µKanren which only works for Cammy’s type grammar, and I monomorphize when emitting bytecode. In CHICKEN Scheme for Cammy, I take full advantage of CHICKEN’s flexible encoding to intermix logic variables and AST fragments with user-level values.

score 3 · canonical