### What Makes Haskell Unique (2020 update) * Michael Snoyman * VP of Engineering, FP Complete * Haskell in the City, April 28, 2020 <div><img src="/static/fpcomplete-logo.png" style="border:0;margin:0"></div> --- ## Why uniqueness matters * Programmers have lots of options * Need some filtering mechanism for choosing languages * Need to know what distinguishes programming languages from each other * Today's topic: if I'm going to use Haskell, what makes it special? --- ## First guess: Haskell is functional * Is Haskell the only functional language? * What about Scala, LISP, ML, F#... * What makes a language functional? * Lax definition * First class functions * Higher order functions * Wait... is C functional? __Haskell may be functional, but that doesn't make it unique__ --- ## Let's Describe Haskell * Functional * Statically typed * Pure * Lazy * Strongly typed * Green threads * Native executables * Garbage collected * Immutability <aside class="notes"> <ul> <li>Some features are rare: pure and lazy</li> <li>Some are common</li> <li>No one feature is enough to motivate using Haskell</li> </ul> </aside> --- ## Are those unique? * Not a single one of those features is unique to Haskell! * Very few languages have _any_ one feature that no one else has * Instead, we have to look at the _feature stack_ to understand the whole picture * Haskell is unique because of its _unique combination of features_ --- ## Combination examples * Example: purity + strong typing + functional style leads to: * Easy to write * Easy to read * Easy to modify * Efficient * We'll get to this later * Now: lots of examples! * Different here is usually better, but some downsides --- ## Async I/O and Concurrency What's wrong with this? ``` json1 := httpGet(url1) json2 := httpGet(url2) useJsonBodies(json1, json2) ``` * Hint: it's in the title of this slide * Ties up an entire system thread on blocking I/O calls * We want to be more efficient with resources, so... --- ## Callbacks ``` httpGetA(url1, |json1| => httpGetA(url2, |json2| => useJsonBodies(json1, json2) ) ) ``` * Aka "callback hell" * Lots of techniques to work around it * Promises/futures * Async/await syntax * How does Haskell solve this? --- ## Asynchronous Haskell version ```haskell json1 <- httpGet url1 json2 <- httpGet url2 useJsonBodies json1 json2 ``` * But that looks just like the blocking code! Exactly * Runtime converts to async system calls * Runtime schedules threads * Sleeps when waiting for data * Wake them up when data is available * Not only Haskell: Erlang and Go do this too * Therefore.... --- <img src="/static/unique/deeper.jpg" style="width:100%"> --- ## Concurrency * Why wait for `url1` before starting `url2`? * Need to fork threads, write to mutable variables, do some locking * Or be awesome <div class="fragment"> <pre><code class="haskell">(json1, json2) <- concurrently (httpGet url1) (httpGet url2) useJsonBodies json1 json2</code></pre> <ul> <li>Cheap green thread implementation</li> <li>Wonderful `async` library</li> <li>Builds on the async I/O system</li> </ul> </div> <aside class="notes"> So far: elegant in Haskell, but not terribly difficult in other languages. </aside> --- ## Canceling * We only want one of the responses * Take whichever comes first ``` promise1 := httpGet(url1) promise2 := httpGet(url2) result := newMutex() promise1.andThen(|json1| => result.set(json1) promise2.cancel()) promise2.andThen(|json2| => result.set(json2) promise1.cancel()) useJsonBody(result.get()) ``` --- ## Canceling in Haskell ```haskell eitherJson <- race (httpGet url1) (httpGet url2) case eitherJson of Left json1 -> useJsonBody1 json1 Right json2 -> useJsonBody2 json2 ``` * More than just a well designed API * Depends on asynchronous exceptions * Cancel any other running thread --- ## Not just about I/O * Thread scheduling, sleeping, killing works for CPU bound tasks too! * Don't need to worry about a heavy computation starving other threads * No need to offload your heavy tasks to a different microservice, do it all in Haskell ```haskell let tenSeconds = 10 * 1000 * 1000 timeout tenSeconds expensiveComputation ``` --- ## Summary: concurrency and async I/O <div style="text-align:left"> <h3>Advantages</h3> <ul> <li>Cheap threads</li> <li>Simple API</li> <li>Highly responsive</li> </ul> <h3>Disadvantages</h3> <ul> <li>Complicated runtime system</li> <li>Need to be aware of async exceptions when writing code</li> </ul> </div> --- ## Immutability and purity * Most languages default to mutable values * Haskell differs in two ways: * Immutable by default, explicit mutability * Mutating is an effect, tracked by the type system --- ## Mutable Haskell Impossible ```haskell let mut total = 0 loop i = if i > 1000000 then total else total += i; loop (i + 1) in loop 1 ``` Real and tedious ```haskell total <- newIORef 0 let loop i = if i > 1000000 then readIORef total else do modifyIORef total (+ i) loop (i + 1) loop 1 ``` <aside class="notes"> <ul> <li>In pure code, we cannot create, read, or modify a mutable variable</li> <li>Have to use non-pure code</li> <li>Lots of ceremony for something simple, so don't do that</li> </ul> </aside> --- ## Better Haskell Recursive and immutable, much better! ```haskell let loop i total = if i > 1000000 then total else loop (i + 1) (total + i) in loop 1 0 ``` But why does this matter? --- ## Predicting code behavior Guess the output ``` // scores.txt Alice,32 Bob,55 Charlie,22 func main() { results := readResultsFromFile("results.txt") printScoreRange(results) print("First result was by: " + results[0].name) } func printScoreRange(results: Vector<TestResult>) { ... } ``` <aside class="notes"> <ul> <li>Personally think the phrase "reasoning about code" is overused, but here's a concrete example.</li> <li><i>Describe slide</i></li> <li>What's the expected output? Reasonable to guess...</li> </ul> </aside> --- ## Expected output ``` Lowest: 22 Highest: 55 First result was by: Alice ``` <aside class="notes">But let's see the definition of <code>printScoreRange</code></aside> --- ## What's in printScoreRange? ``` func printScoreRange(results: Vector<TestResult>) { results.sortBy(|result| => result.score) print("Lowest: " + results[0].score) print("Highest: " + results[results.len() - 1].score) } ``` <div class="fragment"> Actual output: <pre>Lowest: 22 Highest: 55 First result was by: Charlie</pre> Non-local changes broke our predicted result </div> <aside class="notes">Our assumptions changed because of mutation</aside> --- <img src="/static/unique/doh.gif"> <aside class="notes"> <ul> <li><code>results</code> from <code>main</code> has been modified</li> <li>Can't just look at <code>main</code> to understand what will happen</li> <li>Need to be aware of mutation happening in the rest of the program</li> </ul> </aside> --- ## Do it in Haskell ```haskell main :: IO () main = do results <- readResultsFromFile "results.txt" printScoreRange results putStrLn $ "First result was by: " ++ name (head results) printScoreRange :: [TestResult] -> IO () printScoreRange results = do let results' = sortBy score results putStrLn $ "Lowest: " ++ show (score (head results')) putStrLn $ "Highest: " ++ show (score (last results')) ``` * Impossible for `printScoreRange` to modify results * `printScoreRange` sorts into a local copy * Have to think about less when writing `main` --- ## Data races ```haskell main :: IO () main = do results <- readResultsFromFile "results.txt" concurrently_ printFirstResult printScoreRange printFirstResult results = putStrLn $ "First result was by: " ++ name (head results) printScoreRange results = do let results' = sortBy score results putStrLn $ "Lowest: " ++ show (score (head results')) putStrLn $ "Highest: " ++ show (score (last results')) ``` * Concurrent data accesses? No problem! * Concurrent data writes? Impossible! * We'll come back to mutable, multithreaded data <aside class="notes">Multithreaded cases is more interesting. We can easily parallelize our previous code.</aside> --- ## Mutability when needed * In place, mutable algorithms can be much faster * Example: sorting a vector with only pure transformations is __slow__ * Haskell's answers: 1. You can still have mutable data structures if you want them, but they're __explicit__ 2. Temporary mutable copy, then freeze it <aside class="notes">Option 1 breaks our guarantees. But still better than other languages: know exactly which data to look at</aside> --- ## Freeze! ```haskell sortMutable :: MutableVector a -> ST (MutableVector a) sortMutable = ... -- normal sorting algorithm sortImmutable :: Vector a -> Vector a sortImmutable orig = runST $ do mutable <- newMutableVector (length orig) copyValues orig mutable sortMutable mutable freeze mutable ``` * `ST` is for temporary, local mutability * Cannot be affected by the outside world, and cannot affect it * Keeps functional guarantee: same input ==> same output --- ## Summary: immutability and purity <div style="text-align:left"> <b>Advantages</b> <ul> <li>Easier to predict code behavior</li> <li>Avoid many cases of data races</li> <li>Functions are more reliable, returning the same output for the same input</li> </ul> <b>Disadvantages</b> <ul> <li>Lots of ceremony if you actually want mutation</li> <li>Some runtime performance hit for mutable algorithms</li> </ul> </div> --- ## Concurrent Mutation What's wrong with this code? ``` runServer (|request| => { from := accounts.lookup(request.from) to := accounts.lookup(request.to) accounts.set(request.from, from - request.amt) accounts.set(request.to, to + request.amt) }) ``` Looks reasonable, but... ```text Thread 1: receive request: Alice gives $10 Thread 2: receive request: Alice receives $10 Thread 1: lookup that Alice has $50 Thread 2: lookup that Alice has $50 Thread 1: set Alice's account to $40 Thread 2: set Alice's account to $60 ``` NOTE: * What if you actually need to mutate values, and from multiple threads? * *Describe slide* * Alice ends up with either $40 or $60 instead of $50 --- ## Locking ``` runServer (|request| => { accounts.lock(request.from) accounts.lock(request.to) // same code as before accounts.unlock(request.from) accounts.unlock(request.to) }) ``` ```text Thread 1: receive request: $50 from Alice to Bob Thread 2: receive request: $50 from Bob to Alice Thread 1: lock Alice Thread 2: lock Bob Thread 1: try to lock Bob, but can't, so wait Thread 2: try to lock Alice, but can't, so wait ``` __Deadlock!__ NOTE: Typical solution to this is to use locking, but it leads to other problems --- ## Software Transactional Memory ```haskell runServer $ \request -> atomically $ do let fromVar = lookup (from request) accounts toVar = lookup (to request) accounts origFrom <- readTVar fromVar origTo <- readTVar toVar writeTVar fromVar (origFrom - amt request) writeTVar toVar (origTo + amt request) ``` * Looks like it has a race condition * But STM ensures transactions are atomic * No explicit locking required * `TVar` is an example of explicit mutation * Alternatives: `IORef`, `MVar` NOTE: * There are helper functions to make this shorter * Want to make a point with the longer code * STM will automatically retry when needed --- ## The role of purity STM retries if another thread modifies variables. If I can retry: how many Bitcoins will I buy? ```haskell atomically $ do buyBitcoins 3 -- side effects on my bank account modifyTVar myBitcoinCount (+ 3) ``` * Trick question! Code doesn't compile * `atomically` only allows side effects on `TVar`s * Other side effects (like my bank account) are disallowed * Safe for runtime to retry thanks to purity NOTE: * `buyBitcoins` needs to go to an exchange and spend $100,000 * Due to retry, this code could spend $10m * This is where purity steps in --- ## Summary of STM <div style="text-align:left"> <h3>Advantages</h3> <ul> <li>Makes concurrent data modification much easier</li> <li>Bypass many race conditions and deadlocks</li> </ul> <h3>Disadvantages</h3> <ul> <li>Depends on purity to work at all</li> <li>Not really a disadvantage, you're already stuck with purity in Haskell</li> <li>Not really any other disadvantages, so just use it!</li> </ul> </div> --- ## Laziness *A double edged sword* Let's revisit our previous summing example ```haskell let loop i total = if i > 1000000 then total else loop (i + 1) (total + i) in loop 1 0 ``` There are two problems with this code: 1. There's a major performance bug in it 2. It's much more cumbersome than it should be NOTE: Kind of cheeky to hold off on laziness this long --- ## Space leaks Consider `let foo = 1 + 2` * `foo` isn't `3`, it's an instruction for how to create `3` * `foo` is a _thunk_ until it's evaluated * Storing thunks is more expensive than simple types like `Int`s * Which values are evaluated in our `loop`? ```haskell let loop i total = if i > 1000000 then total else loop (i + 1) (total + i) in loop 1 0 ``` NOTE: * The bane of laziness is space leaks, which you may have hard about. Need to understand how laziness is implemented. * Explain why `i` is forced and `total` is not * Builds a tree, lots of CPU and memory pressure --- ## Explicit strictness Need to tell Haskell compiler to evaluate `total`. Bang! ```haskell let loop i !total = if i > 1000000 then total else loop (i + 1) (total + i) in loop 1 0 ``` * Needing to do this is a downside of Haskell's laziness * But do we get any benefits in return? NOTE: * Can be explicit about what needs to be evaluated * This is one approach, there are others * Just added a `!` --- ## Looping (1) Let's write our `loop` in an imperative language: ``` total := 0 for(i := 1; i <= 1000000; i++) { total += i } ``` Or just the evens ``` total := 0 for(i := 1; i <= 1000000; i++) { if (isEven(i)) { total += i } } ``` --- ## Looping (2) Now add up the values modulus 13 (for some weird reason) ``` total := 0 for(i := 1; i <= 1000000; i++) { if (isEven(i)) { total += i % 13 } } ``` * Each modification is fine * Getting harder to see the forest for the trees * If our logic was more complicated, code reuse would be an issue NOTE: Example of more complicated use case, writing a lookahead parser --- ## Some better Haskell Our original recursive implementation sucked ```haskell let loop i !total = if i > 1000000 then total else loop (i + 1) (total + i) in loop 1 0 ``` <div class="fragment"> <p>But this is great</p> <pre><code class="haskell">fold' (+) 0 [1..1000000]</code></pre> <ul> <li>Doesn't it allocate 8mb of ints?</li> <li>Nope, laziness!</li> <li>Just a thunk telling us how to get the rest of the list</li> </ul> </div> --- ## Composable Haskell Just the evens? ```haskell sum (filter even [1..1000000]) ``` Modulus 13? ```haskell sum (map (`mod` 13) (filter even [1..1000000])) ``` * Easy and natural to compose functions in a lazy context * Avoids doing unnecessary work or using too much memory NOTE: * Never using more than a few machine words * Other GHC optimizations avoid allocating any thunks * Not covering that today * Mixed bag, but functional+lazy=declarative, performant --- ## Short circuiting for free In most languages, `&&` and `||` short circuit ``` foo() && bar() ``` * `bar` only called if `foo` returns `true` In Haskell: we get that for free from laziness: ```haskell False && _ = False True && x = x True || _ = True False || x = x ``` See also: `and`, `or`, `all`, `any` --- ### Other downsides * Laziness means an exception can be hiding in any thunk * Aka partial functions: `head []` * Also, some inefficient functions still available, `foldl` vs `foldl'` NOTE: * Generally partial functions are frowned upon * But they're still in the language --- ## Summary of laziness <div style="text-align:left"> <h3>Advantages</h3> <ul> <li>More composable code</li> <li>Get efficient results with high level code</li> <li>Short-circuiting no longer a special case</li> </ul> <h3>Disadvantages</h3> <ul> <li>Need to worry about space leaks</li> <li>Exceptions can be hiding in many places</li> <li>Bad functions still linger</li> </ul> </div> --- ## Side note; other languages * Laziness is very similar to features in other languages * Python generators * Rust iterators * In Haskell, it's far more prevalent since it affects how all code works * However, you can get a lot of the benefits of Haskell with these techniques --- ## Other examples * Too much to talk about in 40 minutes! * Two other topics I wanted to touch on --- ## Parser (and other) DSLs * Operator overloading! * Abstractions like `Alternative` a natural fit * `parseXMLElement <|> parseXMLText`. * Able to reuse huge number of existing library functions, * `optional`, `many` * Also: `traverse`, `foldMap`, etc * General purpose `do`-notation is great --- ## Parser example ```haskell data Time = Time Hour Minutes Seconds (Maybe AmPm) data AmPm = Am | Pm parseAmPm :: Parser Time parseAmPm = Time <$> decimal <*> (":" *> decimal) <*> (":" *> decimal) <*> optional (("AM" $> Am) <|> ("PM" $> Pm)) ``` c/o [@queertypes](https://twitter.com/queertypes/status/941064338848100352) --- ## Advanced techniques * Free monads * Monad transformer stacks * Lens, conduit, pipes, ... * Lots of ways to do things in Haskell! * It's a plus and a minus * Don't overcomplicate your code! * Recommendation: choose a useful subset of Haskell and its libraries, and define some best practices * I prefer my Haskell to be boring --- ## Conclusion * Haskell combines a lot of uncommon features * Very few of those features are unique * Combining those features allows you to write code very differently than in other languages * If you want readable, robust, easy to maintain code: I think it's a great choice * Be aware of the sharp edges: they do exist! --- ## Questions? Thanks everyone!