Refactoring Expression Trees

In the first version of my Ix interpreter library I had two expression tree types: AST and AST (Abstract Syntax Tree and Abstract Semantic Graph, respectively). The idea was that syntax would be turned into an AST just after parsing, then by successive transformations become an Abstract Semantic Graph, where nodes in the graphs link to each other in appropriate ways (and so isn't really a tree at all).

The problem with this approach was that there are many transformation processes: the one that parses syntax to create AST, some transformations from AST to AST, and more from ASG to ASG. Where should which transformations take place? The idea, initially, was for all variable resolution to have taken place by the time the graph was an ASG, but this takes place in stages, and there is no easy way to keep track of "an AST with this kind of partial resolution".

Instead, an ideal language would allow the creation of custom types for each state in the process. One might imagine the series of transformations being expressed through a linear type system.

One could approximate a linear type system simply by giving stages names, for example a freshly parsed tree is of type ASG while the variable-resolution result is of type resolved ASG or something similar. After each transformation process we can "annotate" the value type to explain what's been done to it. It would only be meaningful to the user, but type compatibility prevent one from trying to execute, say, a tree which has not performed variable resolution or type checking. Immediately before the execution of the interpreter, we'd check for the existence of resolution, type checking, and other annotations.

I aim to have Ix support such features. We'll see how it works out.