11 ms·

What can we learn from how compilers are designed?

225 points by jsnell 9y ago

Veedrac 9y ago
This all assumes that you want most code to have the properties of compilers, but this seems misguided to me. Compilers don't handle complexity well, they're unreliable and not stable against small random purtubations, naïve approaches tend to be inefficient and complex ones global, etc. A lot of this is just that they're solving a difficult task (converting terrible C code into less terrible assembly), admittedly.
- runevault 9y ago
  I wonder if there are any ways to build simple to compile but still useful languages outside of just doing Lisp or Lisp-like.
  - munificent 9y ago
    Almost every language is less thorny than C because of C's context-sensitivity and the preprocessor. Pascal is a classic language that's useful but easy to compile. Any of Wirth's successor languages are too (occam, etc.). SML is a step up, but still not intractable. Java 1.0 might be fun.
    - runevault 9y ago
      Hm fair point. BTW I'd just like to say thank you for Crafting Interpreters, been going through it (in c#) and enjoying it immensely.
      - munificent 9y ago
        Thank you! That's great to hear. :)
  - shakna 9y ago
    FORTH is probably the classic "easy to compile" language, and is quite a decent language in and of itself.
  - UncleMeat 9y ago
    The hard part of writing a compiler is not the lexing, parsing, type checking, or code generation. The hard part is the optimizing bit. There do exist languages that are more amendable to whole-program analysis but the things that cause problems are usually not obvious. Java, weirdly, is among the easier languages to analyze because its memory model happens to be very easy to work with (excluding nulls).
- vicpara 9y ago
  Language design goes hand in hand with compiler's design. No wonder we have so many languages being born every year. Different mix of ideas being tried in each of them or forgotten lessons being rediscovered. Just taking a look at what D, Rust, Lisp and Scala proposes will give one the chance to ask crucial questions about what are the implication of that guarantee, pros, cons and how it will all work out.
vicpara 9y ago
It's a good article. Indeed, compiling a programming language is such a complex job that is frankly quickly dismissed and taken for granted. My view is that learning and writing a simple compiler will make most of developers on notch better. The very least you'll understand why parsing HTML or XML with regex is such a bad idea :) Another golden resource is the Dragon book: https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...
- mojuba 9y ago
  > My view is that learning and writing a simple compiler will make most of developers on notch better. Agreed. One of the interesting insights I got while building my own compiler was that despite what every compiler book says, there are languages that can be compiled on the fly without building an AST. I'd say for most languages it's an unnecessary step that makes compilation slower and more resource hungry. However, compiling without AST is a next-level skill, another notch I think.
  - justinpombrio 9y ago
    > One of the interesting insights I got while building my own compiler was that despite what every compiler book says, there are languages that can be compiled on the fly without building an AST. PL (but not compiler) researcher here. What you're saying sounds to me like "One of the interesting insights I got while programming my own game was that despite what every game programming book says, there are games that can be programmed without defining any functions." I mean, yes, you can do that, and it may in fact be more efficient, but it's going to cause trouble down the line if you ever want to do something more complex.
    - skybrian 9y ago
      Yes, there's a reason compiler books start with parsing and building an AST. But I think studying Lua [1] or the Wren codebase [2] is still worthwhile, provided you keep in mind that they're relatively simple languages that are designed to be both fast and embedded. [1] https://www.lua.org/doc/jucs05.pdf https://www.lua.org/doc/jucs05.pdf [2] https://github.com/munificent/wren https://github.com/munificent/wren
archi42 9y ago
I think the OO part is a bit ranty, but other than that it's a nice article: Software engineers can really learn a lot from compiler design. Never regret I did take that lecture (we excluded C typedefs and some other meanies). If you're bored and want to learn, write a LLVM frontend, and maybe a simple optimization (e.g. constant propagation or dead code elimination). There is a tutorial for a functional language in the LLVM docs, or just do a subset of C, or your own DSL ;)
skybrian 9y ago
Compiler design is somewhat unusual just because there are so many different cases to deal with. An AST might have 20 different kinds of expressions, and anything traversing it needs to deal with them all. This means that whatever solution you come up with needs to scale to lots of cases, more than you can comfortably remember. And for a language that's not stable, you need to update all the tools when the AST changes, to handle the new construct. (Lisp isn't immune; it calls them special forms and they're uniformly represented as lists, but you still have to deal with them for any kind of deep analysis.)
- UncleEntity 9y ago
  There's an essay on this: https://www.gnu.org/software/dotgnu/treecc_essay.html https://www.gnu.org/software/dotgnu/treecc_essay.html
- seanmcdirmid 9y ago
  You can traverse the AST via internal functions (in OO terminology, virtual methods that make the case matching implicit on this). It really isn't much of a problem if the functions are typecheck, codegen, execute, etc... I don't really get the appeal of using giant mega case matches in a compiler.
  - qznc 9y ago
    AST transformations are a exemplary instance of the Expression Problem. Solutions in mainstream languages, eg the Polyglot framework for Java, lead to ugly overengineered code. Writing AST transformations with multimethods might be nice.
Bizarro 9y ago
That's why I like Clojure's philosophy of a few data structures and many functions operating on them. Of course Alan Perlis wrote "It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures." in 1982. But pipelining outputs into inputs (you'll see it a lot in F# too) is just a simple, flexible concept. As Rich Hickey once said, "We're data processors". I think we somehow took a wrong path when OO got embraced as wholly as it did back in the 90s or so.
- stochastic_monk 9y ago
  Similarly, I like Python and C++’s emphasis on duck-typing. I use STL containers often, and provide similar interfaces to my custom data structures for flexible, general, fast code.
  - jonathanyc 9y ago
    I wish there were tools to auto generate documentation on what interface a duck-typed consumer expects, e.g. what std::vector<T> expects of T.
    - stochastic_monk 9y ago
      Well, C++17 concepts enforce requirements, but hopefully metaclasses will do more in 20.
      - bstamour 9y ago
        Concepts are also C++20. They were voted in, however, shortly after 17 shipped.
        stochastic_monk 9y ago
        Good point. I was thinking of the rudimentary, template-based use of concepts, not the polished, C++20 version.
Bizarro 9y ago
The use of middleware seems to embrace this concept too for very flexible systems. Just pass it along the assembly line and you don't care who's next in line or who was before you.
chubot 9y ago
Regarding splitting lexing and parsing, I argue the opposite point here: When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html http://www.oilshell.org/blog/2017/12/17.html I assert that scannerless parsing is a bad idea, for reasons of efficiency and code complexity. He's making some argument around generated parsers which I don't understand. I believe he's conflating the issue of whether you generate your parser with whether you have a separate parser and lexer. (The OSH parser is hand-written, while the lexer is generated. This is actually the opposite of what you see in many languages -- e.g. in Python the parser is generated, while the lexer is hand-written.) There's no reason that you can't produce good error messages with a separate parser and lexer. In fact I believe you'll get better error messages. I use a "lossless syntax tree" representation which allows good error messages: From AST to Lossless Syntax Tree http://www.oilshell.org/blog/2017/02/11.html http://www.oilshell.org/blog/2017/02/11.html (On the one hand, it's like a parse tree, but less verbose. On the other, it's like an AST, but it doesn't lose information.) ---- Regarding intermediate representations, I had a lot of success with Zephyr ASDL, which is a DSL for using algebraic data types in procedural/OOP languages: http://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL http://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL I also don't really see the strong contrast betweeen OOP and FP he's making. Oil uses both styles -- the IR is at the center, using a functional style (data without methods), but the other components are objects/modules/interfaces/encapsulated state/data hiding. IMO OOP and FP are the same thing when done right: they're about being principled about state. The way I see it, a pure dependency injection style is pretty much equivalent to functional programming. Python is described with ASDL: https://github.com/python/cpython/blob/master/Parser/Python.asdl https://github.com/python/cpython/blob/master/Parser/Python.... ASDL has some relation to "Stanford University Intermediate Format", which sounds like it could have been a precursor to LLVM IR. In other words it happens to be used in interpreters right now, but it was designed for compilers. https://www.cs.princeton.edu/research/techreps/TR-554-97 https://www.cs.princeton.edu/research/techreps/TR-554-97 https://suif.stanford.edu/suif/ https://suif.stanford.edu/suif/ --- I also wrote about "the Lexer Hack" here: http://www.oilshell.org/blog/2017/12/15.html http://www.oilshell.org/blog/2017/12/15.html
evincarofautumn 9y ago
For my main compiler project I’ve actually been moving away from this “pipeline” style because it’s inflexible and not great for incremental operations. Inspired by the Forth dictionary, gradually I’ve arrived at a design where the compiler behaves like a database server—it takes requests in the form of program fragments and produces responses in whatever form you want by querying the database and generating intermediate results as needed. The pipeline is still there, it’s just not hard-coded, and modelled in a more relational way. (I plan on doing a detailed blog post on this after I land the code.) Ordinary compilation? Push a bunch of files and pull the generated code of anything referenced transitively from the program entry point or library exports. Documentation or TAGS generation? Pull the appropriate metadata. Syntax highlighting? Pull the lexical classes and source spans of the tokens—no parsing needs to happen. In general, if you want an intermediate result, you can just ask for it—there’s no hard-coded code path for “run the pipeline up to this point and bail”. The advantage is that this is amenable to producing partial results even when there are program errors—a lexical error doesn’t prevent parsing, it just produces an “error” token that can be displayed in an editor without compromising higher-level features like syntax highlighting, autocomplete, navigation, &c.
- seanmcdirmid 9y ago
  Many pipeline approaches include error tolerance. I specialize in incremental lexing and parsing for IDEs, and even have experience with some state based error recovery (so, for example, unbalanced braces remember previous brace associations, or a bad transient parse error doesn’t destroy the good trees on the precious run). I don’t see how a database approach would help, you just need to incrementalize the structures in your pipeline (or have reproduceable persistent markers like Eclipse’s elastic positions).
  - evincarofautumn 9y ago
    Ah yeah, you can have incremental structures without an incremental pipeline or vice versa, they’ve just worked well together for me.
    - 9y ago
evmar 9y ago
Another place where lexing and parsing interact is JavaScript. Consider the lexer encountering the text "/x;". If it occurs in code like: let a = /x; then it needs to continue lexing a regular expression. If it occurs in code like: let a = b /x; then it needs to lex it as division sign, identifier x, semicolon.
- comex 9y ago
  At least it's not bad as Perl, where the same code can be parsed as division or a regex depending on the 'type signature' of a function it names: https://www.perlmonks.org/?node_id=663393 https://www.perlmonks.org/?node_id=663393
blt 9y ago
The parser/lexer separation feels especially useless in a Lisp interpreter, where the parsing is trivial.
- kazinator 9y ago
  It's there. E.g. ANSI Lisp has the concept of a token. Reading multiple objects until a closing ) via read-delimited-list is like parsing. The actions which accumulate token constituent characters into a token and produce some object from it, like a number or symbol, are like lexing.
tomxor 9y ago
I find this interesting from the perspective of the design mentality. I've read so many comments of people here starting with "I am a PL researcher" and "I am a compiler designer" often with a qualification of "but not the other one", it seems like unless you are doing a Forth style language you're almost never both...? My interpretation of the authors main points are: breaking compilation down into a pipeline of blocks has obvious advantages, but much like when we break any large implementation problem down into blocks, we can loose sight of the whole - in short, it's important to maintain a holistic view while simultaneously making decisions of where to "cut" your problem. But that holistic view to me seems to mostly end at the intersection between compiler and language. When I started my job it involved a lot of one way design implementation, as these became more adventurous I gradually found myself questioning the designs more, until now where I see basically no division between design and implementation - when a "design" for something comes my way I basically pull it to pieces and interrogate the author in order to understand all of the decisions behind the design and then rebuild it (with the author) with implementation and practicality in mind, it always benefits everyone involved. I feel like this previous division that i destroyed is quite similar to this division in compiler and language, but I am mostly an outsider to that world so i could be wrong.

225 points by jsnell 9y ago

This all assumes that you want most code to have the properties of compilers, but this seems misguided to me. Compilers don't handle complexity well, they're unreliable and not stable against small random purtubations, naïve approaches tend to be inefficient and complex ones global, etc. A lot of this is just that they're solving a difficult task (converting terrible C code into less terrible assembly), admittedly.

runevault 9y ago
I wonder if there are any ways to build simple to compile but still useful languages outside of just doing Lisp or Lisp-like.
- munificent 9y ago
  Almost every language is less thorny than C because of C's context-sensitivity and the preprocessor. Pascal is a classic language that's useful but easy to compile. Any of Wirth's successor languages are too (occam, etc.). SML is a step up, but still not intractable. Java 1.0 might be fun.
  - runevault 9y ago
    Hm fair point. BTW I'd just like to say thank you for Crafting Interpreters, been going through it (in c#) and enjoying it immensely.
    - munificent 9y ago
      Thank you! That's great to hear. :)
- shakna 9y ago
  FORTH is probably the classic "easy to compile" language, and is quite a decent language in and of itself.
- UncleMeat 9y ago
  The hard part of writing a compiler is not the lexing, parsing, type checking, or code generation. The hard part is the optimizing bit. There do exist languages that are more amendable to whole-program analysis but the things that cause problems are usually not obvious. Java, weirdly, is among the easier languages to analyze because its memory model happens to be very easy to work with (excluding nulls).
vicpara 9y ago
Language design goes hand in hand with compiler's design. No wonder we have so many languages being born every year. Different mix of ideas being tried in each of them or forgotten lessons being rediscovered. Just taking a look at what D, Rust, Lisp and Scala proposes will give one the chance to ask crucial questions about what are the implication of that guarantee, pros, cons and how it will all work out.

vicpara 9y ago

It's a good article. Indeed, compiling a programming language is such a complex job that is frankly quickly dismissed and taken for granted. My view is that learning and writing a simple compiler will make most of developers on notch better. The very least you'll understand why parsing HTML or XML with regex is such a bad idea :) Another golden resource is the Dragon book: https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...

mojuba 9y ago
> My view is that learning and writing a simple compiler will make most of developers on notch better. Agreed. One of the interesting insights I got while building my own compiler was that despite what every compiler book says, there are languages that can be compiled on the fly without building an AST. I'd say for most languages it's an unnecessary step that makes compilation slower and more resource hungry. However, compiling without AST is a next-level skill, another notch I think.
- justinpombrio 9y ago
  > One of the interesting insights I got while building my own compiler was that despite what every compiler book says, there are languages that can be compiled on the fly without building an AST. PL (but not compiler) researcher here. What you're saying sounds to me like "One of the interesting insights I got while programming my own game was that despite what every game programming book says, there are games that can be programmed without defining any functions." I mean, yes, you can do that, and it may in fact be more efficient, but it's going to cause trouble down the line if you ever want to do something more complex.
  - skybrian 9y ago
    Yes, there's a reason compiler books start with parsing and building an AST. But I think studying Lua [1] or the Wren codebase [2] is still worthwhile, provided you keep in mind that they're relatively simple languages that are designed to be both fast and embedded. [1] https://www.lua.org/doc/jucs05.pdf https://www.lua.org/doc/jucs05.pdf [2] https://github.com/munificent/wren https://github.com/munificent/wren

archi42 9y ago

I think the OO part is a bit ranty, but other than that it's a nice article: Software engineers can really learn a lot from compiler design. Never regret I did take that lecture (we excluded C typedefs and some other meanies). If you're bored and want to learn, write a LLVM frontend, and maybe a simple optimization (e.g. constant propagation or dead code elimination). There is a tutorial for a functional language in the LLVM docs, or just do a subset of C, or your own DSL ;)

skybrian 9y ago

Compiler design is somewhat unusual just because there are so many different cases to deal with. An AST might have 20 different kinds of expressions, and anything traversing it needs to deal with them all. This means that whatever solution you come up with needs to scale to lots of cases, more than you can comfortably remember. And for a language that's not stable, you need to update all the tools when the AST changes, to handle the new construct. (Lisp isn't immune; it calls them special forms and they're uniformly represented as lists, but you still have to deal with them for any kind of deep analysis.)

UncleEntity 9y ago
There's an essay on this: https://www.gnu.org/software/dotgnu/treecc_essay.html https://www.gnu.org/software/dotgnu/treecc_essay.html
seanmcdirmid 9y ago
You can traverse the AST via internal functions (in OO terminology, virtual methods that make the case matching implicit on this). It really isn't much of a problem if the functions are typecheck, codegen, execute, etc... I don't really get the appeal of using giant mega case matches in a compiler.
- qznc 9y ago
  AST transformations are a exemplary instance of the Expression Problem. Solutions in mainstream languages, eg the Polyglot framework for Java, lead to ugly overengineered code. Writing AST transformations with multimethods might be nice.

Bizarro 9y ago

That's why I like Clojure's philosophy of a few data structures and many functions operating on them. Of course Alan Perlis wrote "It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures." in 1982. But pipelining outputs into inputs (you'll see it a lot in F# too) is just a simple, flexible concept. As Rich Hickey once said, "We're data processors". I think we somehow took a wrong path when OO got embraced as wholly as it did back in the 90s or so.

stochastic_monk 9y ago
Similarly, I like Python and C++’s emphasis on duck-typing. I use STL containers often, and provide similar interfaces to my custom data structures for flexible, general, fast code.
- jonathanyc 9y ago
  I wish there were tools to auto generate documentation on what interface a duck-typed consumer expects, e.g. what std::vector<T> expects of T.
  - stochastic_monk 9y ago
    Well, C++17 concepts enforce requirements, but hopefully metaclasses will do more in 20.
    - bstamour 9y ago
      Concepts are also C++20. They were voted in, however, shortly after 17 shipped.
      - stochastic_monk 9y ago
        Good point. I was thinking of the rudimentary, template-based use of concepts, not the polished, C++20 version.

Bizarro 9y ago

The use of middleware seems to embrace this concept too for very flexible systems. Just pass it along the assembly line and you don't care who's next in line or who was before you.

chubot 9y ago

Regarding splitting lexing and parsing, I argue the opposite point here: When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html http://www.oilshell.org/blog/2017/12/17.html I assert that scannerless parsing is a bad idea, for reasons of efficiency and code complexity. He's making some argument around generated parsers which I don't understand. I believe he's conflating the issue of whether you generate your parser with whether you have a separate parser and lexer. (The OSH parser is hand-written, while the lexer is generated. This is actually the opposite of what you see in many languages -- e.g. in Python the parser is generated, while the lexer is hand-written.) There's no reason that you can't produce good error messages with a separate parser and lexer. In fact I believe you'll get better error messages. I use a "lossless syntax tree" representation which allows good error messages: From AST to Lossless Syntax Tree http://www.oilshell.org/blog/2017/02/11.html http://www.oilshell.org/blog/2017/02/11.html (On the one hand, it's like a parse tree, but less verbose. On the other, it's like an AST, but it doesn't lose information.) ---- Regarding intermediate representations, I had a lot of success with Zephyr ASDL, which is a DSL for using algebraic data types in procedural/OOP languages: http://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL http://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL I also don't really see the strong contrast betweeen OOP and FP he's making. Oil uses both styles -- the IR is at the center, using a functional style (data without methods), but the other components are objects/modules/interfaces/encapsulated state/data hiding. IMO OOP and FP are the same thing when done right: they're about being principled about state. The way I see it, a pure dependency injection style is pretty much equivalent to functional programming. Python is described with ASDL: https://github.com/python/cpython/blob/master/Parser/Python.asdl https://github.com/python/cpython/blob/master/Parser/Python.... ASDL has some relation to "Stanford University Intermediate Format", which sounds like it could have been a precursor to LLVM IR. In other words it happens to be used in interpreters right now, but it was designed for compilers. https://www.cs.princeton.edu/research/techreps/TR-554-97 https://www.cs.princeton.edu/research/techreps/TR-554-97 https://suif.stanford.edu/suif/ https://suif.stanford.edu/suif/ --- I also wrote about "the Lexer Hack" here: http://www.oilshell.org/blog/2017/12/15.html http://www.oilshell.org/blog/2017/12/15.html

evincarofautumn 9y ago

For my main compiler project I’ve actually been moving away from this “pipeline” style because it’s inflexible and not great for incremental operations. Inspired by the Forth dictionary, gradually I’ve arrived at a design where the compiler behaves like a database server—it takes requests in the form of program fragments and produces responses in whatever form you want by querying the database and generating intermediate results as needed. The pipeline is still there, it’s just not hard-coded, and modelled in a more relational way. (I plan on doing a detailed blog post on this after I land the code.) Ordinary compilation? Push a bunch of files and pull the generated code of anything referenced transitively from the program entry point or library exports. Documentation or TAGS generation? Pull the appropriate metadata. Syntax highlighting? Pull the lexical classes and source spans of the tokens—no parsing needs to happen. In general, if you want an intermediate result, you can just ask for it—there’s no hard-coded code path for “run the pipeline up to this point and bail”. The advantage is that this is amenable to producing partial results even when there are program errors—a lexical error doesn’t prevent parsing, it just produces an “error” token that can be displayed in an editor without compromising higher-level features like syntax highlighting, autocomplete, navigation, &c.

seanmcdirmid 9y ago
Many pipeline approaches include error tolerance. I specialize in incremental lexing and parsing for IDEs, and even have experience with some state based error recovery (so, for example, unbalanced braces remember previous brace associations, or a bad transient parse error doesn’t destroy the good trees on the precious run). I don’t see how a database approach would help, you just need to incrementalize the structures in your pipeline (or have reproduceable persistent markers like Eclipse’s elastic positions).
- evincarofautumn 9y ago
  Ah yeah, you can have incremental structures without an incremental pipeline or vice versa, they’ve just worked well together for me.
  - 9y ago

evmar 9y ago

Another place where lexing and parsing interact is JavaScript. Consider the lexer encountering the text "/x;". If it occurs in code like: let a = /x; then it needs to continue lexing a regular expression. If it occurs in code like: let a = b /x; then it needs to lex it as division sign, identifier x, semicolon.

comex 9y ago
At least it's not bad as Perl, where the same code can be parsed as division or a regex depending on the 'type signature' of a function it names: https://www.perlmonks.org/?node_id=663393 https://www.perlmonks.org/?node_id=663393

blt 9y ago

The parser/lexer separation feels especially useless in a Lisp interpreter, where the parsing is trivial.

kazinator 9y ago
It's there. E.g. ANSI Lisp has the concept of a token. Reading multiple objects until a closing ) via read-delimited-list is like parsing. The actions which accumulate token constituent characters into a token and produce some object from it, like a number or symbol, are like lexing.

tomxor 9y ago

I find this interesting from the perspective of the design mentality. I've read so many comments of people here starting with "I am a PL researcher" and "I am a compiler designer" often with a qualification of "but not the other one", it seems like unless you are doing a Forth style language you're almost never both...? My interpretation of the authors main points are: breaking compilation down into a pipeline of blocks has obvious advantages, but much like when we break any large implementation problem down into blocks, we can loose sight of the whole - in short, it's important to maintain a holistic view while simultaneously making decisions of where to "cut" your problem. But that holistic view to me seems to mostly end at the intersection between compiler and language. When I started my job it involved a lot of one way design implementation, as these became more adventurous I gradually found myself questioning the designs more, until now where I see basically no division between design and implementation - when a "design" for something comes my way I basically pull it to pieces and interrogate the author in order to understand all of the decisions behind the design and then rebuild it (with the author) with implementation and practicality in mind, it always benefits everyone involved. I feel like this previous division that i destroyed is quite similar to this division in compiler and language, but I am mostly an outsider to that world so i could be wrong.