The AST Typing Problem
A few weeks ago I was visiting Mark Jones, and feeling particularly foolish I asked him what people do about "the AST typing problem" in a language like Haskell or SML. To my great surprise, he answered that he knew of no clean solutions. I'm curious whether a bunch of people with lots of PL-fu can identify some solution that we have failed to see.
The "AST typing problem" is a problem in static typing that consists of three parts:
Note that I'm looking for techniques here that are practical in a serious commercial grade compiler. Solving the problem at a high cost of indirections, e.g. by building a map of some sort, is not a production-grade solution; we're looking to compile at a rate very close to 100,000 lines of source code per second. Similarly, solving the problem by unifying the symbol resolution and type inference passes would compromise maintainability.
It's hard to imagine that this isn't well-trodden ground, but if Mark doesn't know, and I don't see it, it seems like it's at least a question worth posing. Dependent type can certainly handle some of this problem, but I'm really looking for clarification on how to do this in non-dependent type systems.
I should perhaps add: the first issue may not be apparent in current Haskell or ML compilers. The data structure presumed is unnatural in a functional language, so implementers building compilers in these languages have likely selected other ways to handle the evolution of AST structures across phases. I'm interested in those solutions, but I would expect (naively) that they fail the compile speed goal due to memory indirection overhead. I would be very interested to learn otherwise!
Active forum topics
New forum topics