Stack Safety for Free

Transcript

1. Stack Safety for Free Phil Freeman paf31/codemesh2016
2. Hello! I'm Phil, I write Haskell and PureScript paf31 on Twitter/GitHub
3. Motivation
4. Motivation Consider this Haskell function: replicateM_ :: Monad m => Int -> m a -> m () replicateM_ 0 _ = return () replicateM_ n x = x >> replicateM_ (n - 1) x
5. Motivation We can test this using GHC: main = print $ replicateM_ 100000000 (Just ()) This gets compiled to a tight loop: $ ./test +RTS -s Just () 52,104 bytes allocated in the heap MUT time 0.007s ( 0.008s elapsed) GC time 0.000s ( 0.001s elapsed) %GC time 2.0% (10.5% elapsed)
6. Motivation But how would we write this function in a strict language like PureScript? PureScript a strict Haskell-like language compiling to JS features type classes, HKP see purescript.org
7. Motivation In PureScript: replicateM_ :: ∀ m a. Monad m => Int -> m a -> m Unit replicateM_ 0 _ = pure unit replicateM_ n x = x *> replicateM_ (n - 1) x This fails quickly with RangeError: Maximum call stack size exceeded (demo)
8. Tail Recursion
9. Tail Recursion Recap: A tail recursive function can either return a value or loop, modifying some function arguments at each step. The compiler can turn such a function into a loop.
10. Tail Recursion For example: replicateM_ :: ∀ m a. Monad m => Int -> m a -> m Unit replicateM_ n x = loop (pure unit) n where loop :: m Unit -> Int -> m Unit loop acc 0 = acc loop acc n = loop (x *> acc) (n - 1)
11. Tail Recursion This works for some monads, like Maybe : > replicateM_ 1000000 (Just 42) Just unit but still fails for others, like Eff : > replicateM_ 1000000 (log "testing") RangeError: Maximum call stack size exceeded
12. Tail Recursion Now let's reify those constraints as a data structure: data Step a b = Done b | Loop a A tail recursive function can either return a value or loop, modifying some function arguments “ “
13. Tail Recursion Now we can write a general-purpose tail-recursive function of one argument: tailRec :: ∀ a b. (a -> Step a b) -> a -> b This can be used to write variants with multiple arguments: tailRec2 :: ∀ a b c . (a -> b -> Step { fst :: a, snd :: b } c) -> a -> b -> c
14. Tail Recursion This is enough to reimplement replicateM_ : replicateM_ :: ∀ m a. Monad m => Int -> m a -> m Unit replicateM_ n x = tailRec2 loop (pure unit) n where loop :: m Unit -> Int -> Step { fst :: m Unit, snd :: Int } (m Unit) loop acc 0 = Done acc loop acc n = Loop { fst: x *> acc, snd: n - 1 } Of course, this doesn't solve the problem, yet
15. Tail-Recursive Monads
16. Tail-Recursive Monads The trick: Generalize tailRec to monadic tail recursion using a new type class class Monad m <= MonadRec m where tailRecM :: (a -> m (Step a b)) -> a -> m b What should the laws be?
17. Tail-Recursive Monads tailRecM should be equivalent to the default de nition: tailRecM f a = step <- f a case step of Done b -> pure b Loop a1 -> tailRecM f a1 However, we can provide a more ef cient implemenation!
18. Tail-Recursive Monads Example: ExceptT newtype ExceptT e m a = ExceptT (m (Either e a)) instance MonadRec m => MonadRec (ExceptT e m) where tailRecM f = ExceptT <<< tailRecM \a -> case f a of ExceptT m -> m >>= \m' -> pure case m' of Left e -> Done (Left e) Right (Loop a1) -> Loop a1 Right (Done b) -> Done (Right b)
19. Tail-Recursive Monads More Examples Identity StateT s WriterT w ReaderT r Eff eff Aff eff
20. Tail-Recursive Monads We can x replicateM_ by requiring MonadRec : replicateM_ :: ∀ m a. MonadRec m => Int -> m a -> m Unit replicateM_ n x = tailRecM loop n where loop :: Int -> m (Step Int Unit) loop 0 = pure (Done unit) loop n = x $> Loop (n - 1) This is stack-safe for any law-abiding MonadRec instance! We can also implement other functions like mapM and foldM .
21. Tail-Recursive Monads Taxonomy of Recursion Schemes StateT : Additional accumulator WriterT : Tail-call modulo "cons" ExceptT : Tail-call with abort
22. Applications
23. 1. Free Monads
24. Free Monads The free monad for a functor f data Free f a = Pure a | Impure (f (Free f a)) instance monadFree :: Functor f => Monad (Free f) liftFree :: ∀ f a. Functor f => f a -> Free f a liftFree fa = Impure (fmap Pure fa) represents sequences of instructions de ned by f .
25. Free Monads Example: data DatabaseF a = Insert Key Value a | Select Key (Maybe Value -> a) type Database = Free DatabaseF insert :: Key -> Value -> Database Unit insert k v = liftFree (Insert k v unit) select :: Key -> Database (Maybe Value) select k = liftFree (Select k id)
26. Free Monads Interpretation: runFree :: ∀ m f a . Monad m => (f (Free f a) -> m (Free f a)) -> Free f a -> m a runFree f (Pure a) = pure a runFree f (Impure xs) = do next <- f xs runFree f next
27. Free Monads Testing type Test = State (Map Key Value) testDB :: ∀ a. Database a -> Test a testDB = runFree go where go :: DatabaseF (Database a) -> Test (Database a) go (Insert k v next) = do modify (insert k v) next go (Select k next) = do v <- gets (lookup k) next v
28. Free Monads Problem: runFree uses monadic recursion. We cannot interpret deep or in nite computations without the risk of blowing the stack.
29. Free Monads Solution: Instead we use runFree :: ∀ m f a . MonadRec m => (f (Free f a) -> m (Free f a)) -> Free f a -> m a runFree can be written using tailRecM directly and uses a constant amount of stack.
30. 2. Free Monad Transformers
31. Free Monad Transformers The free monad transformer: newtype FreeT f m a = FreeT (m (Either a (f (FreeT f m a)))) interleaves effects from the base monad m .
32. Free Monad Transformers The previous technique extends to the free monad transformer: runFreeT :: ∀ m f a . MonadRec m => (f (FreeT f m a) -> m (FreeT f m a)) -> FreeT f m a -> m a (see the paper)
33. 3. Coroutines
34. Coroutines The free monad transformer gives a nice (safe!) model for coroutines over some base monad. For example: data Emit o a = Emit o a type Producer o = FreeT (Emit o) Producer _ (Aff _) is useful for modelling asynchronous generators
35. Coroutines Consumers: data Await i a = Await (i -> a) type Consumer i = FreeT (Consumer i) Consumer _ (Aff _) is useful for modelling asynchronous enumerators E.g. chunked handling of HTTP responses
36. Coroutines Fusion type Fuse f g h = ∀ a b c . (a -> b -> c) -> f a -> g b -> h c fuse :: ∀ f g h m a . (Functor f, Functor g, Functor h, MonadRec m) => Fuse f g h -> FreeT f m a -> FreeT g m a -> FreeT h m a
37. Coroutines Producer - Producer Fuse (Emit o1) (Emit o2) (Emit (Tuple o1 o2)) Consumer - Consumer Fuse (Await i1) (Await i2) (Await (Tuple i1 i2)) Producer - Consumer Fuse (Emit o) (Await o) Identity
38. Coroutines Applications: Websockets File I/O AJAX Cooperative multitasking (Demo)
39. Conclusion
40. Conclusion MonadRec can make a variety of tasks safe in a strict language like PureScript We trade off some instances for a safe implementation MonadRec has been implemented in PureScript, Scalaz, cats and fantasy-land. Check out the paper: functorial.com/stack-safety-for-free/index.pdf
41. Thanks!