Evaluating Expressions

The behaviour of our evaluation function is largely the same as before. We need to adapt it to deal with lval* and our more relaxed definition of what constitutes an expression. We can think of our evaluation function as a kind of transformer. It takes in some lval* and transforms it in some way to some new lval*. In some cases it can just return exactly the same thing. In other cases it may modify the input lval* and return it. In many cases it will delete the input, and return something completely different. If we are going to return something new we must always remember to delete the lval* we get as input.

For S-Expressions we first evaluate all the children of the S-Expression. If any of these children are errors we return the first error we encounter using a function we’ll define later called lval_take.

If the S-Expression has no children we just return it directly. This corresponds to the empty expression, denoted by (). We also check for single expressions. These are expressions with only one child such as (5). In this case we return the single expression contained within the parenthesis.

If neither of these are the case we know we have a valid expression with more than one child. In this case we separate the first element of the expression using a function we’ll define later called lval_pop. We then check this is a symbol and not anything else. If it is a symbol we check what symbol it is, and pass it, and the arguments, to a function builtin_op which does our calculations. If the first element is not a symbol we delete it, and the values passed into the evaluation function, returning an error.

To evaluate all other types we just return them directly back.

  1. lval* lval_eval_sexpr(lval* v) {
  3.   /* Evaluate Children */
  4.   for (int i = 0; i < v->count; i++) {
  5.     v->cell[i] = lval_eval(v->cell[i]);
  6.   }
  8.   /* Error Checking */
  9.   for (int i = 0; i < v->count; i++) {
  10.     if (v->cell[i]->type == LVAL_ERR) { return lval_take(v, i); }
  11.   }
  13.   /* Empty Expression */
  14.   if (v->count == 0) { return v; }
  16.   /* Single Expression */
  17.   if (v->count == 1) { return lval_take(v, 0); }
  19.   /* Ensure First Element is Symbol */
  20.   lval* f = lval_pop(v, 0);
  21.   if (f->type != LVAL_SYM) {
  22.     lval_del(f); lval_del(v);
  23.     return lval_err("S-expression Does not start with symbol!");
  24.   }
  26.   /* Call builtin with operator */
  27.   lval* result = builtin_op(v, f->sym);
  28.   lval_del(f);
  29.   return result;
  30. }
  1. lval* lval_eval(lval* v) {
  2.   /* Evaluate Sexpressions */
  3.   if (v->type == LVAL_SEXPR) { return lval_eval_sexpr(v); }
  4.   /* All other lval types remain the same */
  5.   return v;
  6. }

There are two functions we’ve used and not defined in the above code. These are lval_pop and lval_take. These are general purpose functions for manipulating S-Expression lval types which we’ll make use of here and in the future.

The lval_pop function extracts a single element from an S-Expression at index i and shifts the rest of the list backward so that it no longer contains that lval*. It then returns the extracted value. Notice that it doesn’t delete the input list. It is like taking an element from a list and popping it out, leaving what remains. This means both the element popped and the old list need to be deleted at some point with lval_del.

The lval_take function is similar to lval_pop but it deletes the list it has extracted the element from. This is like taking an element from the list and deleting the rest. It is a slight variation on lval_pop but it makes our code easier to read in some places. Unlike lval_pop, only the expression you take from the list needs to be deleted by lval_del.

  1. lval* lval_pop(lval* v, int i) {
  2.   /* Find the item at "i" */
  3.   lval* x = v->cell[i];
  5.   /* Shift memory after the item at "i" over the top */
  6.   memmove(&v->cell[i], &v->cell[i+1],
  7.     sizeof(lval*) * (v->count-i-1));
  9.   /* Decrease the count of items in the list */
  10.   v->count--;
  12.   /* Reallocate the memory used */
  13.   v->cell = realloc(v->cell, sizeof(lval*) * v->count);
  14.   return x;
  15. }
  1. lval* lval_take(lval* v, int i) {
  2.   lval* x = lval_pop(v, i);
  3.   lval_del(v);
  4.   return x;
  5. }

We also need to define the evaluation function builtin_op. This is like the eval_op function used in our previous chapter but modified to take a single lval* representing a list of all the arguments to operate on. It needs to do some more rigorous error checking. If any of the inputs are a non-number lval* we need to return an error.

First it checks that all the arguments input are numbers. It then pops the first argument to start. If there are no more sub-expressions and the operator is subtraction it performs unary negation on this first number. This makes expressions such as (- 5) evaluate correctly.

If there are more arguments it constantly pops the next one from the list and performs arithmetic depending on which operator we’re meant to be using. If a zero is encountered on division it deletes the temporary x, y, and the argument list a, and returns an error.

If there have been no errors the input arguments are deleted and the new expression returned.

  1. lval* builtin_op(lval* a, char* op) {
  3.   /* Ensure all arguments are numbers */
  4.   for (int i = 0; i < a->count; i++) {
  5.     if (a->cell[i]->type != LVAL_NUM) {
  6.       lval_del(a);
  7.       return lval_err("Cannot operate on non-number!");
  8.     }
  9.   }
  11.   /* Pop the first element */
  12.   lval* x = lval_pop(a, 0);
  14.   /* If no arguments and sub then perform unary negation */
  15.   if ((strcmp(op, "-") == 0) && a->count == 0) {
  16.     x->num = -x->num;
  17.   }
  19.   /* While there are still elements remaining */
  20.   while (a->count > 0) {
  22.     /* Pop the next element */
  23.     lval* y = lval_pop(a, 0);
  25.     if (strcmp(op, "+") == 0) { x->num += y->num; }
  26.     if (strcmp(op, "-") == 0) { x->num -= y->num; }
  27.     if (strcmp(op, "*") == 0) { x->num *= y->num; }
  28.     if (strcmp(op, "/") == 0) {
  29.       if (y->num == 0) {
  30.         lval_del(x); lval_del(y);
  31.         x = lval_err("Division By Zero!"); break;
  32.       }
  33.       x->num /= y->num;
  34.     }
  36.     lval_del(y);
  37.   }
  39.   lval_del(a); return x;
  40. }

This completes our evaluation functions. We just need to change main again so it passes the input through this evaluation before printing it.

  1. lval* x = lval_eval(lval_read(r.output));
  2. lval_println(x);
  3. lval_del(x);

Now you should now be able to evaluate expressions correctly in the same way as in the previous chapter. Take a little breather and have a play around with the new evaluation. Make sure everything is working correctly, and the behaviour is as expected. In the next chapter we’re going to make great use of these changes to implement some cool new features.

  1. lispy> + 1 (* 7 5) 3
  2. 39
  3. lispy> (- 100)
  4. -100
  5. lispy>
  6. ()
  7. lispy> /
  8. /
  9. lispy> (/ ())
  10. Error: Cannot operate on non-number!
  11. lispy>