The Lisp Interpreter
I recently got a code challenge to where I had to write my own lisp interpreter. After looking at how it works for a bit, I decided to write a guide to understanding and solving the problem. This is not a common interview question, but if you happen to come across one.
Understanding what Lisp Interpreter is —
The heart of the Lisp interpreter is the “read-eval-print” loop. That is, the interpreter does the following three jobs over and over:
- read an input expression
- evaluate the expression
- print the results
This loop can be written in Lisp itself very simply:
(loop (print (eval (read)))Of course, this doesn’t take into account error handling, multiple values, and so on, but much of what Lisp does, including some things that seem unintuitive, can be understood by reasoning about the above three step process.
The Lisp Reader
The input to the Lisp reader is a sequence of characters. The output is a Lisp expression. The job of the reader is to convert objects in character world to objects in expression world.
The Lisp Evaluator
The Lisp evaluator takes an expression and returns an expression. The expression returned is called the value of the expression evaluated. [I’ll ignore expressions that return multiple values here.]
The rules for evaluation are surprisingly simple. Graphically, it looks like this:
The Lisp Printer
The input to the Lisp printer is a Lisp expression. The output is a sequence of characters. The job of the printer is to convert objects in expression world to objects in character world.
Sources :