archives

The AST Typing Problem (a bleg, also "why did attribute-grammars fail?")

TL;DR I'm looking for open-source-available multipass compilers in the spirit of what "shap" wrote about, as inputs to a project to understand whether attribute-grammars could help make them more tractable.

A decade ago, user "shap" posted about "The AST Typing Problem" ( http://lambda-the-ultimate.org/node/4170 ) and this generated a great discussion. In that discussion, a number of commenters also chimed-in about their own problems in writing multipass compilers. There was a post in 2019 at the OCaml Discussion Forum ( https://discuss.ocaml.org/t/an-ast-typing-problem/3677 ) that raised the same issues. The situation hasn't actually gotten better (AFAICT), and I'd like to revisit the subject.

I have a belief (which might or might not be right) that attribute-grammars might be an expressive medium that could produce sufficiently modular descriptions, that avoid some of the problems raised in shap's post. the problem with this belief, is that attribute grammars were tried decades ago, and arguably failed. I'm not going to sugar-coat this: on this forum, with lots of hard-core compiler-writers, nobody seriously considers them as an implementation technology. But, I'm not saying they failed for *technical* reasons: that might or might not be the case, and resolving that is part of why I'm writing this post.

I'd like to understand why, and the best way I know of, for doing so, would be to take some of the multipass compilers that "shap" and the commenters mentioned, 10 years ago, and translate them to the AG formalism, to see what happens: are they uglier, messier, harder to get right? [and for sure, merely translating an already-written compiler isn't a full test, but it's a start] To that end, I'm writing this post to ask for pointers to such multipass compilers, that I might use as experimental subjects.

I'm in the process of "software archeology", writing an AG evaluator-generator, based on published writings about previous systems (so far, I've only found one that still works -- Eli from Waite at Colorado) and so experimental subjects to which I could apply the system I'm devloping would be very useful,

Thanks in advance