''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 ''expression''s. Thus, an ''expression'' can contain other ''expression''s. To evaluate the parent ''expression'', you have to evaluate the child ''expression''s 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.