Expression Structure

We need a way to store S-Expressions as lval. This means we’ll also need to store Symbols and Numbers. We’re going to add two new lval types to the enum. The first is LVAL_SYM, which we’re going to use to represent operators such as +. The second new type is LVAL_SEXPR which we’re going to use to represent S-Expressions.

enum { LVAL_ERR, LVAL_NUM, LVAL_SYM, LVAL_SEXPR };

S-Expressions are variable length lists of other values. As we learnt at the beginning of this chapter we can’t create variable length structs, so we are going to need to use a pointer. We are going to create a pointer field cell which points to a location where we store a list of lval*. More specifically pointers to the other individual lval. Our field should therefore be a double pointer type lval**. A pointer to lval pointers. We will also need to keep track of how many lval* are in this list, so we add an extra field count to record this.

To represent symbols we’re going to use a string. We’re also going to change the representation of errors to a string. This means we can store a unique error message rather than just an error code. This will make our error reporting better and more flexible, and we can get rid of the original error enum. Our updated lval struct looks like this.

typedef struct lval {
  int type;
  long num;
  /* Error and Symbol types have some string data */
  char* err;
  char* sym;
  /* Count and Pointer to a list of "lval*" */
  int count;
  struct lval** cell;
} lval;

Are there ever pointers to pointers to pointers?

There is an old programming joke which says you can rate C programmers by how many stars are on their pointers.

Beginner’s programs might only use char* or the odd int*, so they were called one star programmers. Most intermediate programs contain double pointer types such as lval**. These programmers are therefore called two star programmers. To spot a triple pointer is something special. You would be viewing the work of someone grand and terrible, writing code not meant to be read with mortal eyes. As such being called a three star programmer is rarely a compliment.

As far as I know, a quadruple pointer has never been seen in the wild.

What is that struct keyword doing there?

Our new definition of lval needs to contain a reference to itself. This means we have to slightly change how it is defined. Before we open the curly brackets we can put the name of the struct, and then refer to this inside the definition using struct lval. Even though a struct can refer to its own type, it must only contain pointers to its own type, not its own type directly. Otherwise the size of the struct would refer to itself, and grow infinite in size when you tried to calculate it!