How to bootstrap a Lisp interpreter using the metacircular evaluator

Question

I am implementing a Lisp interpreter in pure C and am having trouble transitioning from C into Lisp.

Following Peter Norvig's steps in his blog post, I have a REPL which so far parses Lisp expressions into Lisp data structures and serializes the resulting data structure back into a lisp expression that is printed as shown below:

I also have implemented the seven primitives described by Paul Grahm, and understand the metacircular evaluator therein. My troubles arise in writing the part of the C code (not lisp!) that actually executes the data structure once it has been parsed (the "eval") part in the image shown above.

From my understanding, with the metacircular evaluator it is possible to write the semantics of evaluating Lisp procedures in Lisp itself. Because of this I want to leave this part of the program in lisp, however, it seems apparent that at some point I need to write C code that actually applies primitives or procedures to Lisp data structures. When I go to write this code however, I find myself writing the same logic as the metacircular evaluator itslef, just the C version.

My question is whether I need to implement eval and apply in C (as Peter Norvig did in Python) or whether there is some way to bootstrap the lisp interpreter where the only implementation of eval and apply are actually written in Lisp?

Answer 1

It is no way possible to implement eval and apply in lisp if you are making an interpreter in C. The reason is that you need some way to interpret the interpreter and you will have a bootstrap problem.

You can make it minimal by having it data driven. eg All primitive syntax has a tag and a function pointer that takes expression and environment. Basically the symbol quote can evaluate to that and you have eval call the function. All primitive functions have a tag + function pointer and then apply and eval will have far less to do and easier to extend.

You are right that eval and apply will feel like the C equivalent of the very same since that is exactly what it is. Heck even my brainfuck project leaks a metacircular evaluator if you look close enough.