31

It seems lazy evaluation of expressions can cause a programmer to lose control over the order in which their code is executed. I am having trouble understanding why this would be acceptable or desired by a programmer.

How can this paradigm be used to build predictable software that works as intended, when we have no guarantee when and where an expression will be evaluated?

Improve this question
9
  • 10
    In most cases it just doesn't matter. For all others you can just enforce strictness.
    – Cat Plus Plus
    Sep 6, 2012 at 21:57
  • 23
    The point of purely functional languages like haskell is that you don't have to bother when code is run, as it is side-effect free.
    – bitmask
    Sep 6, 2012 at 22:00
  • 22
    You need to stop thinking about "executing code" and start thinking of "calculating results", for that's what you really want in most interesting problems. Of course programs usually also need to interact with the environment in some way, but that can often be reduced to a small part of the code. For the rest, you can work purely functional, and there lazyness can make reasoning a lot simpler.
    – leftaroundabout
    Sep 6, 2012 at 22:45
  • 6
    The question in the title ("Why use lazy evaluation?") is very different from the question in the body ("How do you use lazy evaluation?"). For the former, see my answer to this related question.
    – Daniel Wagner
    Sep 6, 2012 at 22:47
  • 1
    An example when laziness is useful: In Haskell head . sort has O(n) complexity due to laziness (not O(n log n)). See Lazy Evaluation and Time Complexity.
    – Petr
    Sep 8, 2012 at 9:57

8 Answers 8

Reset to default
65

A lot of the answers are going into things like infinite lists and performance gains from unevaluated parts of the computation, but this is missing the larger motivation for laziness: modularity.

The classic argument is laid out in the much-cited paper "Why Functional Programming Matters" (PDF link) by John Hughes. The key example in that paper (Section 5) is playing Tic-Tac-Toe using the alpha-beta search algorithm. The key point is (p. 9):

[Lazy evaluation] makes it practical to modularize a program as a generator that constructs a large number of possible answers, and a selector that chooses the appropriate one.

The Tic-Tac-Toe program can be written as a function that generates the whole game tree starting at a given position, and a separate function that consumes it. At runtime this does not intrinsically generate the whole game tree, only those subparts that the consumer actually needs. We can change the order and combination in which alternatives are produced by changing the consumer; no need to change the generator at all.

In an eager language, you can't write it this way because you would probably spend too much time and memory generating the tree. So you end up either:

  1. Combining the generation and consumption into the same function;
  2. Writing a producer that works optimally only for certain consumers;
  3. Implementing your own version of laziness.
Improve this answer
7
  • Please more info or an example. This sounds intriguing.
    – Alex Nye
    Nov 25, 2012 at 18:22
  • 1
    @AlexNye: The John Hughes paper has more info. Despite being an academic paper---and therefore no doubt intimidating---it's actually very accessible and readable. If not for its length, it would probably fit as an answer here!
    – Tikhon Jelvis
    Nov 26, 2012 at 6:19
  • Perhaps to understand this answer, one must read the paper by Hughes... not having done so, I am still failing to see how and why laziness and modularity are related.
    – stakx
    Nov 30, 2014 at 17:47
  • @stakx Without a better description, they don't seem to be related except by chance. The advantage of laziness in this example is that a lazy generator is capable of generating all possible states of the game, but isn't going waste time/memory doing so because only the ones that happen will be consumed. The generator can be separated from the consumer without being a lazy generator, and it's possible (albeit more difficult) to be lazy without being separated from the consumer.
    – Izkata
    Nov 30, 2014 at 18:02
  • 1
    Very good example, but isn't this a particular application of lazy infinite lists / streams?
    – Giorgio
    Dec 1, 2014 at 20:33
32

How can this paradigm be used to build predictable software that works as intended, when we have no guarantee when and where an expression will be evaluated?

When an expression is side-effect free, the order in which the expressions are evaluated does not affect their value, so the behavior of the program is not affected by the order. So the behavior is perfectly predictable.

Now side effects are a different matter. If side effects could occur in any order, the behavior of the program would indeed be unpredictable. But this is not actually the case. Lazy languages like Haskell make it a point to be referentially transparent, i.e. making sure that the order in which expressions are evaluated will never affect their result. In Haskell this is achieved by forcing all operations with user-visible side effects to occur inside the IO monad. This makes sure that all side-effects occur exactly in the order you'd expect.

Improve this answer
8
  • 15
    This is why only languages with "enforced purity" like Haskell support laziness everywhere by default. "Encouraged purity" languages like Scala need the programmer to explicitly say where they want laziness, and it's up to the programmer to ensure that the laziness won't cause problems. A language that had laziness by default and had untracked side-effects would indeed be difficult to program predictably.
    – Ben
    Sep 7, 2012 at 2:18
  • 1
    surely monads other than IO can also cause side effects
    – jk.
    Sep 7, 2012 at 7:37
  • 1
    @jk Only IO can cause external side effects.
    – dave4420
    Sep 7, 2012 at 7:40
  • @dave4420 yes but that not what this answer says
    – jk.
    Sep 7, 2012 at 9:51
  • 1
    @jk In Haskell actually no. No monad except for IO (or ones build upon IO) has side effects. And this is only because the compiler treats IO differently. It thinks of IO as "Immutable Off". Monads are just a (clever) way to ensure a specific execution order (so your file will only be deleted after the user entered "yes").
    – scarfridge
    Sep 7, 2012 at 20:21
25

If you are familiar with databases, a very frequent way to process data is:

  • Ask a question like select * from foobar
  • While there is more data, do: get next row of results and process it

You do not control how the result is generated and in which way (indexes? Full table scans?), or when (should all the data be generated at once or incrementally when being asked for?). All you know is: if there is more data, you will get it when you ask for it.

Lazy evaluation is pretty close to the same thing. Say you have an infinite list defined as ie. the Fibonacci sequence - if you need five numbers, you get five numbers calculated; if you need 1000 you get 1000. The trick is that the runtime knows what to provide where and when. It is very, very handy.

(Java programmers can emulate this behavior with Iterators - other languages may have something similar)

Improve this answer
3
  • Good point. For example Collection2.filter() (as well as the other methods from that class) pretty much implements lazy evaluation: the result "looks like" an ordinary Collection, but the order of execution might be non-intuitive (or at least non-obvious). Also, there is yield in Python (and a similar feature in C#, which I don't remembe the name of) which is even closer to supporting lazy evaluation than a normal Iterator.
    – Joachim Sauer
    Sep 7, 2012 at 7:04
  • @JoachimSauer in C# its yield return, or of course you can use the prebuild linq oprerators, about half of which are lazy
    – jk.
    Sep 7, 2012 at 7:08
  • +1: For mentioning iterators in an imperative / object-oriented language. I used a similar solution for implementing streams and stream functions in Java. Using iterators I could have functions like take(n), dropWhile() on an input stream of unknown length.
    – Giorgio
    Sep 7, 2012 at 10:11
14

Consider asking your database for a list of the first 2000 users whose names start with "Ab" and are older than 20 years. Also they must be male.

Here's a little diagram.

You                                            Program Processor
------------------------------------------------------------------------------
Get the first 2000 users ---------->---------- OK!
                         --------------------- So I'll go get those records...
WAIT! Also, they have to ---------->---------- Gotcha!
start with "Ab"
                         --------------------- NOW I'll get them...
WAIT! Make sure they're  ---------->---------- Good idea Boss!
over 20!
                         --------------------- Let's go then...
And one more thing! Make ---------->---------- Anything else? Ugh!
sure they're male!

No that is all. :(       ---------->---------- FINE! Getting records!

                         --------------------- Here you go. 
Thanks Postgres, you're  ---------->----------  ...
my only friend.

As you can see by this terrible terrible interaction, the "database" isn't actually doing anything until it's ready to handle all the conditions. It's lazy-loading results at each step and applying new conditions each time.

As opposed to getting the first 2000 users, returning them, filtering them for "Ab", returning them, filtering them for over 20, returning them, and filtering for male and finally returning them.

Lazy loading in a nutshell.

Improve this answer
3
  • 1
    this is a really lousy explanation IMHO. Unfortunately I don't quite have enough rep on this particular SE site to down vote it. The real point of lazy evaluation is that none of these results are actually produced until something else is ready to consume them.
    – Alnitak
    Nov 24, 2012 at 21:09
  • My posted answer is saying the exact same thing as your comment.
    – sergserg
    Nov 25, 2012 at 6:18
  • That's a very polite Program Processor.
    – Julian
    Jun 19, 2018 at 15:01
9

Lazy evaluation of expressions will cause the designer of a given piece of code lose control over the sequence their code is executed.

The designer shouldn't care about the order in which expressions are evaluated provided the result is the same. By deferring evaluation, it may be possible to avoid evaluating some expressions altogether, which saves time.

You can see the same idea at work at a lower level: many microprocessors are able to execute instructions out of order, which lets them use their various execution units more efficiently. The key is that they look at dependencies between instructions and avoid reordering where it would change the result.

Improve this answer
7

There are several arguments for lazy evaluation I think are compelling

  1. Modularity With lazy evaluation you can break code up into parts. For example, suppose you have the problem to "find the first ten reciprocals of elements in a list list such that the reciprocals are less than 1." In something like Haskell you can write

    take 10 . filter (<1) . map (1/)

    but this is just incorrect in a strict language, since if you give it [2,3,4,5,6,7,8,9,10,11,12,0] you will be dividing by zero. See sacundim's answer for why this is awesome in practice

  2. More things work Strictly (pun intended) more programs terminate with non strict evaluation than with strict evaluation. If your program terminates with an "eager" evaluation strategy it will terminate with a "lazy" one, but the oposite is not true. You get stuff like infinite data structures (which are really only kinda cool) as specific examples of this phenomenon. More programs work in lazy languages.

  3. Optimality Call-by-need evaluation is asymptotically optimal with respect to time. Although the major lazy languages (that essentially being Haskell and Haskell) don't promise call-by-need, you can more or less expect an optimal cost model. Strictness analysers (and speculative evaluation) keep the overhead down in practice. Space is a more complicated matter.

  4. Forces Purity using lazy evaluation makes dealing with side effects in an undisciplined way a total pain, because as you put it, the programmer loses control. This is a good thing. Referential transparency makes programming, refractoring, and reasoning about programs so much easier. Strict languages just inevitably cave to the pressure of having impure bits--something Haskell and Clean have resisted beautifully. This is not to say that side effects are always evil, but controlling them is so useful that this reason alone is enough to use lazy languages.

Improve this answer
2

Suppose you have a lot of expensive calculations on offer, but don't know which ones will actually be needed, or in which order. You could add a complicated mother-may-i protocol to force the consumer to figure out what's available and trigger calculations that are not yet done. Or you could just provide an interface that acts as though the calculations were all done.

Also, suppose you have an infinite result. The set of all primes for example. It's obvious that you can't calculate the set in advance, so any operation in the domain of primes has to be lazy.

Improve this answer
1

with lazy evaluation you do not lose control about code execution, it is still absolutely deterministic. It is hard to get used with it, though.

lazy evaluation is useful because it is a way of reduction of lambda-term that will terminate in some cases, where eager evaluation will fail, but not vise versa. This includes 1) when you need to link to computation result before you actually execute computation, for example, when you constructs cyclic graph structure, but want to do it in functional style 2) when you define infinite data structure, but function this structure feed to use only part of datastructure.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.