Learn C and build your own Lisp (2014) | Hacker News Reader

Learn C and build your own Lisp (2014)

buildyourownlisp.com

151 pointspelasaco45 comments

That book is a little bit controversial. Here is the main criticism leveled at it: https://gist.github.com/no-defun-allowed/7e3e238c959e27d4919...

> The interpreter uses very dubious implementation decisions, and the language that is created as a side-effect makes reasoning about anything near impossible.

Personally I really like the writing style of the book and had fun following it BUT you definitely shouldn't use it as your primary source to learn about these things.You need to do you own research and figure out why some ideas presented in the book are dead-ends that should be avoided.

It is definitely NOT a useful for those who want to learn the proper way to implement a Lisp, especially a non-toy one.

Alternatives are Crafting Interpreters by Robert Nystrom and MAL (Make your own Lisp). Here is also a good-short tutorial how to write one in OCaml: https://bernsteinbear.com/blog/lisp/00_fundamentals/

Edit: Updated link to the criticism.

My favorite language implementation tutorial is "An Incremental Approach to Compiler Construction" by Abdulaziz Ghuloum: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf

What makes it stand out is that it shows you how to build a compiler rather than an interpreter, and shows that it's really not that much more difficult.

There is a book-length "sequel" to this paper that goes into more detail: https://github.com/IUCompilerCourse/Essentials-of-Compilatio...

I did this one too get back into programming after a career change and it worked for me.

One tip I got back in the day (mid-90's), regarding compilers vs interpreters.

Make the compiler output some kind of bytecode in a format, which can be easily interpreted, or with the help of a Macro Assembler, very quickly transformed into machine code.

It won't win performance prices, however it is quite easy to get going.

Naturally fitting these ideas into Lisp like languages is quite straightforward.

Thanks for the book tip.

It moves fast at the start so maybe not for the complete beginner, but I can really recommend "Lisp in Small Pieces" by Christian Queinnec: https://www.amazon.ca/Lisp-Small-Pieces-Christian-Queinnec/d... It's a bit old now (early 90s) but Lisp is timeless :) I think it's out of print now. It goes through the implementation of both interpreters and compilers for Lisp, in Lisp.

It starts with a very minimal meta-evaluator for something similar to McCarthy's original Lisp, and then explains why all the changes from Lisp 1.0 since were made. Why did language designers change things in the first place? And then it shows you how those differences are implemented. One of the first lessons is the problems with the semantics of dynamic scoping, and the implementation of dynamic vs. lexical environments. I personally worked through the book writing in SML. Despite the name and approach, it's not really a Lisp book; it's a compiler implementation book.

It's still in print. Or at least, the last print run has not run out!

Wow, it's... very expensive. Is there an ebook which doesn't cost more than a bookshelf full of paperbacks? It sounds like an excellent book, and, as you mention, the sort of thing which is timeless.

It's excellent. Get it at the library before buying.

Cheaper than some stupid generic college textbook though.

This looks like an excellent way of doing a deep dive that I'm tempted to do myself, now. It looks like a fascinating historical exposition of what is indeed one of the oldest languages in our field.

But for someone who just wants the most dead simple Lisp implementation possible, there's always SICP, which ends in them writing out a basic metacircular lisp intepreter on just a few blackboards, in Scheme.

Of course they skip parsing and boring details, as well as macros. But it's a good place to start.

I've gone through similar books at some point. The closest that comes to "Crafting Interpreters" is "Writing an Interpreter/Compiler in Go" by Thorsten Ball. You can tell that these authors really took their time to describe everything going on with the code presented and carefully guide you through testable code leading to a full functioning interpreter at the end without having to look elsewhere outside the book.

How well do these books strike a balance between feeding you the code and forcing you to think for yourself before implementing the code?

Why don’t you check yourself? https://craftinginterpreters.com/contents.html

I haven't worked through these books so someone that has would know.

As the books document complete implementations, they do feed you the code, and it is easy to fall to the trap of just copying the code from the book. I think the best approach is to port it to another implementation language as you read the book. However, compared to other books I've seen these are more "granular" in the code explanations so you're simulating the authors' coding thought process instead of just looking at big blocks of finished code.

In particular in Crafting Interpreters, there are many parts where you go back and revise the code from previous chapters as some language features/concepts are introduced in subsequent chapters (my memory of Writing an Interpreter/Compiler in Go is not that fresh).

I think it is a good sign that these books start with "int main()" (or it's equivalent). Other books I've seen start by describing functions in isolation, so they are not immediately testable, and it encourages the reader to just get the finished codebase to have something to play with.

That criticism seems pretty tangential to BYOL's stated goal of learning C.

"C programs crashing is a fact of life. If anything goes wrong the operating system kicks them out" is _very_ bad advice for someone learning C. The introduction reads

> This book is for anyone wanting to learn C, or who has once wondered how to build their own programming language.

which I interpret as having "design a language" as another goal. Arguably the book succeeds at building a programming language, but it mangles the theory in unhelpful ways, e.g. lexical scoping isn't a static analysis per chapter 16, nor is parsing the consumption of an abstract syntax tree per chapter 10.

Original author of that critique here - it's been edited a bit since that fork was made: https://gist.github.com/no-defun-allowed/7e3e238c959e27d4919...

Updated the link, thank you!

I think it's right to emphasise 'your first interpreter', and it does depend on the person's prior proficiency with C and language design/implementation. It's perfectly doable though, my first compiler (technically a transpiler) was written in C, and it worked well although I was hardly a C n00b.

(Just a polite other viewpoint)

Thanks, that's a good point. If it's also a book for learning C, I'd think the proficiency of the audience varies substantially then.

> If it's also a book for learning C

that would be a car crash!

(edited cos it came across a bit horrible unintentionally)

There are some many things wrong with this book but this critique is really bad and I wish people would stop sharing it.

It starts with: >> First off: God help you if you are going to write your first interpreter in C of all things.

How can anybody take this seriously.

Both Crafting Interpreters and MAL are bad tutorials for non-toy Lisps and use dubious implementation decisions (just not as many as "build your own lisp").

Good references for building a Lisp are "Lisp in small pieces" and Nils Holm's "LISP from nothing".

I'm interested to know what is wrong with the approach in Crafting Interpreters, if you don't mind sharing.

Not the parent and I've never read that particular book, but the premise seems rather bizarre to me, where is the excitement in implementing a slow version of Java in Java? If anyone is going to want to implement a custom interpreted language, it will likely be very different to Java, e.g. Lisp, the core of a DSL or configuration language. But it's still going to probably have functions and data types. Writing Lisp in C is exciting, one is moving up the abstraction hierarchy, building a more expressive and powerful language.

If one wants to learn specifically how Java works, then maybe a book on compilers would be better?

You might not be excited about “implementing a slow version of Java in Java”, but that doesn’t make it a bad approach. (Also, second part is about implementing same interpreter in C)

Well implementing all the OOP semantics and such could complicate and dilute the essentials. A simpler language would also make it easier to cover more ground, such as type checking. So I don't think it sounds ideal from a pedagogical perspective either, but again, I haven't read the book.

Note that Lisp in Lisp (SICP) works well because Lisp itself is very simple and just the essentials. It's just one chapter in SICP.

Java in Java isn't slow, it is a matter of how it is done.

JikesRVM, MaximeVM and now GraalVM.

I agree but the context was interpreters. GraalVM is a compiler, it JIT compiles bytecode into machine code.

Interesting, I started going through Lisp In Small Pieces a while ago, and I enjoyed the first chapter, but put it on the shelf for a while.

I've been meaning to pick it back up, but was considering going through Crafting Interpreters first (and started reading it but since I don't know Java I spent more time trying to figure out a good setup with Java and Emacs).

How is Nils Holm's "LISP from nothing?" I discovered it a while ago, but probably judged it by its cover (and the typesetting).

Any other recs in the PL/compilers world would be appreciated. I'm probably the only person that did not like EOPL. I bought the 3rd edition, went back to the 2nd edition, and at some point early on the eval did not work. Which is a shame since I enjoyed Friedman's Little/Seasoned Schemer and Scheme and the Art of Programming

> > The interpreter uses very dubious implementation decisions, and the language that is created as a side-effect makes reasoning about anything near impossible.

That is in my opinion just completely unconstructive hate that I would not take serious as criticism. It doesn't give any concrete things that could be improved and instead just gives some vague statement about the whole site being generally bad.

Good thing the rest of the document is dedicated to pointing out all the specific things wrong with it, then?

The things it points out seem rather small and nitpicky. Doesn't really support the negative summary of the article.

The criticism seems well-founded, but at the same time, perfect is the enemy of good. If the book is entertaining, I think people should be allowed to learn through their mistakes if the alternative is not learning at all. We need more people who feel empowered to build interpreters and whatever they want without worrying too much about proper form.

My dad was a high school math teacher who became a COBOL programmer by accident in the early 1980s because a large local IT company put out an ad saying they’ll hire anyone with a college degree. A couple of years later, when I was eight, I was writing terrible BASIC programs and asked him if it’s possible to invent a new programming language. He showed me how to write an interpreter in BASIC for a custom language. It wasn’t useful for anything and it certainly had no LISP-like elegance, but it was a revelation to me that everything that happens on the computer was defined by people, and I can be one of those people even if I’m an eight-year-old in the middle of nowhere.

""" it was a revelation to me that everything that happens on the computer was defined by people, and I can be one of those people even if I’m an eight-year-old in the middle of nowhere. """

Never forget.

The problems with the standard library (and I will say I agree with the criticism) all seem to stem from the fact that this text appears to be a 'port' of the "Write yourself a Scheme in 48 hours" which implements a scheme interpreter in haskell from 2008, thus the standard library is built upon haskell's list processing.

Implement Scheme in Common Lisp. Peter Norvig has written about it. Read it online:

Chapter 22, Scheme: An Uncommon Lisp

https://norvig.github.io/paip-lisp/#/chapter22

Chapter 23, Compiling Lisp

https://norvig.github.io/paip-lisp/#/chapter23

BYOL gets criticized, and folks recommend other texts over it, but as someone who has worked through both BYOL and Crafting Interpreters I can say they both provide value.

BYOL is nice because it’s short and quick (you can power through it in a weekend) and gets you some momentum if you’ve never written a basic language.

Move on to something like Crafting Interpreters which is a well thought out book but definitely more of a marathon than a sprint.

The bootstrap project did the other way around:

They did build lisp from a intermediate assembly language, then a bootstrap C compiler to compile tinycc then gcc 4.7.4, then gcc (the last iso C++98 one), then the last gcc (is c++11).

Yep, moving gcc to c++ is one of the biggest mistakes in open source software, ever.

Bootstrap project?

https://bootstrappable.org/projects.html

Actually I kind of enjoy that decision, after years of putting off with "my compiler compiles yours", it was yet another domain where C lost to C++.

Regarding FOSS, C++ is also a UNIX child, born on the same offices.

Yep, we all know the real issues are c++ itself and compilers by themselves.

Read SICP and build your own Scheme in Scheme.

Reply on news.ycombinator.com