Crafting “Crafting Interpreters” (2020) | Hacker News Reader

Crafting “Crafting Interpreters” (2020)

journal.stuffwithstuff.com

180 pointsall217 comments

Open articleView on HN

Previous discussion: https://news.ycombinator.com/item?id=22788738

Also, when it came out in print: https://news.ycombinator.com/item?id=27997167

Here is my journey with this book so far:

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

In case you keep the S-expressions:

http://www.ccs.neu.edu/home/shivers/papers/sre.txt

https://docs.racket-lang.org/parser-tools/Lexers.html#%28for...

Just for clarification: I meant S-expressions for the language in the book (by changing the proposed syntax) so I can dramatically simplify the lexer.

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!

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

It can be simpler to not make a finite state machine. Instead, try the different alternatives one by one, the longest one first.

Instead of

    if (next == '>') {
        advance()
        if (next == '=') {
            advance()
            return GREATER_EQUAL
        } else {
            return GREATER
        }
    }

it can be simpler to do

    if (next is ">=")
        return GREATER_EQUAL
    if (next is ">")
        return GREATER

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.

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.

[0] http://journal.stuffwithstuff.com/2021/07/29/640-pages-in-15...

> high-level goal: a small book that builds a complete, efficient interpreter.

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.

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

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 :))

I have a book sitting half finished (well several books). This is what I need to finish it (clutch that sand as his memorable metaphor has it)

  how can I take two implementations of the same language, and break them into incremental pieces that I can build up a chapter at a time?

This sounds really well-done.

It is!

What a coincidence—I ordered the print version, and it’s arriving today.

I’ve been following the book for a while but decided to wait until the print version was out.

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.

Reply on news.ycombinator.com