Call-by-Value vs. Call-by-Name: A Historical Perspective

Hello! Welcome to the first lesson in our module on Evaluation Strategies.

This lesson will introduce the fundamental concepts of how programming languages handle arguments passed to functions. Understanding this is crucial, as it affects everything from program performance and predictability to the very kinds of abstractions a language can offer.

Specifically, we will focus on the learning outcome: Contrast call-by-value and call-by-name evaluation, citing historical examples like Algol 60 and their influence on modern languages.

We'll start by defining the two main evaluation strategies, explore their mechanics with concrete examples, and discuss their historical origins and trade-offs. Given your background in mathematics and economics, you'll likely appreciate the focus on formal rules and the analysis of design trade-offs that these concepts entail.

Let's begin.

1. The Foundation: L-values and R-values

Before we can compare evaluation strategies, we need a precise way to talk about variables and their values. A useful mental model, originating from early languages like C, is the distinction between an L-value and an R-value.

• L-value (Location): Think of this as the memory address or location of a variable. It's the "box" where a value is stored. The 'L' can be thought of as standing for "left-hand side" of an assignment, since that's where a location is required.
• R-value (Value): This is the actual value stored at a location. It's the "contents" of the box. The 'R' can be thought of as "right-hand side" of an assignment, where a value is expected.

For example, in the statement x = 10;, x provides the L-value (the location to store something) and 10 provides the R-value (the value to be stored).

The distinction between evaluating an argument to get its R-value versus using its L-value is the crux of the difference between many parameter-passing mechanisms.

To solidify this, please read a brief introduction to these concepts.

2. Call-by-Value: The Default Strategy

Call-by-value is the most common evaluation strategy in modern programming languages, including Python, Java, C, and C++.

The Rule:

1. The argument expression is fully evaluated to a value (its R-value) before the function is called.
2. A new memory location is created for the formal parameter inside the function.
3. The value from step 1 is copied into this new location.

The key takeaway is that the function receives a copy of the argument's value, not the original variable itself. Any modifications to the parameter inside the function affect only this local copy.

To see this in action, let's watch a video that explains call-by-value (referred to as "in mode").

A Note on Objects and References

You might have heard people say that Java or Python pass objects "by reference." This is a common point of confusion. In reality, they use call-by-value, but the value being passed for an object is its memory address (a reference). This is sometimes called call-by-sharing.

This means:

• A copy of the reference is passed to the function.
• The function can use this copied reference to modify the contents of the original object.
• However, if the function reassigns the parameter to a new object, this only changes the local copy of the reference and has no effect on the caller.

The same video explains this nuance very well.

Pros and Cons of Call-by-Value:

• Pro: It's simple and predictable. It prevents functions from having unexpected side effects on the caller's state, making programs easier to reason about.
• Con: Copying can be inefficient for large data structures.

3. Call-by-Name: The Algol 60 Approach

Call-by-name is a much rarer and more powerful—but also more complex—evaluation strategy. It was famously introduced in Algol 60.

The Rule:
The argument expression is not evaluated before the function call. Instead, the unevaluated expression is passed directly. This expression is then re-evaluated every single time the parameter is accessed within the function.

Conceptually, this is often described by the Algol 60 copy rule: the procedure call behaves as if the formal parameter were textually replaced by the actual argument expression throughout the function body (with careful handling to avoid name clashes).

This is fundamentally different from call-by-value. We are not passing a value, but a computation to be performed later. In modern terms, you can think of it as passing a thunk—a small, anonymous function that wraps the expression and its evaluation context.

Let's watch a video that demonstrates the peculiar behavior of call-by-name.

The Power and Peril of Call-by-Name

The video example shows how call-by-name can lead to surprising results if you're accustomed to call-by-value. The expression a[J] doesn't refer to a fixed location; it refers to a different element of the array in each iteration because J changes.

This capability enabled a famous programming technique known as Jensen's Device. It allowed programmers in Algol 60 to write highly generic procedures, such as a summation function that could sum the elements of an array V by being called as Sum(i, 1, 100, V[i]). The Sum procedure would manipulate the index i and re-evaluate the expression V[i] for each new value of i.

The Stack Overflow thread below contains an excellent summary and a direct quote from John C. Mitchell's book, which you expressed an interest in.

Pros and Cons of Call-by-Name:

• Pro: Incredibly powerful for creating generic abstractions (like Jensen's Device). It also has the property that if an argument is never used in the function, it is never evaluated. This means a function can terminate even if one of its arguments is an expression that would cause an error or an infinite loop.
• Con: The interaction with side effects makes it extremely difficult to reason about program behavior. It can also be inefficient if an argument is used many times, as it is re-evaluated each time.

4. Direct Contrast and a Worked Example

Let's solidify the contrast with a classic example, adapted from Mitchell's book and also found in the Cambridge lecture slides.

Consider this Algol-like code:

begin
  integer i; i := 1;
  integer array A[1:2]; A[1] := 2; A[2] := 3;

  procedure P(x); integer x;
  begin
    i := x;
    x := 1;
  end

  P(A[i]);
  print(i, A[1], A[2]);
end

What does this program print? The answer depends entirely on the evaluation strategy.

Analysis with Call-by-Value:

1. P(A[i]) is called: The argument A[i] is evaluated first. Since i is 1, A[1] evaluates to 2.
2. Inside P: A local variable x is created and initialized to 2.
3. i := x;: i is assigned the value of x, so i becomes 2.
4. x := 1;: The local variable x is assigned 1. This has no effect outside the function.
5. Result: The program prints i=2, A[1]=2, A[2]=3.

Analysis with Call-by-Name:

1. P(A[i]) is called: The unevaluated expression A[i] is passed. Conceptually, the body of P becomes:

   begin
     i := A[i];
     A[i] := 1;
   end
   

2. i := A[i];: This statement is executed. The current value of i is 1. So, A[1] (which is 2) is fetched and assigned to i. Now i is 2.
3. A[i] := 1;: This statement is executed. The current value of i is now 2. So, the location A[2] is assigned the value 1.
4. Result: The program prints i=2, A[1]=2, A[2]=1.

This example perfectly illustrates how call-by-name's re-evaluation of both the value and location of an expression within a changing context can lead to dramatically different outcomes.

Conclusion

In this lesson, we've contrasted two fundamental evaluation strategies.

Key Takeaways:

• Call-by-Value: Evaluates arguments before the function call and passes a copy of the value. It's simple, predictable, and protects the caller from side effects. It is the standard in almost all modern mainstream languages.
• Call-by-Name: Passes an unevaluated expression which is re-evaluated on each use. It's powerful and allows for unique abstractions like Jensen's Device in Algol 60, but its interaction with side effects makes it complex and difficult to reason about.
• Historical Influence: While call-by-value became the dominant paradigm for its safety and simplicity, the core idea of call-by-name—delaying evaluation—was not abandoned. It was refined and evolved.

Preview of the Next Lesson:

The inefficiency and complexity of call-by-name led to its decline. However, what if we could keep its benefit (evaluating only when needed) while fixing its main drawback (re-evaluating every time)? This leads directly to our next topic: lazy evaluation, also known as call-by-need. We will see how this strategy, which is central to the Haskell programming language, evaluates an argument the first time it's needed and then saves the result for all subsequent uses.