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

61–70 of 87 posts

Re: Teaching Compilers Backward

#61

Post by wrycoder »

nand2tetris teaches compilers backwards.

For that matter, they teach the whole computer backwards. Students start with NAND gates and implement a computer in a hardware definition language. They then implement an assembler for that hardware.

The next step is to implement a virtual stack machine, written in that assembler.

Then the students implement a compiler for an object-oriented language similar to Java. The target for the compiler is the stack machine language. This is done in two passes: lexing and a PEG compiler.

Finally, a simple OS is implemented.

In most courses, if you copy back what has been covered, you will have no problem completing the class. But in nand2tetris, some of the key material is omitted from each stage. You have to figure it out yourself.

https://www.nand2tetris.org/

https://www.coursera.org/learn/build-a-computer

Re: Teaching Compilers Backward

#62

Post by the-smug-one »

tester756 wrote: post #57

>implementing passes over the AST using visitors, Why Visitor Pattern is so popular around ASTs? I always feel like this particular patterns adds too much boilerplate and is not really needed in "modern" languages.

Because the visitor pattern is just pattern matching in OO clothing.

Re: Teaching Compilers Backward

#63

Post by ajfapoiawejf »

CMU's compiler's course teaches neither "forward" nor "backward".

It teaches in increasing complexity.

You start by writing the whole pipeline for straight line code. Then you add branches, and structs, and functions, in succession.

This bypasses the whole "which direction?" debate.

https://www.cs.cmu.edu/afs/cs/academic/class/15411-f20/www/a...

Re: Teaching Compilers Backward

#64

Post by hctaw »

CalChris wrote: post #58
hctaw wrote: post #38

Earlier quoted context omitted.

This has been my experience as well, but I'd extend it to parsing in production. There are a million reasons why you need to write custom parsing code and 99% of them are faster and better implemented by hand than using a generator.

Moreover, buggy parsing code is massive security hole.

well anything that takes untrusted input that might need to be validated with parsing is a massive security hole. Parsing generators don't fix this class of bug, they just change how it manifests.

Re: Teaching Compilers Backward

#65

Post by peteretep »

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…

> Two examples: XML and JSON are bad re-inventions of S-expressions.

What? This sounds like you read something that was true but you’ve misunderstood and regurgitated.

XML is absolutely S-expressions, JSON is absolutely not. How in the heck is JSON a reinvention of an S-expression?

Re: Teaching Compilers Backward

#67

Post by lifthrasiir »

ajfapoiawejf wrote: post #63

CMU's compiler's course teaches neither "forward" nor "backward". It teaches in increasing complexity. You start by writing the whole pipeline for straight line code. Then you add branches, and structs, and functions, in succession. This bypasses the whole "which direction?" debate. https://www.cs.cmu.edu/afs/cs/academic/class/15411-f20/www/a...

Yes, very much yes! Compiler pipeline is highly decomposable and can be taught in pretty much any order. Which one to teach first is really the matter of importance (like, I learned physics by starting with dynamics and as a result I have a good understanding of dynamics but not much for subsequent topics like thermodynamics, optics or electomagnetism...). I do agree the importance of parsing is currently overstated, but its solution has to be topic-agnostic as you can't build compilers only with parsing or codegen.

Re: Teaching Compilers Backward

#68

Post by tikhonj »

pitterpatter wrote: post #66

I want to see new compiler paradigms. Most compilers end up working the same way but is there room to innovate? I know the Rust compiler is kinda moving away from "passes" to "queries".

Program synthesis seems like the most promising area of research for that—treat compilation as a search problem or even a series of search problems rather than as a pipeline of (mostly) deterministic steps. Couple a compiler with search-based optimization, some kind of lightweight verification and a more interactive interface with the programmer and you have a programming environment that can aggressively use today's powerful compute resources to provide a qualitatively different experience.

Re: Teaching Compilers Backward

#69

Post by tikhonj »

munificent wrote: post #53
lisper wrote: post #51

Earlier quoted context omitted.

Sure, but 1) s-expressions also have native symbols whereas JSON has only strings, and 2) it is trivial to extend standard s-expression syntax to include a native dictionary serialization, and to extend existing s-expression parsers to parse that extension. It is much, much harder to add symbols to JSON. JSON is also very profligate with its use of punctuation, with tons of unnecessary commas and colons all over the…

> 1) s-expressions also have native symbols whereas JSON has only strings, This is inconsistent with the claim that s-exprs are better because of their simplicity. Having two very similar string-like things is unnecessarily complex for little (no?) benefit in return. 2) > it is trivial to extend standard s-expression syntax to include a native dictionary serialization Sure, and when you do you get something at about…

I mean, greater brevity in theory, but having used both s-expressions and JSON for config files, I can tell you that the s-expression version ends up noticeably less verbose and noisy in practice.

> This despite the fact that that notation is decades older than almost every other syntax out there and yet still lost the popularity contest.

Beyond some minimal level, quality and popularity aren't all that heavily correlated; something not becoming popular tells us almost nothing about it.

Re: Teaching Compilers Backward

#70

Post by lisper »

peteretep wrote: post #65
lisper wrote: post #22

Earlier quoted context omitted.

> 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…

> Two examples: XML and JSON are bad re-inventions of S-expressions. What? This sounds like you read something that was true but you’ve misunderstood and regurgitated. XML is absolutely S-expressions, JSON is absolutely not. How in the heck is JSON a reinvention of an S-expression?

How is it not? Both are serialization formats for trees with strings and numbers at the leaves.
Post reply on HN