Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Teaching Compilers Backward

blog.sigplan.org

Post reply on HN
Print view View original

21–30 of 87 posts

Re: Teaching Compilers Backward

#21

Post by hardwaregeek »

I learned how to compile to WebAssembly by getting nice and intimate with the WebAssembly spec, learning the ins and outs, then writing a basic emitter for the bytecode, then writing a code generator for basic operations like arithmetic, then extending it to locals, then first class functions, etc. So kind of backwards.

I did start with a parser and typechecker, but if anything that made it too difficult. I had all of these extremely high level concepts that I struggled to map to WebAssembly (pattern matching, closures, etc.) and discouraged me in the process. If I had started with WebAssembly and moved to my high level language, I'd probably have restricted myself to a much more practical set of language features. On the flip side, my language would probably be influenced by how easy it is to code generate to WASM, which isn't necessarily what I want.

Re: Teaching Compilers Backward

#22

Post by lisper »

smasher164 wrote: post #3

Much to the chagrin of a lot of educators, I think this approach is the way to go. Too many compilers classes get bogged down in grammar classifications and parsing. Some argue that parsing is a microcosm of the rest of the compiler, since it requires one to transform a program from one representation to another. However, this message doesn't really come across when you're operating on highly unstructured input, and…

> Too many compilers classes get bogged down in grammar classifications and parsing.

Oh so very this.

This has repercussions far beyond students who can't write compilers. It infects the entire culture of software engineering with people who think that syntax is everything, and who spend their lives designing grammars and writing parsers for them. The problem with that is for every new grammar, it's not just that you need a new parser, but some human needs to learn that grammar too if it's going to do you any good at all. So we have this proliferation of zillions of grammars, not just in programming languages, but in config files, data formats, etc. Two examples: XML and JSON are bad re-inventions of S-expressions. And the sieve language (which I am currently dealing with because I'm working on a new spam filter) is just an abomination from top to bottom.

Re: Teaching Compilers Backward

#23

Post by whateveracct »

smasher164 wrote: post #3

Much to the chagrin of a lot of educators, I think this approach is the way to go. Too many compilers classes get bogged down in grammar classifications and parsing. Some argue that parsing is a microcosm of the rest of the compiler, since it requires one to transform a program from one representation to another. However, this message doesn't really come across when you're operating on highly unstructured input, and…

the best PL/compilers classes i took were using Scheme, with a simple pattern matching macro [1]

so there was no parsing. it was just s-exps. But you still got to write interpreters with different semantics & compilers.

[1] https://gist.github.com/cbrooks90/125393006ec7bd137ff6364a9f...

Re: Teaching Compilers Backward

#24

Post by jfoutz »

agnokapathetic wrote: post #13

This approach has the added benefit of teaching "mechanical sympathy". We're often told "Let the complier do the work" without really understanding what "work" the compiler is doing. Learning concepts like branch prediction, out-of-order execution, pipelining, register planning, caches, memory management is far far more important than Lexing/Parsing/Intermediate Representations and SSA.

I have a different take. Compilers are usually the first really big project students encounter. There's a lot of complexity around keeping things organized and still efficient. There's a lot of real world hassle around both ends - the input can be anything, and the implementer has to deal with that. The output is subtle with lots of gnarly little details that have to be exactly right.

Compilers also have this wonderful side effect of eliminating all the magic. after a compiler class, there aren't many mysteries left about how computers work. they take a string and do stuff.

Personally, I haven't gotten much milage out of shift reduce parsing, but parsing in general has been super important. Intermediate representations, coming from complexity to something canonical, and then transforming that back to complexity has probably given me the biggest bang for my time. If you squint your eyes, frameworks and dsls are kinda just intermediate representations. Sticking the parts together in a coherent way helped me.

I've never been in a situation where out-of-order execution really mattered to my code. but my compiler course taught me enough to know valgrind, so I'd go look for whatever the modern equivalent is.

Everybody is different, but compilers for me is where everything really jelled. There is so much complexity you just eat, day after day. Memorization only got me so far, at some point, I had to have real organization and clarity.

I think, if I had to give a compiler class, I'd start in the middle. tools for manipulating trees, tools to build that tree up, tools to tear that tree down. I know it's kind of a breezy approach, but the clarity seems like a prerequisite for dealing with complexity. the tree is the one thing the implementer owns, and is free to structure (and restructure) however they wish.

Re: Teaching Compilers Backward

#25

Post by [deleted] »

lisper wrote: post #22
smasher164 wrote: post #3

Much to the chagrin of a lot of educators, I think this approach is the way to go. Too many compilers classes get bogged down in grammar classifications and parsing. Some argue that parsing is a microcosm of the rest of the compiler, since it requires one to transform a program from one representation to another. However, this message doesn't really come across when you're operating on highly unstructured input, and…

> Too many compilers classes get bogged down in grammar classifications and parsing. Oh so very this. This has repercussions far beyond students who can't write compilers. It infects the entire culture of software engineering with people who think that syntax is everything, and who spend their lives designing grammars and writing parsers for them. The problem with that is for every new grammar, it's not just that you…

[deleted]

Re: Teaching Compilers Backward

#26

Post by 908B64B197 »

agnokapathetic wrote: post #13

This approach has the added benefit of teaching "mechanical sympathy". We're often told "Let the complier do the work" without really understanding what "work" the compiler is doing. Learning concepts like branch prediction, out-of-order execution, pipelining, register planning, caches, memory management is far far more important than Lexing/Parsing/Intermediate Representations and SSA.

These belong in a separate class about low level systems (CPU architecture and assembly).

Re: Teaching Compilers Backward

#27

Post by kazinator »

Jtsummers wrote: post #11
smasher164 wrote: post #3

Much to the chagrin of a lot of educators, I think this approach is the way to go. Too many compilers classes get bogged down in grammar classifications and parsing. Some argue that parsing is a microcosm of the rest of the compiler, since it requires one to transform a program from one representation to another. However, this message doesn't really come across when you're operating on highly unstructured input, and…

Yeah. I got really good at parsing to an AST and various semantic analysis steps. One course got too bogged down there and we never went further. Another got to the point of emitting machine code, but no optimizations. Only one, in grad school, actually went the whole way (prof could assume knowledge of parsing so that step was fast ) with anything on optimizations. Given that parsing is also a critical part of many…

Optimizing work requires wrangling fairly complex, multi-faceted data structures like augmented graphs. Unless you do that in a very high level language in which that is as easy as possible, it's largely intractable for undergrad.

When I did this stuff in school, it was C on Unix. Nobody was going to get to a debugged data flow analysis of basic blocks with all the liveness info, optional register allocation, DAG-driven CSE, and whatever topics out of the Dragon Book. Not in one or even two semesters, with undergrad-level C skills, and a full load of other courses.

I think that working in Java wouldn't help much. You don't have premature free problem in Java, but in a batch compiler written in C, you can just avoid calling free.

Re: Teaching Compilers Backward

#28

Post by Jasper_ »

smasher164 wrote: post #3

Much to the chagrin of a lot of educators, I think this approach is the way to go. Too many compilers classes get bogged down in grammar classifications and parsing. Some argue that parsing is a microcosm of the rest of the compiler, since it requires one to transform a program from one representation to another. However, this message doesn't really come across when you're operating on highly unstructured input, and…

The overemphasis on parsing is ridiculous, with way too much theory that has little practical application. Parsing is boring, IMHO -- production compilers basically all use hand-written recursive descent, it's boring but it works just fine and is plenty readable, no need to replace it.

The rest of the compiler is far more interesting, but a few people in the 60s got caught up on parsing theory based on limitations of their computers at the time, so there's a lot more formalism and theory and of course that's what academia teaches.

Re: Teaching Compilers Backward

#29

Post by ahartmetz »

JoelMcCracken wrote: post #9
smasher164 wrote: post #3

Much to the chagrin of a lot of educators, I think this approach is the way to go. Too many compilers classes get bogged down in grammar classifications and parsing. Some argue that parsing is a microcosm of the rest of the compiler, since it requires one to transform a program from one representation to another. However, this message doesn't really come across when you're operating on highly unstructured input, and…

This is what happened in my compilers class. We spent, like, the whole thing talking about grammars etc. Which is mind-numbingly boring (to me), and especially given a significant number of industry parsers are hand-rolled/recursive descent style, its not terribly useful information.

Same here, at FU Berlin. We spent several weeks on LR and LALR parsers and such and, IIRC, even more than a week on regular expressions. Somehow we talked about two-address and three-address instructions, but never seemed to do any code generation, and certainly no optimization. It was very disappointing.

Re: Teaching Compilers Backward

#30

Post by smasher164 »

waynesonfire wrote: post #17
smasher164 wrote: post #3

Much to the chagrin of a lot of educators, I think this approach is the way to go. Too many compilers classes get bogged down in grammar classifications and parsing. Some argue that parsing is a microcosm of the rest of the compiler, since it requires one to transform a program from one representation to another. However, this message doesn't really come across when you're operating on highly unstructured input, and…

And, it seems to be is a really understood problem that has efficient solutions.

Yes and no. The traditional goal of a parser that accepts valid inputs, and rejects invalid inputs is well understood.

A more relevant goal of error-tolerant parsers that can respond quickly to incremental changes is still a wide research problem.

Post reply on HN