Simple example of call-by-need

Question

I'm trying to understand the theorem behind "call-by-need." I do understand the definition, but I'm a bit confused. I would like to see a simple example which shows how call-by-need works.

After reading some previous threads, I found out that Haskell uses this kind of evaluation. Are there any other programming languages which support this feature?

I read about the call-by-name of Scala, and I do understand that call-by-name and call-by-need are similar but different by the fact that call-by-need will keep the evaluated value. But I really would love to see a real-life example (it does not have to be in Haskell), which shows call-by-need.

Answer 1

The function

say_hello numbers = putStrLn "Hello!"

ignores its numbers argument. Under call-by-value semantics, even though an argument is ignored, the parameter at the function call site may need to be evaluated, perhaps because of side effects that the rest of the program depends on.

In Haskell, we might call say_hello as

say_hello [1..]

where [1..] is the infinite list of naturals. Under call-by-value semantics, the CPU would run off trying to build an infinite list and never get to the say_hello at all!

Haskell merely outputs

$ runghc cbn.hs
Hello!

For less dramatic examples, the first ten natural numbers are

ghci> take 10 [1..]
[1,2,3,4,5,6,7,8,9,10]

The first ten odds are

ghci> take 10 $ filter odd [1..]
[1,3,5,7,9,11,13,15,17,19]

Under call-by-need semantics, each value — even a conceptually infinite one as in the examples above — is evaluated only to the extent required and no more.

Answer 2

update: A simple example, as asked for:

ff 0 = 1
ff 1 = 1
ff n = go (ff (n-1))
  where
  go x = x + x

Under call-by-name, each invocation of go evaluates ff (n-1) twice, each for each appearance of x in its definition (because + is strict in both arguments, i.e. demands the values of the both of them).

Under call-by-need, go's argument is evaluated at most once. Specifically, here, x's value is found out only once, and reused for the second appearance of x in the expression x + x. If it weren't needed, x wouldn't be evaluated at all, just as with call-by-name.

Under call-by-value, go's argument is always evaluated exactly once, prior to entering the function's body, even if it isn't used anywhere in the function's body.

---

Here's my understanding of it, in the context of Haskell.

According to Wikipedia, "call by need is a memoized variant of call by name where, if the function argument is evaluated, that value is stored for subsequent uses."

Call by name:

take 10 . filter even $ [1..]

With one consumer the produced value disappears after being produced so it might as well be call-by-name.

Call by need:

import qualified Data.List.Ordered as O

h = 1 : map (2*) h <> map (3*) h <> map (5*) h
    where
    (<>) = O.union

The difference is, here the h list is reused by several consumers, at different tempos, so it is essential that the produced values are remembered. In a call-by-name language there'd be much replication of computational effort here because the computational expression for h would be substituted at each of its occurrences, causing separate calculation for each. In a call-by-need--capable language like Haskell the results of computing the elements of h are shared between each reference to h.

Another example is, most any data defined by fix is only possible under call-by-need. With call-by-value the most we can have is the Y combinator.

See: Sharing vs. non-sharing fixed-point combinator and its linked entries and comments (among them, this, and its links, like Can fold be used to create infinite lists?).