Let's talk Eval/Apply

mgcadmin 27-03-2025

Ahh yes, back again with some more of that sweet lisp content. I'm sure by now you've guessed that I've been ankle deep in the parens again, and i've managed to pop my head up long enough to talk about it some more. And today I want to talk about one of the central elements of the whole shebang. Today I want to talk about the magic that is the Eval/Apply cycle. 

Courtesy of SICP

Eval and Apply are the name of two mutually recursive procedures which lie at the heart of every lisp interpreter and drive the meta-circular evaluator. Eval is used to evaluate s expressions according to the type of atom while the aptly named apply is used to perform function application. Based in the lambda calculus of Alonzo church, Scheme allows us to build incredibly powerful and complex programs by combining simple building blocks, especially when compared to other programming languages.

Eval

Lisp famously operates on S-Expressions, a symbolic representation of prefix expressions in list form. Members of an s expression are either an atom or a list - a nested s expression. An atom is a base indivisible unit, in short, an atom can be a number, a function, or a symbol  representing a number or function. Lists are collections of those atoms.

It is the purpose of the Eval function to return the value of individual atoms, or dispatch lists to the eval list procedure. As such, the types which evaluate to themselves (numbers, functions, bindings) are simply returned. A symbol, which represents a bound value in the environment returns the value to which it is bound, or an error if one does not exist.

Object eval(Object expr, List* env) {
       if (expr.type == AS_NUM || expr.type == AS_FUNC || expr.type == AS_BINDING)
            return expr;
       if (m.type == AS_SYMBOL)
           return envLookUp(env, expr);
       if (m.type == AS_LIST)
           return evalList(expr, env);

         return makeEmptyList();
}

Strictly speaking, evalList is part of eval(), its just good software engineering to split them into seperate procedures.

If the list to be evaluated is an empty list, which actually happens alot in scheme where an empty list is used as a sentinel for NIL values, we simply return the empty list. Assuming the list isn't empty, we check if the list that has been passed is a Special Form - an expression with a specific syntax who's arguments are not evaluated according to the "normal" rules. This is done by examining the first element of the list. If it is symbol and represents one of the special forms, we call apply special on the list.

If the list is not a special form then it's an s-expression, which may be a function call, or just a list. Either way, the next step is to call eval on every member of the list, saving the result into a new list. (Note: That is, if we are implementing strict evaluation, other evaluation strategies proceed differently).

Object evalList(Object expr, List* env) {
      List* exprList = expr.list;
      if (exprList->empty())
           return expr;
      Object m = list->first()->info;
      if (isSpecialForm(m))
          return applySpecial(m, list->rest(), env);
      List* evald = new List();
      for (ListNode* it = list->first(); it != nullptr; it = it->next) {
             evald->append(eval(it->info, env));
      }
      if (evald->first()->info.type == AS_FUNC)
          return apply(evald->first()->info.function, evald->rest(), env);
      return makeList(evald);
}

If the first atom of the list eval'd to a function, then we apply that function to the rest of the list using the apply, which I will discuss in the next section. Sometimes though, we just get passed a list of values, and we don't want to just throw those away, so if the list is not a function call, we just return the eval'd list as-is.

Apply

Functions fall in to one of three categories in lisp: Primitive Functions, Lambda Functons, and Special Forms. Just as Eval determined which type of atom it is evaluating and acts appropriatley, so apply does with functions. 

Function Primitives are those functions for which the interpreter supplies a built-in definition, such as '+' which performs addition on a list. Primitive functions are called through a function pointer with our previously evaluated list of arguments.

Lambda Functions are those which are defined using the lambda keyword, and before we can execute them we have a little bit of work to do.

Object apply(Function* func, List* args, List* env) {
    if (func->type == FN_PRIM) {
        return func->func(args);
    }
    if (func->type == FN_LAMBDA) {
        List* nenv = makeNewEnv(func->freeVars, args);
        nenv->addMissing(func->env);
        nenv->addMissing(env);
        return eval(func->code, nenv);
    }
    return makeList(new List());
}

Special Forms are just special cases for function primitives who's syntax doesn't follow the default evaluation order of evaluating every member of a variadic number of arguments. Some examples of special forms are the define, lambda, and cond functions.

Object applySpecial(SpecialForms sf, List* args, List* env) {
    List* evald = new List();
    ListNode* curr = args->first();
    for (int i = 0; i < args->size(); i++) {
        Object res = curr->info;
        if (sf.numFlags > 0 && i < sf.numFlags && sf.flags[i]) {
            res = eval(res, env);
        }
        evald->append(res);
        curr = curr->next;
    }
    return sf.func(evald, env);
}

Special Forms vary in which arguments should be evaluated before being called, and the number of arguments which they accept. It is for this reason that we track the number of arguments being evaluated and their corresponding entry in the flags array to determine which arguments to evaluate. But that is an implementation detail which can be handle any number of ways in different languages.

Anyway, That's what I've got for today, Until next time Happy Hacking!

---