3 ms·

An Incremental Approach to Compiler Construction (2006) [pdf]

111 points by rspivak 11y ago

fao_ 11y ago
Here are some related papers you might be interested in (If you haven't seen them already): http://lambda-the-ultimate.org/node/1589 http://lambda-the-ultimate.org/node/1589 http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf http://www.cs.indiana.edu/~dyb/pubs/commercial-nanopass.pdf http://www.cs.indiana.edu/~dyb/pubs/commercial-nanopass.pdf
diginux 11y ago
A friend and I used this paper as part of an independent study in compilers, it was a lot of fun and I think strikes the right balance of concepts core to compiler construction. I highly recommend it.
amelius 11y ago
What I'd like to see is "An Approach to Incremental Compiler Construction", i.e., a compiler that outputs code which evaluates its input incrementally wrt. previous inputs.
- nfoz 11y ago
  The best example I know of is Papa Carlo: http://lakhin.com/projects/papa-carlo/ http://lakhin.com/projects/papa-carlo/ I had been working on an incremental-compiler-generator in C++, but suspended the project recently because it's a lot of work.
- seanmcdirmid 11y ago
  Or how about a live programming environment that incrementally recomputes a new programming execution based on incremental changes to the program's code. Anyways, I've been working on this problem for a few years now...the first step is incremental compilation.
  - vive-la-liberte 11y ago
    You're probably aware of Smalltalk already but in case you're not, I think it might be of interest to you. There's an open source implementation of Smalltalk called Pharo. They have a few screencasts and recordings of presentations at their website. http://pharo.org/documentation http://pharo.org/documentation Edit: Checked your profile. Going to say that yes, you almost certainly know about Smalltalk -- far more than do I.
    - seanmcdirmid 11y ago
      I would argue this a lot with people like Gilad Bracha :), but ya. Incremental compilation is pretty trivial in Smalltalk though given the lack of a static type system.
      - cbsmith 11y ago
        ...and no explicit native macro system either (lot can be laid atop it of course...).
    - cbsmith 11y ago
      There is a lot to be said for a language where a single edit somewhere in a program can't have snowballing effects across the entire codebase. In practice, that means deferring logic to the runtime...
- emptybits 11y ago
  Perhaps a nanopass framework is of interest? "a compiler as a collection of many fine-grained passes, each of which performs a single task" http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf
- sitkack 11y ago
  Using purely functional data structures and an AST walking interpreter one could make this fairly compact.
juliangamble 11y ago
Nada Amin, who gave the keynote at Strange Loop in 2014 "Programming Should Eat Itself" https://www.youtube.com/watch?v=SrKj4hYic5A https://www.youtube.com/watch?v=SrKj4hYic5A has worked through the implementation https://github.com/namin/inc https://github.com/namin/inc and provided the corresponding workshop documentation in her github account. https://github.com/namin/inc/blob/master/docs/tutorial.pdf https://github.com/namin/inc/blob/master/docs/tutorial.pdf She's also been involved in contributing to the next generation Scala compiler (Dotty).
sepeth 11y ago
A bit old and it is in Pascal, but still, Let's Build a Compiler by Jack Crenshaw is also fun to read: http://compilers.iecc.com/crenshaw/ http://compilers.iecc.com/crenshaw/

111 points by rspivak 11y ago

fao_ 11y ago

Here are some related papers you might be interested in (If you haven't seen them already): http://lambda-the-ultimate.org/node/1589 http://lambda-the-ultimate.org/node/1589 http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf http://www.cs.indiana.edu/~dyb/pubs/commercial-nanopass.pdf http://www.cs.indiana.edu/~dyb/pubs/commercial-nanopass.pdf

diginux 11y ago

A friend and I used this paper as part of an independent study in compilers, it was a lot of fun and I think strikes the right balance of concepts core to compiler construction. I highly recommend it.

amelius 11y ago

What I'd like to see is "An Approach to Incremental Compiler Construction", i.e., a compiler that outputs code which evaluates its input incrementally wrt. previous inputs.

nfoz 11y ago
The best example I know of is Papa Carlo: http://lakhin.com/projects/papa-carlo/ http://lakhin.com/projects/papa-carlo/ I had been working on an incremental-compiler-generator in C++, but suspended the project recently because it's a lot of work.
seanmcdirmid 11y ago
Or how about a live programming environment that incrementally recomputes a new programming execution based on incremental changes to the program's code. Anyways, I've been working on this problem for a few years now...the first step is incremental compilation.
- vive-la-liberte 11y ago
  You're probably aware of Smalltalk already but in case you're not, I think it might be of interest to you. There's an open source implementation of Smalltalk called Pharo. They have a few screencasts and recordings of presentations at their website. http://pharo.org/documentation http://pharo.org/documentation Edit: Checked your profile. Going to say that yes, you almost certainly know about Smalltalk -- far more than do I.
  - seanmcdirmid 11y ago
    I would argue this a lot with people like Gilad Bracha :), but ya. Incremental compilation is pretty trivial in Smalltalk though given the lack of a static type system.
    - cbsmith 11y ago
      ...and no explicit native macro system either (lot can be laid atop it of course...).
  - cbsmith 11y ago
    There is a lot to be said for a language where a single edit somewhere in a program can't have snowballing effects across the entire codebase. In practice, that means deferring logic to the runtime...
emptybits 11y ago
Perhaps a nanopass framework is of interest? "a compiler as a collection of many fine-grained passes, each of which performs a single task" http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf
sitkack 11y ago
Using purely functional data structures and an AST walking interpreter one could make this fairly compact.

juliangamble 11y ago

Nada Amin, who gave the keynote at Strange Loop in 2014 "Programming Should Eat Itself" https://www.youtube.com/watch?v=SrKj4hYic5A https://www.youtube.com/watch?v=SrKj4hYic5A has worked through the implementation https://github.com/namin/inc https://github.com/namin/inc and provided the corresponding workshop documentation in her github account. https://github.com/namin/inc/blob/master/docs/tutorial.pdf https://github.com/namin/inc/blob/master/docs/tutorial.pdf She's also been involved in contributing to the next generation Scala compiler (Dotty).

sepeth 11y ago

A bit old and it is in Pascal, but still, Let's Build a Compiler by Jack Crenshaw is also fun to read: http://compilers.iecc.com/crenshaw/ http://compilers.iecc.com/crenshaw/