Evaluation order¶

The goal of this lecture note is to investigate some more the notion of when and in which order a computation takes place. Intuitively, all the traced functions we have used so far helped us visualize the order in which calls, returns, and tail calls are taking place, but still, intuition is not reason. Consider, for example, the following expression, which was the topic of Question 12 in the mini-project about the underlying determinism of OCaml:

(fun _ -> 42) (1 / 0)

What is the result of evaluating this expressions?

Analysis:

the expression is a function application: the application of (fun _ -> 42) to (1 / 0);
the function denoted by (fun _ -> 42) ignores its argument and returns 42; and
the actual parameter (1 / 0) is the infix application of the division operator to 0.

Possible answers:

the answer is 42 because the function does not need the value of its argument to return its result: there is no need to evaluate the argument;
there is no answer because the exception Division_by_zero is raised: functions are applied to the value of their arguments.

The issue is that of evaluation order, and each programming language has a specific one. This issue determines how function applications are evaluated and what names denote. Many evaluation orders exist: here, we concentrate on call by value, call by name, and call by need.

Call by value¶

A programming language is call by value (or again strict or eager) if function arguments are evaluated before functions are applied.

OCaml, for example, is call by value, and so in the example above, the exception Division_by_zero is raised.

In a call-by-value language, names denote values, i.e., the result of evaluating actual parameters (for functions) and definienses (for let-expressions).

Unfolding a function call in a call-by-value language requires the actual parameters to be evaluated first, as articulated in the section about The recipe to unfold the call to a function in Week 07. For example,

(fun n -> n + n) e is unfolded into let n = e in n + n and
(fun _ -> 42) (1/0) is unfolded into let _ = 1/0 in 42

where the let-expression is strict (i.e., its definiens is evaluated before its body).

Call by name¶

A programming language is call by name (or again non strict or lazy) if function arguments are not evaluated before functions are applied, but only when they are needed as the body of the function is being evaluated.

ALGOL 60, for example, is call by name, and so in the example above (rewritten in a suitable syntax), the answer is 42.

In a call-by-name language, names denote suspended evaluations, i.e., the result of not evaluating actual parameters (for functions) and definienses (for let-expressions).

Each time a name is evaluated in the body of a function or of a let expression, the suspended evaluation is “thawed” and takes place.

A language which is call by name implements what is known as the copy rule in that when unfolding a function call, the actual parameters are substituted for the formal parameters (i.e., copied) in the body of the inlined function. For example,

(fun n -> n + n) e is unfolded into e + e and
(fun _ -> 42) (1/0) is unfolded into 42.

In practice, the copy rule requires local renaming for names not to shadow other names. For example, (fun x y -> x + y) (y + 1) is unfolded into (fun y' -> (y + 1) + y'), where y has been renamed into y' in order not to shadow y in (y + 1).

Call by need¶

A programming language is call by need (or again non strict or fully lazy) if function arguments are not evaluated before functions are applied, but only when they are needed as the body of the function is being evaluated. Furthermore, the first time a function argument is evaluated, the result of this evaluation is memoized to be subsequently reused, should it be needed again.

Haskell, for example, is call by need, and so in the example above (rewritten in a suitable syntax), the answer is 42, no matter the argument of the function.

In a call-by-need language, names denote suspended evaluations, i.e., the result of not evaluating actual parameters (for functions) and definienses (for let-expressions).

The first time a name is evaluated in the body of a function or of a let expression, the suspended evaluation is “thawed” and takes place. The result is then memoized and subsequently reused, should this name be evaluated again.

In practice, unfolding a call requires to be mindful of the context. For example:

(fun x -> x + x) e is unfolded into let x = e in x + x;
x + x is evaluated in the delimited context let x = e in [.], and since addition is strict (i.e., requires its arguments to be evaluated), the first occurrence of x is evaluated, which forces e, in the context, to be evaluated;
assuming that evaluating e yields n, the context becomes let x = n in [.] before the second occurrence of x is evaluated in this new context; this evaluation yields n;
the addition then takes place and its result is the result of (fun x -> x + x) e.

Memoization has been achieved by changing the context.

Example: a non-strict function¶

The introductory example, i.e., (fun _ -> 42) (1 / 0), was that of a non-strict function, i.e., a function whose result does not need its argument to be evaluated:

in a call-by-value language, its argument is always evaluated;
in a call-by-name language, its argument is never evaluated; and
in a call-by-need language, its argument is never evaluated.

So the example makes it possible to distinguish call by value from call by name and call by need, but not call by name from call by need.

Example: a linear function¶

A linear function uses its argument exactly once. Like a non-strict function, it makes it possible to distinguish call by value from call by name and call by need (since in call by value, the argument is evaluated before the function is called, whereas in call by name and call by need, it is evaluated after the function is called), but not call by name from call by need.

Example: a non-linear function¶

A non-linear function uses its argument more than once.

Consider the following function application:

(fun n -> n + n) (let () = Printf.printf "hello\n" in 10)

Analysis:

the expression is a function application: the application of (fun n -> n + n) to (let () = Printf.printf "hello\n" in 10);
the function denoted by (fun n -> n + n) adds its argument to itself and returns the result; and
when evaluated, the actual parameter (let () = Printf.printf "hello\n" in 10) prints hello and yields 10.

So:

in a call-by-value language, evaluating this expression has the effect of printing hello (before the function is called) and yields the result of adding 10 and 10, i.e., 20; the argument is evaluated once, before the function is called;
in a call-by-name language, evaluating this expression has the effect of printing hello twice (after the function is called) and yields the result of adding 10 and 10, i.e., 20; the argument is evaluated twice, after the function is called;
in a call-by-need language, evaluating this expression has the effect of printing hello once (after the function is called) and yields the result of adding 10 and 10, i.e., 20; the argument is evaluated once, after the function is called.

Left-to-right call by value¶

A programming language is left-to-right call by value if, in an application, the function is evaluated before the actual parameter. Standard ML, for example, is such a programming language.

Right-to-left call by value¶

A programming language is right-to-left call by value if, in an application, the function is evaluated after the actual parameter. As investigated in Question 02 in the midterm mini-project, OCaml is such a programming language.

Call by value in an unspecified order¶

In Scheme, procedure arguments are evaluated before procedures are applied. As to whether sub-expressions in an application are evaluated from left to right, or from right to left, or in any given order, that is left unspecified.

Ditto in C for function arguments.

Exercise 01¶

Consider the following function declaration in the syntax of OCaml:

let chirpy b x y =
  if b
  then x
  else y + y;;

The goal of this exercise is to determine what happens when the following two expressions are evaluated in a variety of evaluation orders:

chirpy true
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)

chirpy false
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)

Assuming left-to-right call by value, what happens when the first expression (the one with true) is evaluated?

Justify your answer.
Assuming right-to-left call by value, what happens when the first expression (the one with true) is evaluated?

Justify your answer.
Assuming call by name and that the arguments of + are evaluated from left to right, what happens when the first expression (the one with true) is evaluated?

Justify your answer.
Assuming call by name and that the arguments of + are evaluated from right to left, what happens when the first expression (the one with true) is evaluated?

Justify your answer.
Assuming call by need and that the arguments of + are evaluated from left to right, what happens when the first expression (the one with true) is evaluated?

Justify your answer.
Assuming call by need and that the arguments of + are evaluated from right to left, what happens when the first expression (the one with true) is evaluated?

Justify your answer.
Assuming left-to-right call by value, what happens when the second expression (the one with false) is evaluated?

Justify your answer.
Assuming right-to-left call by value, what happens when the second expression (the one with false) is evaluated?

Justify your answer.
Assuming call by name and that the arguments of + are evaluated from left to right, what happens when the second expression (the one with false) is evaluated?

Justify your answer.
Assuming call by name and that the arguments of + are evaluated from right to left, what happens when the second expression (the one with false) is evaluated?

Justify your answer.
Assuming call by need and that the arguments of + are evaluated from left to right, what happens when the second expression (the one with false) is evaluated?

Justify your answer.
Assuming call by need and that the arguments of + are evaluated from right to left, what happens when the second expression (the one with false) is evaluated?

Justify your answer.

Solution for Exercise 01¶

Assuming left-to-right call by value, here is what happens when evaluating:
```
chirpy true
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. chirpy is evaluated and the result is a function
2. the first actual parameter, i.e., true, is evaluated and the result is true
3. the second actual parameter, i.e., (let () = Printf.printf "hello\n" in 1), is evaluated, and so hello is printed and the result is 1
4. the third actual parameter, i.e., (let () = Printf.printf "world\n" in 10), is evaluated, and so world is printed and the result is 10
5. the function denoted by chirpy is applied to true, 1, and 10
6. the expression if b then x else y + y is evaluated in an environment where b denotes true, x denotes 1, and y denotes 10
7. the test b is evaluated, yielding true
8. the consequent branch, i.e., x, is selected
9. x is evaluated, yielding 1
The result is 1.

So all in all, hello is printed, world is printed, and 1 is returned.
Assuming right-to-left call by value, here is what happens when evaluating:
```
chirpy true
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. the third actual parameter, i.e., (let () = Printf.printf "world\n" in 10), is evaluated, and so world is printed and the result is 10
2. the second actual parameter, i.e., (let () = Printf.printf "hello\n" in 1), is evaluated, and so hello is printed and the result is 1
3. the first actual parameter, i.e., true, is evaluated and the result is true
4. chirpy is evaluated and the result is a function
5. the function denoted by chirpy is applied to true, 1, and 10
6. the expression if b then x else y + y is evaluated in an environment where b denotes true, x denotes 1, and y denotes 10
7. the test b is evaluated, yielding true
8. the consequent branch, i.e., x, is selected
9. x is evaluated, yielding 1
The result is 1.

So all in all, world is printed, hello is printed, and 1 is returned.
Assuming call by name and that the arguments of + are evaluated from left to right, here is what happens when evaluating:
```
chirpy true
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. chirpy is evaluated and the result is a function
2. the function denoted by chirpy is applied to the suspended evaluation of its three actual parameters
3. the expression if b then x else y + y is evaluated in an environment where b, x, and y respectively denote the suspended evaluation of the three actual parameters
4. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields true
5. the consequent branch, i.e., x, is selected
6. x is evaluated, which forces the evaluation of the second actual parameter, which prints hello and yields 1
The result is 1.

So all in all, hello is printed and 1 is returned.
Assuming call by name and that the arguments of + are evaluated from right to left, here is what happens when evaluating:
```
chirpy true
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
The same thing happens as in c., since + is not applied.
Assuming call by need and that the arguments of + are evaluated from left to right, here is what happens when evaluating:
```
chirpy true
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. chirpy is evaluated and the result is a function
2. the function denoted by chirpy is applied to the suspended evaluation of its three actual parameters
3. the expression if b then x else y + y is evaluated in an environment where b, x, and y respectively denote the suspended evaluation of the three actual parameters
4. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields true; this value is memoized
5. the consequent branch, i.e., x, is selected
6. x is evaluated, which forces the evaluation of the second actual parameter, which prints hello and yields 1; this value is memoized
The result is 1.

So all in all, hello is printed and 1 is returned.
Assuming call by need and that the arguments of + are evaluated from right to left, here is what happens when evaluating:
```
chirpy true
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
The same thing happens as in e., since + is not applied.
Assuming left-to-right call by value, here is what happens when evaluating:
```
chirpy false
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. chirpy is evaluated and the result is a function
2. the first actual parameter, i.e., false, is evaluated and the result is false
3. the second actual parameter, i.e., (let () = Printf.printf "hello\n" in 1), is evaluated, and so hello is printed and the result is 1
4. the third actual parameter, i.e., (let () = Printf.printf "world\n" in 10), is evaluated, and so world is printed and the result is 10
5. the function denoted by chirpy is applied to false, 1, and 10
6. the expression if b then x else y + y is evaluated in an environment where b denotes false, x denotes 1, and y denotes 10
7. the test b is evaluated, yielding false
8. the alternative branch, i.e., y + y, is selected
9. the first argument of + (i.e., the left occurrence of y) is evaluated, yielding 10
10. the second argument of + (i.e., the right occurrence of y) is evaluated, yielding 10
11. the addition takes place, yielding 20
The result is 20.

So all in all, hello is printed, world is printed, and 20 is returned.
Assuming right-to-left call by value, here is what happens when evaluating:
```
chirpy false
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. the third actual parameter, i.e., (let () = Printf.printf "world\n" in 10), is evaluated, and so world is printed and the result is 10
2. the second actual parameter, i.e., (let () = Printf.printf "hello\n" in 1), is evaluated, and so hello is printed and the result is 1
3. the first actual parameter, i.e., false, is evaluated and the result is false
4. chirpy is evaluated and the result is a function
5. the function denoted by chirpy is applied to false, 1, and 10
6. the expression if b then x else y + y is evaluated in an environment where b denotes false, x denotes 1, and y denotes 10
7. the test b is evaluated, yielding false
8. the alternative branch, i.e., y + y, is selected
9. the second argument of + (i.e., the right occurrence of y) is evaluated, yielding 10
10. the first argument of + (i.e., the left occurrence of y) is evaluated, yielding 10
11. the addition takes place, yielding 20
The result is 20.

So all in all, world is printed, hello is printed, and 20 is returned.
Assuming call by name and that the arguments of + are evaluated from left to right, here is what happens when evaluating:
```
chirpy false
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. chirpy is evaluated and the result is a function
2. the function denoted by chirpy is applied to the suspended evaluation of its three actual parameters
3. the expression if b then x else y + y is evaluated in an environment where b, x, and y respectively denote the suspended evaluation of the three actual parameters
4. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields false
5. the alternative branch, i.e., y + y, is selected
6. the first argument of + (i.e., the left occurrence of y) is evaluated, which forces the evaluation of the third parameter, which prints world and yields 10
7. the second argument of + (i.e., the right occurrence of y) is evaluated, which forces the evaluation of the third parameter, which prints world and yields 10
8. the addition takes place, yielding 20
The result is 20.

So all in all, world is printed twice and 20 is returned.
Assuming call by name and that the arguments of + are evaluated from right to left, here is what happens when evaluating:
```
chirpy false
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. chirpy is evaluated and the result is a function
2. the function denoted by chirpy is applied to the suspended evaluation of its three actual parameters
3. the expression if b then x else y + y is evaluated in an environment where b, x, and y respectively denote the suspended evaluation of the three actual parameters
4. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields false
5. the alternative branch, i.e., y + y, is selected
6. the second argument of + (i.e., the right occurrence of y) is evaluated, which forces the evaluation of the third parameter, which prints world and yields 10
7. the first argument of + (i.e., the left occurrence of y) is evaluated, which forces the evaluation of the third parameter, which prints world and yields 10
8. the addition takes place, yielding 20
The result is 20.

So all in all, world is printed twice and 20 is returned.
Assuming call by need and that the arguments of + are evaluated from left to right, here is what happens when evaluating:
```
chirpy false
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. chirpy is evaluated and the result is a function
2. the function denoted by chirpy is applied to the suspended evaluation of its three actual parameters
3. the expression if b then x else y + y is evaluated in an environment where b, x, and y respectively denote the suspended evaluation of the three actual parameters
4. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields false; this value is memoized
5. the alternative branch, i.e., y + y, is selected
6. the first argument of + (i.e., the left occurrence of y) is evaluated, which forces the evaluation of the third parameter, which prints world and yields 10; this value is memoized
7. the second argument of + (i.e., the right occurrence of y) is evaluated, which forces the evaluation of the third parameter, which yields the memoized value 10
8. the addition takes place, yielding 20
The result is 20.

So all in all, world is printed once and 20 is returned.
Assuming call by need and that the arguments of + are evaluated from right to left, here is what happens when evaluating:
```
chirpy false
       (let () = Printf.printf "hello\n" in 1)
       (let () = Printf.printf "world\n" in 10)
```
1. chirpy is evaluated and the result is a function
2. the function denoted by chirpy is applied to the suspended evaluation of its three actual parameters
3. the expression if b then x else y + y is evaluated in an environment where b, x, and y respectively denote the suspended evaluation of the three actual parameters
4. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields false; this value is memoized
5. the alternative branch, i.e., y + y, is selected
6. the second argument of + (i.e., the right occurrence of y) is evaluated, which forces the evaluation of the third parameter, which prints world and yields 10; this value is memoized
7. the first argument of + (i.e., the left occurrence of y) is evaluated, which forces the evaluation of the third parameter, which yields the memoized value 10
8. the addition takes place, yielding 20
The result is 20.

So all in all, world is printed once and 20 is returned.

Interlude¶

Edsger Dijkstra (sententiously): Progress is possible only if we train ourselves to think about programs without thinking of them as pieces of executable code.

Rick Blaine: Not so fast, Louie.

Halcyon: Where is Mimer?

Gad Elmaleh (dutifully): Mi-mer is in the kit-chen.

Exercise 02¶

Consider the following function declaration in the syntax of OCaml:

let jolly x y =
  if x >= 0
  then x
  else x + y;;

The goal of this exercise is to determine what happens when the following two expressions are evaluated in a variety of evaluation orders:

jolly (let () = Printf.printf "hello\n" in 1)
      (let () = Printf.printf "world\n" in 10)

jolly (let () = Printf.printf "hello\n" in -1)
      (let () = Printf.printf "world\n" in 10)

(Hint: look at the solution for Exercise 01.)

Assuming left-to-right call by value, what happens when the first expression (the one with 1) is evaluated?

Justify your answer.
Assuming right-to-left call by value, what happens when the first expression (the one with 1) is evaluated?

Justify your answer.
Assuming call by name and that the arguments of + are evaluated from left to right, what happens when the first expression (the one with 1) is evaluated?

Justify your answer.
Assuming call by name and that the arguments of + are evaluated from right to left, what happens when the first expression (the one with 1) is evaluated?

Justify your answer.
Assuming call by need and that the arguments of + are evaluated from left to right, what happens when the first expression (the one with 1) is evaluated?

Justify your answer.
Assuming call by need and that the arguments of + are evaluated from right to left, what happens when the first expression (the one with 1) is evaluated?

Justify your answer.
Assuming left-to-right call by value, what happens when the second expression (the one with -1) is evaluated?

Justify your answer.
Assuming right-to-left call by value, what happens when the second expression (the one with -1) is evaluated?

Justify your answer.
Assuming call by name and that the arguments of + are evaluated from left to right, what happens when the second expression (the one with -1) is evaluated?

Justify your answer.
Assuming call by name and that the arguments of + are evaluated from right to left, what happens when the second expression (the one with -1) is evaluated?

Justify your answer.
Assuming call by need and that the arguments of + are evaluated from left to right, what happens when the second expression (the one with -1) is evaluated?

Justify your answer.
Assuming call by need and that the arguments of + are evaluated from right to left, what happens when the second expression (the one with -1) is evaluated?

Justify your answer.

After hours¶

Halcyon (candidly): In denotational semantics, is the evaluation order of the meta-language call by name or call by value?

{John Reynolds && Peter Landin} (simultaneously): Call by {name && value} of course.

A second of eternity passes, and the universe resumes its course.

Richard Bird (mildly): Call by name enables one to reason about one’s programs equationally.

Mitchell Wand (sotto voce): I prefer call by value because it is so much more predictable.

Version¶

Added the “After hours” section [25 Mar 2023]

Created [27 Oct 2022]

Evaluation order¶

Call by value¶

Call by name¶

Call by need¶

Example: a non-strict function¶

Example: a linear function¶

Example: a non-linear function¶

Left-to-right call by value¶

Right-to-left call by value¶

Call by value in an unspecified order¶

Exercise 01¶

Solution for Exercise 01¶

Interlude¶

Exercise 02¶

After hours¶

Version¶

Table Of Contents

Previous topic

Next topic

Navigation

Evaluation order¶

Call by value¶

Call by name¶

Call by need¶

Example: a non-strict function¶

Example: a linear function¶

Example: a non-linear function¶

Left-to-right call by value¶

Right-to-left call by value¶

Call by value in an unspecified order¶

Exercise 01¶

Solution for Exercise 01¶

Interlude¶

Exercise 02¶

After hours¶

Version¶

Table Of Contents

Previous topic

Next topic

Quick search

Navigation