Applicative Order Evaluation Essay

The term you are reducing is $(K_y \Omega)$ where $K_y$ is the constant function $\lambda x. y$ (it always returns $y$, ignoring its argument) and $\Omega = (\lambda x. (x \, x) \: \lambda x. (x \, x))$ is a non-terminating term. In some sense $\Omega$ is the ultimate non-terminating term: it beta-reduces to itself, i.e. $\Omega \to \Omega$. (Make sure to work it out on paper at least once in your life.)

Applicative order reduction must reduce the argument of the function to a normal form, before it can evaluate the top-level redex. Since the argument $\Omega$ has no normal form, applicative order reduction loops infinitely. More generally, for any term $M$, $M \Omega \to M \Omega$, and this is the reduction chosen by the applicative order strategy.

Normal order reduction starts by reducing the top-level redex (because the function $K_y$ is already in normal form). Since $K_y$ ignores its argument, $(K_y \Omega) \to y$ in one step. More generally, $K_y N \to y$ for any term $N$, and this is the reduction chosen by the normal order strategy.

This case illustrates a more general phenomenon: applicative order reduction only ever finds a normal form if the term is strongly normalizing, whereas normal order reduction always finds the normal form if there is one. This happens because applicative order always evaluates fully arguments first, and so misses the opportunity for an argument to turn out to be unused; whereas normal order evaluates arguments as late as possible, and so always wins if the argument turns out to be unused.

(The flip side is that applicative order tends to be faster in practice, because it's relatively rare for an argument to be unused; whereas it's common for an argument to be used multiple times, and under applicative order the argument is only evaluated once. Normal order evaluates the argument as often as it's used, be it 0, 1 or many times.)

Applicative order (without taking into account the order of evaluation ,which in scheme is undefined) would be equivalent to cbv. All arguments of a function call are fully evaluated before entering the functions body. This is the example given in SICP

If you define the function, and call it with these arguments:

When using applicative order evaluation (default in scheme) this will produce and error. It will evaluate before entering the body. While with normal order evaluation, this would return 1. The arguments will be passed without evaluation to the functions body and will never be evaluated because is true, avoiding the error.

In the article you link to, they are talking about Lambda Calculus when they mention Applicative and Normal order evaluation. In this article wiki It is explained more clearly I think. Reduced means applying reduction rules to the expression. (also in the link).

α-conversion: changing bound variables (alpha);

β-reduction: applying functions to their arguments (beta);

Normal order:

The leftmost, outermost redex is always reduced first. That is, whenever possible the arguments are substituted into the body of an abstraction before the arguments are reduced.

Call-by-name

As normal order, but no reductions are performed inside abstractions. For example λx.(λx.x)x is in normal form according to this strategy, although it contains the redex (λx.x)x.

A normal form is an equivalent expression that cannot be reduced any further under the rules imposed by the form

In the same article, they say about call-by-value

Only the outermost redexes are reduced: a redex is reduced only when its right hand side has reduced to a value (variable or lambda abstraction).

And Applicative order:

The leftmost, innermost redex is always reduced first. Intuitively this means a function's arguments are always reduced before the function itself.

You can read the article I linked for more information about lambda-calculus. Also Programming Language Foundations

0 thoughts on “Applicative Order Evaluation Essay”

    -->

Leave a Comment

Your email address will not be published. Required fields are marked *