Lazy Evaluation: Haskell vs. Scala

Short talk to introduce the concept of laziness and to show the differences between strict and non-strict languages.

Transcript

1. @filippovitale May 2017 Ann Arbor FP Lazy Evaluation Haskell vs. Scala
2. From Useless to Nirvana
3. Effects Anywhere
4. https://www.youtube.com/watch?v=06x8Wf2r2Mc#t=21m52s Limited Controlled Effects Effects Anywhere
5. https://www.youtube.com/watch?v=06x8Wf2r2Mc#t=21m52s Limited Controlled Effects Effects Anywhere
6. https://www.youtube.com/watch?v=06x8Wf2r2Mc#t=21m52s Limited Controlled Effects Effects Anywhere Nirvana
7. https://www.youtube.com/watch?v=06x8Wf2r2Mc#t=21m52s Useful Limited Controlled Effects Effects Anywhere Nirvana
8. https://www.youtube.com/watch?v=06x8Wf2r2Mc#t=21m52s Useful Useless Limited Controlled Effects Effects Anywhere Nirvana
9. https://www.youtube.com/watch?v=06x8Wf2r2Mc#t=21m52s Useful Useless Limited Controlled Effects Effects Anywhere Nirvana
10. https://www.youtube.com/watch?v=06x8Wf2r2Mc#t=21m52s Useful Useless Limited Controlled Effects Effects Anywhere Nirvana
11. Effects & Evaluation Models
12. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered
13. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered - easy to predict when and in what order things will happen
14. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered - easy to predict when and in what order things will happen - f(release_monkeys(), increment_counter()) - it doesn't matter if `f` uses those results or not
15. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered When “side effects” are allowed, strict evaluation is really what you want.
16. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered Call-by-name - arguments are passed unevaluated
17. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered Call-by-name - arguments are passed unevaluated If an argument is not used in the function body ⇒ the argument is never evaluated If it is used several times ⇒ it is re-evaluated each time it appears
18. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered Call-by-name - arguments are passed unevaluated Call-by-need - arguments are passed unevaluated but an expression is only evaluated once and shared upon subsequent references http://dev.stephendiehl.com/fun/005_evaluation.html
19. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered Call-by-name - arguments are passed unevaluated Call-by-need - arguments are passed unevaluated but an expression is only evaluated once and shared upon subsequent references Lazy evaluation makes it hard to reason about when things will be evaluated Side effects in a lazy language would be extremely unintuitive Lazy evaluation strategy essentially forces you to also choose purity https://en.wikipedia.org/wiki/Evaluation_strategy
20. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered Call-by-name - arguments are passed unevaluated Call-by-need - arguments are passed unevaluated but an expression is only evaluated once and shared upon subsequent references In a “pure“ (effect-free) setting ⇒ this produces the same results as call-by-name https://en.wikipedia.org/wiki/Evaluation_strategy
21. Evaluation Models 3 dominant models: Call-by-value - arguments are evaluated: before a function is entered Call-by-name - arguments are passed unevaluated Call-by-need - arguments are passed unevaluated but an expression is only evaluated once and shared upon subsequent references In a “pure“ (effect-free) setting ⇒ this produces the same results as call-by-name (memoized version of call-by-name) Unevaluated expressions are represented by thunks https://en.wikipedia.org/wiki/Evaluation_strategy
22. Thunks
23. Thunks Unevaluated expressions in heap memory, built to postpone the Evaluation https://takenobu-hs.github.io/downloads/haskell_lazy_evaluation.pdf (pg. 68)
24. Thunks Unevaluated expressions in heap memory, built to postpone the Evaluation https://takenobu-hs.github.io/downloads/haskell_lazy_evaluation.pdf (pg. 68) Suspended Computations
25. Thunks GHC uses Thunks to achieve Laziness
26. GHC uses Thunks to achieve Laziness Thunks http://scalapuzzlers.com/#pzzlr-012 “...but wait, we have laziness in Scala too!”
28. λ> head [1, undefined] 1 scala> ??? scala.NotImplementedError
29. λ> head [1, undefined] 1 λ> rest = drop 1 [1, undefined] λ> :sp rest rest = _
30. λ> head [1, undefined] 1 λ> rest = drop 1 [1, undefined] λ> :sp rest rest = _ λ> print $ head rest [*** Exception: Prelude.undefined
31. λ> head [1, undefined] 1 λ> rest = drop 1 [1, undefined] λ> :sp rest rest = _ λ> print $ head rest [*** Exception: Prelude.undefined scala> val leroyJenkins = List(1, ???) scala.NotImplementedError
32. scala> lazy val a = 1 a: Int = <lazy> scala> lazy val b = ??? b: Nothing = <lazy> scala> List(a, b)
33. scala> lazy val a = 1 a: Int = <lazy> scala> lazy val b = ??? b: Nothing = <lazy> scala> List(a, b) scala.NotImplementedError
34. scala> val ethicList = 1 #:: ??? #:: Stream.empty immutable.Stream[Int] = Stream(1, ?) scala> ethicList.head res0: Int = 1
35. scala> val ethicList = 1 #:: ??? #:: Stream.empty immutable.Stream[Int] = Stream(1, ?) scala> ethicList.head res0: Int = 1 scala> ethicList.length scala.NotImplementedError
36. λ> :set -XMonomorphismRestriction λ> let ethicList = [1, undefined] λ> head ethicList 1 λ> length ethicList 2 λ> :sp ethicList ethicList = [1,_]
37. Thunks Scala is a multi-paradigm language ⇒ Imperative first https://www.quora.com/What-is-the-philosophy-of-functional-programming/answer/Tikhon-Jelvis?srid=Ezlj
38. Thunks Scala is a multi-paradigm language ⇒ Imperative first https://www.quora.com/What-is-the-philosophy-of-functional-programming/answer/Tikhon-Jelvis?srid=Ezlj Does the order in which expressions are evaluated matter?
39. Thunks Haskell is all about evaluation and simplification https://www.quora.com/What-is-the-philosophy-of-functional-programming/answer/Tikhon-Jelvis?srid=Ezlj
40. “Laziness allows you to express your thoughts concisely, letting the compiler figure out how to efficiently execute your code.”
41. @filippovitale May 2017 Ann Arbor FP Thanks!
42. Why make Haskell a non-strict language? - Separation of concerns without time penalty: WYSIWYG - Improved code reuse - Infinite data structures - Can make qualitative improvements to performance - Can hurt performance in some other cases - Makes code simpler - Makes hard problems conceivable - Allows for separation of concerns with regard to generating and processing data - Laziness often introduces an overhead that leads programmers to hunt for places where they can make their code more strict - The real benefit of laziness is in making the right things efficient enough - Lazy evaluation allows us to write more simple, elegant code than we could in a strict environment
43. “Hard work pays off later. Laziness pays off now!” – Steven Wright