7 ms·

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 lea

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
  - mojuba 9y ago
    No, it's not the same thing. A compiler without the AST phase itself is more compact and arguably more beautiful, but again not every language is compile-able this way (C++ being a notable example).
  - compiler-guy 9y ago
    Yeah, the grandparent is only true if you don't want to do interesting things with the language, like nearly any but the most basic peephole optimization. But a fun fact, if you know about single-pass compiling, you can figure out a lot of why the original C syntax is what it is. A declaration is a "reserve some memory" statement. Local variables had to be declared at the beginning of scope so that the compiler could deallocate them at scope close. Without an AST, the compiler had to produce instructions immediately. With a true AST, you don't need such a restrictive syntax. There are many other possible examples.
  - munificent 9y ago
    > 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." Ex-game programmer and current PL programmer here. I think a better analogy is that you can make a game without having a scene graph. And, indeed, you can. And it works fine for many simple games, though as some scales it starts to be a hindrance.
  - HumanDrivenDev 9y ago
    well there's no need for an AST in a concatenative language - that might be what he's talking about.
- robertelder 9y ago
  My experience has been that you can get incredibly far (much farther than you'd think) without any form of AST and just iterate over the raw parse tree and tokens, but the problem you eventually encounter when you do this is that if you want to support all the different cases in a 'real' and messy evolved language like C is that you get a combinatorical exposion when you try to support all the corner cases of the language. A great example of this would be if you try to figure out how to write a function to iterate over the tokens that make up a struct definition in C: http://blog.robertelder.org/magical-world-of-structs-typedefs-scoping/ http://blog.robertelder.org/magical-world-of-structs-typedef... This is the reason for needing the extra 'abstract' syntax tree layer that lets you generalize over all those different cases and avoid having 20-level nested if statements in your compiler.
- seanmcdirmid 9y ago
  Compiling without an AST is actually more like an old school skill than a next generation one: very common in the 60s and 70s, very rare today.
kazinator 9y ago
Sunday before last (twelve days ago) I started working on a VM, assembler/disassembler and compiler for TXR Lisp, just early morning and evening spare time. Assembler and VM handle lexical closures, exception handling, unwind-protect, function calls (of course) and global variable access, and dynamic environments (special variables). Compiler handles a significant number of important special forms: let, lambda, function calls, assignment and others. lambda handles optional parameters with default values, and any parameter can be a special variable, correctly saved and restored, and excluded from the lexical environment. VM closures are hooked into the rest of the environment; they are represented as a new kind of function and can be used in the normal ways. https://www.reddit.com/r/lisp/comments/84j8l0/txr_lisp_vm_compiler_under_construction/?st=jeujl1so&sh=f426fd96 https://www.reddit.com/r/lisp/comments/84j8l0/txr_lisp_vm_co... This stuff is not terribly difficult. Compiling Lisp is in many respects easier than interpretation. A huge simplifying factor is that in the compiler, you can mutate an environment object as you compile: that is to say, add a binding, compile something, add a binding, compile something ... The compiled something, even if it contains a lexical closure, does not see any of the bindings you didn't add yet. Can't do that in the interpreter; not with the same environment representation. If you interpret something which captures a closure and then extend the captured environment, you've screwed up. I have to grapple with a couple of messy special forms. That's how it goes when you've been interpreting for years and now you're introducing a compiler. One form is the one which underlies the evaluation of the string quasiliteral syntax. Unfortunately, the special form is deeply interpretive; it passes the environment into some functions which walk the syntax of the quasiliteral doing eval here and there, which come up with the pieces of strings that catenate together to form the output. I'm unraveling that stuff for compiling; coming up with a way to hoist the evals out into static code, and some function API that can then just work with the results of the evaluation, yet maintain compatibility with the interpreted semantics. The annoying thing is that just the partially complete transformation code for this crud is 60 lines of Lisp so far, whereas the entire compiler (so far) which accomplishes so much more is only 378. One is a big percentage, in other words. It's an annoying thing in programming that sometimes code which is very specialized and achieves little in the "big picture" burns more LOC's then you'd think it deserves.
- dfox 9y ago
verletx64 9y ago
Can I ask, as somebody that hasn't dived into Compiler's yet; not out of not wanting to, but more a 'so much to learn' scenario How does it make a developer better? I see this repeated often, but I don't really see how.
- magpi3 9y ago
  Compilers are a great example of taking a very complicated task and breaking it down into simpler (though not necessary simple) steps. Just going through the practice of building one might change how you look at other projects you've worked on in the past. And I think the insights you take from designing a compiler translate into data processing as a whole, as other commenters have noted.
- Ono-Sendai 9y ago
  You get an insight into why current languages and compilers are designed the way they are. For example, why does C have #include? Probably because it's the easiest possible way of including/referencing source code from another file.
- kqr 9y ago
  It's surprisingly practical to view a lot of data mangling tasks through one's compiler glasses.
- slx26 9y ago
  For example: once you see what the compiler does, you can write readable code without sacrificing efficiency. When you don't really know what's going on under the hood, consciously or unconsciously you write code based on assumptions, which a lot of the time are wrong. It's very hard to exemplify because the mental model programmers have about programming can be very different, and therefore the benefits of a better understanding provided by learning about compilers can have different effects on different people. And still, everyone who has tried recommends learning about compilers. Programming languages are our most fundamental tool as programmers, and yet it's pretty much impossible to make a fair assessment of why they are designed the way they are, why they work the way they do, why they provide the abstractions and structures they provide, until you try for yourself. Understand programming languages better => use them more naturally.
mbrodersen 9y ago
The dragon book is not recommended. It is very out of date. I write (among other things) high performance compilers for a living. And the Dragon book is not useful at all.

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
- mojuba 9y ago
  No, it's not the same thing. A compiler without the AST phase itself is more compact and arguably more beautiful, but again not every language is compile-able this way (C++ being a notable example).
- compiler-guy 9y ago
  Yeah, the grandparent is only true if you don't want to do interesting things with the language, like nearly any but the most basic peephole optimization. But a fun fact, if you know about single-pass compiling, you can figure out a lot of why the original C syntax is what it is. A declaration is a "reserve some memory" statement. Local variables had to be declared at the beginning of scope so that the compiler could deallocate them at scope close. Without an AST, the compiler had to produce instructions immediately. With a true AST, you don't need such a restrictive syntax. There are many other possible examples.
- munificent 9y ago
  > 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." Ex-game programmer and current PL programmer here. I think a better analogy is that you can make a game without having a scene graph. And, indeed, you can. And it works fine for many simple games, though as some scales it starts to be a hindrance.
- HumanDrivenDev 9y ago
  well there's no need for an AST in a concatenative language - that might be what he's talking about.
robertelder 9y ago
My experience has been that you can get incredibly far (much farther than you'd think) without any form of AST and just iterate over the raw parse tree and tokens, but the problem you eventually encounter when you do this is that if you want to support all the different cases in a 'real' and messy evolved language like C is that you get a combinatorical exposion when you try to support all the corner cases of the language. A great example of this would be if you try to figure out how to write a function to iterate over the tokens that make up a struct definition in C: http://blog.robertelder.org/magical-world-of-structs-typedefs-scoping/ http://blog.robertelder.org/magical-world-of-structs-typedef... This is the reason for needing the extra 'abstract' syntax tree layer that lets you generalize over all those different cases and avoid having 20-level nested if statements in your compiler.
seanmcdirmid 9y ago
Compiling without an AST is actually more like an old school skill than a next generation one: very common in the 60s and 70s, very rare today.

kazinator 9y ago

Sunday before last (twelve days ago) I started working on a VM, assembler/disassembler and compiler for TXR Lisp, just early morning and evening spare time. Assembler and VM handle lexical closures, exception handling, unwind-protect, function calls (of course) and global variable access, and dynamic environments (special variables). Compiler handles a significant number of important special forms: let, lambda, function calls, assignment and others. lambda handles optional parameters with default values, and any parameter can be a special variable, correctly saved and restored, and excluded from the lexical environment. VM closures are hooked into the rest of the environment; they are represented as a new kind of function and can be used in the normal ways. https://www.reddit.com/r/lisp/comments/84j8l0/txr_lisp_vm_compiler_under_construction/?st=jeujl1so&sh=f426fd96 https://www.reddit.com/r/lisp/comments/84j8l0/txr_lisp_vm_co... This stuff is not terribly difficult. Compiling Lisp is in many respects easier than interpretation. A huge simplifying factor is that in the compiler, you can mutate an environment object as you compile: that is to say, add a binding, compile something, add a binding, compile something ... The compiled something, even if it contains a lexical closure, does not see any of the bindings you didn't add yet. Can't do that in the interpreter; not with the same environment representation. If you interpret something which captures a closure and then extend the captured environment, you've screwed up. I have to grapple with a couple of messy special forms. That's how it goes when you've been interpreting for years and now you're introducing a compiler. One form is the one which underlies the evaluation of the string quasiliteral syntax. Unfortunately, the special form is deeply interpretive; it passes the environment into some functions which walk the syntax of the quasiliteral doing eval here and there, which come up with the pieces of strings that catenate together to form the output. I'm unraveling that stuff for compiling; coming up with a way to hoist the evals out into static code, and some function API that can then just work with the results of the evaluation, yet maintain compatibility with the interpreted semantics. The annoying thing is that just the partially complete transformation code for this crud is 60 lines of Lisp so far, whereas the entire compiler (so far) which accomplishes so much more is only 378. One is a big percentage, in other words. It's an annoying thing in programming that sometimes code which is very specialized and achieves little in the "big picture" burns more LOC's then you'd think it deserves.

dfox 9y ago

verletx64 9y ago

Can I ask, as somebody that hasn't dived into Compiler's yet; not out of not wanting to, but more a 'so much to learn' scenario How does it make a developer better? I see this repeated often, but I don't really see how.

magpi3 9y ago
Compilers are a great example of taking a very complicated task and breaking it down into simpler (though not necessary simple) steps. Just going through the practice of building one might change how you look at other projects you've worked on in the past. And I think the insights you take from designing a compiler translate into data processing as a whole, as other commenters have noted.
Ono-Sendai 9y ago
You get an insight into why current languages and compilers are designed the way they are. For example, why does C have #include? Probably because it's the easiest possible way of including/referencing source code from another file.
kqr 9y ago
It's surprisingly practical to view a lot of data mangling tasks through one's compiler glasses.
slx26 9y ago
For example: once you see what the compiler does, you can write readable code without sacrificing efficiency. When you don't really know what's going on under the hood, consciously or unconsciously you write code based on assumptions, which a lot of the time are wrong. It's very hard to exemplify because the mental model programmers have about programming can be very different, and therefore the benefits of a better understanding provided by learning about compilers can have different effects on different people. And still, everyone who has tried recommends learning about compilers. Programming languages are our most fundamental tool as programmers, and yet it's pretty much impossible to make a fair assessment of why they are designed the way they are, why they work the way they do, why they provide the abstractions and structures they provide, until you try for yourself. Understand programming languages better => use them more naturally.

mbrodersen 9y ago

The dragon book is not recommended. It is very out of date. I write (among other things) high performance compilers for a living. And the Dragon book is not useful at all.