Search | Blog | Contact

Imposing the Edges Later 12

Posted by Michael Feathers Sat, 08 Aug 2009 16:12:00 GMT

Here’s what wikipedia has to say about lazy evaluation:

The benefits of lazy evaluation include: performance increases due to avoiding unnecessary calculations, avoiding error conditions in the evaluation of compound expressions, the ability to construct infinite data structures, and the ability to define control structures as regular functions rather than built-in primitives.

It’s all true, but I think it misses a point. One of the nicest things about lazy evaluation is that it enables a different form of abstraction. Take a look at this code. It computes the Mandelbrot Set. There are many ways to code up this algorithm, but the code I just linked to is very typical – it’s a doubly nested loop which iterates over a specific rectangle in the complex plane. It’s hard to see anything that’s awkward about its iteration strategy in a procedural language – the algorithm does require starting and ending points in the plane.

Let’s look at a different way of approaching this. Here’s part of a Mandelbrot Set generator in Haskell: 

mandelbrot :: Double -> [[Int]]
mandelbrot incrementSize =
  [[ escapeIterations $ translate offset . translate (x,y) . mandel
    | x <- increments]
    | y <- increments] 
   where increments = [0.0, incrementSize .. ]

window :: (Int, Int) -> (Int, Int) -> [[a]] -> [[a]]
window (x0, x1) (y0, y1) = range y0 y1 . map (range x0 x1)
  where range m n = take (n-m) . drop m

The interesting bit is the mandelbrot function. It contains a doubly-nested list comprehension which, essentially, mimics the behavior of a doubly-nested loop in the procedural algorithm. However, there is one interesting difference. This list comprehension actually represents the mandelbrot computation across a full quarter of the infinite plane – it goes from zero to infinity in x and y. All we have to do is pass it an increment size and it is configured to create that grid. If we want to zoom in to a particular place in the Mandelbrot Set, we can use the window function like this: 

-- compute the mandelbrot from (10,10) inclusive to
-- (20,20) exclusive with an increment of 0.05 

window (10, 20) (10, 20) $ mandelbrot 0.05

The trick to this code is in window’s range computation. It takes a starting position, an ending position, and a list and it drops all of the elements of the list before the starting position, without evaluating them, and then it takes, from the front of the new list, end - start elements, giving us a sub-range from the original list. When that elements of that sub-list are evaluated, the computation for each point in the window occurs.

This code yields the computation that we want and the neat thing is, we are really only computing the piece we specified with window. We’ve essentially formed a general computation and imposed the edges later.

Looking back now at the imperative mandelbrot code, it’s easy to see that it was, in a way, mixing two concerns. The code which determined the range was mixed with the code which generated the set. Laziness allows us to separate the two concerns.

Note: There are much more direct ways of computing the Mandelbrot Set in Haskell. Here’s one which is particularly brief.

Comments

Leave a response

  1. Avatar
    Cristiano Paris about 4 hours later:

    As a Haskell fan I’m searching for examples where the lazy-by-default approach of Haskell beats other like Python’s iterators… the only one I’m aware of is when you use the “tying-the-knot” techniques which has more to do with performance than with good software engineering practices…

  2. Avatar
    Michael Feathers about 4 hours later:

    Cristiano: Are you talking about this? http://www.haskell.org/haskellwiki/Tying_the_Knot

  3. Avatar
    Dawid about 8 hours later:

    Michael,

    Interesting read, indeed lazy eval is extremely useful for all forms of culling.

    I am personally very interested in picking up a purely functional lazy language to do some experimenting in.

    For my personal enjoyment I am fanatical about seeing my results so I did a lot of hobby coding with C++ and OpenGL.

    Which functional language will be easiest to get me drawing nice graphical things?

    Regards Dawid

  4. Avatar
    Dawid about 8 hours later:

    Sorry wrong email

  5. Avatar
    Michael Feathers about 10 hours later:

    Dawid: I think Clean and Miranda are fully lazy also, but Haskell has the best support and it has a growing community around it.

    If you like graphics work, consider this book: http://www.amazon.com/Haskell-School-Expression-Functional-Programming/dp/0521644089/ It introduces Haskell from the beginning using graphics and gaming examples. You will probably need at least one other introductory Haskell book also to round out the edges.

  6. Avatar
    zorg about 20 hours later:

    > Laziness allows us to separate the two concerns.

    Indeed, see also John Hughes : http://www.cs.chalmers.se/~rjmh/Papers/whyfp.pdf

    “Since this method of evaluation runs f as little as possible, it is called “lazy evaluation”. It makes it practical to modularise a program as a generator which constructs a large number of possible answers, and a selector which chooses the appropriate one. [...] Lazy evaluation is perhaps the most powerful tool for modularisation in the functional programmer’s repertoire.”

  7. Avatar
    Eli Barzilay 1 day later:
    That’s not really a good example. 2.5 questions:
    1. What happens with window (10000010, 10000010) (10000015, 10000015) $ (mandelbrot 1.0)?
    2. If modularization is the ultimate goal here, then why isn’t the final product used as window (10, 20) (10, 20) 0.05 $ mandelbrot?
      • And if you do abstract it as #2, then where did the laziness go?
  8. Avatar
    Michael Feathers 2 days later:

    Eli: That just returns an empty list. Each pair is a range along a dimension, not a coordinate. Are you making a point about the cost of dropping all of those list elements?

    Not quite sure what you are getting at with (2). If it’s the fact that we could pass the computation for single points to iteration code, then I agree that is a different way of factoring this, but it couples the gridding and constraints in the window function.

  9. Avatar
    Eli Barzilay 3 days later:

    Let me clarify the two points I’m making:

    1. While you do save the cost of computing each item, you still need to consider such costs. When I used that expression (with your code as I found on some mailing list) in GHC, it worked for a long time and then stopped with a stack overflow error. In other words, laziness makes certain considerations easy, but overall it’s not a magic solution to all such problems. In addition, laziness brings with it its own share of new problems to consider (as seen in many Haskell programs that use the strict operator and other tricks like CPSing the code).
    1. The second point is similar in nature. Yes, your code shows how you can “separate the two concerns”, but if you do that, then it’s natural to further abstract away the resolution of the grid. When you do that, you will basically get a simple higher order function that consumes the computation function as its input which means that at the API level there is no particular role for laziness. It’s true that in this case laziness will play the same role inside the window function, but that’s pretty minor since it is very straightforward to do the same in a strict language.

    Combine the two points (avoid the cost for dropping items, abstract the resolution), and the code that you end up with is going to be nearly identical in either a lazy or a strict language. That’s why I started by saying that this is not a good example (of using a lazy language).

    Just to balance things, let me point out one big advantage of a lazy language. A feature that is desirable in many languages is list comprehension. Now the thing is how do you deal with list comprehension vs iteration? In Python, for example, if you use for i in range(1,100000000), it will actually (try to) build the huge list and then perform the iteration. As a result, strict languages might have one syntax for lists and another for loops. As another example, in PLT Scheme there is an in-range function that instead of generating a list, it generates a “sequence” value, which can be used in a for expression (and easily convertible into a list, but that’s irrelevant).

    But in a lazy language a list is the same as a specification of an iteration, and the equivalent of such a range function can be used either as a list or as a specification for a loop and you don’t lose any efficiency. The obvious way to see this is to see how the language deals with infinite iterations: in Python range produces a finite range, in PLT Scheme there is a in-naturals function but it produces one of these sequence values rather than a list—but only in Haskell you have the same value representing both an infinite iteration and a list.

  10. Avatar
    Eli Barzilay 3 days later:

    (BTW, gravatar-enabled comments are cute, but the interface should remember my email for later posts…)

  11. Avatar
    rölli 6 days later:

    It’s easier and faster to handle the separation of concerns on a slightly different level: (1) computing mandelbrot value for a single point and (2) computing some value for all points on a grid. This does not even require laziness, just higher order functions.

    let map2d fn xs ys = [[fn x y | x <- xs] | y <- ys]

    map2d mandelpoint [x0, x0+step .. x1] [y0, y0+step .. y1]

    Using an infinite list isn’t a good idea here. Like Eli argued, computing the values far away from origin is going to be super slow due to drop taking O(x0 times y0) time. Some abstraction cost may be acceptable, but jumping from O(1) to O(N times M) is not.

  12. Avatar
    mod converter 6 months later:

    http://www.haskell.org/haskellwiki/Tying_the_Knot should be better knowned.

Comments