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" ( ) 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 ( ) 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

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

JastAdd examples

You might find something useful on the JastAdd applications page.

Looking for examples *not* written using AGs (though)

Ah, but the JastAdd examples would be written using JastAdd, one presumes. What I'm looking for, are examples written using whatever prevailing method (typically, I'm guessing, multiple passes of top-down bottom-up left-to-right map/rewrite/iter over the tree). And especially if the author of the compiler finds the multiple passes a bit of a pain to maintain in the face of evolution of the language or specification.


I'm most interested in whatever you can learn on this. My own sense is that, while attribute grammars were invented to coordinate compilation, types are a formal imitation of the conceptual structure of the data. It's no secret on LtU that I'm skeptical of types altogether; my most recent take on this is that concepts are sapient structure, not formal structure, so that types by crossing over into the formal realm necessarily start to skew away from the conceptual structure they mimic. The conceptual-formal mismatch has been evident for a long time; there's a recent thread about it on Language Log, which references a 1952 essay by Jorge Luis Borges. The compilation process being intensely formal, this deviation from conceptual structure would, I suppose, become quite severe, making types a less effective compilation-coordination tool than attribute grammars.

Re: fwiw

Doesn't answer your question, but:

I don't know how to contact the author of that "The AST Typing Problem" post, but I sure would like to get more details, because early returns are ... not promising. To wit, I described this problem to a friend who teaches compiler courses, including writing optimizing backends. He observed that:

(1) there are pretty few passes of the compiler that focus on the AST: symbol-resolution, typing (though often these are *combined*), translation to some graph-like IL

(2) from there, you can't really use AGs -- it's a graph, after all.

Most of the hard work of a compiler is with the IL. So I'd really like to understand what these "many passes" compilers are doing in their passes.

But this *does* present a possible use-case *adjacent* to compilers: linters. Because in linting, you want to write a bunch of independent analyses, and combine them while getting something efficient that isn't "N times slower" for N analyses.

I'm not a compiler jock: I made my living doing transaction-processing. So I really would like to talk to these guys who write hard-core compilers, and perhaps try to "port" one of them to the AG formalism.

If nothing else, it would be *loads of fun*.

P.S. In the OP, it seemed that a big problem the author was alluding to, was that of program tranformations (e.g. inlining, constant-folding, maybe simplification, rewrites of pattern-matching, etc) on the source AST, and maintaining attribution (== "results of analyses") in the face of those transformations, so that full analyses need not be re-run. This seemed to be something for which incremental re-attribution might be appropriate, but again, without more details, I cannot judge.


Hi Chet,

In ICFP 2004, Dipanwita Sarkar, Oscar Waddell, and Kent Dybvig wrote A Nanopass Framework for Compiler Education, which showed how to build a lots-and-lots-of-passes compiler for education. In ICFP 2013, Andrew Keep and Kent Dybvig published A Nanopass Framework for Commercial Compiler Development, in which they reimplemented Chez Scheme using the nanopass style while remaining in the same compile speed benchmark (and Chez is famous for fast compiles).

Andrew Keep's PhD thesis (of the same title) should make a good read, since you can use the features he needs as an upper bound on what your attribute grammar thing will need to support.

PS -- your paper about Friedman's A-translation is one that I really liked, and which remains a big influence on me!

Previous discussion.

A-translation and constructions from classical proofs

I don't see that it's confirmed that chetmurthy is the same as the Chetan Murthy who worked on extracting constructive content from classical proofs from 1990 on, but if it is the same, he was a huge influence on my doctoral studies.


Yes indeed, I am he. I stopped doing anything remotely recognizable as research in 1995, and at this point I'm a hard-core systems-jock, so all of that stuff is .... ancient history. If we're ever in the same city (with covid and CO2, it seems unlikely) I'd be happy to hoist a pint and chew the old fat.

Neel, I see that you're at Cambridge: have you ever talked with Tim Griffin (who's there also)? He discovered all this stuff -- seriously. I added a jot, maybe a comma: he did all the important bits.