Call by need vs call by name

Question

I didn't understand the diffrence between Call-by-name and Call-by-need. As I understood, Call-by-need method restores the answer returned. But how It helps us, and Is there any fundamental difference between the results ?

For example,

begin integer n;
  procedure foo(e, n);
  integer e, n;
  begin
    for n := 1 step 1 until 10 do begin
      prints(`;;; the value of e is ');
      printnln(e)
    end
  end;
  foo(2 * n, n)
end

So in call-by-name, as I understood, We will get:

;;; the value of e is 2
;;; the value of e is 4
;;; the value of e is 8

and so on. This is because we pass 2*n to e, and e is evaluate with the new i everytime. What would happen in call-by-need?

Answer 1

It seems that your confusion stems from the fact that you are thinking in an imperative context. The discussion of call-by-need vs. call-by-value mostly comes up about declarative and functional languages, and lambda calculus.

You can see in this article about evaluation strategies that both call-by-name and call-by-need are considered lazy evaluation strategies. Lazy evaluation means that when an expression is passed as a parameter to a function, it is not evaluated before entering the function body, but only when it is accessed/read the first time inside the function. If the result of such expression is never used inside, then it will never be evaluated.

For example the ? : operator is lazy in Java as the below code demonstrates:

String test(Object obj)
{
    return 1 == 2 ? obj.toString() : "Hello World";
}

test(null); // this won't throw a NullPointerException

Call-by-need is an essential feature of most functional languages which have a pure subset. In a purely functional language, every function has to be referentially transparent, i.e. they cannot have side-effects. Such pure functions have the property that for some given input they always return the same output, no matter how many times called, and that they never change anything in the "state of the world". They behave just like mathematical functions written on the paper.

As you have already realized, call-by-need strategy is not feasible when calling non-pure functions, because you are most probably interested in the side-effects due to the consecutive calls. On the other hand it becomes an essential feature for performance when used in purely functional languages (see the second example below). Also, see these wiki pages about the concepts of Graph Reduction and Memoization.

Real-world examples

First. One example of a commonly used system which uses graph reduction is Apache Ant. Ant does not evaluate a target twice. This design makes it convenient to sketch up a declarative build plan.

Second. If you want to see a good demonstration of memoization, type this Haskell code to a GHC interpreter and see what happens:

Prelude> let fibs = 0:1:(zipWith (+) fibs (tail fibs))
-- This defines the Fibonacci sequence.
Prelude> fibs !! 200000
-- Prints the 200,000th Fibonacci number,
-- takes several seconds to calculate.
Prelude> fibs !! 200000
-- Prints the same number as before,
-- but this time it returns immediately.

---

Note. You might also have heard about the call-by-value evaluation strategy. In contrast with call-by-name and call-by-need, call-by-value is a strict evaluation strategy. It is like call-by-name in the sense that calling multiple times result in multiple evaluation. This is the most common paradigm for programmers who are accustomed to imperative languages like C# or Java.