What is call-by-need?

Question

I want to know what is call-by-need.

Though I searched in wikipedia and found it here: http://en.wikipedia.org/wiki/Evaluation_strategy, but could not understand properly. If anyone can explain with an example and point out the difference with call-by-value, it would be a great help.

Answer 1

Suppose we have the function

square(x) = x * x

and we want to evaluate square(1+2).

In call-by-value, we do

1. square(1+2)
2. square(3)
3. 3*3
4. 9

In call-by-name, we do

1. square(1+2)
2. (1+2)*(1+2)
3. 3*(1+2)
4. 3*3
5. 9

Notice that since we use the argument twice, we evaluate it twice. That would be wasteful if the argument evaluation took a long time. That's the issue that call-by-need fixes.

In call-by-need, we do something like the following:

1. square(1+2)
2. let x = 1+2 in x*x
3. let x = 3 in x*x
4. 3*3
5. 9

In step 2, instead of copying the argument (like in call-by-name), we give it a name. Then in step 3, when we notice that we need the value of x, we evaluate the expression for x. Only then do we substitute.

BTW, if the argument expression produced something more complicated, like a closure, there might be more shuffling of lets around to eliminate the possibility of copying. The formal rules are somewhat complicated to write down.

Notice that we "need" values for the arguments to primitive operations like + and *, but for other functions we take the "name, wait, and see" approach. We would say that the primitive arithmetic operations are "strict". It depends on the language, but usually most primitive operations are strict.

Notice also that "evaluation" still means to reduce to a value. A function call always returns a value, not an expression. (One of the other answers got this wrong.) OTOH, lazy languages usually have lazy data constructors, which can have components that are evaluated on-need, ie, when extracted. That's how you can have an "infinite" list---the value you return is a lazy data structure. But call-by-need vs call-by-value is a separate issue from lazy vs strict data structures. Scheme has lazy data constructors (streams), although since Scheme is call-by-value, the constructors are syntactic forms, not ordinary functions. And Haskell is call-by-name, but it has ways of defining strict data types.

If it helps to think about implementations, then one implementation of call-by-name is to wrap every argument in a thunk; when the argument is needed, you call the thunk and use the value. One implementation of call-by-need is similar, but the thunk is memoizing; it only runs the computation once, then it saves it and just returns the saved answer after that.

Answer 2

Imagine a function:

fun add(a, b) {
  return a + b
}

And then we call it:

 add(3 * 2, 4 / 2)

In a call-by-name language this will be evaluated so:

1. a = 3 * 2 = 6
2. b = 4 / 2 = 2
3. return a + b = 6 + 2 = 8

The function will return the value 8.

In a call-by-need (also called a lazy language) this is evaluated like so:

1. a = 3 * 2
2. b = 4 / 2
3. return a + b = 3 * 2 + 4 / 2

The function will return the expression 3 * 2 + 4 / 2. So far almost no computational resources have been spent. The whole expression will be computed only if its value is needed - say we wanted to print the result.

Why is this useful? Two reasons. First if you accidentally include dead code it doesn't weigh your program down and thus can be a lot more efficient. Second it allows to do very cool things like efficiently calculating with infinite lists:

fun takeFirstThree(list) {
  return [list[0], list[1], list[2]]
}

takeFirstThree([0 ... infinity])

A call-by-name language would hang there trying to create a list from 0 to infinity. A lazy language will simply return [0,1,2].