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

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