Roll A Lisp In C

• Reading
• Evaluation
• Environments
• Procedures

In the previous article we went over a simple evaluator that can produce values. With a language that can produce values from evaluation comes the question of storing values.

Environments

The environment presented in this article will be simple mapping from symbols to values.

typedef struct {
  char sym[32];
  void* val;
} Entry;

Entry entry[32];
Entry* entryptr = entry;

Here we have 32 entries. An entry is a symbol and a value pair. The environment structure has 2 operations put and get for storing and retrieving values.

char symbol[2048];
char* symbolptr = symbol;

void* cpysym(void* sym) {
  if (sym) {
    sym = strcpy(symbolptr, sym);
    symbolptr = symbolptr + strlen(sym) + 1;
  }
  return sym;
}

void put(void* sym, void* val) {
  strcpy(entryptr->sym, sym);
  entryptr->val = cpysym(val);
  entryptr++;
}

void* get(void* sym) {
  Entry* seek = entryptr;
  for (;seek != entry-1; --seek)
    if (strcmp(seek->sym, sym) == 0)
        return seek->val;
}

For now, the only values the environment will store are symbols. With this we can implement a new language feature to our lisp, define.

define

define creates a variable with a value. define is like something of the following,

;; (define <var> <val>) => <var>
;;
;; where <var> <=> <symbol>
;; where <val> <=> exp | Integer | Boolean
;; so that,

(define a 10) => a
(define b a) => b
a => 10
b => 10

Implementing this in the evaluator can be done like this,

void* eval_exp(void* exp) {
  if (istext(exp)) {
    Text* text = exp;
    if (strcmp("define", text->car) == 0) {
      void* var = text->cdr->car;
      void* val = eval_exp(text->cdr->cdr->car);
      put(var, val);
      return var;
    }
    ...
  }
  return isdigit(*((char*)exp)) || strcmp(exp, "#t") == 0 || strcmp(exp, "#f") == 0 ? exp : get(exp);
}

We now have a syntactic form define that can create variables that hold values. Notice that to retrieve a value from a variable we evaluate the variable. Our language no longer has the ability to evaluate program text to itself. A feature often referred to as autoquote.

And yet, we still do autoquote somethings like numbers and booleans. But, you could imagine a lisp where knowledge of these things are in the environment. A language where get already knows about numbers and booleans. You could also imagine a language where we still have autoquoting of text and, get is a syntactic form in our language like define is to put.

These things are easy to implement in this evaluator and, I encourage trying to implement them.

List Structured Memory

A common feature of most lisps is to be able to work with list structured data. In fact, we’ve already seen list structured memory used for the reader. But, now we’ll implement list structured memory for the environment.

Pair list[1280];
Pair* listptr = list;

int islist(void* x) {
  return x >= (void*)&list &&
         x <  (void*)&list[1280];
}

Pair* cons(void* x, void* y) {
  assert(islist(listptr));
  listptr->car = x;
  listptr->cdr = y;
  return listptr++;
}

This should be familiar. It’s exactly like the list structured data for the reader. But, now we can augment put to accept symbols or lists.

void* cpy(Text* text) {
  if (istext(text) || islist(text)) {
    if(istext(text->car) || islist(text->car))
      return cons(cpy((Text*)text->car), text->cdr ? cpy(text->cdr) : NULL);
    else
      return cons(cpysym(text->car), text->cdr ? cpy(text->cdr) : NULL);
  }
  return cpysym(text);
}

void put(void* sym, void* val) {
  strcpy(entryptr->sym, sym);
  if (islist(val) || istext(val))
    entryptr->val = cpy(val);
  else
    entryptr->val = cpysym(val);
  entryptr++;
}

It’s important to consider the difference between creating a variable by reference and creating a variable by value. Here we’re creating a variable by it’s value. But, we could also create a variable by not copying the value and just setting the value to be a reference. But, what happens if that reference goes away?

In this evaluator, references are held in the reader and in ret. This evaluator can be augmented to create variables by reference. It’s a slight optimization over copying and, I encourage trying to implement it.

cons, car &, cdr

cons creates a pair and, car & cdr retrieve the first and second of a pair. These are something like the following,

;; (cons <val> <val>) => <pair>
;;
;; so that,

(cons 12 10) => (12 . 10)
(cons #t 3) => (#t . 3)

;; (car <pair>) => <val>
;;
;; so that,

(car (cons 12 10)) => 12
(car (cons #t 3)) => #t

;; (cdr <pair>) => <val>
;;
;; so that,

(cdr (cons 12 10)) => 10
(cdr (cons #t 3)) => 3

Implementing this in the evaluator can be done like this,

void* eval_exp(void* exp) {
  char ret[32];
  if (istext(exp)) {
    Text* text = exp;
    if (strcmp("cons", text->car) == 0) {
      void* left = eval_exp(text->cdr->car);
      void* right = eval_exp(text->cdr->cdr->car);
      return cons(left, right);
    }
    else if (strcmp("car", text->car) == 0) {
      Pair* pair = eval_exp(text->cdr->car);
      return pair->car;
    }
    else if (strcmp("cdr", text->car) == 0) {
      Pair* pair = eval_exp(text->cdr->car);
      return pair->cdr;
    }
    ...
  }
  return isdigit(*((char*)exp)) || strcmp(exp, "#t") == 0 || strcmp(exp, "#f") == 0 ? exp : get(exp);
}

But, if you tried running the evaluator now and used cons in the repl it would probably segfault. The reason being that the printer doesn’t know how to display pairs.

This isn’t the only way of working with list structured data. Lisp’s syntax is itself made from lists and, this homoiconic quality can be used to make lists as well.

quote

quote evaluates to the text of it’s application. In other words it returns a list or a symbol of the text passed to it. quote is like the following,

;; (quote <exp>) => <exp>
;;
;; so that,

(quote (cons 12 10)) => (cons 12 10)
(quote (cons #t 3)) => (cons #t 3)

Implementing this in the evaluator can be done like this,

void* eval_exp(void* exp) {
  if (istext(exp)) {
    Text* text = exp;
    if (strcmp("quote", text->car) == 0) {
      return text->cdr->car;
    }
    ...
  }
  return isdigit(*((char*)exp)) || strcmp(exp, "#t") == 0 || strcmp(exp, "#f") == 0 ? exp : get(exp);
}

There’s another way of making lists and, that’s a list syntactic form.

list

list creates a list from it’s arguments. list is like something of the following,

;; (list <vals>) => <vals>
;;
;; where <vals> <=> <vals> | <val>
;; so that,

(list 1 2 3) => (1 2 3)

Implementing this in the evaluator can be done like this,

void* evalargs(Text* args) {
  return cons(eval_exp(args->car), args->cdr ? evalargs(args->cdr) : NULL);
}

void* eval_exp(void* exp) {
  char ret[32];
  if (istext(exp)) {
    Text* text = exp;
    if (strcmp("list", text->car) == 0) {
      return evalargs(text->cdr)
    }
    ...
  }
  return isdigit(*((char*)exp)) || strcmp(exp, "#t") == 0 || strcmp(exp, "#f") == 0 ? exp : get(exp);
}

Notice that list evaluates it’s arguments to create a list. It looks just like a procedure. It’s useful to consider a variant of list which doesn’t evaluate it’s arguments. A list which is like a variadic quote. That’s not hard to implement in this evaluator. Could you write a list procedure like that in terms of cons, car and, cdr?

Conclusion

In this evaluator we’ve added quite a few new features. We’ve shown a simple environment data structure that maps symbols to values. We’ve shown a way of working with and creating list structured data. We’ve seen that this evaluator is flexible and, is useful for studying other language concepts with. But, we’ve only been using syntactic forms to implement features. In the next and final article it’s shown a technique for implementing first-class lexically scoped procedures.

In the gist is a full source code listing which also contains code for a reader and printer that can use the features we’ve added to this language. The gist also contains an implementation of = that works with lists and the empty list.

Further Reading

Github Gist