Advanced Topic: Writing an Interpreter (for Lisp)

Notes:

Advanced topics are not in CS Academy, but are required and can appear on any future quiz or exam.
However, even if these topics appear on a future assessment, we would not expect you to have an understanding beyond what is covered in these notes.
In particular, you are not responsible for the actual code we wrote, even though we provide it here for the curious.

Here are the Lisp interpreters we wrote in lecture:

lisp1.py (Lecture 1)
lisp2.py (Lecture 2)

Lecture Notes:

Lisp is a real language invented by John McCarthy at MIT in 1958. It is the second-oldest programming langauge (Fortran is older) that is still in use today.

We wrote a small subset of Lisp. We also modified the language a bit (such as by adding a block statement instead of progn).

Lisp code (like Python code and all code) is just a multiline string of text.

Lisp uses prefix or RPN notation. Lisp expressions are of the form (command arg0 ... argN). For example, (+ 1 2 3) adds the numbers 1, 2, and 3 to get 6.

Lisp expressions can be nested, so they can contain more Lisp expressions. For example:
```
    (+  (+ 1 2)
        (* 3 4)
        (+ 5
           (* 6 7)))
```
This evaluate to (+ 3 12 47), which is 62.

An interpreter is a program that takes code as input and directly runs the code. This is in contrast to a compiler which translates code into another language (such as assembly language).

Our interpreter followed these steps:
1. Tokenize
2. Parse
3. Evaluate

Tokenizing starts with code (a multiline string) and returns a 1d list of tokens, where a token can be a keyword (like 'while'), a variable (like 'x'), an integer (like 123), legal punctuation (like a parenthesis), or other legal syntactic elements of a language.

Tokenizing also is where we remove whitespace and comments.

We added a special character EOF (for End-Of-File) to the end of the input to assist with tokenizing. We used chr(0) for this, since chr(0) cannot appear in our code.

In the example from above, the tokens are:

['(', '+', '(', '+', 1, 2, ')', '(', '*', 3, 4, ')', '(', '+', 5, '(', '*', 6, 7, ')', ')', ')', EOF]

Parsing starts with the 1d list of tokens, and returns a parse tree. This is a hierarchical data structure that captures the structure of the program, so we can tell which parts are structurally within other parts of the program.

To keep things simple and to mostly rely on concepts we have learned so far, we used multi-dimensional lists to represent a parse tree. Each expression is a list, and sub-expressions are lists within lists.

We used recursion to create the parse tree because expressions can be arbitrarily nested (an expression can contain another expression which contains yet another, and so on).

In the example above, the parse tree is:

    ['+',
        ['+', 1, 2],
        ['*', 3, 4],
        ['+', 5,
              ['*', 6, 7]
        ]
    ]

After parsing, the final step is evaluating. This is where we finally run the code. This takes a parse tree and performs the computations that produce the output of the program.

Just as we used recursion to create the parse tree, we use recursion to evaluate it. This is for the same reason: expressions can contain arbitrarily deeply nested expressions.

We used a dictionary to map variable names to their values. At the top level, we created a dictionary to hold the globals. Just before we call a user-defined function, we first create a new dictionary to hold its local variables.

We used another dictionary to map functions to their definitions. Specifically, we mapped function names to a tuple of their parameter list and their body. The parameter list is just a list of variable names, like ['x', 'y'], and the body is a parse tree of the code we need to run when the function is called.

We raised exceptions in our code when we detected common errors, such as illegal tokens, undefined variables, and unknown commands. This was extremely helpful for real-time debugging as we wrote the interpreter.

We took some major shortcuts while writing the code for simplicity, so that we could get the whole thing written in just over an hour using mostly just what we have learned so far in 112. For example, in our tokenizer, we stored the code in a list and popped off the front of the list. This is very inefficient and should not be done in practice. We had several ways to avoid this, such as reversing the list and popping off the right side, or by using a deque (which is like a list but efficiently pops off the front), or by using indexes and never mutating the list.

We ultimately tested our intepreter by running recursive fib (Fibonnaci) in Lisp, which succeeded! Here's the Lisp code:

code = '''
    (block
        (function fib (n)
            (if (< n 2)
                1
                (+ (fib (- n 1))
                   (fib (- n 2))
                )
            )
        )
        (set x 0)
        (while (< x 10)
            (block
                (output x (fib x))
                (set  x (+ x 1))
            )
        )
    )
'''