[ACCEPTED]-What is call-by-need?-call-by-need

Suppose we have the function

square(x) = x * x

and we want 43 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 42 that since we use the argument twice, we 41 evaluate it twice. That would be wasteful 40 if the argument evaluation took a long time. That's 39 the issue that call-by-need fixes.

In call-by-need, we 38 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 37 2, instead of copying the argument (like 36 in call-by-name), we give it a name. Then 35 in step 3, when we notice that we need the value 34 of x, we evaluate the expression for x. Only 33 then do we substitute.

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

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

Notice also that "evaluation" still 20 means to reduce to a value. A function call 19 always returns a value, not an expression. (One 18 of the other answers got this wrong.) OTOH, lazy 17 languages usually have lazy data constructors, which 16 can have components that are evaluated on-need, ie, when 15 extracted. That's how you can have an "infinite" list---the 14 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 13 has lazy data constructors (streams), although 12 since Scheme is call-by-value, the constructors 11 are syntactic forms, not ordinary functions. And 10 Haskell is call-by-name, but it has ways 9 of defining strict data types.

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

Imagine a function:

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

And then we call it:

 add(3 * 2, 4 / 2)

In 16 a call-by-name language this will be evaluated 15 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 14 a call-by-need (also called a lazy language) this 13 is evaluated like so:

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

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

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

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

takeFirstThree([0 ... infinity])

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

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 20 say we're using the eager evaluation strategy, then 19 it would calculate both 7*0 and 7/0 eagerly. If 18 it is a lazy evaluated strategy (call-by-need), then 17 it would just send the expressions 7*0 and 7/0 through to 16 the function without evaluating them.

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

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

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

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

Here's a concrete example for a bunch of 30 different evaluation strategies written 29 in C. I'll specifically go over the difference 28 between call-by-name, call-by-value, and 27 call-by-need, which is kind of a combination 26 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 25 part we're most interested in is the fact 24 that foo is called with k++ as the actual parameter 23 for the formal parameter c.

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

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

Here's what happens for this line 16 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 15 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 14 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 13 differentiate how call-by-value, call-by-name, and 12 call-by-need work. If it would be helpful 11 to differentiate call-by-value and call-by-need 10 more clearly, let me know in a comment and 9 I'll explain the code earlier on in foo and 8 why it works the way it does.

I think this line from Wikipedia sums 7 things up nicely:

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