November 2018, rev. July 2019, rev. September 2019

Eval runs faster if it makes more than one pass. If eval interprets directly, it's faster for a human to calculate the results but it's not faster for a machine. To make eval run faster by a machine, don't make eval interpret directly.

There are two reasons why. The first is that recursive evaluation isn't as fast as iterative evaluation. If eval is implemented recursively, where eval calls eval to interpret the rest of an expression, then the number of recursive calls to eval adds up. This is slower because a lot of state is initialized to make a function call. In both a physical and a virtual machine, a stack frame gets allocated, parameters are passed on the stack, and intermediate registers get re-initialized.

The more interesting reason why eval runs faster when it doesn't interpret directly is that it's faster to generate a plan ahead of time. There are advantages to not waiting until runtime to evaluate some results and instead prepare them at read time. The glaring example is evaluating a function. It's faster to generate IR or machine code ahead of time when the function is defined, so that when the function is called it can start executing directly rather than wait to get interpreted. A read-only list can be allocated ahead of time instead of generated at runtime, and allocated in the data section of a function without needing calls to malloc instead of allocated on the heap.

Defining eval in Lisp in as few lines of code as possible is great in theory because it turns computation into math. Practice is different. In practice, math doesn't separate between planning and execution, doesn't specify the order in which commands are run, and doesn't specify how to use memory.