4.2.1 Normal Order and Applicative Order

In section 1.1, where we began our discussion of models of evaluation, we noted that JavaScript is an applicative-order language, namely, that all the arguments to JavaScript functions are evaluated when the function is applied. In contrast, normal-order languages delay evaluation of function arguments until the actual argument values are needed. Delaying evaluation of function arguments until the last possible moment (e.g., until they are required by a primitive operation) is called lazy evaluation.[1] Consider the function

function try_me(a, b) {
    return a === 0 ? 1 : b;	
}

Evaluating try_me(0, head(null)); signals an error in JavaScript. With lazy evaluation, there would be no error. Evaluating the statement would return 1, because the argument head(null) would never be evaluated.

An example that exploits lazy evaluation is the declaration of a function unless

function unless(condition, usual_value, exceptional_value) {      
    return condition ? exceptional_value : usual_value;
}

that can be used in statements such as

unless(is_null(xs), head(xs), display("error: xs should not be null"));

This won't work in an applicative-order language because both the usual value and the exceptional value will be evaluated before unless is called (compare exercise 1.6). An advantage of lazy evaluation is that some functions, such as unless, can do useful computation even if evaluation of some of their arguments would produce errors or would not terminate.

If the body of a function is entered before an argument has been evaluated we say that the function is non-strict in that argument. If the argument is evaluated before the body of the function is entered we say that the function is strict in that argument.[2] In a purely applicative-order language, all functions are strict in each argument. In a purely normal-order language, all compound functions are non-strict in each argument, and primitive functions may be either strict or non-strict. There are also languages (see exercise 4.29) that give programmers detailed control over the strictness of the functions they define.

A striking example of a function that can usefully be made non-strict is pair (or, in general, almost any constructor for data structures). One can do useful computation, combining elements to form data structures and operating on the resulting data structures, even if the values of the elements are not known. It makes perfect sense, for instance, to compute the length of a list without knowing the values of the individual elements in the list. We will exploit this idea in section 4.2.3 to implement the streams of chapter 3 as lists formed of non-strict pairs.

Exercise 4.23 Suppose that (in ordinary applicative-order JavaScript) we define unless as shown above and then define factorial in terms of unless as

function factorial(n) {
    return unless(n === 1,
                  n * factorial(n - 1),
                  1);
}

What happens if we attempt to evaluate factorial(5)? Will our functions work in a normal-order language?

(provided by GitHub user joeng03) When evaluated in default (‘strict’) mode, the code undergoes applicative order reduction and runs into an infinite loop because it needs to evaluate the arguments of the unless function, but the factorial function does not have a terminating condition. When evaluated in lazy mode, the code undergoes normal order reduction. It produces the correct output because the unless function is applied before its arguments are evaluated.

Exercise 4.24 Ben Bitdiddle and Alyssa P. Hacker disagree over the importance of lazy evaluation for implementing things such as unless. Ben points out that it's possible to implement unless in applicative order as a syntactic form. Alyssa counters that, if one did that, unless would be merely syntax, not a function that could be used in conjunction with higher-order functions. Fill in the details on both sides of the argument. Show how to implement unless as a derived component (like operator combination), by catching in evaluate applications whose function expression is the name unless. Give an example of a situation where it might be useful to have unless available as a function, rather than as a syntactic form.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

[1] The difference between the lazy terminology and the normal-order terminology is somewhat fuzzy. Generally, lazy refers to the mechanisms of particular evaluators, while normal-order refers to the semantics of languages, independent of any particular evaluation strategy. But this is not a hard-and-fast distinction, and the two terminologies are often used interchangeably.

[2] The strict versus non-strict terminology means essentially the same as applicative-order versus normal-order, except that it refers to individual functions and arguments rather than to the language as a whole. At a conference on programming languages you might hear someone say, The normal-order language Hassle has certain strict primitives. Other functions take their arguments by lazy evaluation.

< Previous

Next >

4.2.1 Normal Order and Applicative Order