Roll A Lisp In C - Procedures

Procedures provide a way of abstracting imperative knowledge that can be represented in a language. In this article I show a technique for implementing lexically scoped first-class closures. This is the concluding article in the Roll A Lisp In C series.

Roll A Lisp In C

In the previous article we showed a simple way of creating environments structures using pairs. But, there’s still something our language is missing and, that’s a way of creating abstraction. So, presented in this article is a technique for implementing first-class closures.

Environments

With first-class closures the simple environment data structure we’ve been using isn’t enough and needs to be augmented. Instead of just a symbol and value pair we have a more elaborate structure containing 32 pairs, a pointer into those pairs and, a pointer to another closure environment.

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

typedef struct Env {
  Entry entry[32];
  Entry* entryptr;
  struct Env* next;
} Env;

Env frame[128];
Env* frameptr = frame;

Env* extend(Env* env) {
  frameptr->next = env;
  frameptr->entryptr = frameptr->entry;
  return frameptr++;
}

This has a lot of parity with the previous environment data structure that was used before except now it’s given a name and has a reference to another environment. Because Env holds a reference to another environment it becomes straight forward to implement an extend function which creates an enclosing environment.

get needs to be modified to work with Env but, it’s a very simple modification. get needs to look in the Env for a value or the Env’s enclosing environment.

void* get(void* sym, Env* env) {
  Entry* seek = env->entryptr;
  for (;seek != env->entry-1; --seek)
    if (strcmp(seek->sym, sym) == 0)
        return seek->val;
  // Look in the next Environment
  return get(sym, env->next);
}

put remains mostly the same it just acts on an Env instead of a global symbol-value store.

Up to this point we’ve used syntactic forms for implementing procedures but, now procedures can be values that exist in the environment.

Env global = {
  {{ .sym = "+", .val=(void*)1 },
   { .sym = "-", .val=(void*)2 },
   { .sym = "*", .val=(void*)3 },
   { .sym = "/", .val=(void*)4 },
   { .sym = "car", .val=(void*)5 },
   { .sym = "cdr", .val=(void*)6 },
   { .sym = "=", .val=(void*)7 },
   { .sym = "cons", .val=(void*)8 },
   { .sym = "list", .val=(void*)9 },},
  .entryptr = global.entry+9,
  NULL
};

Now, we have a global environment that eval can get values from. In this case the built-in procedures that we’ve implemented before are assigned reserved values that apply knows about.

Evaluator

With procedures as first-class values there’s no need to have syntactic forms in eval to evaluate a procedure. Instead eval has a general case of procedure application that calls apply with the procedure value and arguments.

void* eval_exp(void* exp, Env* env) {
  if (istext(exp) || islist(exp)) {
    Text* text = exp;
    ...
    else {
      void* fun = eval_exp(text->car, env);
      return apply(fun, text->cdr, env);
    }
  }
  // evaluate the symbol in the environment if it's not self-evaluating.
  return isdigit(*((char*)exp)) || strcmp(exp, "#f") == 0 || strcmp(exp, "#t") == 0 ? exp : get(exp, env);
}

The syntactic forms in eval are now replaced with a call to apply.

apply

The results of the built-in procedures are now in apply.

void* apply(void* func, Text* args, Env* env) {
  char evret[32];
  if (func == (void*)1) {
    int left = atoi(eval_exp(args->car, env));
    int right = atoi(eval_exp(args->cdr->car, env));
    sprintf(evret, "%d", left+right);
    return cpysym(evret);
  }
  else if (func == (void*)2) {
    int left = atoi(eval_exp(args->car, env));
    int right = atoi(eval_exp(args->cdr->car, env));
    sprintf(evret, "%d", left-right);
    return cpysym(evret);
  }
  else if (func == (void*)3) {
    int left = atoi(eval_exp(args->car, env));
    int right = atoi(eval_exp(args->cdr->car, env));
    sprintf(evret, "%d", left*right);
    return cpysym(evret);
  }
  else if (func == (void*)4) {
    int left = atoi(eval_exp(args->car, env));
    int right = atoi(eval_exp(args->cdr->car, env));
    sprintf(evret, "%d", left/right);
    return cpysym(evret);
  }
  else if (func == (void*)5) {
    Pair* pair = eval_exp(args->car, env);
    return pair->car;
  }
  else if (func == (void*)6) {
    Pair* pair = eval_exp(args->car, env);
    return pair->cdr;
  }
  else if (func == (void*)7) {
    char* left = eval_exp(args->car, env);
    char* right = eval_exp(args->cdr->car, env);
    if(left && right)
      return strcmp(left, right) == 0 ? "#t" : "#f";
    return left == right ? "#t" : "#f";
  }
  else if (func == (void*)8) {
    void* left = eval_exp(args->car, env);
    void* right = eval_exp(args->cdr->car, env);
    return cons(left, right);
  }
  else if (func == (void*)9) {
    return evalargs(args, env);
  }
}

The evaluator can evaluate first-class procedures but, these are only built-in procedures. The language still doesn’t have any means of creating abstraction.

lambda

lambda creates a procedure. lambda is like something of the following,

;; (lambda (<arglist>) <body>) => <#lambda>
;;
;; where <arg> <=> exp | NONE
;; where <body> <=> exp | <body>
;; where <arglist> <=> <arg> | <arglist>
;; so that,

(lambda () (+ 1 2)) => <#lambda>
((lambda () (+ 1 2))) => 3
((lambda (a b) (+ a b)) 2 2) => 4

lambda is an object that abstracts imperative knowledge within a language. It can be constructed from it’s parameters, body and, enclosing environment.

void* lambda(Text* args, Text* body, void* env) {
  return cons(env, cons(args, body));
}

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

The lisp syntax makes it easy to pick this information out and create a lambda object. lambda contains an environment as the first element in it’s object and, requires a modification to put to be copied into the environment.

int isenv(void* x) {
  return x >= (void*)&frame &&
         x <  (void*)&frame[128] ||
         x == (void*)&global;
}

void* cpylambda(Pair* val) {
  Pair* lambda = val->cdr;
  lambda->car = lambda->car ? cpy(lambda->car) : NULL;
  lambda->cdr = cpy(lambda->cdr);
  return val;
}

void put(void* sym, void* val, Env* env) {
  strcpy(env->entryptr->sym, sym);
  if (istext(val) || islist(val)) {
    Pair* pair = val;
    if (isenv(pair->car))
      env->entryptr->val = cpylambda(val);
    else
      env->entryptr->val = cpy(val);
  }
  else
    env->entryptr->val = cpysym(val);
  env->entryptr++;
}

Finally, apply needs to know how to bind values to the parameters of a lambda closure and, evaluate it’s body in that closure.

void* evalbody(Text* body, Env* env) {
  void* val = eval_exp(body->car, env);
  if (body->cdr)
    return evalbody(body->cdr, env);
  else
    return val;
}

void parameterize(Text* args, Text* para, Env* env) {
  put(para->car, args->car, env);
  if (args->cdr != NULL)
    parameterize(args->cdr, para->cdr, env);
}

void* apply(void* func, Text* args, Env* env) {
  if (islist(func)) {
    Pair* pair = func;
    Env* closure = pair->car;
    Pair* lambda = pair->cdr;
    Text* para = lambda->car;
    Text* body = lambda->cdr;
    Env* lambdaenv = extend(closure);
    if (para) {
      Text* evargs = evalargs(args, env);
      parameterize(evargs, para, lambdaenv);
    }
    return evalbody(body, lambdaenv);
  }
  else {
    // apply a built-in procedure.
    ...
  }
}

Notice that parameterize copies it’s value when setting up the closure. This is called pass-by-value. This isn’t the only way to evaluate procedures but, it works well for this language.

Conclusion

These are the essentials of interpretation in C. There are still many more improvements that can be made to this evaluator. For example, there’s no garbage collection for the language and, the evaluator itself needs garbage collection or tail-call optimization to evaluate many procedure applications. In this article we went over procedures as a means of abstracting imperative knowledge but, macros are also a means of abstracting imperative knowledge. But, that’s beyond the scope of these articles.

The gist contains a full source code listing as well as some additional changes to the printer for lambda. The Github repository contains a slightly different lisp based on the one presented in the articles.

Further Reading

Github Gist

Git Repository

Reader Comments