Lists and Lisps

ALL CAPS • SO RIGHT YET SO WRONG.

Lisps are famous for having little distinction between data and code. They use the same structures to represent both. This allows them to do many powerful things which other languages cannot do. If we want this power for our programming language we’re going to have to separate out the process of reading in input, and evaluating the input we have stored.

The final result of this chapter will only differ slightly in behaviour from the previous chapter. This is because we are going to spend time changing how things work internally. This is called re-factoring and it will make our life a lot easier later on. Like preparation for a meal, just because we’re not putting food onto plates it doesn’t mean we’re wasting time. Sometimes the anticipation is even better than eating!

To store the program we will need to create an internal list structure that is built up recursively of numbers, symbols, and other lists. In Lisp, this structure is commonly called an S-Expression standing for Symbolic Expression. We will extend our lval structure to be able to represent it. The evaluation behaviour of S-Expressions is the behaviour typical of Lisps, that we are used to so far. To evaluate an S-Expression we look at the first item in the list, and take this to be the operator. We then look at all the other items in the list, and take these as operands to get the result.

By introducing S-Expressions we’ll finally be entering the world of Lisp.