Lambda the Ultimate

You might find something useful on the JastAdd applications page.

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.

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!