Ask HN: Ideas for a Programming Language Book

6 points by wycliffb 7 years ago | 3 comments

Hey! So I intend to write an end-to-end book on the design and implementation of a programming language, right from design choices, type system, native implementation to formal semantics (K Framework). Any pointers/requests?

s-p-n 7 years ago |

While working on a language design over the last 6 years, I've created my own rules to achieve my own goals. I made a seemingly backwards switch from using an Abstract Syntax Tree, to a method of just simply lexing and replacing.

I find that it's very hard to write "good code" when writing a language. I also found that the Abstract Syntax Tree didn't help me write good code. It appeared to, but the biggest stride I made was when I took out that middle man and abstracted the grammar and lexer instead.

I would never have taken out the AST if it weren't for one problem: lexer state changes at compile time. Now, it's possible to do that with an AST.. But in my case, I couldn't go back to the lexer and change states after the AST was generated. I was specifically working on regular expressions, string interpolation, and XML Tags, and managing precedence for all these things (you gotta remember, greater than and less than tokens hate XML...). My biggest problem was that in each of those "sub-syntax" features, each sub-syntax needed the entire feature set and complexity of the rest of the language. I solved all that. String interpolation was the straw that broke my delicate parser's back. Before I knew it, despite my attempted use of "good practice", the token ambiguity problem became far too big to solve without modifying the lexer. And modifying the lexer was simply too hard, as many sub-systems managed each other, and I noticed I somehow created a very deep dependency hell despite my efforts.

Today, my grammar isn't perfect. I did, however, gain the ability to entangle the lexer with an API that tries to achieve loose coupling between rules, but the coupling problem is inherit to language design- the issue is ingrained in the algorithm.

See, writing grammars are very susceptible to tight coupling. I guess that's my whole point.

We should talk sometime.

s-p-n 7 years ago | |

Oh, it should be noted that I no longer needed an AST after rethinking my grammar approach. It was easy enough to just translate in-place. The best part, it wouldn't be too hard to change the output to AST, but I think my next step is to output an execution stream instead of a complete executable program. I'm currently considering the use of neural networks for error detection and suggested error-correction.

federicobond 7 years ago |

Not sure which audience you are targetting but I would love to read more on modern compiler design. There is very little information on the web on how to design a compiler to provide good error messages and code intelligence features even in the face of incomplete or incorrect source code.

A good starting point would be some of the themes touched towards the end of this article: https://blog.adamant-lang.org/2019/dreaming-of-a-parser-gene...