As someone who has worked on various Lisp implementations over time, as well as programmed in Lisp, C, C++, Java, and several other programming languages, I feel vaguely knowledgeable enough to give a pretty harsh review of this book. First off: God help you if you are going to write your first interpreter in C of all things. No one I know thinks it’s a good idea to start inventing a programming language, which perhaps is one of the more ill-defined and bug-prone things you can do, with an implementation in C. So the premise is already a bad idea.
Second off: God can’t help you if you read this book. The interpreter uses very dubious implementation decisions, and the language that is created as a side-effect makes reasoning about anything near impossible. Perhaps it could be done well - Nystrom’s Crafting Interpreters shows off a bytecode machine written in C (but only after a tree-walking interpreter written in Java), but this book ain’t it.
Someone once said “you can’t be doing it wrong if nobody knows what you’re doing.” And when you have a book which just introduces a language lazily, there is no way to check if you’ve implemented anything correctly. I suppose that is not a problem if you have decided it can be “your” language, and the only notion of ownership is that it contains your blunders (as well as those by the author); but it makes coming up with a mental model for the language absolutely impossible, and so the language is useless because programs cannot be written in it.
The book also misses the “point” of Lisp frequently. The first occurrence is in making parsing more difficult than it should be.
It never struck me as a good idea to start off with an evaluator for a toy calculator language, and then only slowly build up to an actual programming language. This is the beginning of the “nobody knows what you’re doing” line, really. The language is never presented in the book - you are just expected to know how it works from the C code. And you end up rewriting a lot of code as the author drip-feeds you marginally better approximations of the programming language.
And a parser generator is very overkill for a Lisp parser - just use recursive decent! If it weren’t for how C makes memory management a pain, it would be pretty easy to write a recursive decent parser, and you would have a program with no external libraries.
As for why a parser generator is a bad idea for Lisp: the single syntax rule
E ::= atom | '(' E* ')'
is pretty simple to translate into an algorithm for a reader. Such an algorithm could be written in English as “if the next character is an open paren, keep reading expressions until you see an otherwise unmatched close paren; else if the next character is whitespace, keep looking; else read an atom until you reach either kind of paren or whitespace.” Explaining how parser combinators and EBNF work is unnecessary with this operational description.
It’s okay if a program crashes during development, but our final program would hopefully never crash
braces for disaster
but our final program would hopefully never crash, and should always explain to the user what went wrong.
Okay, guess we avoided that one.
C programs crashing is a fact of life. If anything goes wrong the operating system kicks them out.
Nope, we’re fucked. Note that, without manual intervention
c.f. -fsanitize=memory, C programs do pretty much no error detection
and a lot of things can go wrong without it being the kind of error
that the operating system has to handle.
And, while a crash is preferable to the program doing something bad,
it is not useful on its own to find programming errors. We built a few of
the programs, gave them ^D and they all gave a segmentation fault, which is as
much of a useful error as “you’re sick” is useful diagnosis from a doctor. At
this point, we really would want to pull up gdb and try to work our way
backwards from the cause of the crash. (gdb fortunately is mentioned by the
book, but the reader isn’t given much of a clue other than it “can be difficult
and complicated to use”, which doesn’t inspire much confidence; and the only
instruction is to figure out how to run your program under gdb.)
Now, I will be honest, I hate C with a passion. You shouldn’t learn it to write an interpreter, you pretty much should never even have a reason to use it, and I’d hate to write “reliable” software in it. But credit where it’s due: if “C programs crashing is a fact of life” was true, then most computers would be very broken. People who write real C programs manage to not mess up that badly…most of the time (the other times usually produce a CVE report and everyone has to update their systems).
We start to see an object representation emerge in this chapter.
I suppose we could say that it is silly to have a value and error
type all in a struct instead of using a union. Any Lisp value, moreso
when other data types are introduced, is going to be huge.
Ideally in an actual programming language we would also implement
errors using exceptions, so that we don’t have to check that every Lisp
value isn’t an error value, but that isn’t going to happen in this book.
Also, shouldn’t we use an enum type and then use that instead of int?
Early on in the book, we are taught something else that contradicts what might be taken for granted in Lisp: the ability to add language features without hacking the parser or interpreter (by means of a macro system). We are told that one needs to introduce syntax, data types, parsing, and semantics. One should be aware that, depending on the feature, usually only one or two of those would be required.
For example, introducing a new data type only requires defining
the data type and relevant functions. The “semantics” of those functions
is very different to, say, the semantics of the if special form, as the
user does not need to know any special evaluation rules or anything of the
sort. In a Lisp system, many other language constructs can be implemented
using a macro system, and they do not need new data types, parsing (which,
by the way, is an implementation detail and not part of a language), or
any syntax, at least from the point of view of the parser.
I suppose that a “Q-expression” is their own poor attempt at adding a macro system, but even that is far harder than a macro system. A macro does have grammar, I suppose, but it does not affect the reader at all. It does not require a new data type - a macro call looks pretty much exactly like a normal function call. And, yes, the evaluator must be modified to handle macros. But that is the only correct step on the list.
The “q-expression” stuff reminds me of a fexpr, which is a function
which is called without evaluating its arguments. But BYOL does
evaluate the arguments always, and instead quotes its arguments. And
it quotes them in a weird way: instead of writing =’(a b c)= we write
{a b c}. To quote a symbol (i.e. =’a=) one is supposed to write…
{a}? And that is not going to end up as a list, but {a b c} will?
How do you write a function call with 0 arguments? I don’t think you
can even create a function of 0 arguments, but that’s silly.
This list also conflates the role of an interpreter and the semantics of the language. Theoretically, the interpreter can do anything, as long as it happens to coincide with the semantics of the language. This gives way to the possibility to add a compiler for the language, even though the specification gives you a sort of algorithm for interpreting a program. So the semantics of a language are not how your implementation interprets them (unless your language is Python and you wrote CPython, I suppose), and the parser algorithm is similarly irrelevent.
And, of course, many features can be added without any of those. For
example, if we were just introducing numeric computation into the
system, we might have a + function but not a - function. I don’t
know why, but let’s go with it. Introducing the latter does not add
any new syntax, doesn’t add a representation, doesn’t change the
parser, and doesn’t require changing the evaluator.
Built-in functions end up not working like functions somewhere around here, but I can’t find exactly where. What I mean is that they take an environment argument, and they take the environment of the caller, which makes calling `eval` magically work with lexically bound variables.
In any case, the introduction of these Q-expressions makes it too hard to tell what will be evaluated or not. In Chapter 15 we see how it compounds into a hilarious failure.
Look at the first yellow box on the page:
In our Lisp, when we re-assign a name we’re going to delete the old association and create a new one. This gives the illusion that the thing assigned to that name has changed, and is mutable, but in fact we have deleted the old thing and assigned it a new thing.
Must I say more? What would be the result of evaluating:
(let ((a 1)) (+ (let ((a 2)) a) a))
It would be 3, but this contrived attempt at adding “mutation” or something completely breaks scoping. I bet that copying everything as the interpreter does constantly also ends up making mutation make no sense.
Symbols aren’t interned - they are kept as strings forever and
=strcmp=ed all the time. I suppose that works, but it is slow
and I think it looks a bit stupid to be writing
if (!strcmp(a, b)) instead of if (a == b). And then the
builtin_op dispatch also uses strings when an enum would work.
Quick update on the object layout:
struct lval {
int type;
/* Basic */
long num;
char* err;
char* sym;
char* str;
/* Function */
lbuiltin builtin;
lenv* env;
lval* formals;
lval* body;
/* Expression */
int count;
lval** cell;
};On Linux on x86-64, a Lisp value always takes 88 bytes of memory. Congratulations!
The main reason I wanted to write this “review” was about this chapter. That reason was this code block:
; First, Second, or Third Item in List
(fun {fst l} { eval (head l) })
(fun {snd l} { eval (head (tail l)) })
(fun {trd l} { eval (head (tail (tail l))) })Spaces flailing everywhere, and evaluating elements of a list for no good reason. A beautiful four-line summary of the sheer stupidity this book is built upon. With the bold title - hey, anyone can build their own language, and add whatever features they want, no one stopped to ask why or how the hell those features would work. But why it works in this interpreter is just as funny. Back up a few lines, and we see the reason:
The
headfunction is used to get the first element of a list, but what it returns is still wrapped in the list. If we want to actually get the element out of this list we need to extract it somehow.
Single element lists evaluate to just that element, so we can use the
eval function to do this extraction. But a single element list with
a “normal” list (or “S-expression” in the obscene terminology of the
author) is evaluated - so if that element does side effects for some
reason, it could be evaluated multiple times!
lispy> ((\ {x} {list (fst x) (fst x)}) {(print "hi")})
"hi"
"hi"
{() ()}You see this bogosity in any if form, such as the one in the snippet
just after:
; List Length
(fun {len l} {
if (== l nil)
{0}
{+ 1 (len (tail l))}
})Beautiful placement of {} by the way - clearly this guy is well
experienced in Lisp. So, we aren’t calling the 0, but we are still
calling the +, and we can only tell because there are more arguments
to +. Riiiiight.
Despite the previously mentioned flaws, the author still insists that you just need some more features in order to have a “production-strength” programming language. Which, granted, if you are a game developer, or have a startup, or even both, is probably not far off. For the rest of us, well…
The idea of using a “variable hash table” per environment is plain silly. If you can afford some “compile-time” preprocessing, you could rewrite local variables to use fixed indices, then use real arrays for each environment frame; which would avoid performing hashing and probing and all that noise.
And, again, how environments are implemented is not a property of a language, rather a property of an implementation. The distinction is pretty important when you wish to specify how the language works. Consider that, if one wants to evaluate an expression on paper, they might write down an environment, but they don’t draw out a linked list or hash table or whatever else - they just draw the environment as an opaque object, without drawing its internals.
With the pervasive use of defensive copies and mutation of objects in this interpreter, we would be impressed if anyone found out how to make the interpreter use structure sharing without rewriting most of it.
The author also suggests using pool allocation, but a mark-sweep collector as suggested would require more complexity in the memory pool. We think that such a pool would end up with a worse implementation of malloc, which would have to be even more complex if one also wants to introduce variable-sized structure types in the language. At this rate, we most likely have a buggy version of the memory manager provided by the C standard library, which the author has painted in a very bad light. We are told to write another memory manager which “[allocates] a large chunk of memory” and then “slices and dices up this memory for use in the program”, and with the requirements to put a mark bit, handle freeing, and handle variable sized allocations, we are nearly left with a general purpose memory manager again.
The author also has no idea of what lexical scoping is, claiming that it is
a static analysis pass which detects unbound variables. The language in the
book uses dynamic scoping, so finding unbound variables using “the rules for
variable definition” requires global program analysis, if it is even decidable
with fexprs! (Also note that using an environment based on vectors even
for nested environments, requires lexical scoping, so that variable numbering
can be done per function.) Static typing may also be undecidable with fexprs,
or at least incredibly difficult, as we have to type check eval.
Okay, back to the start. Where we’re being told about the lovely things we’ll make in this book. Apparently I am Ada Lovelace…or a fridge? No, wait, Mike Tyson. One of them. But the introduction sheds light on what this writeup is really about. (Emphasis mine.)
The type of Lisp we’ll be building is one I’ve invented for the purposes of this book. I’ve designed it for minimalism, simplicity and clarity, and I’ve become quite fond of it along the way. I hope you come to like it too. Conceptually, syntactically, and in implementation, this Lisp has a number of differences to other major brands of Lisp. So much so that I’m sure I will be getting e-mails from Lisp programmers telling me it isn’t a Lisp because it doesn’t do/have/look-like this or that.
I’ve not made this Lisp different to confuse beginners. I’ve made it different because different is good.
My problem is that I am just complaining about difference, and difference is good! Instead of fanboying over computer brands like Apple and Microsoft, I have been fanboying over language brands like Common Lisp or Scheme or Smalltalk the whole time. That all makes sense.
Suppose I’ll hold off on the e-mail then.
Another project of the author, the Cello C library, has a benchmark list. The garbage collection benchmark is horribly broken. The C “baseline” looks pretty straightforward; one function =malloc=s a few dozen objects, then frees it. But we note three immediate bugs:
- There are 35 variables
i00throughi34which hold allocated pointers. Buti33is never freed. - The author used a
volatile intto fool the C optimizer into not removing the malloc/free pairs, but it is trivial to see that there can only be one assignment to the variable, and so the compiler optimizes it out anyway. - There is a memory leak when
depth = 2.
The end result is that the entire C program could be folded out, and so the benchmark measures startup time. The same thing happens with the JS and Java benchmarks, as they can also identify that no allocated objects are actually used.
Trying to get the C compiler to not fold out malloc/free was tricky, but here
is one possible approach. We declare extern void use(void* p); in the benchmark
file, and then create a separate file with a definition of use like
void use(void* p) { (void)p; }. Then we compile the benchmark and use files
separately, and link (without link-time optimization, not that I know if it would
affect this test). The end result is that when compiling the benchmark, the compiler
is forced to actually allocate. On the other hand, one could well state that we incur
overhead of one extra function call per allocation.
When I run the new test, the program takes somewhere between 14 and 20 milliseconds to
run, rather than total noise between 0 and 1 milliseconds as before. So the polite thing
to do is to increase the work size. I increased the loop bound in main from 100 to
10,000, and found it took 674 milliseconds to run. (Note that the provided Java benchmark
also runs 10,000 iterations rather than 100, and no scaling of the result times is presumably
done, which is quite concerning.)
We could use a JVM option to avoid
inlining the use function with Java. However, the execution time does not seem to be affected
by it. (I’d love to hear if someone figures out a more rigorous way to test this stuff.)
In either case, the execution time lays somewhere between 90 and 125 milliseconds, which
is faster than the fixed C code. With this in mind, it is easy to believe the statement that
“that by manually managing memory Cello achieves performance much closer to C/C++” if we
note that C is pretty damn slow in this case.
I would suggest flicking through the slides for “How NOT to write a benchmark” by Dr Cliff Click on the matter of writing a micro-benchmark. One of the grave sins he mentions is just what we have been observing, that compilers will remove crucial parts of benchmarks if they are never used.