News for hackers. Stuff that matters.
Re:What can we learn from how compilers are designed? by vicpara on Friday March 16, 2018 @05:10PM (#16604049)
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,_Techniq...

Re:What can we learn from how compilers are designed? by mojuba on Friday March 16, 2018 @05:45PM (#16604246)
> 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.

Re:What can we learn from how compilers are designed? by justinpombrio on Friday March 16, 2018 @06:15PM (#16604376)
> 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.

Re:What can we learn from how compilers are designed? by munificent on Friday March 16, 2018 @07:17PM (#16604674)
> 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.

Re:What can we learn from how compilers are designed? by compiler-guy on Friday March 16, 2018 @07:04PM (#16604604)
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.

Re:What can we learn from how compilers are designed? by skybrian on Friday March 16, 2018 @07:03PM (#16604593)
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 [2] https://github.com/munificent/wren

Re:What can we learn from how compilers are designed? by HumanDrivenDev on Saturday March 17, 2018 @01:51AM (#16605761)
well there's no need for an AST in a concatenative language - that might be what he's talking about.
Re:What can we learn from how compilers are designed? by mojuba on Friday March 16, 2018 @07:04PM (#16604603)
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).
Re:What can we learn from how compilers are designed? by robertelder on Friday March 16, 2018 @07:09PM (#16604634)
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-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.

Re:What can we learn from how compilers are designed? by seanmcdirmid on Friday March 16, 2018 @08:19PM (#16604930)
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.
Re:What can we learn from how compilers are designed? by verletx64 on Friday March 16, 2018 @09:12PM (#16605085)
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.

Re:What can we learn from how compilers are designed? by slx26 on Saturday March 17, 2018 @05:53AM (#16606219)
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.

Re:What can we learn from how compilers are designed? by magpi3 on Friday March 16, 2018 @09:57PM (#16605217)
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.

Re:What can we learn from how compilers are designed? by Ono-Sendai on Saturday March 17, 2018 @12:31AM (#16605617)
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.
Re:What can we learn from how compilers are designed? by kqr on Saturday March 17, 2018 @02:43AM (#16605864)
It's surprisingly practical to view a lot of data mangling tasks through one's compiler glasses.
Re:What can we learn from how compilers are designed? by mbrodersen on Sunday March 18, 2018 @08:34PM (#16615380)
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.
Re:What can we learn from how compilers are designed? by kazinator on Friday March 16, 2018 @07:00PM (#16604579)
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_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.

Re:What can we learn from how compilers are designed? by dfox on Friday March 16, 2018 @07:42PM (#16604777)
One thing I tried to do in dfsch is to use the same IR format (in the sense of being interpretable by the interpreter) accross all the stages. What I found out is that this is surprisingly hard to do in Lisp-1 language while preserving the semantics to the extent of somehow abandoning the language and thinking about making it CL-style fully lexically scoped (ie. with suport for labels and similar special forms) Lisp-2.

(CPS-style IR does not make much sense for dfsch, as it explicitly and intentionally does not support call/cc, as the main use-case is easy and straightforward C interoperability)

Edit: dfsch distinguishes mutable, immutable (which are somewhat redundant and in fact consume one combination of tag bits which can be used for something more useful, like strings) pairs and CDR-coded lists, which are always immutable and CDR-coded lists have additional slot that records where they came from in case of things that either was parsed from source or is result of macro-expansion, which in my opinion meets the intention of R5RS. On the other hand the very aggressive constant folding done by the macro-expansion stage probably does not.