scala.bythebay.io: Kelley Robinson, Why the Free Monad Isn't Free
Recording: scala.bythebay.io: Kelley Robinson, Why the Free Monad Isn't Free
so this all kind of started a few years ago when I was working at a company our back-end was written in Scala there was so many issues with it we decided to just completely overhaul the architecture but we were gonna do it right we were gonna be functional we added Scala Zed we added the state monad it was gonna be beautiful until we started seeing stack overflow errors and this was just in testing we hadn't even deployed anything to production yet so my coworker says let's just trampoline it and add the free monad and that was kind of my reaction to that comment I didn't know what he meant that was the first time I'd heard of the free monad and then a couple years later I'm at a different company and a different Scala code base there was this one application no one wanted to touch I finally looked at the code and I understood why we were using the free monad to manage a very simple datastore application the purpose of the application was really straightforward but the code made it look really complicated this might sound familiar so I wanted to understand if I was justified and being annoyed with that application so decided to figure out what the heck of free monad is so you don't have to my name is Kelly Robinson and I'm an engineering team lead here in San Francisco at a company called share through and today I'm going to talk to you about why the free monad isn't free so before we talk about free monads we're gonna talk about monads and we're gonna explain that using ma nodes and monads this explanation is going to be a little bit shorter than I would like because of the time constraints there's a talk later this afternoon that's gonna go into some of this stuff in detail I hope if you are not familiar with these concepts which don't be afraid if you're not that's fine go to that talk and hopefully you can get a better understanding all right we have all heard monads or simply mono AIDS in the end category of endo functors but what does that mean so we're gonna start by talking about mono AIDS mono aids are an idea that comes from category theory they come from math these are ideas that are not implemented in the Scala language but we can represent them using Scala so in mono II does some type that is going to have a couple of methods on it it's going to have an append method and that basically means that you're going to take two of the type put it together to create one of the type and then you're gonna have some method usually called identity that's going to be a no op or zero it's gonna have no effect when used with the append method so we can let a couple examples of this string concatenation is a really good example of a mono ID you can take two strings put them together and you have another string and then for the identity value to have no effect you use the empty string string Mahanoy great example of a mono it is integer addition so if you take two integers and put them together you have another instance of an integer and then for the identity value to have no effect you set it to zero so it's like a super super brief introduction to mono AIDS and that brings us to talking about monads we can use mono it's kind of you build our understanding of monads so I really like this quote from a stack overflow post that says the term monads a bit vacuous if you're not a mathematician an alternative term is computation builder so like mono AIDS you build computations using that append method you can do something similar with monads and this helps my argument that you don't need to be a mathematician to understand this stuff these are ideas these are ideas that we can use in our programs to make ourselves more productive so in Scala this is kind of what a monad is gonna look like omona is going to be some collection some family of types that's going to have a couple of methods defined on it it's going to have a pure method and that's going to lift the value into the container into that context creating the monad and then it's also going to have the flat matte method and this is going to apply a function to every value inside of the container and then flatten a context so we can look at an example of what a monad is using Scala's option and so some of you may know that option is a monad you might not really know what that means and for very simplistic overview this is how we could represent option as a monad so it's going to have a pure method I talked about that lifting into the context it's wrapping a value in the sum type and then you also have the flat matte method you can see here how our pattern matching on the different contexts to apply a function to the contained value if there's something there and then flattening that context we don't wrap it in another Sun we want it to come out flattened at the end of the day so monads are useful because they allow us to compose functions for values in a context and the reason that this is useful is because at the end of the day when you're building programs when you're making tons of HTTP calls creating futures of requests you don't want to be left with a future of a future a future of a future of a future you just want to be left with a future of your result and that's the type of thing that we use monads for in our programs okay that was like the briefest introduction to monads ever let's talk about what it means to be free now so we use the word free to me a few things let's clarify what I mean when I'm talking about free and when we talk about free in the context of free monads we're talking about free as unrestricted not free as in zero cost free to be interpreted in any way that's what we want to focus on or if you're a fan of Richard Stallman you can think of this as free as in freedom and not free as in beer so let's revisit kind of our building blocks let's talk about what it would mean to be a free mano aid so quick refresher we have monolids the append method and the identity method in order for a monoid to be free we can't lose any input data while we're doing that append step we want to keep it free from interpretation so let's look at an example of what this would mean so a list concatenation could be a really good example of a free mono because when you take two lists and shove them together you're doing just that you're just shoving the data together and creating a new list that has no interpretation of the underlying type you're not losing input information about what came into the append function you're shoving the data together and it's important here that in Scala we define this with a generic type because we don't know what is contained in that it could be enlist another list it could be an INT a string a function other complex types we don't know and that means that we can't make any interpretation about the underlying data keeps it free from interpretation and that's why this mono ID is free in contrast something like an enduring is not free because when you take two teachers and put them together you're losing information about the input types the input data you don't know what those inputs were to the existing result and so that's why this isn't free it's an explicit interpretation of the integer type and that brings us to free monads so the important thing that we want to remember here is that we can't lose any data during that upend that flat map that compositions step we can't lose any data about the input to those functions so how are we gonna build up this idea in Scala we can do this using some constructors that we define ourselves so we can start with some trait free I'm sure Adrian has feelings about using traits for this but we can start with some trait free add a class return that's going to be used in our free and our pair of functions and to indicate that there's no more computation and then we'll add a class suspend and this is going to be used to indicate we're going to suspend the computation and we're ready to process and do some interpretation at a later point in time and then we'll add a class flat map and this is going to be used to chain methods together to keep the data free to keep the information about the inputs as we're building up our structures and this looks a lot like the flat map method signature and that's gonna help us out so then we're gonna add some functions to help with our composition this will be help some of the syntactic sugar that we loved in Scala and this will allow us to chain these methods together but again we're not gonna evaluate anything doing this we just want to build up some ideas about what we're talking about doing and so let's look at an example of what this would look like so if we build a free monad for actions on a to-do list we can start with some kind of syntax some kind of DSL for actions on a to-do list we'll add a class to create a task to complete a task to retrieve some tasks but these are just talking about some actions these aren't actually doing anything they're just representing some data and then we'll add some methods that will lift those representations into our free monad that will suspend them into that context so that we can do the interpretation at a later point in time and the reason this is free is again because we haven't done anything yet we're just kind of talking about what we want to do we're representing the data in this very explicit way so that we can interpret it at a later point in time so when we chain these together it's gonna end up looking something like this and so this is pretty cool we can use a for comprehension this is pretty easy to read most of you might think this looks familiar to a lot of stuff that exists in your Scala programs and this might again look familiar but the difference here is nothing has actually happened yet again we're just talking about what we want to do and underlying that data structure this is what's going to be under the hood we've changed these operations together in this list like nested structure to represent the actions that we're talking about taking shoving the data together right like we did with the list mono Eid and so the reason this is free is because again nothing is evaluated there's no operations to find and that's why it's free from interpretation we can call this a free monad so why would anyone do this there's a couple reasons one of the big ones that people talk about is deferring side effects so when we say that we're going to defer all of the evaluation that means that the actual IO of our programs or whatever you want to do that's going to cause a side effect that's also deferred until the very end we're composing functions but not computing them and then that syntax tree that we define the DSL for our to-do list that can be used to create multiple interpreters to then later define what we want to do with that data if I write out a list of instructions and hand it to everyone in this room you're all gonna interpret that a little differently that's kind of what we're doing with the free monad and then if you think about something like this maybe this looks familiar to some things that you have in your programs use your imagination for what those dosomething functions do they could be side affecting or they could add another thousand calls to the stack but in the course of our programs things are gonna start to look like this every function in the monadic context is going to be added to the stack so remember my coworker just trampolina and add the free monad so when we talk about trampolining we're talking about expressing all of the control flow all of the function passing all of those chain functions we want to express that in a loop instead of putting additional functions on the stack we want to achieve stack safety by using heap instead of stack the free monad comes down to this exact trade-off it's going to use more heap instead of using additional stack frames so remember our expanded lists like syntax this is the big data structure that we've essentially created it's going to take up that space on the heap instead of taking up space on the stack and so in order to keep this free and trampoline what we want to do is when we interpret this we want to make sure that we in value ate it using a loop we don't want to put any additional functions on the stack so very quickly go over what the evaluation function for this will look like this is the function signature you can see how it takes some input your free monad that you want to evaluate and then it's going to take a transformer this is going to what's going to be what we'll do the actual evaluation and then we also have this implicit con this implicit constraint that the transform type is also a monad so that functor transformer you might also hear this called a natural transformation and in some programs it also has that really confusing symbolic operator I wanted to be very explicit about what it's doing it's a functor transformer that's what it's going to do to do the interpretation and so when we look at the function body for this evaluation we can see a couple of things that stand out here this is already a lot of code so I've left it off it's in my github you can look at it later but the important things to take keep in mind here that this is going to use tail recursion which is in Scala going to put again turn things into a loop instead of putting additional functions on the stack and it's going to pattern match on those cases that we define for our free monad the return the suspending the flat map the important thing to note with this pattern match is that the transformation is going to happen on that suspend step this is where the interesting stuff happens this is where the evaluation occurs and so let's look at a couple examples of interpreters for this so we can define a test interpreter and this is going to take some input list of actions it's going to start being empty and we're going to build up our expected list of actions using this test interpreter and so in the body of the supply method to create the test interpreter you can start to see how the evaluation will happen and so we're pattern matching on that DSL to define the actions that we want to take and this is where you can just start you to think about how you define multiple interpreters you know we've defined here creating the tasks to be adding it to that variable list of actions but in your production interpreters this will probably be making a database call and so the cool thing about this is then you can then create test interpreters production interpreters maybe multiple production interpreters if you have different use cases for that but you can start to kind of see how this would take shape and this would how this is how you run it so you'll feed your list of - dues to the run free function give it the instance of the test interpreter or the interpreter in general that you want to use and then you can see here how we've compared it to our an expected list of actions and for something like this to-do list something that's probably going to in production be hitting a database causing some side-effect the really nice thing about the free monad is then you can then define a test interpreter that will bypass all of the side affecting parts of your code you can test that the program is going to evaluate the code and the order that you expect it to but you don't have to use testing mocks anymore and then really quickly this is an example of what your production interpreter might look like you can see how we're returning an option instead of a trivial context and this is probably going to look a little different than your test interpreters and that's expected so again there's a several reasons that people are using free monads I've talked about a few of them but I think the thing that I want to impress upon you is that a lot of times people are using abstractions like this simply because they can they think it's a cool way to use the code and that's fine but there's usually an easier way so last year Jessica Kerr gave a really great talk at Scala exchange where she talked about blue sky Scala so the the easy stuff in our applications the Greengrass all the way up to the outer space stuff the you know the the hard stuff in outer space and the free monad isn't free because it falls into that outerspace category it's applications are impressive but the path to get there is pretty broken and why is that so composition is great we love using monads in our programs but that boilerplate that you're gonna have to build up to create the abstract syntax tree you're taking all of the implicit actions in your code and turning them into explicit datatypes that's gonna be a lot of work for you and then the learning curve for some of this stuff I can guarantee that if you've never heard of this my 20 minute talk is not gonna be enough for you to go start using this in production this is gonna take a while for you to grasp go talk to a Rob Norris later so it's easy to be frustrated with this and a lot of that is because the context that a lot of explanations assume especially for scholar developers assume that you either have a background in category theory or that you came from Haskell I really don't want to have to be linked to learn you a Haskell for great good anymore in any Scala documentation yes thank you but this is one of the reasons that it makes it really hard to maintain this kind of stuff we want to stay in the blue sky we want to be able to use things in our programs that make sense to us as developers it was kind of like Adrian was saying in this talk just now leave it to the compiler thing the compiler team to implement the hard stuff us as developers we don't want to have to think about a lot of that stuff and so this kind of motivates how we'll think about what we do with this you should know your own domain so I'm not saying that we can't use the free monad but like everything in programming it's all about trade-offs so know your domain Scala is very powerful and a lot of you probably think about Scala is somewhere on this spectrum most people from Scala think about it as like Java scholar or Haskell Scala know the expertise of your team a lot of my team came from Java and so even though we like functional programming and want to make use of the functional programming style we're somewhat centered on this spectrum and that's because we're gonna hire we're more likely to hire X Java engineers and we rx Haskell or X interests engineers so if you're doing a greenfield project and considering putting some of this stuff into your code ask yourself are your coworkers going to understand this do you have the time and the tooling to make these things understandable to everyone into the future versions of your team and yourself and is this necessary for your business logic that's one that people tend to forget and so this motivates how we think about alternatives depending on what the way that your code is structured now I can tell you to use loops and more technically imperative style programming if that's something that your code will allow but if you're highly invested in functional paradigms that might not work for you that's fine but keep in mind looping can be better or it can be better for a lot of reasons this is the Scala standard library from awhile ago at least a lot of this stuff in Scala is built using VARs and can build friends and that's because it's technically more efficient we can also think about other ways to manage side effects not all side effects are bad keep in mind things like logging are really helpful think about how you would log using a free monad hint you can't and so things like this you know error handling is good but Martineau turkey isn't gonna smite you if you use a try except block this is perfectly acceptable and this is the way that we thought about managing some of our side affecting code in a database and so let's think about some of the things that exist for this in the real world if you want to go play around with this you can look at my github or there's projects that exists that have implemented some of this already scholars ed and Katz talked to miles if you're interested in the Katz implementation a lot of these have been defined in the Scala libraries there you don't have to start from scratch and kind of the reason that motivated this from the beginning is this is a scala said method that we use all over our code task is really helpful for concurrent programming but this is what it looks like under the hood and I don't know about most of you but I don't really want to have to think about this stuff when I'm looking at my code and this is the stuff that motivated this talk is because there was code like this in our production systems so what happened well at the first company where my coworker said let's just trampoline and have the free monad like two weeks after he said that he quit and then we never added a free monad to that code base which was fine because at that company we were building a very very basic web app and the sign of Stack Overflow airs it was like a really really bad sign for us and so we didn't have to do it because our business logic did not necessitate it and then it's the last company that I was at when I was using the three moana to manage those datastore the reason that that code was complicated I think largely did not have to do that it was with the fact that it was using the free monad but the code was very over engineered and that's kind of a problem when you start to introduce concepts like this is it's really easy to start to over engineer your systems when you start introducing a lot of this stuff keep in mind that most of us are getting paid by a company that's using us to make them money and at the end of the day we might not need a lot of these abstractions so for people in this room take away from this clock nothing else no your domain know what you need to do when you're building your systems be judicious in your use of these abstractions just because you can doesn't mean you should and sometimes it's okay to forego the most functional style for the sanity of your code and the sanity of your team but most of all if you're someone that understands this share knowledge help build that learning gap and if you're someone like me that's thinking about introducing these abstractions into your codebase I hope I've given you some tools to evaluate whether or not that's a good idea thank you