This blogpost shows how learning how to make languages are useful. I would’ve never considered making a comment DSL that describes code snippets in books.
The blogpost on actually typesetting it is also very interesting[0] — you should really check that post out as well.
I decided to follow the book but write in Clojure (at least the interpreter) instead of Java.
This went well, but then I decided I also wanted to write the lexer as a state machine in a data DSL (nested maps).
This went kind of well, but it seemed incredibly verbose, because a ton of states would have the same input messages, so I decided to write a macro that maps regular expressions to tokens one to one and produces a (data DSL) state machine that later drives the lexer.
Then I realized that I get a non-deterministic state machine that I needed to convert to a deterministic one.
Then I decided that the string representation of regular expressions suck, and that I want to write a DSL for those too...
Then left at the above, switched to a few other books in between and am trying to decide whether I should ditch the lexer entirely and just use s-expressions. I probably won't, because it's fun so far, but boy did I get sidetracked...
That's what I did. I made a Scheme instead of Lox because I'm not that interested in parsers; s-expression recursive descent parsers are almost trivial to implement. And I wanted to try implementing macros, which are so much simpler in a Lisp.
I loosely followed the second half of book - but I found that for a Scheme or Lisp, it made more sense to have separate parsing and compilation steps. Because implementing quotation is trivial if you parse first, but would have been kind of messy to do in a single pass.
(I also used Rust instead of C, which means I skipped a lot of the memory management code, at the cost of more indirection in some places.)
For what it's worth, if you only go through the implementation of the tree-walk interpreter in Java, that's 234 pages.
The next 370-ish pages are the C re-implementation as a bytecode interpreted language. So that adds a bunch more stuff to cover: actually compiling, bytecode interpretation, garbage collection, etc.
Also, a huge chunk of it is code listings. Unlike other comparable books I've seen, Nystrom's doesn't skimp on the details, or make you go download the code from GitHub. Compared to how other books I've seen tend to do it, I'd argue that that's several hundred pages' worth of making the book quicker to read.
This book seemed like a labor of love before I read this blog post. Now it seems just more so. Thank you Robert, I wrote my interpreter in C++ and learned so much about the language through my tiny Lox (I've been writing C++ for 8 years now :))
This book is incredible. Super well-written and informative on a previously opaque topic, with information delivered in a conversational, approachable way. And the fact that it has _so much_ content crammed in, AND is offered for free on the Internet, is just crazy to me.
Looks like perfect case for Literate Programming. And LaTeX is much nicer than Markdown, IMHO. Markdown is too limited and is not useful for fixed media. Footnotes is simplest thing which is not supported, for example.
18 comments
[ 2.7 ms ] story [ 49.0 ms ] threadI’ve been following the book for a while but decided to wait until the print version was out.
The blogpost on actually typesetting it is also very interesting[0] — you should really check that post out as well.
[0] http://journal.stuffwithstuff.com/2021/07/29/640-pages-in-15...
I decided to follow the book but write in Clojure (at least the interpreter) instead of Java.
This went well, but then I decided I also wanted to write the lexer as a state machine in a data DSL (nested maps).
This went kind of well, but it seemed incredibly verbose, because a ton of states would have the same input messages, so I decided to write a macro that maps regular expressions to tokens one to one and produces a (data DSL) state machine that later drives the lexer.
Then I realized that I get a non-deterministic state machine that I needed to convert to a deterministic one.
Then I decided that the string representation of regular expressions suck, and that I want to write a DSL for those too...
Then left at the above, switched to a few other books in between and am trying to decide whether I should ditch the lexer entirely and just use s-expressions. I probably won't, because it's fun so far, but boy did I get sidetracked...
http://www.ccs.neu.edu/home/shivers/papers/sre.txt
https://docs.racket-lang.org/parser-tools/Lexers.html#%28for...
But using s-expressions for regular expression DSL is a given, since I would do it in macros. The resources you linked seem fantastic, thank you!
I loosely followed the second half of book - but I found that for a Scheme or Lisp, it made more sense to have separate parsing and compilation steps. Because implementing quotation is trivial if you parse first, but would have been kind of messy to do in a single pass.
(I also used Rust instead of C, which means I skipped a lot of the memory management code, at the cost of more indirection in some places.)
Instead of
it can be simpler to do The price is a little bit of performance. It needs more than one character of "lookahead" and may have to re-scan some parts of the input.Bob, you wrote 600 full-sized pages, not including appendices.
And I'm going to spend my 3-week vacation coming up reading all of them.
The next 370-ish pages are the C re-implementation as a bytecode interpreted language. So that adds a bunch more stuff to cover: actually compiling, bytecode interpretation, garbage collection, etc.
Also, a huge chunk of it is code listings. Unlike other comparable books I've seen, Nystrom's doesn't skimp on the details, or make you go download the code from GitHub. Compared to how other books I've seen tend to do it, I'd argue that that's several hundred pages' worth of making the book quicker to read.