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:

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

What is the result of evaluating it?

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 variables 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, variables denote values, i.e., the result of evaluating actual parameters (for functions) and definienses (for let-expressions).

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, variables denote suspended evaluations, i.e., the result of not evaluating actual parameters (for functions) and definienses (for let-expressions).

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

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.

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

The first time a variable 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 variable be evaluated again.

Example: a non-strict function

The introductory example 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.

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 we have seen, that is the case for OCaml.

Exercise 1

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)

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

   Justify your answer.

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

   Justify your answer.

3. 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.

4. 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.

5. 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.

6. 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.

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

   Justify your answer.

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

   Justify your answer.

9. 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.

10. 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.

11. 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.

12. 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 1

1. 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. the first actual parameter, i.e., true, is evaluated and the result is true
   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 third actual parameter, i.e., (let () = Printf.printf "world\n" in 10), is evaluated, and so world is printed and the result is 10
   4. chirpy is applied to true, 1, and 10
   5. 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
   6. the test b is evaluated, yielding true
   7. the consequent branch, i.e., x, is selected
   8. x is evaluated, yielding 1

   The result is 1.

   So all in all, hello is printed, world is printed, and 1 is returned.

2. 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 applied to true, 1, and 10
   5. 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
   6. the test b is evaluated, yielding true
   7. the consequent branch, i.e., x, is selected
   8. x is evaluated, yielding 1

   The result is 1.

   So all in all, world is printed, hello is printed, and 1 is returned.

3. 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 applied to the suspended evaluation of its three actual parameters
   2. 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
   3. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields true
   4. the consequent branch, i.e., x, is selected
   5. 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.

4. 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.

5. 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 applied to the suspended evaluation of its three actual parameters
   2. 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
   3. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields true; this value is memoized
   4. the consequent branch, i.e., x, is selected
   5. 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.

6. 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.

7. 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. the first actual parameter, i.e., false, is evaluated and the result is false
   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 third actual parameter, i.e., (let () = Printf.printf "world\n" in 10), is evaluated, and so world is printed and the result is 10
   4. chirpy is applied to false, 1, and 10
   5. 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
   6. the test b is evaluated, yielding false
   7. the alternative branch, i.e., y + y, is selected
   8. the first argument of + (i.e., the left occurrence of y) is evaluated, yielding 10
   9. the second argument of + (i.e., the right occurrence of y) is evaluated, yielding 10
   10. the addition takes place, yielding 20

   The result is 20.

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

8. 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 applied to false, 1, and 10
   5. 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
   6. the test b is evaluated, yielding false
   7. the alternative branch, i.e., y + y, is selected
   8. the second argument of + (i.e., the right occurrence of y) is evaluated, yielding 10
   9. the first argument of + (i.e., the left occurrence of y) is evaluated, yielding 10
   10. the addition takes place, yielding 20

   The result is 20.

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

9. 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 applied to the suspended evaluation of its three actual parameters
   2. 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
   3. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields false
   4. the alternative branch, i.e., y + y, is selected
   5. 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
   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 addition takes place, yielding 20

   The result is 20.

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

10. 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 applied to the suspended evaluation of its three actual parameters
    2. 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
    3. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields false
    4. the alternative branch, i.e., y + y, is selected
    5. 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
    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 addition takes place, yielding 20

    The result is 20.

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

11. 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 applied to the suspended evaluation of its three actual parameters
    2. 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
    3. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields false; this value is memoized
    4. the alternative branch, i.e., y + y, is selected
    5. 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
    6. 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
    7. the addition takes place, yielding 20

    The result is 20.

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

12. 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 applied to the suspended evaluation of its three actual parameters
    2. 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
    3. the test b is evaluated, which forces the evaluation of the first actual parameter, which yields false; this value is memoized
    4. the alternative branch, i.e., y + y, is selected
    5. 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
    6. 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
    7. the addition takes place, yielding 20

    The result is 20.

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

Exercise 2

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 1.)

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

   Justify your answer.

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

   Justify your answer.

3. 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.

4. 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.

5. 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.

6. 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.

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

   Justify your answer.

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

   Justify your answer.

9. 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.

10. 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.

11. 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.

12. 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.

Version

Fixed a typo in the narrative, thanks to Yunjeong Lee’s eagle eye [11 Jun 2019]

Created [28 Mar 2019]