begriffs

Thinking with Laziness

June 17, 2015

Tikhon Jelvis gave this talk at Bayhac 2015. He describes how lazy evaluation supports deeper kinds of program modularity and suggests we embrace it for what it really is. [slides]

Summary

  • Stop thinking of Haskell like a strict language which happens to be lazy
  • Laziness ia a new sort of modularity that we’re not used to from other languages
  • It separates the definition of something from how it gets evaluated
  • It lets us think of control flow the way we would think of data structures
  • Deal with arbitrary precision (like vector graphics vs raster graphics)
  • Shortcuts for free — take 5 $ sort xs actually stops the sorting after five elements are found. No break statement needed inside the sort function.
  • Another example: alpha beta pruning game trees. We can use a simple tree structure and just choose not to evaluate branches and that does pruning.
  • In Haskell lists stand in for loops. Control flow can be manipulated as data.
  • Lazy structures don’t necessarily need to fully exist in memory.
  • Convenient nondeterministic programming
    • variables can take many combinations of values from which we can later choose
    • map coloring example
  • Lazy data structures is like precision on demand
    • it’s like the advantage of vector graphics over raster
    • exact real arithmetic
    • infinite quadtrees
  • Laziness allows memoization below the level of abstraction
    • we can rely on it without having to do it ourselves
    • similar to garbage collection in this way, improves modularity
  • Some people mistakenly believe Haskell does memoization automatically everywhere
  • Dynamic programming
    • no need to initialize everything or worry about reading one subproblem too early
    • just declare your array as containing all subproblems and the fact that it’s lazy ensures everything is evaluated in the correct order and at most once
  • We saw four perspectives that turned out to be interrelated: modularity, control, precision, and memorization
  • Q&A