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.

Answer 2

Call-by-name is a function calling discipline where when a call is made to a receving function foo, instead of the arguments to foo being evaluated, foo receives (behind the scenes) an appropriate object that will allow it to evaluate the parameters it needs; or equivalently, evaluation progresses by macro substitution. If a parameter is required more than once, it will be evaluated more than once. See: http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_name

Call-by-need is much the same, except that the object passed is a promise, and will be evaluated no more than once; on subsequent references to a parameter, the memoised value is used. See: http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need

Answer 3

First of all, either call-by-need or call-by-name represent ways of implementing lazy-evaluation, so it necessary to know what is lazy-evaluation ...

You can see call-by-need in Haskell for example and call-by-name in Scala.

call-by-need is maybe the expected way of implementing laziness. The first time you "really" need the value, you computed it and you make a cache of the computed value for future access.

when you have call-by-name you don't perform this sort of caching, you evaluate the function arguments every time they are used in the function body. It is possible to think that it does not have sense, but it is useful to implement some flow control structure as function of the language, let say a while.

def myWhile (cond : => Boolean, body : => Unit) {
  if (cond) { body ; myWhile (cond, body) }
}

And then you can call the function myWhile,

var x = 3

myWhile (x != 0, {
  print (x)
  x = x - 1   
})

If we had call-by-name for the example above, the expression "cond" is not cached and it is evaluated each time is needed.