Programming Languages – Are Normal Order and Call-by-Name the Same?

functional programminglambdaprogramming-languages

I was studying the book Structure and Interpretation of Computer Programs and in section 1.1.5 The Substitution Model for Procedure Application the author explains the concepts of normal order and applicative order, which I believe I have understood well.

Now, I am taking a course on Coursera called Function Programming Principles in Scala and there the professor Martin Odersky (who based much of his course in the book cited above) explains the same concepts under the names of call-by-name and call-by-value.

In his course, professor Odersky says the substitution model is based on the Lambda Calculus, so I consulted a book on my library An Introduction to Functional Programming Though Lambda Calculus and in page 22, the author does define the terms as applicative order and normal order. Interestingly in his definition he says that applicative order is like Pascal's call-by-value whereas normal order is like Algol's call-by-name.

The use of the words "is like" in his explanation is what made me doubt. Thus my questions:

  • Are these two terms equivalent or are there any
    subtle differences?
  • Can I use one or the other interchangeably
    without risking making a mistake in the meaning they convey?
  • Are there any reasons you know about that justify the existence of different terminology to refer to the same thing?

Best Answer

Normal order evaluation and call-by-name evaluation are not quite the same thing. In normal order evaluation, the outermost function is evaluated before any of its arguments, and those arguments are evaluated only if needed. In call-by-name evaluation, the arguments are effectively copied into the body of the outermost function and then that function is evaluated. In both cases, the outermost function is technically evaluated before the arguments, but in pure call-by-name, the arguments are evaluated each time they are used (either zero, one, or many times). In normal order, the function arguments are evaluated at the very least only when first needed (typically zero or one times).

Thus normal order evaluation leaves open the possibility of memoizing the arguments as an optimization (sometimes called call-by-need), while call-by-name does not. Thus one could say that call-by-name evaluation is a special case of normal order evaluation. In other words, normal order evaluation refers to the general approach of evaluating a function before its arguments, while call-by-name evaluation refers to a specific technique for implementing normal order evaluation.

As an example, given f(x, y) = sqrt(x*x + y*y) we could have two ways of implementing f(a+b, c+d) with normal order evaluation:

Memoized:

t1 = a+b;
t2 = c+d;
return sqrt(t1*t1 + t2*t2);

Call-by-name:

return sqrt((a+b)*(a+b) + (c+d)*(c+d));

As you can see, if the call to f included other function calls (i.e. f(random(1,100), ask_user_for_value()) ), the two will have very different behavior. The memoized version will square a single random number and ask the user for a value only once, while the call-by-name version will multiply two random numbers and ask the user for a value twice.

To learn more about these concepts, I recommend reading the evaluation strategy Wikipedia page, and https://cs.stackexchange.com/questions/7702/applicative-order-and-normal-order-in-lambda-calculus.

Related Topic