Normal, Applicative and Lazy Evaluation

A lambda expression is said to be in normal form if it cannot be reduced any further, meaning that the expression no longer contains any function applications. More formally, a reducible expression is called a redex, and a lambda expression is in normal form when it contains no more redexes.

Redex
A reducible function expression.
Normal Form
A lambda expression that contains no redexes.

Given a lambda expression, there are two primary strategies for reducing it to normal form: normal-order evaluation, or applicative-order evaluation. This article discusses both methods, their pros and cons, and an alternative evaluation strategy that combines the pros from both — lazy evaluation.

Normal-Order Evaluation

Normal-order evaluation of a lambda expression is the repeated application of the leftmost reducible function application. In other words, normal order evaluation is the strategy that always reduces the left-most outer-most redex first. You can think about normal-order evaluation as traversing the lambda expression and evaluating every function you find before evaluating any function arguments.

The most noticeable effect of using normal-order evaluation is that, since we evaluate the leftmost function first, arguments to that function are not evaluated. If those arguments are themselves functions, we may pass unevaluated functions as function arguments. Speaking in terms of lambda calculus, an expression with an unevaluated function application as argument will replace all bound variables with the unevaluated function application.

Applicative-Order Evaluation

Applicative-order evaluation means that a function’s arguments are evaluated before the function is applied. In other words, with applicative-order evaluation, internal reductions are applied first, and only after all internal reductions are complete, the left-most redex is reduced. More formally, we evaluate the left-most redex free of any internal redexes.

The most noticeable effect of applicative-order evaluation is that recursive functions may not terminate. For example, if an argument to a function must be evaluated before calling the function, and if that argument is recursive, the function will never terminate.

To illustrate the differences between normal and applicative order reduction, let’s walk through a few examples.

Comparison

Consider a function double that doubles two numbers, and a function average that takes the average of two numbers.

def double x = (plus x x)
def average x y = (divide (plus x y) 2)

Now let’s use these functions to create a lambda expression that we can evaluate in normal order:

Normal-Order Evaluation

(double (average 2 4)) =>
(plus (average 2 4) (average 2 4)) =>
(plus (divide (plus 2 4) 2) (average 2 4)) =>
(plus (divide 6 2) (average 2 4)) =>
(plus 3 (average 2 4)) =>
(plus 3 (divide (plus 2 4) 2)) =>
(plus 3 (divide 6 2)) =>
(plus 3 3) =>
6

Applicative-Order Evaluation

We can evaluate that same function in applicative order:

double (average 2 4) =>
double (divide (plus 2 4) 2) =>
double (divide 6 2) =>
double 3 =>
plus 3 3 =>
6

Notice how, under normal-order evaluation, the left-most function application is always evaluated first, and with applicative-order evaluation, the inner-most functions are evaluated first. Also notice how normal-order evaluation applies the (average 2 4) function more than once.

Now consider an if function with an argument that is an illegal operation. Semantically, the if function takes three arguments, and if the first argument evaluates to True return the second argument, otherwise, return the third argument. For example:

if True x y = x
if False x y = y

Normal-Order Evaluation

With normal-order evaluation, we derive the value 10.

if (less 3 4) (plus 5 5) (divide 1 0) =>
if True (plus 5 5) (divide 1 0) =>
(plus 5 5) =>
10

Applicative-Order Evaluation

With applicative-order evaluation, we end up with an error because we evaluate the illegal argument before applying the function.

if (less 3 4) (plus 5 5) (divide 1 0) =>
if True (plus 5 5) (divide 1 0) =>
if True 10 (divide 1 0) =>
Error — Divide by Zero

In this case, the applicate-order evaluation results in a run-time error, while the normal-order evaluation completes.

Lazy Evaluation

While normal-order evaluation may result in doing extra work by requiring function arguments to be evaluated more than once, applicative-order evaluation may result in programs that do not terminate where their normal-order equivalents do. In practise, most functional programming languages solve this problem using lazy evaluation.

With lazy evalution, we delay function evaluation in a way that avoids multiple evaluations of the same function — thus combining the benefits of normal-order and applicative-order evaluation. With lazy evaluation, we evaluate a value when it is needed, and after evaluation all copies of that expression are updated with the new value. In effect, a parameter passed into a function is stored in a single location in memory so that the parameter need only be evaluated once. That is, we remember all of the locations where we a certain argument will be used, and when we evaluate a function, we replace the argument with the value. As a result, with lazy evaluation, every parameter is evaluated at most once.

Summary

This article briefly covered the differences between normal-order and applicative-order evaluation, with special care given to the degenerative cases for both. In particular, normal-order evaluation may result in duplicate function applications, whereas applicative-order evaluation may increase the chance of non-termination (due to infinite recursion), or errors (due to evaluating all potential paths). In practise, no programming language uses normal-order evaluation because of the performance penalty, and it is also difficult to use strict applicative-order evaluation because of the increase in non-terminating cases. Rather, programming languages tend to use lazy-evaluation as a means of enabling the performance benefit of applicative-order evaluation without the risk.

comments powered by Disqus