Roll A Lisp In C - Evaluation

Evaluation is the process of taking an expression and producing a value. In this article I show how to take expresions held in list structured data and produce values.


In the previous article we went over how to represent Lisp data in C. With this representation we can begin to implement a simple evaluator.

Evaluator

The evaluator presented in this article will achieve 2 things. It will evaluate simple arithmetic expressions and, it will be able to branch to a consequent or alternative expression given a predicate.

Arithmetic

The arithmetic expressions we’d like to evaluate will be the following:

;; (<operator> <exp> <exp>) => <num>
;;
;; where <operator> <=> <+ | - | * | />
;; where <num> <=> Integer
;; where <symbol> <=> Text
;; where <exp> <=> <(<operator> <exp> <exp>) | <num> | <symbol>>
;; so that,

(+ 1 2) => 3
(+ (+ 3 2) 5) => 10

First, we’ll create a new type that will allow working with list structured data easier.

typedef struct Text {
  char* car;
  struct Text* cdr;
} Text;

This allows different parts of a read expression to be accessed simply and, the evaluation of addition can be implemented as follows:

char ret[32];

void* eval(void* exp) {
  return eval_exp(exp);
}

void* eval_exp(void* exp) {
  if (istext(exp)) {
    Text* text = exp;
    if (strcmp("+", text->car) == 0) {
      void* left = eval_exp(text->cdr->car);
      void* right = eval_exp(text->cdr->cdr->car);
      sprintf(ret, "%d", atoi(left) + atoi(right));
      return ret;
    }
  return exp;
}

Likewise other arithmetic operators can be implemented in the same way.

void* eval_exp(void* exp) {
  if (istext(exp)) {
    Text* text = exp;
    ...
    else if (strcmp("-", text->car) == 0) {
      void* left = eval_exp(text->cdr->car);
      void* right = eval_exp(text->cdr->cdr->car);
      sprintf(ret, "%d", atoi(left) - atoi(right));
      return ret;
    }
    else if (strcmp("*", text->car) == 0) {
      void* left = eval_exp(text->cdr->car);
      void* right = eval_exp(text->cdr->cdr->car);
      sprintf(ret, "%d", atoi(left) * atoi(right));
      return ret;
    }
    else if (strcmp("/", text->car) == 0) {
      void* left = eval_exp(text->cdr->car);
      void* right = eval_exp(text->cdr->cdr->car);
      sprintf(ret, "%d", atoi(left) / atoi(right));
      return ret;
    }
  }
  return exp;
}

Predicates

The predicate we’d like to implement will be the following:

;; (= <exp> <exp>) => <predicate>
;;
;; where <predicate> <=> <#t | #f>
;; so that,

(= 1 2) => #f
(= 1 1) => #t
(= (+ 1 1) 2) => #t

The implementation is simple. Evaluate the left and right expressions and, see if they’re the same symbol.

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

Branching

The branching we’d like to implement will be the following:

;; (if <predicate> <exp> <exp>)
;;
;; so that,

(if #t (+ 1 2) (+ 2 3)) => 3
(if #f (+ 1 2) (+ 2 3)) => 5

The implementation can be done by evaluating the conditional and evaluating either the consequent expression or the alternative expression.

void* eval_exp(void* exp) {
  if (istext(exp)) {
    Text* text = exp;
    if (strcmp("if", text->car) == 0) {
      void* conditional = eval_exp(text->car);
      if (strcmp("#t", text->cdr->car) == 0)
        return eval_exp(text->cdr->cdr->car);
      else
        return eval_exp(text->cdr->cdr->cdr->car);
    }
    ...
  }
  return exp;
}

Conclusion

In this article we’ve seen how to evaluate simple arithmetic expressions. We’ve also seen how to evaluate equality in a naive way and, how to branch on a given value. We can now produce values that can be stored in an environment.

Further Reading

Github Gist

Reader Comments