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.

Desai

Answer 1

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

Wakeful

I think you may be confusing call-by-name with call-by-value, and call-by-need with call-by-name. – Pleuro

I also think it's not precise. Isn't what you mentioned as call-by-name, actually a call-by-value? – Hellenhellene

It's unfortunate that this is the accepted answer as it is almost entirely wrong and doesn't explain what call-by-need is. People should be aware that this answer has 10 downvotes, for good reason. – Amundsen

Answer 2

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

Novgorod

Isn't Haskell call-by-need, rather than call-by-name? – Weinstock

Answer 3

Call-by-need uses lazy evaluation. A simple, yet illustrative example:

function choose(cond, arg1, arg2) {
   if (cond)
      do_something(arg1);
   else
      do_something(arg2);
}

choose(true, 7*0, 7/0);

Now lets say we're using the eager evaluation strategy, then it would calculate both 7*0 and 7/0 eagerly. If it is a lazy evaluated strategy (call-by-need), then it would just send the expressions 7*0 and 7/0 through to the function without evaluating them.

The difference? you would expect to execute do_something(0) because the first argument gets used, although it actually depends on the evaluation strategy:

If the language evaluates eagerly, then it will, as stated, evaluate 7*0 and 7/0 first, and what's 7/0? Divide-by-zero error.

But if the evaluation strategy is lazy, it will see that it doesn't need to calculate the division, it will call do_something(0) as we were expecting, with no errors.

In this example, the lazy evaluation strategy can save the execution from producing errors. In a similar manner, it can save the execution from performing unnecessary evaluation that it won't use (the same way it didn't use 7/0 here).

Thomasina

Even eager languages actually do that. – Wakeful

I just felt it misleading since even languages that call themselves eager will not give you a divided by zero error in this case - since they are eager they will first evaluate the boolean and then figure that calculating the division is pointless. What you are describing as eager would be more an evaluate everything language. – Wakeful

@JakubHampl That's really not the case - eager languages first evaluate all parameters to the function, then call it. So in this case, it evaluates true, 7*0, 7/0... and then throws the error/exception - choose is never called. Your argument would only (possibly) work if choose were to be inlined, and the compiler sees that 7/0 is a pure (non-sideeffecting) computation, so can be removed without any semantic change (although seeing the guaranteed divide by 0 error might well constitute a side-effect - the definition is up to the language/compiler). – Madra

@JakubHampl "eager evaluation is a technique where an expression is evaluated as soon as it is bound to a variable or passed as an argument" ... 7/0 is bound to arg2 and therefore is immediately evaluated. (Many compilers will actually evaluate it at compile time and yield an error then.) – Amundsen

Answer 4

Here's a concrete example for a bunch of different evaluation strategies written in C. I'll specifically go over the difference between call-by-name, call-by-value, and call-by-need, which is kind of a combination of the previous two, as suggested by Ryan's answer.

#include<stdio.h>
int x = 1;
int y[3]= {1, 2, 3};
int i = 0;
int k = 0;
int j = 0;

int foo(int a, int b, int c) {
    i = i + 1;
    // 2 for call-by-name
    // 1 for call-by-value, call-by-value-result, and call-by-reference
    // unsure what call-by-need will do here; will likely be 2, but could have evaluated earlier than needed
    printf("a is %i\n", a);
    b = 2;
    // 1 for call-by-value and call-by-value-result
    // 2 for call-by-reference, call-by-need, and call-by-name
    printf("x is %i\n", x);

    // this triggers multiple increments of k for call-by-name
    j = c + c;

    // we don't actually care what j is, we just don't want it to be optimized out by the compiler
    printf("j is %i\n", j);

    // 2 for call-by-name
    // 1 for call-by-need, call-by-value, call-by-value-result, and call-by-reference
    printf("k is %i\n", k);
}

int main() {
    int ans = foo(y[i], x, k++);
    // 2 for call-by-value-result, call-by-name, call-by-reference, and call-by-need
    // 1 for call-by-value
    printf("x is %i\n", x);
    return 0;
}

The part we're most interested in is the fact that foo is called with k++ as the actual parameter for the formal parameter c.

Note that how the ++ postfix operator works is that k++ returns k at first, and then increments k by 1. That is, the result of k++ is just k. (But, then after that result is returned, k will be incremented by 1.)

We can ignore all of the code inside foo up until the line j = c + c (the second section).

Here's what happens for this line under call-by-value:

1. When the function is first called, before it encounters the line j = c + c, because we're doing call-by-value, c will have the value of evaluating k++. Since evaluating k++ returns k, and k is 0 (from the top of the program), c will be 0. However, we did evaluate k++ once, which will set k to 1.
2. The line becomes j = 0 + 0, which behaves exactly like how you'd expect, by setting j to 0 and leaving c at 0.
3. Then, when we run printf("k is %i\n", k); we get that k is 1, because we evaluated k++ once.

Here's what happens for the line under call-by-name:

1. Since the line contains c and we're using call-by-name, we replace the text c with the text of the actual argument, k++. Thus, the line becomes j = (k++) + (k++).
2. We then run j = (k++) + (k++). One of the (k++)s will be evaluated first, returning 0 and setting k to 1. Then, the second (k++) will be evaluated, returning 1 (because k was set to 1 by the first evaluation of k++), and setting k to 2. Thus, we end up with j = 0 + 1 and k set to 2.
3. Then, when we run printf("k is %i\n", k);, we get that k is 2 because we evaluated k++ twice.

Finally, here's what happens for the line under call-by-need:

1. When we encounter j = c + c; we recognize that this is the first time the parameter c is evaluated. Thus we need to evaluate its actual argument (once) and store that value to be the evaluation of c. Thus, we evaluate the actual argument k++, which will return k, which is 0, and therefore the evaluation of c will be 0. Then, since we evaluated k++, k will be set to 1. We then use this stored evaluation as the evaluation for the second c. That is, unlike call-by-name, we do not re-evaluate k++. Instead, we reuse the previously evaluated initial value for c, which is 0. Thus, we get j = 0 + 0; just as if c was pass-by-value. And, since we only evaluated k++ once, k is 1.
2. As explained in the previous step, j = c + c is j = 0 + 0 under call-by-need, and it runs exactly as you'd expect.
3. When we run printf("k is %i\n", k);, we get that k is 1 because we only evaluated k++ once.

Hopefully this helps to differentiate how call-by-value, call-by-name, and call-by-need work. If it would be helpful to differentiate call-by-value and call-by-need more clearly, let me know in a comment and I'll explain the code earlier on in foo and why it works the way it does.

I think this line from Wikipedia sums things up nicely:

Call by need is a memoized variant of call by name, where, if the function argument is evaluated, that value is stored for subsequent use. If the argument is pure (i.e., free of side effects), this produces the same results as call by name, saving the cost of recomputing the argument.

Magnetochemistry