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

51–60 of 87 posts

Re: Teaching Compilers Backward

#51

Post by lisper »

slaymaker1907 wrote: post #50
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…

I agree about XML, but I don't think JSON is a reinvention of S-expression. JSON is great if you are representing a lot of (string) key/value data since it has a canonical way of representing string keyed dictionaries. I guess you can represent these as a list of pairs, but that obviously is ambiguous to a a list of pairs... JSON doesn't have this problem since if you see {"name": ...} you know that you are reading a…

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 place. So I stand by my initial characterization.

Also, Common Lisp s-expressions include a standard syntax for structures, which are essentially dictionaries. Extending that to a generic dictionary (using, say, #D(key value key value ...), which is actually available) takes about three lines of code.

Re: Teaching Compilers Backward

#52

Post by not2b »

todd8 wrote: post #34
Jasper_ wrote: post #28

Earlier quoted context omitted.

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…

After working with real-world compilers in industry I was surprised to hear CS professors that taught the compiler class say that no one should be writing parsers by hand because compiler writers should just build a table driven parser using YACC. The error messages are so much better coming out of recursive descent parsers. (I know that there are all sorts of mechanisms for better error messages, but back when I hea…

gcc ripped out its bison-generated parsers in favor of recursive descent parsers long ago, for exactly this reason (also, because C++ isn't LR-n for any n, so to get bison to work as well a third pass called "spew" sat between the lexer and the Bison parser so it could do arbitrary lookahead to figure out what the tokens were).

Re: Teaching Compilers Backward

#53

Post by munificent »

lisper wrote: post #51
slaymaker1907 wrote: post #50

Earlier quoted context omitted.

I agree about XML, but I don't think JSON is a reinvention of S-expression. JSON is great if you are representing a lot of (string) key/value data since it has a canonical way of representing string keyed dictionaries. I guess you can represent these as a list of pairs, but that obviously is ambiguous to a a list of pairs... JSON doesn't have this problem since if you see {"name": ...} you know that you are reading a…

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 the level of complexity of JSON, so it's not clear what the value proposition is here.

> JSON is also very profligate with its use of punctuation, with tons of unnecessary commas and colons all over the place. So I stand by my initial characterization.

JSON uses a richer set of delimiters, which provides:

1. Greater brevity. Basic information theory says that it takes fewer characters to encode a given piece of data if your character set is larger.

2. Some level of redundancy. This isn't necessary for data transmission for JSON, but it does make it much easier for parsers to provide good localized error reporting.

3. Easier visual parsing. Most humans have functional eyeballs connected to optical processing neurons dedicated to detecting different shapes. Using characters with a greater variety of shapes to encode structure takes advantage of that.

Don't get me wrong, I like Lisps and s-exprs. But it seems like any time any notation comes up for discussion, a lisper appears to claim how s-exprs are clearly superior. This despite the fact that that notation is decades older than almost every other syntax out there and yet still lost the popularity contest.

Re: Teaching Compilers Backward

#54

Post by deckard1 »

lisper wrote: post #51
slaymaker1907 wrote: post #50

Earlier quoted context omitted.

I agree about XML, but I don't think JSON is a reinvention of S-expression. JSON is great if you are representing a lot of (string) key/value data since it has a canonical way of representing string keyed dictionaries. I guess you can represent these as a list of pairs, but that obviously is ambiguous to a a list of pairs... JSON doesn't have this problem since if you see {"name": ...} you know that you are reading a…

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

The only standardization effort of generalized s-expressions that I know of is http://people.csail.mit.edu/rivest/Sexp.txt, which makes strings and symbols/tokens equivalent.

Most languages do not have a runtime symbol table or the concept of a symbol as a data atom. In languages outside Lisp, what would a symbol even mean?

> extend existing s-expression parsers to parse that extension. It is much, much harder to add symbols to JSON

This sounds like a form of "No True Scotsman" argument. If you're extending S-Exp parsing via Lisp, then you can extend JSON parsing too. Once you add code, then it's not a format. It's whatever you want it to be.

> Extending that to a generic dictionary (using, say, #D(key value key value ...), which is actually available) takes about three lines of code.

Three lines of code in what language? C? C++? Java? It should be obvious you're conflating two things here. Generalized formats vs. a full Lisp ecosystem.

Re: Teaching Compilers Backward

#55

Post by renox »

harperlee wrote: post #7

In a similar vein, networking is typically taught bottom-up, but some people swear by the backwards top-down approach: https://www.goodreads.com/book/show/83847.Computer_Networkin...

Yep, I had two classes about network the first was 'top to bottom' and let me really confused, the second was 'bottom to top' and I understood the whole lesson without difficulty..

That said, it could be me: I was never able to get inheritance until I learned how it was implemented..

Re: Teaching Compilers Backward

#56

Post by dragonwriter »

lisper wrote: post #51
slaymaker1907 wrote: post #50

Earlier quoted context omitted.

I agree about XML, but I don't think JSON is a reinvention of S-expression. JSON is great if you are representing a lot of (string) key/value data since it has a canonical way of representing string keyed dictionaries. I guess you can represent these as a list of pairs, but that obviously is ambiguous to a a list of pairs... JSON doesn't have this problem since if you see {"name": ...} you know that you are reading a…

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…

> s-expressions also have native symbols whereas JSON has only strings

I'm not sure “native symbols” are a good thing in an interchange format. If you are serializing constructs from a language (Lisp, Erlang, Ruby) where that's a fundamental type, sure, it's convenient, but largely that’s a language implementation detail, from an interchange perspective there's not a lot of reason to distinguish symbols from (possibly format-constrained) strings. That they are immutable (in languages where strings are either wise mutable) and/or interned doesn't mean anything at the interchange level.

Re: Teaching Compilers Backward

#57

Post by tester756 »

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

Re: Teaching Compilers Backward

#58

Post by CalChris »

hctaw wrote: post #38
todd8 wrote: post #34

Earlier quoted context omitted.

After working with real-world compilers in industry I was surprised to hear CS professors that taught the compiler class say that no one should be writing parsers by hand because compiler writers should just build a table driven parser using YACC. The error messages are so much better coming out of recursive descent parsers. (I know that there are all sorts of mechanisms for better error messages, but back when I hea…

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.

Re: Teaching Compilers Backward

#60

Post by tester756 »

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.

why?
Post reply on HN