2

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?

Jon Deaton
  • 3,943
  • 6
  • 28
  • 41
  • I believe that if you've implemented those seven primitives correctly, Graham's `eval` should work as-is. – molbdnilo Sep 07 '17 at 10:07
  • That was what I thought as well, but if that is the case I am confused about what the implementation of "eval/execute" should be in C. It seems inevitable that once I have parsed the data structure (even if it is a procedure call to the metacircular `eval`) I need to actually execute it in the interpreter, otherwise it's just a data structure that doesn't do anything (i.e. compute things). Right? – Jon Deaton Sep 07 '17 at 16:10
  • Yes, you need to interpret the primitives and evaluate them, not just parse them. This is not the metacircular evaluator, but it's the straps of your boots. – molbdnilo Sep 07 '17 at 21:17
  • Okay, I see. So in the `eval` implementation in C, I am imagining then basically just implementing the classic eval/apply loop described in SICP? https://mitpress.mit.edu/sicp/full-text/sicp/book/node77.html – Jon Deaton Sep 07 '17 at 21:20

1 Answers1

2

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.

Sylwester
  • 47,942
  • 4
  • 47
  • 79
  • Thank you for the answer that confirmed my suspicions. I like how you say "you need some way to interpret the interpreter", which nicely sums up my conclusions about this issue. I have since implemented the eval/apply in C and it seems to be working. I have been going about this in the way that you describe with a tag+function pointer for primitive operations. – Jon Deaton Sep 08 '17 at 21:30