Eval Apply

Before we apply a function we must first evaluate its arguments.

This, or something like it, is one of the inner mysteries of programming languages. EvalApply is written, inside a ying-yang logo, on the front cover of StructureAndInterpretationOfComputerPrograms. When in EarlyHistoryOfSmalltalk AlanKay bet he could define "the most powerful language in the world" in "a page of code", what he delivered was essential Eval and Apply. ChristopherStrachey pointed out that we must also evaluate the function itself, if function-expressions are first-class objects.

Well, if you're going to be minimalistic, you can define a TuringComplete language with an array and "subtract, then jump". Big deal. The goal is to make a usable language.

Yes. Smalltalk is usable, and is close to what Kay had in mind. Lisp likewise.

---

But, with LazyEvaluation, you don't have to evaluate the arguments until they're actually used.

Indeed. Logical "before" rather than temporal.

---

(I wrote this because I came across the 3 references mentioned recently, and I don't know if I fully grok this stuff yet.)

It's pretty easy. In a subexpression, you might have a function call. The function call has arguments that are also expressions. Thus, an expression can contain other expressions. To evaluate the parent expression, you have to evaluate the child expressions first. The apply is just the function call. Hence, EvalApply.

---

Here's roughly how the famous pair looks:

 define eval(expr, environment):
   if is_literal(expr): return literal_value(expr)
   if is_symbol(expr):  return lookup_symbol(expr, environment)
   ;; other similar cases here
   ;; remaining (and commonest) case: function application
   function  = extract_function(expr)
   arguments = extract_arguments(expr)
   apply(eval(function, environment), eval_list(arguments, environment))

 define apply(function, arguments):
   if is_primitive(function): return apply_primitive(function, arguments)
   environment = augment(function_environment(function),
                         formal_args(function), arguments)
   return eval(function_body(function), environment)

 def eval_list(items, environment):
   return map( { x -> eval(x, environment) }, items)

There are plenty of minor variations: you can cram the two functions into a single evalapply function and gain a little efficiency that way; you can put your environment implicitly on a stack; you don't really have to build a new list for your evaluated arguments; and so on.

More interestingly: the above implements lexical scoping. For dynamic scoping (as e.g. in early Lisp systems), pass the environment from eval into apply and extend that instead of the defining environment of the function being applied.

It also implements StrictEvaluation.

Yep. For lazy evaluation (albeit not done very efficiently), you can do something like: slap an extra eval around the call to lookup_symbol, and don't do eval_list on the argument list before handing to apply.

The point here isn't that it's exciting that we can implement any one evaluation or scoping scheme, but that changing from one to another need only involve changing a few lines of code. Of course, if you want an efficient language implementation then you need to work a bit harder.