SBTB 2015: David Hoyt, Drinking the Free Kool-Aid
Recording: SBTB 2015: David Hoyt, Drinking the Free Kool-Aid
okay so this is drinking the free kool-aid before we begin I want to make some acknowledgments so a lot of the content of this talk is built upon ideas proposed in the book functional programming in Scala which is by Brunner Arneson if I'm saying his name correctly and Paul Chisinau an excellent read highly recommend you you read it and I also consider this talk to be a prequel of sorts to another book or sorry not a book but a presentation that renard Arneson gave at scala days in 2014 titled compositional application architecture with reasonably-priced monads so I don't think I'm actually the first person to say monad at the conference it was is that it was mentioned in a slide so I thought I was going to be the first I guess not so when people hear of monads for some reason that seems to inspire fear in people and it's really not that bad as soon as you as soon as you've learned some of these concepts if you like me you start to see that they're applicable all over the place but I will say that the concept at least with when it comes to the free monad for me took it took a while for me to understand and so if you if you end up confused at the end of this talk well I guess I didn't do my job but but I'll also say that you know you're not alone there are plenty of other people who have also had a hard time understanding these concepts and for me I had to come back around not once not twice but a few times before I really understood these concepts and I think actually looking at code and writing up actually writing the code is what gave me the intuition so this is an introduction to the idea of the free monnet and I also want to say originally if you read the description for this talk I had anticipated doing a lot more live coding but at the behest and advice of a friend in order to garner better intuition these concepts he recommended that I do less at the live coding and more of the slides so apologize if you were here for more the live coding okay so why do we care at all about this concept of the free monad right why do we care so let's take a look at a program here okay very simple kind of imperative style program we're leveraging Scala's syntactic sugar where what we have is it looks like an imperative program where we're asking for a Twitter handle and we use that information to go out and fetch tweets for that for that Twitter user and then we want to display them okay so if we have a program that looks like that let's look at maybe some of the things that we can do with that program actually before we do that okay so I'm gonna take that program and I'm gonna run it in in the terminal and here I'm just displaying a prompt and I've a default value this is Rob Norrises Twitter handle and we're gonna go out and we're gonna fetch his his tweets the last two tweets all right so that same program is going to work unchanged in the browser okay so we're gonna fetch some tweets so William here saw my talk on free monads before I gave it it's very prescient and then here's Rob Morris's tweets so we have the same program but executed in two different very in two very different ways all right so how do we achieve that let me see if I can work my way back to my slides okay so we made no changes to our original program yet yet we were yet we were able to have two different versions of it how do we do that okay so enter the free monad all right the free monad is just another tool for us to use this software engineers we have lots of them and one of the goals one of the takeaways from this presentation is to help us to learn to use the free monad judiciously in a safe way so you might be asking yourself again why do I care well the free Moana is going to give us purity of abstraction reusable definitions and it actually allows us to defer eFax so as functional programmers we often like to we like to bottle the effects or we like to push effects and side effects out to the edges of our programs and the reason why we do that is to is to enable reasoning about how we've developed and composed our programs so let's talk about micro services or services services services there's our old friend Steve Ballmer okay so Twitter and in other companies like Netflix they might have tens or hundreds of micro services and how do you coordinate how do you orchestrate across all these micro services so say that say yeah I'm I'm Netflix and you've logged in I want to display your your username and I want to fetch some movies for you I might have to fan out to all these different micro services I might end up contacting the same micro service multiple times I might ask for the same piece of information multiple times if I'm not careful so what would this look like in the imperative landscape you would have you would end up confusing a lot of your logic or mixing it in between caching and batching so what if I told you what if I told you that you could you could achieve these you could achieve the caching and the batching and just to find sorry you could issue the cashing and the batching and instead just think about what it is you want to do and not how you want to achieve it all right so that's where it's another plug for obviously the free monad okay so for the rest of this talk this is what we're gonna do we're going to we're going to review some fundamentals we're gonna look at some code we are going to get some intuition about the way this works and also intuition about the free monad we're gonna look at some more code and then quick wrap-up okay so a quick aside about design patterns mathematical rigor so design patterns are very useful abstractions right that come up you know after after we see repeated uses in in our programs and so we end up coming up with with these patterns but what what I really want to say is about the abstractions that we're about to just review really quick these are attractions that have also come up many people have seen it and they cross many different disciplines so not only do you see its application in computer science but you're also seeing its application in in disparate areas such as music theory so first up is natural transformation again I'm not the first person at this conference to say natural transformation I was quite surprised by that so so we are going to concentrate not on the theory but more on the pragmatics the pragmatic ideas behind these concepts so a natural transformation says if I have two type constructors an F and a G so if it helps think of an F as like an option it so the type constructor in this case if you notice there is one underscore there for the type constructor which means it has one type parameter so if I have an F energy and I have an apply method which again if you notice apply is polymorphic so it takes a type parameter a so given an f of a I can convert into G of a alright so and down below we just have our little arrow there which is just an alias for natural transfer the reason why we want to use the little arrow is because Scala gives us some nice sugar to to reorder those type parameters so we can put the F arrow and then the G okay so a simple example so we can get some intuition we have our option and our list classes we see that option has a single type parameter and list as a single type parameter so if we use option and list as type constructors we have the AR option to lists which given an option is very easily converted into a list and Scala we just call to list on the option and in that case we have an option we have a list sorry okay so next up Mon weights okay so let's go straight on the append there so so am on way it says if I have two A's and have this append method I can take those two ways and I can then I can produce a single a out of those okay so a canonical example is maybe string concatenation so how do you append two strings together well you simply concatenate them together right and so a zero says if I use a zero with the append so if my a one is a 0 a 2 there is some other string and if I concatenate my 0 to my a 2 then I just get my T to back alright okay so so a lot of these abstractions I'll also say have laws associated with them so we are going to enlarge parts ignore the laws in order to concentrate more on the important concepts later on in the talk okay so we have we have more free things than a free Mona we also have free Mon winds so a free Mon ways basically just says I don't know how to append so what I'm going to do is I'm just going to stuff one a next to another and if we do that now we get something that kind of looks like a list of sorts okay so moving along on to a functor so we have a type class kind of version of the functor where where we are taking a type constructor F so functors hire kinda and we have a map to type parameters a B so given an F okay so you can consider F to be our payload so it can be an option it could be a list so given an option okay and a function that goes from A to B how do we produce a new option of type B now okay so there is something called the free functor so we have frémont anoints now we have free functors so a free functor is also known as the Kali Anita and what that says is I have a functor but I don't really know how to map so I have my F of a I start off with the identity function a to a and then as you try to map over me I'm just going to store all the things all the functions that you're giving me then at some later point maybe I'll be able to actually to run that and and get an F in this case an f of C out of it so it seems somewhat useless you know why would we just why would we do this okay well it kind of seems like that on the surface except for what we'll see later on is that the free functor in the kannada actually enables us to to get a functor for any type or any any type constructor F we get it for free so even if that F is not actually a functor itself okay alright so monad Simona ad says we have a type of constructor M pure we have a pure operation which says given given something of type a then I want to create an M of a which means so let's use option as an example so if I want to lift a value like a string in your arbitrary string and I want to turn it into an option of string well the monad say this the the monad for option would describe how we can do that and flatmap here it would take an MFA and a function that goes from a now to M of B okay so this is what flatmap says is if you have an option of string or anything in any M there I know how to again if you look at if you look at the function there you'll see that it takes an A so it says that I know how to pull out the value that's wrapped in my option and give it to you and then you produce a new MFP so that or a new option right so you could choose to return some you could choose to return none so in this way monads are encode sequential computation if you think about it now Mona's also nominally functors just because we can derive a map very easily in terms of pure and flat map so the quick little side on sequencing computation so quick example here we have we're composing two futures together and in where we have the value 1 error future 1 that's just extracting a value basically out of the future and then at that point on the next line we have value 2 and then at the very end we're yielding value 1 and value 2 so we're just adding those two values together ok sorry I got ahead of myself a little bit in my mind so the ok so as a result of this if you look at value 1 and if we were to do this you would see that that these that the D sure good representation of this actually just results in a series of flat maps and maps so you can think of a value 2 as being kind of the rest of the program that is yielded as a result of evaluating the first line but that doesn't make much sense my apologies come find me Edwards ok so I also want to touch briefly on the I on the identity monad so here what we have is it's almost a type level version of pomona ad where if you look we have type ID of a and that equals a ok so at runtime the the fact that we're using this that we're using ID is almost shed completely because almost erased and what the identity monad basically says is even though you give me something to sequence I'm just going to strictly value evaluate it right then okay so it's almost a pass-through and almost it almost does nothing okay okay so moving on now to the free monad okay so repeat after me a free monad is basically an ast or an abstract syntax tree plus an interpreter combined so an abstract syntax tree basically just expresses computation as data so it's more the what's of what needs to be done and we have an interpreter which gives meaning to our data so that's how the how we will actually execute it so I have a math problem I'm going to propose and it should be pretty simple for all of us here so what's one plus two okay again pretty straightforward but let's think about how do we express what one plus two is in terms of an F check syntax tree okay so let's cut over to the code okay so simple application here and we are going to define an F check syntax tree that represents mathematical expressions okay so I'm going to come up start off with a sealed trait the XP are short for expression and we're going to create a case class constants short for a constant value this case is just going to be an integer it's going to extend the xpr we're gonna create another one called the pad which takes two operands each of type expression in itself is an expression and we'll create one called subtract okay all right so okay so what we've been able to achieve here on line 13 is if it's in a representation of what it means to add two values or sorry it's more an ast that represents the mathematical expression of adding two values so given this this is fine and good but now what can we do with it okay just a second okay all right so we have our ast but now we need to give meaning to it so on line 17 what we have here is an evaluate method and that takes our expression and using recursion and also the Scala's pattern matching and extraction we can we can produce an integer value out of the expression that we gave it and this will work for any arbitrary ast that's the corresponds to a mathematical expression that we give it so if we were to actually run that we would see that one plus two is actually three right a lot of work for just that but here's where the power starts to come in so given an ast we can out we can find we can have we can have a different way of expressing that or evaluating that same AST so here on line 25 I have a two string which in this case has taken that ast and instead of actually producing a value out of it or sorry it's instead of actually evaluating that mathematical expression in terms of producing another int we are actually going to evaluate it and produce a string which represents that expression so let's go ahead and run this so we can see what we get as a result okay so on the first line okay this line right here okay that's the result of executing line 23 and the code above okay so we've actually taken one plus two and executed it these lines below are well simply so this is calling the two string basically interpretation of our ast and we get three plus four plus five similar to how we had to find it in terms of our ast we have slightly more complex expression down below on line 32 and we have a series of assertions on 33 through 35 just to do a quick sanity check all right and I do assure you those assertions are actually executing they are actually checking that that's true okay so we have been able to give meeting to to our ast so what does this have to do really with the free monad okay well we're getting there okay patience everyone let's take a look at the way that we define the free monads so we have a seal trait here free and it takes a type constructor F where F is a payload of sorts in our previous example F would be our expression but we would need to modify our expression to have a type parameter which is what the under what the underscore there is referring to and then we also have this type a which is the type that will result that will be the result of of evaluating an instance of our free monad so what the free monad gives us is actually an ast that describes monads okay so we can so what we do is we think about what are the operations that a monad does and how would we react i those operations in terms of data constructors okay well so we have something well with both monad we have the pure operation where where we take something of some arbitrary type a and we want to want to lift that into the context of the monad so how do we lift that into the context of the free monad well we define a data constructor called return and it's basically it's a simple case class and we give it a value okay and so now how do we do the flat map operation well very very similarly okay we take an instance of free that you already give me and a function that goes from a to another to a free of the same payload type but a potentially different kind of return type and so once we have those data constructors we can go back to our definition of free we can define map and flatmap so map is fairly simple we define that in terms of flat map and we use the return data constructor and we have flat map down below which which all we do is we stuff we stuff the current instance into into the flat map data constructor and then we also provide a method that that basically carries forward your function okay so so a simple example of how this might be used and it may not be entirely clear at this point why we want to go through all this trouble but but so the free monad is actually itself a monad so you can use it in a for comprehension just like you would with any other monad that you're familiar with so here we have so we have an instance of return and return is a extends free and we're just composing together a bunch of returns together and yielding hope it works if we recall this is just syntactic sugar where we're each item and the for comprehension gets D sugared into a series of flat maps and maps so this is actually what's going on under the hood so once we do all this what we what we're really getting is something that looks like this where we have a series of actually nested data constructors okay so what is it that a free matter what is it that a free monad is actually doing well a free monad is like a functor except it doesn't know how to do a join so joins here take an f of F of a and shed one layer off of that and turn it into just an F of a so what you end up getting is you end up accumulating all these FS right and then the question becomes if we've accumulated all these FS how do we get rid of them okay so what I am saying is we do have a monad for monads and it doesn't seem on the surface that they're really doing kind of monad e things right so a monad should be doing a join so how are we going to compensate for that so how do we do that so how do we remove those layers so we have we define another method we'll call it in this case run free takes two type constructors f G and an a so what that says is if you give me an instance of free okay an instance of this free monad and you give me a natural transformation which takes me from my F to a G+ if we add the constraint that G has to be a monad itself then I can shed those layers and actually and actually evaluates the free monnet that you gave me and so what we end up getting is a G of a and so why why this might be important so if we have if F is so let me back up let's say Y is this version actually somewhat important if we express run in these terms where we have the natural transformation and we make the imposition that G has to be a monad then then that allows us to get around the fact that if we didn't have these constraints F would have to be a functor and so anyway so this this just allows for more you see what's the word I want to use it's it's more open it's it's easier to use so what do we mean by free okay how is this actually free free as a bird well so if if F is actually a functor in this case we we actually get a monad without having to do anything extra we just we automatically get a monad for it so it's defined in functional programming in Scala as as a free in this context means generated freely in the sense that if you have a foo where foo might be a monoid or or functor or a monad so you have Fremont annoyed or a free functor or free monad then that free foo it's elf doesn't need to have any foo structure of its own so free monad doesn't need to actually have all the magnetic structure that's required with scaffolding that's required okay so if you recall at the beginning of the talk we showed we showed a brief example of of taking a single program let me bring it up so this program from line 13 to 20 so we took that program and we ran it in the command line and we also ran it in the browser so how do we achieve that okay so this is where it starts to get interesting so let's go to the definition of this tell here all right so what we've done on line 10 is we've defined this thing I'm just calling not only an instruction he has a type parameter a and then we define an AST that describes in this case interacting with the user so we have an AST that describes prompting a user with some bit of information and we have an AST that also describes getting getting information from the user so if we have something that is an abstraction over these concepts it's just an AST then actually applying it is more the job of the interpreter we also have on lines 15 and 16 we have data constructors that represent fetching tweets for a user and then also displaying them on lines 18 through 22 what we do is we have a series of you know in air quotes smart constructors that take our values and and lift them into into an instance of free reason why we do this is so it's more out of convenience so we don't have to litter our code with with returned with the return data constructor of the flat map data constructor in this case there's a suspend data constructor which is more a convenience thing which we won't really have time to get into at this point but so once I have these smart constructors I'm able to compose them because these smart constructors are returning instances of free free is free is a monad okay so we can we can compose them just like we can any other monad and if you recall once we compose it we actually get a series of nested data constructors so this is well and good but now how do we get rid of those layers we'll come over here this is the these the terminal or the console representation of our program so what we do is we have this thing called standard evaluator and it is a natural transformation from our instruction we're an instruction if you recall is actually a data constructor for tell or ask or get tweets or display tweets so we take we have a natural transformation from the instruction over to ID so ID is actually the identity monad so if we have all the scaffolding in place then given than given an instruction how do we actually how does that actually result in printing to standard out or reading from standardin right so that's what this standard evaluator is doing here maybe maybe it should be better it would be more properly named you know standard interpreter standard out interpreter but this gives the mapping from our ast into some concrete app operation which might be site affecting okay so given that interpreter we can run it we look on line 50 there so we're giving the the program we give it an interpreter and we're able to execute it and from there right it will it'll print out to standard out let's just run it again huh okay all right so what's interesting about this is the program unchanged works like this just as before thanks Rob I assume that's in reference to this Chuck okay and so but we can also apply a different interpreter so we have this thing called the test evaluator we're here what we're going what we're going to do is we're gonna we're going to give a series of pre-canned answers so think about using this in terms of a unit test okay so we define our single program which we can which we can test and then interpret in different ways depending on the context in which we want to to to have it run so with test evaluator we give a series of pre can't answers and then when it comes to actually printing something out we just return units we just ignore it when it when something says hey you need to respond to an ask so when our when our run method is shutting the layers and it comes across and ask it's going to call this natural transformation and it's going to say okay here's the ask what do you want to do in response to that in this case we're just going to we're just going to take we're just going to basically a pop an answer off of our list or sequence and then we're and then we're going to return it and then on line 31 we're actually ignoring what whatever name user names that you're giving me and I'm just going to give you back a series of tweets that I want that you know pre-canned tweets that I want you to use and so if we run this program now you'll see that it's not going to prompt us for a user name is it's going to use that's going to it's going to directly execute with the interpreter that we provided so now the question becomes okay so this is cool with the standardout version how about the the web browser version how did that work okay so let's come over here really quick okay so the web browser version actually looks very similar now I cheated a little bit in that I'm hiding some of some of the actual rendering of this if we go over here you'll see that we're using some of the scholar Jas libraries in order to construct some HTML but not only the the program itself is unchanged so come over here so I actually do in this case I actually do two passes over our program I use I on the first pass I go over it with something that knows how to render the ast so it's producing your your divs your labels and your text boxes and then so that's just for displaying purposes and then when you click the button I do another pass over the same program and I use another interpreter which knows how to pull the values out of the text box and then execute on it and when we do that all right we get this again okay so repeat after me okay a free monad is simply an AST and an interpreter and then so you might ask can I compose different F's it's a great question you read my mind how to do that so what what I mean by this is so say we have a foo of a and a bar of a and we have two instances of free so one is it's a free of food and the other one is a free a bar can we compose these things together actually we can so we there's something called the co-product and it's not something that we really have time to treat in this presentation but you can use these things these co-products in order to compose basically different different F's together if you're interested in that subject I invite you to read the book datatypes ala carte and I don't think I'll pronounce his name correctly so moving along you can also watch the movie so this is ruiners talk that he gave at scala days as well where he treats this topic probably in much greater depth than I'll be able to hear okay so some things that we didn't have the time to really get to is trampolining and so again if you read the book or watch the movie you'll get some more insight and intuition into into what trampolining is and how you can have different versions of run that that account for trampolining okay so honorable mentions so there are libraries already out there cats in Scala Zed or Scala Z I'm not going to get into that war I say Scala Zed so that's that's that so cats and Scala Zed both have they both have their versions of the free monad that are in there they are pretty similar so you don't need to code all this up from scratch you can just leverage what everyone else has already done for you so other resources limiting scale the Z datatypes Alucard free monads the janay dilemma and talk by Noel Welsh or actually it's an article free monads are simple where can you get the source for this talk there it is the slides will be available at some points and so you can get the link there from the slides later and that's it thank you okay so questions they have to be gentle I wouldn't put myself at Rob's Rob Norris's or at Who am I thinking of Dibble go Tony Morris right I would I would put myself out there levels so be gentle questions oh compositional application architectures with reasonably priced monads it's a mouthful yes I can do that so alright so I don't want to get too deep into the category theory concepts of this will just say pragmatically right now as its defined right now and on this slide right there are there are really no constraints right so f is is any type constructor yeah we can talk afterwards if you want some more insight yes so okay so the question is would it be useful to have a free completely free mode as completely free yeah sure actually if you if you think about using the free monad in conjunction with the with a free functor it does become actually very useful because then your your type constructor f doesn't itself need to also be a functor yes so yeah there is useful utility there oh great okay so that was a plug for Scholars ed right over cats okay any other questions okay then thank you very much