Functional Programming with Effects

scale.bythebay.io: Rob Norris, Functional Programming with Effects

Recording: scale.bythebay.io: Rob Norris, Functional Programming with Effects

you thank you take these off okay Wow thanks everybody for coming this is a pretty big crowd all right so my name's Rob I do functional programming and I'm tea polecat pretty much everywhere online I'm easy to find I like to help help people with functional programming so feel free to reach out if you if you want to chat I work in a bunch of open source functional programming libraries for Scala a lot of type level libraries so I'm kind of involved in in that part of the community and I write software for the Gemini Observatory so we take pictures like this it's not showing up that well that's NGC 660 it's a ring galaxy I don't know it's a pretty picture so before before I get started I want to kind of motivate this talk and and and why I'm here and why I'm talking about this stuff so about five years ago I started coming to Scala conferences and like so earlier this morning Runa was up you're talking about at junctions five years ago he was up here explaining what monads are so we've kind of come a long way like three years ago everybody was talking about free monads last year everybody was talking about recursion schemes and and and that kind of stuff but I'm concerned about people who kind of just got here right so Mona's have not gotten any easier over the last five years there are a lot of beginners a lot of newcomers to this kind of programming and I I don't think we're doing a great job helping people get started I think organizations are trying to dive into this and they're having a rough time and Kelly Robinson has given a few talks over the last like year and a half or she's like really hammered home this this point the people are struggling with this and and I'm convinced and I think we need to do better teaching people these sort of fundamental I is about functional programming so this year my friend Adelbert he's probably out there somewhere we decided we were going to talk about these kind of core ideas and hopefully some of you saw his talk yesterday and and so I'm hoping this will kind of wash over you and a different from a different direction it's similar ideas but I'm gonna try and come at it from a different point of view I think it just helps to see things from different just sort of different from different directions and eventually stuff overlaps enough that it'll start making sense okay so the goals today don't panic and I say this for all my talks in this case it goes for me too I haven't given this talk before I'm gonna be looking at my notes more than I would like to but that's just kind of the way it goes so we want to understand what functional programming is what's benefits are we want to gain some insight into the way functional programmers think about things this is a big deal right you when you when you do FP you have to change the way you think about programming and it helps to just kind of see people doing it to see how you how you approach things so I'm going to try and illustrate that a little bit understand why monads are useful so this is a talk about monads if you already know everything about monads you may not learn anything we're gonna see where they come from and and how they fit into sort of the bigger scheme of things and I want you to be inspired to be curious I want you to not come away with this and not come always saying I've gotta learn all this stuff but like I get to learn all this stuff okay and and so be open be curious there's a lot of really cool stuff out there to learn I'm gonna go through a lot of code and do a lot of code manipulation and I'm gonna drive a lot of things kind of from first principles so the goal for you is not to follow every single step that I make you can always go back and look at the slides for that their goal is to understand how things are connected and how this these the things that we do are not arbitrary they have some some basis behind them and as you learn more and more of this you'll sort of build a puzzle the puzzle pieces will start getting filled up in your mind and eventually you'll start be able to you'll be able to sort of fill them in yourself and explore on your own all right so functional programming what is functional programming well let's let's take it way back right so we have values and there's a Scala so we classify values in two types which we can treat as sets in a language like Python everything's in the same set everything has the same type and then we have functions that map values from one type to another okay so notice that this is I'm talking about a mathematical function it Maps every value in type a to some value in type B okay that means it's a total function also it's not necessarily clear from the picture but that is all it does okay it doesn't increment a counter it doesn't check the system clock it doesn't write to a file a function is a mapping from values to values and that's all it is okay so functions like this are said to be pure okay the output is determined entirely by the input okay and there are a lot of good consequences to programming with pure functions so evaluating an expression always gives you the same answer you can memorize anything freely we can always inline a function and we can always factor one out because it's just a symbolic manipulation we can always substitute a variable for whatever expression it was bound to or we can introduce a new variable and factor out a common sub-expression and that property you've probably heard of and it's called referential transparency it's this the the fact that we can perform the substitution so let's look at some examples so are these two programs the same anyone it depends write in functional programming the answer is always yes and that's the key thing okay those programs are always the same in functional programming and from that fact you can build up a lot of really powerful stuff but in general it depends so this one I would say the programs are the same we're just a is just 42 what about here what do you have an iterator all right those are not the same program are they okay so internet next is not referentially transparent you can't perform that substitution legally and notice that it goes both ways right these are the same programs so you can go from one to the other in either direction right so you can't factor it out either you're stuck okay and you just have to know that you can't do it for that expression that's a lot to keep in your head and we're trying to make programming easier so getting rid of that worry is very powerful what about this one not the same program obviously one prints I want some one prints it twice what about this one what do you think about this that one kind of depends it's pure as long as you never mutate the result because one of them has one array in one of them has two distinct arrays and once you mutate you can observe that these things aren't the same so if you have part of your program that's pure and part of it that's side-effect D you can you can run into these problems as well so we've got to be careful when doing functional programming in Scala because the the compiler doesn't help us very much all right we've got a we have to be kind of careful when we think about this all right so let's review this idea every expression in your program is either referentially transparent or it's a side-effect it's one or the other okay so saying something that is it saying that something is a side-effect is it's a syntactic property saying something about your ability to perform substitutions okay it's only an indirect statement about sort of runtime behavior of your program so if you think about it in these terms I think it's pretty easy to understand what a side effect is it's just can you do the substitution or not is it is it ever going to cause the behavior of your program to change to do so okay so this is important point an important point I think because in factual programming we live in the world of let's see go one more okay so we can use the substitutions to do equation already and and NFP we're sort of in the world we're out of the world of statements were in the world of equations and expressions so functional programs are expressions okay it's not a step oh it's not a list of instructions it's an expression that is reduced to produce some answer for you running a functional program is is is a process of reducing an expression to a value and we build bigger programs by taking smaller ones and composing them which is the kind of thing we do all the time with expressions we have two things and we two numeric expressions and we can put a plus between them and when I wave a bigger one so because all we have so far is function composition let's talk about that we have pure all we have is values and pure function so let's let's compose some functions okay so here's our function again and we can't use another function that goes from b to c a function called g and we can compose them end to end like that and and and now we can create by doing that we can make a new function f and then g that kind of goes all the way through in one step okay so what does that look like in scala okay like this so this is how we were defined in Scala it's pretty straightforward and there's probably you know I think there's only one way to write that that will go type check so when we see an operation like this you know we're in the world of expressions and and and it's interesting to look for algebraic properties that operators like this have and we might ask for instance is this an associative operation so let's find out so what we want to know is does it matter does the order where the print friends go does it matter so let's just inline this and see what it looks like so F and then G and then H so in lining the outer end then we end up with this GN + H applied to F of a we inline the inner one and then we get another function B - H of G of be applied to F of a so we can just substitute F of a in there and then we get a to H of G of F of a which seems correct to me let's look at the other side F and then G and then H with a prince the other way H of F then G applied to a substitute the inner one and again we have a function applied to a and we can substitute a all the way through we get agent G of F of a right and they're the same and we proved it right this isn't something that we're you know this is this is a fact okay and I think it's pretty cool ok so we have this new legal substitution that we can perform on our programs which is which is awesome now we can substitute variables and we also have this other thing we can do so purity gives us it gives us the ability to derive these substitutions these bigger more interesting substitutions we can make and that's where FP becomes really powerful what else might be what might we ask about this if you have a an operation that might have an identity so let's look at that my conjecture is that if we compose with a function that does nothing but return what you give it it will be a no op let's look at right identity F and then ID is a to ID of F of a which is B to be applied to F of a which is this F of a a to F of a which is f ok so right identity works and the same thing works for left identic okay so we have that too and we have associativity okay so we have mappings between types we have an associative operator with an identity at each type and we've proved it's true by the definition of function composition and because there's really only one way to define function composition this actually follows naturally from the type of function composition which I think is really interesting so it turns out there's a mathematical structure that represents this kind of thing exactly which is called a category so category has four things it has objects in this case they're types it has arrows which in this case are pure functions between types it has an associative composition operator which is and then in this example and it has identity arrows at each object and these are defined by our polymorphic ID method okay and if you were in renard session or unsession yesterday you'll know a lot more about categories but this is as far as we're going to go today so I mean the question is why do we care right so it just turns out that math is useful but we identify these connections between types and and programs and mathematics and we can do a lot of really amazing things FP is just just doing some astonishing things by tracing its roots back to these mathematical structures I think one of the benefits is that these connections are very apparent when you're doing functional programming I think the gap between theory and practice is really quite small and we can apply these ideas very directly so and by doing this we can be very precise about what our programs mean which makes it easier to be convinced that our programs are correct and because we have these substitutions we can do we can refactor our programs very confidently so it helps our programs start correct and stay correct and this is kind of the value proposition for functional programming but in but all we have our values and pure functions right so in we've given up a lot of expressiveness to do this so so what about partiality right so functions have to have an answer and in you know writing Java sometimes you return null or something how do we deal with that exceptions so we're in the world of expressions and expressions don't throw exceptions right non-determinism functions have to have exactly one answer dependency injection right so our are the power of FP comes from you know we give it gives us an ability to reason locally about stuff and if we have this sort of big global scope that's introducing stuff that any part of our program might depend on then that hinders our ability to do that logging is a side effect right and the whole point of logging is to see when things are happening and in functional programming we're dealing with expressions we don't care when things happen it doesn't matter so what happens to logging immutable state obviously we don't have var anymore an imperative programming in general what where does it go so it seems like a lot to give up right and and the big barrier to learning functional programming is understanding what to do when you need one of these things and what functional principles do you apply to solve these problems that are pretty you know you run into them all the time when you writing programs so this is where effects come into play so effect is a very vague term and that's okay because we're trying to talk about something that's sort of outside the language and it can be hard to grab a hold up and then we're gonna spend the rest of the time in the talk talking about it so I should if there's one thing to take away from it from the talk today is that effect and side effect are not the same thing okay effects are good side effects are bugs and their similarity there like lexical similarity is really unfortunate because it leads to a lot of people conflating these ideas when they read about them and people using one instead of the other so it leads to a lot of confusion so when you see effect when you're reading or talking to somebody think think a little bit about about what's going on because it is a continual point of confusion so what I want to do is talk about six of the effects there are kind of the first ones you learn when you start to do a functional programming it is just kind of the first things in your toolbox there are many more and many ways to classify them but we're gonna start small okay we're gonna look at them these effects talk about what they mean and try and figure out what's what's in common about all of them so hopefully we'll be able to by the end have a pretty precise definition of what these things have in common all right let's talk about option so we're Scala programmers I'm I'll assume everybody has seen option and and the intuition about that and in functional programming is it's is partiality we can define functions like F and G that might not return an answer it gives us a way to represent the fact that I don't have an answer for you okay so we can have an a to option B and a B to option C and if if we could combine these and the adoption BB to option C and end up with an A to option C what would have to happen is the effect would have to be combined right if either of them failed we couldn't possibly get a C out right so if we had a way it's sort of smashing them together by doing function composition that would be pretty powerful but we can't write we don't we don't and then doesn't work we could write it out but we're not going to do that we're gonna keep going let's talk about either so the intuition here I assume everybody's seeing either it's either you don't left or right intuition here is that you can have functions that might fail but also give you a reason why they failed okay so this kind of gives us exceptions back okay so I don't have an answer here's why I don't have an answer and again if you were able to compose them together if you finally got a C out you would know that both of the computations worked if one of them failed you will get you get a left and you get the first left that wasn't because the computation would have to stop there they wouldn't have a value to pass on but again that composition operator isn't defined so we can't do that but can can you can you see at least in principle the power that you would get by being able to do that and chain these things together makes knots okay let's talk about lists here's another one so in in functional programming we take kind of an interesting interpretation of lists we sometimes think about it as a kind of non determinism we can have defined functions that might return any number of answers okay and and if we were to compose these two together end to end we would we would want to get every possible answer that we could have gotten from these two functions F and G okay but again we we can't do that so these three effects most Scala programmers have run into and then you run into him pretty quickly you might not think of them as effect but but they are and so now we're going to talk about some that that are they're less familiar if you're just starting this this stuff this journey this this just fell out of heaven the other day so this is Jamie up in up in Seattle accusing Andy of teaching people the reader monad and so he he was skeptical so he didn't want people talking about the reader monads so if there's anyone down here from Seattle from from from Starbucks let's talk about the reader monad so this is a little data type and it says if I have a reader a reader of a B what it does is it wraps a function from A to B which is really pretty simple but the idea is we can return we can compute values that have a dependency okay so a to reader of config B where configures like some you know config file or something we're passing around its equivalent to an a to config to be okay let's see I think I have some examples of that yeah okay so here's an example I have a method path it takes a string and it returns a reader of host and string okay so what I can do is I can construct this computation P with a path and then I can run it with different hosts and I'll get a different answer back okay so it just is just sort of it's just sort of a currying thing at this point a partial application thing but if we were to compose these things we could have multiple computations that were dependent on that same configuration we could compose them together and get a new computation and pass the configuration in and get our complete answer back we can't do that yet because we haven't defined function composition for that type so if there's reader there's got to be writer right so this is another effect that's a pair of some value W and an answer a and the intuition here is functions that can annotate the values that they compute so if we have something that returns a writer of B info be alert return info and the B and the info might be a log message or something here's an example so it's pretty simple so something that's going to convert an into a double and it'll tell you about it and we can run it and we can get we can get that back and the the state that it returns is a list of strings so so if we were to be if we were able to compose these things together what we would get is these computations that can talk about what they're doing and then if we had a way to smash those infos together we could run it we could make a big computation and run it and get an answer and some kind of extra collected bit of information like a log for instance right so but we can't do that yet let's do one more this is the hard one so this is a type called state Runa I talked about it this morning I think in the injunction talking I over talked about it yesterday so what it is it's a computation that takes some input state and computes a value and returns and returns another state that might have been modified so here's an example we've got something it's really simple it just counts the number of people that it has greeted so far so it takes it takes count and it returns a message and then increments the counter so if we we construct Greek for Bob and we run it with one it says hello Bob your first number one and the next counter is two right that's the current state that's coming back out that we could pass on to the next computation and if we were able to compose these things together then we could do that we would have this state sort of threaded through our computation which is nice that kind of gives us immutability back okay or a lot of the cases that immutability is used for all right so what do we so what do we see here what do they have in common so all of them compute kind of an answer but there's some extra stuff associated with it and this is what we call an effect it's still kind of vague but that's but that's the idea it's let's try to be more precise so we talk about these things they all have the same shape okay so for either reader/writer and state we have to fix one of the type parameters but if we assume we're only talking about either with a string on the left or read or writer with only a list of numbers on the left or whatever then there's only one type parameter left and they can all be described by the shape okay so my sort of big statement about this is in fact it's just whatever distinguishes everyday from hey that's about as precise as we can be about it an effect is sometimes called a context which I don't really like but you'll hear people say that and there are tons and tons of effects that we can model with different levels of expressiveness and these are just the first ones like I said these the first ones you pick up when you start doing functional programming and I'm doing this because they all have a similar amount of expressive power to them and so we're going to talk about about what that is in a little bit because effect full-value takes too long to say sometimes we just call them programs so if you have an FFA you will hear people say this is a program an F that computes a value of type A Okay it might seem weird to think of something like options string as a program but if you think about something like state like we just saw or an i/o program like John was talking about earlier it makes a lot more sense so that's a good generic way to refer to these things as computations or programs you'll hear people use both of those in terms but they don't compose right that's our problem we have these two functions that go to option that have options there affect and we can't we can't compose them so what can we do so our question is what would it take to make them compose all right so here's our function diagram for a pure function composition and if we just sort of replace things with effectual functions they look like this okay so we have something like and then that looks kind of like a fish and then we have an ID at every type and I'm calling it pure because the intuition is it kind of takes a pure value and it turns it into a computation somehow so if we were able to define this and make it compose then we would get that power we've been talking about so how would we write this in Scala something like this it's parameterised over some type constructor as two operations as pure and the fish composition we can actually start to implement the fish right because we have an A and an F of a right so we can we can apply at least one of those and now what we have is an f of B and a B to F of C and we're stuck so who can tell me I mean does that signature look look familiar to anybody F of B and then B to F of C I think it looks like flat map okay so really the the fish operator is a kind of something we can we can derive later really the operation we need is flat map okay we can find the fish operator as syntax I'm not gonna go into well I guess I will so what it does is it takes well I mean it's not obvious so it'll take a function from A to F B and it'll add a fish method on it and the fish method takes a function from B to F of C but also it takes a fishy instance right it takes it takes evidence that we know how to flat map this F type okay and then it just delegates and implements it we can define an option for an option of this for option or instance for option so Pierre is just some and flat map I'm just delegating to the one in standard library it's a save time here's our function here are functions that do not compose but now they do so the fish operator works now so we can look at some examples we can apply it to foo and we get none we can apply it to a long string and we get the ASCII code for the U if we change it to a 9 we get none again right so so this is cool um we've we've implemented this and we can do this kind of composition but what we've forgotten about is all the rules for the category we can't forget those so let's look at this look at our diagram again what are the rules well we need identity we need left and right identity and we need associativity so what we want to do is figure out what this means in terms of flatmap okay so let's look at that so left identity is pure fishy a we can just inline the fish and what we get is a to pure of a flat map F F we can just we can physically de expansion we can turn tweak and F into a2 F of a it's the same thing but because a is introduced on both sides we can just treat it as a free variable like this okay so that's what we need to satisfy for left identity for right identity it's a similar thing will in line do the same trick we can treat a is a free variable but we can also say F of a is just any arbitrary value in this effect and so we'll just call it M okay so these are identity laws will do associativity really quickly well in line the outer fish and then the inner fish and what we have in the middle is B to F of B flat map G all applied to a so we can substitute a in right there okay and then write associativity remember these things have to be the same we can inline the outer one and then the inner one and again we can do the same trick we did before just treat as free variable and then just just just an arbitrary term in that effect so these two things have to be the same and that's our associativity law that has to be true okay so we have these two operations pure and flat map and laws telling us how they relate to each other and this isn't something arbitrary so that's what I'm trying to get across these are things that come naturally from the category laws just by analogy with normal pure function function compositions okay so I'll go ahead and tell you what we've been doing this is called the closely category for F this is the closely composition operator and and this fishy type class that we derived from nothing using math is Mona right okay so the scary thing it just it just comes naturally and and I haven't seen people talk about getting to it from this direction so I hope that was helpful we also divide derived all the laws we got the whole thing everything you can say about monads is on the slide okay but notice that unlike the the rules for function composition which we proved were true and are necessarily true from the types this is not the case for a monad you can satisfy this type and break the laws okay so when we define instances we have to verify that they meet the laws and cats and scholars that both provide some some machinery to make this very easy for you to do so if you define instances you have to check them someone should do a conference talk on that because it's it's really important and I haven't never seen a talk about it okay so we have pure and flatmap that are abstract but how can we define some familiar operations in terms of them we can find map right okay so everybody's seen map on list and option we can define that in terms of pure and flat map we can define a tuple operator which is kind of interesting it takes two sort of existing values FA and FB and smashes them together and you get an F of the pair of a and B okay if you saw Albert's talk yesterday he called it zip I'm calling it something else so I don't conflict with the zip methods in standard library we can define a syntax class that adds these methods so that anything it's an F of a if there's a monad instance you get these operations by syntax and we can make some more we can make some derived syntax and and these operators are interesting what they do is they tuple the things together and then throw away one half of the tuple okay so I call them right shark and left shark the intuition is of the value on the right or on the left is being eaten and what you have left is just whatever was left over okay so with all this stuff let's look at our effects again let's talk about option again we've seen a monad instance for option we saw a fishy instance this is a monad instance I went ahead and wrote out how flatmap works here so what we'll do is we'll inspect F of a if it's a sum we apply our F to that value otherwise we return none okay does that make sense to everybody more or less okay so so notice that this method could return none all the time just always return none and it would type check okay but it would break the right identity law okay so this is why we check our laws when we implement type classes it's very very important to do so okay type checking the Scala is not quite expressive enough to prove that stuff in the types you you've got to you've got to do it as sort of a second pass all right so we're Scala programmers we've probably seen option used in for comprehensions so I'm going to show the tuple operator for this one we have a validate method that just ensures that a string is not empty so we can say validate Bob validate dull and we'll get a pair of Bob and dole if either one of them is an empty string we get none back okay so that's interesting now this next one what we're doing is we're using the left shark and we're throwing away the left value and we just get some dole in the bottom we're using left shark but the left one fails so we get none out okay so even though the value even though we don't care about the value that's yielded on the Left we do care about the effect right that's very important so it's just there for its effect okay the last one is interesting because it's the same as this one right so with option we can flip the values around and flip flip the shark around and it does the same thing okay and this is not true in general it's true of option because option is a commutative monad so but in general it's not and we'll see some where it's not the same I'm gonna have to hustle here talk about either here's the instance you will trust me that it's right so what we can do is we can have a validation thing that says again if the string will pass it some kind of a tag and then a value and it'll and it'll either return the value if it's not empty or it will return a complaint on the Left saying that something is empty so we can make it a method to validate someone's name takes their first and last name and it validates that that they're both non-empty so we can validate when you validate Bob Dole and we'll get right Bob Dole ballot name validate the name and if either of them is empty we get a result that that says that says it's empty but so we kind of get our exceptions back but we don't have to talk about them all the time they're kind of they're kind of ambient there's no mention of these failure cases in our validate name which is kind of nice let's talk about list the the Monad for list just smashes the lists lists together with flatmap so I want to show you the tuple for list which is kind of interesting because I assume we're scholar programmers we've all used lists in a for comprehension which is map and flatmap the tuple operator gives us a Cartesian product it gives us every combination of values from both lists and the reason I want to show this to you is that if we use the left shark operator and we throw away all the numbers we get X Y X Y X Y but if we flip them like we do that we did with option we get x XX y YY so list is not commutative okay so it's important to understand that these effects even effects that are weaker than monad that don't have data dependencies among them can still have dependencies between them on or during dependency for the effects so it's a very important point I'm going to talk about reader super super fast all reader does for flatmap is it runs one value Minette with the environment with the that's passed in and then it computes then it gets the new computation and runs it as well so so here we have a path method that takes a host and it returns a string we have a length that takes a host and returns its length for some reason and now we can write this program it constructs a path and it gets the length and then it prints out a message and now we can run that passing it a value and it gets this google calm out of the reader but the reader is not mentioned anywhere in here right so we have dependency in that injection in a pure functional way we're not talking about this parameter all over the place it's sort of down in the plumbing which is which is nice okay let's talk about writer actually we're not gonna talk about writer because I have to introduce my ma noids to do that but the the gist of it is you can get logging back all right state really quickly the idea for sequencing state together is you run the computation you get the answer in the new state and then you propagate the new state when you run the second computation and that's all I can say about it here's an a state computation for generating a random number so it takes a seed and it produces an int so what it does is it it computes it computes this this modular operation to get a pseudo-random number and then it returns it as the new state as well as the answer and now we can create a d6 for rolling for rolling a value I guess from 0 to 5 actually I should have added 1 and then we can construct a bigger computation will compute to d6 plus 2 and it's it's pretty cool right because we have we're not talking about the state at all it's completely threaded through in the plumbing and we're writing an imperative program that looks like it's using a side affecting random number generator because we have d6 mentioned twice here okay and we could run this if we run it with 17 we'll get 10 as the total and then this gigantic number is the new seed we can compose that again we can run damage twice and and run it and then we'll get two values back or we can even tuple it if we want to all these operations work it all generalizes once you have once you have this notion of monads there's all of this stuff that you can do without thinking about what the particular effect is which is extremely powerful it gives us a huge huge possibilities for abstraction alright that's it not quite this is just a taste okay there are a lot of effects there are a lot of ways to classify them the operations we've defined actually sort of following concentric circles we have things that just have map things that have map and zip map zip and pure and so on and these are functor apply applicative a monad okay but there are a lot of other ways to classify effects okay so this is the rest of the cat's core and scholars headquarter like similar there are a lot of different families of effects and there's a lot of stuff to explore so and I hope this is piqued your curiosity thank you [Applause]