Roll A Lisp In C - Evaluation

May 06, 2022

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.

Roll A Lisp In C

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.