How is lazy evaluation in Haskell useful?

http://arstechnica.com/information-technology/2012/11/how-is-lazy-evaluation-in-haskell-useful/

by Garbage • 14 years ago

60 41 14 years ago

arstechnica.com

Tyr42• 14 years ago

Might as well read the programmers.stackexchange post [1], it's better formatted.

[1] http://programmers.stackexchange.com/questions/163985/why-is...

Evbn4• 14 years ago

And Daniel Wagner links to a very good answer on another question: http://stackoverflow.com/questions/7868507/non-trivial-lazy-...

cageface• 14 years ago

I'm not so sure I'm convinced by the argument for modularity.

Maybe Haskell makes it easier to write generators of possibly infinite sequences but people use the producer-consumer model all the time in other langages to explore potentially large solution spaces generated on demand.

btilly2• 14 years ago

That would be the implementing your own version of laziness part of the modularity argument.

In a language like Haskell you never have to do that. Ever. Because the language is lazy.

hythloday2• 14 years ago

"Implementing your own version of laziness" makes it sound error-prone and difficult. In fact it's this pattern:

  def move(board, position, player):
    """
      board is a 11-character string which is 3 lengths of 3 of the characters
        X, O or _, separated by newlines
      turn is either X or O, depending on who moves
    """
    return board[:position] + player + board[position+1:]

  def getNextStates(board, player):
    spaces = [ i for i,c in enumerate(board) if c == '_' ]
    return [ move(board, i, player) for i in spaces ]

  >>> print board
  X_O
  _OX
  X_O 
  
  >>> for state in getNextStates(board, 'O'):
  ...   print state
  ...   print
  ... 
  XOO
  _OX
  X_O
 
  X_O
  OOX
  X_O
  
  X_O
  _OX
  XOO

I doubt most programmers exposed only to imperative programming would even notice that there was a pattern in what they were implementing, let alone identify it as laziness.

surrealize• 14 years ago

One of the things haskell can do with lazy sequences is fuse away intermediate data structures, e.g. take

  map f . map g

and substitute

  map (f . g)

automatically (as a compiler optimization). I don't think that's a safe transformation in general in a non-pure language; not sure about a pure strict language.

ibotty• 14 years ago

yes, that's possible in a pure referential transparent language (strict or lazy is not the point).

bhickey• 14 years ago

    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.

Isn't referential transparency a consequence of purity, not laziness?

Edit: While I believe the quote is saying (albeit in a peculiar way) that lazy languages must be referentially transparent, I don't see how this particular response was arguing in favor of laziness. Referential transparency is great as an optimization enabler, which provides one compelling case for purity.

Meanwhile I'm working on a nascent project to develop an eager, pure language that targets LLVM.

benbataille• 14 years ago

>I don't see how this particular response was arguing in favor of laziness.

In a referentially transparent language, you don't care about order of evaluation because whatever the order you will always end up with exactly the same result. Thus, losing control of it through laziness doesn't matter.

However, IMHO, the initial argument is kind of wrong. Laziness doesn't really make you lose control of order of evaluation. You know when expressions are going to be evaluated : when they are going to be needed. Obviously, when you use a lot of abstraction you didn't write like in Haskell, it becomes tricky. But, if you perfectly know how your data structures are processed by the compiler, you can safely use side effects with laziness. Not that you should, but you can.

ky33• 14 years ago

RT needs to be seen in the context of reasoning about programs.

Suppose we want to define a constant function f such that f x = 0. Under strict semantics in a total language, you're fine. Under strict semantics in a partial language f undefined blows up. So constant functions, the simplest kind possible, don't even exist! OMGWTFBBQ!

You can still reason about programs, but at a very low-level, i.e. on operational semantics. RT is high-level reasoning. Math, which does have constant functions, seems pretty successful, so we'd like a slice of that cake, please.

rpearl• 14 years ago

http://augustss.blogspot.com/2011/05/more-points-for-lazy-ev... is a very good discussion of why laziness has some nice semantic properties from the theory point of view.

And the post it is responding to, https://existentialtype.wordpress.com/2011/04/24/the-real-po... makes some interesting points against it as well.

cpdean• 14 years ago

Whoa, did they just lift content directly off Stack?

I guess it's appropriate for an article on laziness.

nickbarnwell• 14 years ago

No; they have an agreement with StackExchange to allow for republishing of the content (check the byline).

Moto7451• 14 years ago

Actually I think it has more to do with content on Stack sites being freely available under a creative commons license.

microtonal2• 14 years ago

Note that there is a elephant in the room that the answers fail to reflect on. The questioner asks:

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?

While it is true that this will not lead to unexpected computations in a pure language, it may lead to excessive memory use. For instance, consider the definition of Data.Map.Lazy.Map:

http://www.haskell.org/ghc/docs/latest/html/libraries/contai...

The Map data type is spine-strict and key strict in Weak Head Normal Form (WHNF). However, it is not strict in its values, and values may be thunks (unevaluated expressions). This may result the memory usage of the values to be much larger than when they are fully evaluated.

There is now also a variant of Data.Map that is value-strict, but only in WHNF, so only the outermost constructors may have been evaluated, and you'd have to evaluate the data further to have thunks replaced by actual values.

Thunk leaks are something that every new Haskell programmer will bump into and is something that makes programs less predictable if you are not yet comfortably reason about strictness and laziness.

Edward Yang wrote a nice explanation of such leaks:

http://blog.ezyang.com/2011/05/anatomy-of-a-thunk-leak/

I very much enjoy Haskell, but I think that the benefits of laziness are much overstated. Strict languages are often easier to reason about and laziness can often be emulated when necessary. That said, Haskell has many other attractions ;).

chimeracoder2• 14 years ago

> laziness can often be emulated when necessary.

I haven't used Haskell enough to say that this is anything more than speculation, but I would imagine that the converse would be true. Python is an excessively eager-evaluating language[1], and trying to emulate lazy evaluation in Python requires enough back-bending that it probably wastes more time/memory than it saves.

In Haskell, since you have guarantees about monadic purity, I would speculate that an alternative runtime could use a secondary thread to 'walk' the tree and evaluate the thunks whenever resources are being under-utilized (or when memory is tight). Perhaps that would be effective enough to be a net improvement?

microtonal2• 14 years ago

trying to emulate lazy evaluation in Python requires enough back-bending that it probably wastes more time/memory than it saves.

Wholesale, yes. But one could e.g. use a generator in Python to emulate a infinite list.

I would speculate that an alternative runtime could use a secondary thread to 'walk' the tree and evaluate the thunks whenever resources are being under-utilized (or when memory is tight).

But the thunks could also evaluate to large or infinite data structures, leading to resource starvation when such a strategy is followed.

IMO if the language uses a lazy evaluation regime, the programmer should decide on where strictness can be applied. It's fairly easy to enforce strict evaluation in Haskell via bang patterns, seq, or deepseq. It's reasoning about laziness that is difficult for newcomers.

allertonm2• 14 years ago

I guess the benefit of lazy by default is that (given Haskell is an experiment in purity) it sets the expectation that things will be side-effect free by default.

Were that not a design criteria it might have been better to make things strict by default and have a "lazy" monad rather than do lazy by default and use monads for all the side effecting stuff.

ky33• 14 years ago

Total functions embed into partial ones, which is why we have a partiality monad. The opposite arrow doesn't exist, which is why we don't have a totality monad.

Now lazy and eager are properly adjectives that govern beta reduction, that is, the interaction between a function and its argument.

The short of it is that neither an eager nor a lazy monad makes any sense.

(Heh, I'm totally citing this in the monads class I teach as proof of why unpacking monads starting from functors is a win.)

Symmetry• 14 years ago

I feel like I should point out that we have no guarantee when and where an expression will be evaluated is also true in languages like C, to an extent. The compiler is free to re-schedule operations that don't have a side effect, just as in Haskell - it's just that this happens less since so many actions could potentially have side effects in C.

ky33• 14 years ago

> 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?

s/an expression will be evaluated/commands are fired/

reveals the latent imperative mindset.

FP programs are designed by laying out, not unlike how train tracks are laid out, transformations from input to output. Some of these transformations are too complex to get right all at once, so they get broken down into smaller ones which are then composed together. (Obviously, there are other reasons why composition is a win.)

An FP program "works as intended" because the transformations from input to output are correct. In high-end software some, possibly even all of it are rigorously proven correct using mathematical reasoning.

The two main ways of correctness reasoning about transformations is with strict or with non-strict semantics. Time/space usage, i.e. the performance characteristics, is treated as an operational concern. That's when the nitty-gritty of eager and lazy evaluation come into play.

The bottom line is that if all time is spent stressing over evaluation, you're optimizing prematurely.

yason2• 14 years ago

In my experience, I tend to be of the opinion that lazy, immutable data structures with eager evaluation bring you most of the benefits of lazy evaluation with the control of eager evaluation.

Clojure is an example of that. You can plant printfs there and it just works, but you can also set it to do huge amount of processing on huge amount of data and eventually just consume and crunch small part of it.

tome• 14 years ago

What are "lazy, immutable datastructures with eager evaluation"?

chipsy• 14 years ago

A lazy data structure exposes access methods that exhibit lazy-evaluator behavior. For example, you have a "rectangle" structure that contains position, width and height, and the structure has methods that let you apply matrix transformations to scale, rotate, and skew the rectangle's corners. The matrix methods perform the computation, and then cache that result in case it's needed again.

yason2• 14 years ago

  (defn infinite-series []
    (let [x (atom 0)]
      (repeatedly (fn [] (swap! x inc)))))

  (take 10 (map #(* 10 %) (infinite-series)))

The arguments of 'take' and 'map' are eagerly evaluated. The sequence returned by 'infinite-series' is immutable and infinite and lazy, and as returned it actually gets passed directly to the 'map' function which actually operates on it. Finally, we use 'take' to extract the first ten items and thanks to the data structure being lazy, this will actually limit the execution so that only ten items are ever generated and multiplied by 10.

The code would look conceptually the same in Haskell but if the 10 in 'take' was a variable and could occasionally be 0, in Clojure you can be sure that a debug (println) places in the 'infinite-series' function would actually get executed. Haskell would probably defer the execution forever since "take 0" is a no-op. Yet Clojure doesn't generate or multiply anything if we called (take 0 ...).

gtani• 14 years ago

Let me point out that the haskell / GHC toolset is broad and deep and constantly being expanded, and also the most common causes of space leaks are becoming documented (the wiki and many stackoverflow threads. Tools:

ghc-vis, to visualize sharing: http://felsin9.de/nnis/ghc-vis/

--------------

profilers and analysis of space/time behavior of data structures

http://www.haskell.org/ghc/docs/latest/html/users_guide/prof...

http://blog.ezyang.com/2011/05/space-leak-zoo/

http://lambdamaphone.blogspot.com/2011/02/automatic-asymptot...

--------------

and, sort of a stacktrace:

http://jpmoresmau.blogspot.com/2012/10/using-ghci-history-in...

https://plus.google.com/u/0/107890464054636586545/posts/CfKE...

http://hackage.haskell.org/trac/ghc/wiki/Status/May12

-----------

(not related to time/space reasoning, but a common pea under the mattress): in 7.4 you don't need top level "let" in GHCi

http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/inter...

cousin_it2• 14 years ago

1) Is there a problem that provably requires asymptotically more memory in a lazy language than in a strict one?

2) Is there a problem that provably requires asymptotically more time in a pure language than in an impure one?

Evbn4• 14 years ago

Any impure algorithm on a system that uses pointers can be made pure with I think log(n) oberhead, which in practice is usually equivalent to a constant factor. But in the real world constant factors matter, in time as well as space (cache locality to do work in chip instead of ram instead of disk instead of tape)

gizmo686• 14 years ago

Your answer sounds like the solution to the mutable data question, not the pure/impure question. For the question of memory usage on a lazy language vs a strict language, there is no asymptotic difference. The strict program can be viewed as a series of commands, each modifying the state of the program. For example, consider the following code: int double(int x){ int ans=x; ans=ans2; return ans; } The above code can be viewed as: Input state | execute(ans=x) | execute(ans=2x) | execute(return ans) where execute takes as an input both the state of the program, and a command. (As an aside, this is the approach of piping a state variable across functions is how Haskell handles IO)

The above code can also be viewed as: Input | A(x) | B(x) | C(x)

Evaluating this lazily will get you: C . B . A . Input

What the program wants to return is the final output of C. When the program tries to return C, it will go down the chain of expressions it must evaluate until it reaches one that it can, in this case A(Input). Once A(Input) is calculated, we no longer need Input it memory, so it can be garbage collected. At this point, the program is: C . B . Input' Because Input' is the same size in memory as Input, we are, at this point, using no more memory than the strict version of the program. We can continue this argument until we eventually arrive at the final state, in which we have our answer.

With this, we can see that any strictly evaluated program can be done lazily with no more than twice the memory requirements (there is a point where we need both Input, and Input'), which from an asymptotic standpoint is equvilent.

How is lazy evaluation in Haskell useful?

Related Stories