Scale By The Bay 2020: Justin Heyes-Jones, Applicative: The Origin Story
Recording: Scale By The Bay 2020: Justin Heyes-Jones, Applicative: The Origin Story
Um So, yeah. Uh today uh we've seen a lot of exciting new things in in Scala. Scala 3 is coming. Uh Loom is coming. So, today I'm going to talk about something that is maybe 10 years old. It's a It's an older tech. It's an older thing. Um but learning this will last a long time cuz it's a very useful technique
Um At Yob Works, we do quite a lot of Scala and the code there'll be some Scala code on the slides today. Uh but hopefully you can follow along with the concepts if you're not a Scala programmer. So, what I'm going to talk about is in three parts. So, I will begin with uh an introduction to what what typed pure functional programming is and uh what all the pieces are. And then we'll talk about the origin of applicative. That's the main part of the talk. So, um what applicative is, where it came from, and how it's implemented, and then the last part of the talk, we'll see how you can use it in your programs. Um so, you don't have to rewrite your program completely as a pure program
You can just drop this in like a like a new feature or a new tool. So, here's an example pure function. And this is a function that um like all Scala functions, it has inputs and outputs. So, here it takes a single integer, returns a string, and it's just going to turn every integer into a string. So, there are various things that make a a function pure. And uh conceptually, every pure function is just a mapping of values. So, you can conceptually think of it as only a mapping. So, look at the diagram here
On the left-hand side, we have um every every single value every single little possible int uh is on the left and it has an arrow to uh some string on the right-hand side. And these arrows are fixed in time. So, every time you call the function, you can just follow the arrow with your finger and get the answer, and it's going to be the same every time you call that function. We also uh in pure functions don't have the concept of missing values. So, there's no integer um that doesn't have a string representation in this case. Uh we don't have any concept of null or none. Uh you're always going to get the thing that you uh the thing of type B, or in this case, the string. You're always going to get an instance of that when you call the function
Another thing we don't have with pure functions is some kind of error channel. So, we don't we don't throw errors, we don't handle errors, there's no exceptions. And finally, there's no side effects. So, in this case, uh we're stretching the diagram a little bit, but if you follow the arrow from 22, um and then it goes and looks up in a database, uh this is no longer a pure function because the database might not be there anymore, or someone might have um changed the data. So, the function won't be the same anymore. It's no longer just a simple mapping. Uh if you follow all the rules of being a pure function, uh you get something called referential transparency. What that means is you can replace a function call with um the result of that function call with a particular value
So, here we have a function that just increments a number. And the code on the left calls the function twice and adds the results, and then prints it out. Um the code on the right uh caches the function. So, it only calls the function one time, and then it adds the cached result, and then prints it. And these two programs are exactly the same because um because we have pure functions. And um this is a useful property. In fact, all we need to do to break referential transparency is add a very simple side effect. So, all we do here is uh increment and print is actually going to print something, so it has a side effect
Um side effects are anything you can detect from when you call the function. Um and we're going to see different output when we run these two programs. Um so, even though this is a very simple effect, you can see how the more effects you add, the more uh you have to start reasoning about your code. So, why are pure functions good? Um pure func- pure functions have a bunch of advantages. Um they're easier to reason about because you don't have to think about errors, you don't have to think about missing things, you don't have to think about side effects. Um they're easy to compose for the same reasons. And they're easy to test because you don't need any mocking frameworks for your databases or um you don't have to think about the internal state of any objects. Uh you just call the functions and you test that the value you get back is what you're expecting
So, pure functions are growing in popularity and you can think of this as the analog to immutable data. So, immutable data structures are starting to become popular, too, for the same reasons. So, if you look at um uh React Redux, for example, that brings immutable data to the mainstream front end programming. And we're getting immutable data structures in in Java 14 in the form of records. Um and the reason people like immutable data is it eliminates whole classes of errors and it reduces the amount of um cognitive complexity that you have when you're thinking about how your programs work. So, here's an example of pure function. So, let's say we're we're running a company that can uh grant people loans and it needs to take in some information about the customer and and it will return a loan decision. So, to make this a pure function, it has to take in um um take in data uh has to return a loan decision, no matter what happens
So, this we're not going to throw any errors. Um and we don't have any side effects or anything like that. So, you can imagine if you build a lot of your uh important business logic using pure functions, you get a lot of the benefits that I talked about uh in terms of testing, composition, and so on. And um Sorry. So, you get a lot of benefits um and then the next problem becomes how do we utilize this in a real program? Or how do we write useful programs without side effects? So, the answer to this question um was figured out by the Haskell people in the '90s. Um what we're going to do is wrap side effects into data structures or data types. So, instead of dealing with statements that do things, we're going to just wrap them up in a data in a data type that describes the act of doing something. And there's lots of different effects
So, for example, we can get back the concept of missing values by introducing the option data type. Um the either data type gives you back errors, so you can have a computation that succeeds or it fails for some reason. And um what we'll be looking at mostly today is the IO monad or IO data type that gives you the ability to wrap something that does an action on the world, and um it can handle things like errors, concurrency, and so on. So, we talked about pure functions as being uh nothing but maps, the way to map values to other values. We're going to look at um two more mapping functions, and those mapping functions live in these type classes, uh monad and functor. So, monad and functor came from category theory, which is a branch of mathematics. And um the reason um Haskell adopted them is they map exactly to um the kind of mappings we want to do in functional programs. So, in other words, we'll see in a minute how they can help us combine um pure functions with side effecting functions
So, the functor type class and what we mean by type class is just a a behavior um and when uh what you do is you implement instances of the type class. So, for example, we'll have an instance of IO that can implement um mapping for the IO type. So, functor has this one function that has a map um and if you look at the type signature, what this means is it can it can take a as an input a an effect of some kind, here FA, and it would and it can return an effect of FB. So, essentially, we're just mapping from an FA to an FB. And the way we do that mapping is with a pure function. So, this is literally taking a pure function and applying it to a side effect. So, let's have a have a look at that in uh in real life. So, we have a function called get loan application, and this function takes a pure value, uh which is in this case some identifier for the customer
And then it's going to go to the database or it's going to do an RPC call, something like that. And it's going to come back with the loan application information that we need, and we it's going to be wrapped in a IO data type. So, it's no it's no longer just a pure value. We've actually um when we execute this, it will create a description of a program that goes ahead and gets the data for you. Um In the in the lower third of the slide, you can see this in action. So, we call the get loan application function, and that will return an IO loan application. And then we use functor's map, which will map that um using our pure function to give us an IO of loan decision. And what we've done here is just build a description of a program uh and then if we are going to run it, we can use this unsafe run command
So, what we mean by unsafe is you're leaving the pure world going into the into the real world of effects. Another thing um another mapping function we need is flatMap, and that's in the monad type class. And you can see here that the type signatures are very similar. We're we're going to map FA to FB. Or in our case, it will be an IO loan decision to an IO unit. And this takes a different shape function. So, this one takes a uh pure value and returns an effect. So, in other words, this sort of takes a a program that's in progress, takes an IO, and then it applies function that creates another program, and it lets us sequence them together
So, here's an example of using that uh in our program. So, let's say we have a program uh that we were developing. So, we get the loan application, and then we map our get loan decision. So, now we have an IO um loan decision. And what we want to do with that is something useful like print it to the screen. Um in real life, maybe you'd send it to you'd send it over a message bus or put it in a database. Um but the the shape of the function is always going to be the same. It's going to be something that takes a pure value, in our case, the loan decision, and returns an effect
So, in this case, it's an effect with a unit, which means we don't really care about the return value. We just want to print it to the screen. So, then we've wrapped the actual action of printing it to the screen in an IO. So, now our whole program um first of all, we call the um get loan application, and then we we map it. So, this is um first we used the pure mapping, then we used the Functor mapping, and then the last step is to use flat map. So, that's that's the monad map um and that gives us the whole program. So, now we can run the program and um with between functor and monad and pure functions, we've been able to build a useful program. Um so, flat map is is so common that we have special syntax for it, the full comprehension
So, you can see the little yellow arrows there are basically um flat maps. So, um now we come to the middle section. Um so, applicative, where did applicative come from? Um this is roughly uh 10 years after monads and functors started to be started to be used, uh this paper was published and it's one of the great uh functional pills and um the uh what we'll do is talk about what the title means first. Um applicative programming with effects. So, applicative programming just means applying a function to an argument. So, you take a we take these two pure functions here and um they they take uh pure parameters, pure arguments, and the act of applying the function and replacing it with the result is is applicative programming. So, that's that's pretty common um every programming language looks pretty much like this. Um the there are uh other ways you can do it
There's concatenative programming. Uh I'll put a link in in at the end about that, but concatenative is used in the fourth programming language. Um it's used in the JVM byte interpreter and the uh CPython byte interpreter. Um but mostly we're familiar with applicative programming. So, that's all that means. So, what is applicative programming with effects? So, that's the interesting part is the with effects at the end. So, this is the idea that we would like to take a pure function and apply it to effects. So, the function has say two arguments or or more arguments
Um we'd like to map it somehow. And we can't do that because the shapes the shape's not right. The the types don't match up. So, that's why we need something special to do it. So, here's our fourth mapping function, uh the app. So, app again once again uh it maps an FA to an FB. Um what you'll notice is is the highlighted um A to B function is pure function. But, that is that is in itself an effect
Right? So, that's the the main difference. So, let's see how that works with one argument. So, we take a pure function that increments a number and we want to apply that to an option. So, we can use the app function to do that. The only problem is to match the signature, we need to lift the function itself into the into the option effect type. So, that's why I call the the sum constructor there. So, it takes my takes my function, turns it into an option, and now I can use app to apply that function to the option. Um so, you can see in the output at the bottom that we can we can now uh increment an option
So, what we've done so far is not that interesting because we could do this exactly with a functor. It gets more interesting when we have multiple arguments. So, let's say for two arguments, um we do exactly the same thing. Uh we take the add function and we lift it into the option type using the sum constructor. So, now I can go ahead and and add um the first number using app. But, then I have to call app a second time for the second parameter. So, if you look at the um if you look at the highlighted section the highlighted uh identifier there, to make this work, we had to curry this function. In other words, when we call the first app, we consume that first parameter, and when we call it again, we consume the second parameter
So, following this pattern, we can call we can do applicative programming effects. So, we can take pure functions and we can apply them to as many arguments as we want. So, if you find that idea of carrying and partial application confusing or ugly, um that's that's fine. I mean, it looks a lot nicer in Haskell where we where we got it from, but in Scala, it's more common to use this derived function. So, we can use map two, which is essentially the same as the last slide. It just says, "I'm going to take two options, and I'm going to apply the pure function you give me to those options." And there's also map three, map four, map five for different numbers of arguments. So, what the paper goes on to talk about is the applicative type class, which as we saw in the diagram before is sort of lives in between functor and monad because it's more powerful than functor. It can do things that functor can do, but it's more free than monad
As we'll see what I mean by free later. So, applicative just encodes the the pure function, which lets you take pure values and lift them into effects, and the app function, which lets you map effects. And and as we saw, it gives you the ability to do the applicative programming with effects that we're looking for. So, in the paper, they say, "This is the story of a pattern that popped up time and time again in our daily work programming Haskell until the temptation to abstract it became irresistible." So, unlike monad and functor, which were kind of borrowed from from mathematics because they mapped they they matched the the mappings we wanted to do, applicative is just a pattern that they noticed was useful. So, there's three examples of useful programs you can write in the paper. And we only really have time to look at one, so uh but this is a good one. Um the idea is sequencing commands. So, you have a list of effects and what you would like to do is execute them all and turn them into a list of result values
So, you're going to take a um uh a list of IOs and return an IO list. So, this is actually a very useful thing to do and uh it's actually quite common in Scala for people to ask um I have a list of futures, how do I get a a future list, right? And it's exactly the same question, just with IO instead of future. And the answer in in Scala is that we we have uh future sequence. It's in the standard library and um it does exactly what we're going to be talking about. So, what I've done here is taken that Haskell code from the slide and um converted it to Scala. And um what it's doing here is iterating over the list of effects that we gave it. So, we're using flatMap because we need to get into the into the IO of each one and get the value from it. And then we want to append that to the um the rest of the list
So, we're we're building up an IO list. So, in this slide I've replaced the recursion with a fold left just to make it easier to read and and more video idiomatic uh Scala. And the last step is we don't really need it to be an IO. Um we only need it to be a monad because uh every monad has flatMap, every monad has pure. So, why don't we just go ahead and get rid of IO and replace it with a uh higher kind of type F. And then now we can use this for any monad. So, we're already more general than the standard library version. So, the next part of the paper is we could avoid the need for names to wire these values through to the point of usage if we can if we had a kind of effectful application
So, in other words, what they're saying is why do we bother with that flat map getting that value when all we really want to do is say just append this value to this list using applicative programming. So, in the Haskell code there, even if you don't know much Haskell, that that last line using using applicative is is a lot simpler than what we had before. And it also expresses more um it also expresses more directly what what the what the goal is the code. So, here's the same thing in Scala and I've gone ahead and replaced it with the map two. So, now what we have is sequence and no longer needs monad because map two is applicative, right? So, we can go ahead and make that sequence function work for any applicative. We could go ahead and make it work for different kinds of collections instead of just list as well because what we really want to do is anything that can be folded over we could use um but that's that's complication for another time and if you look in cats and ScalaZ and so on you'll see that they already do that. Um so, traverse if you ever listen to functional programming is talking they will often mention how great traverse is and traverse is built on applicative. So, we start off with our sequence function here
Um this is the function we've been building up to and then what traverse is is that quite often we might have a list of pure values instead of effects. And so, traverse lets you pass in a function that turns those pure values into an effect. Um so that gives you a more flexible function and it also means you don't have to traverse the list two times to to uh get the kind of effects you would like to get. So here's a simple program, uh print IO. So what this program does is print a string after waiting for 1 second. And um what we're going to do is traverse a list of uh strings and um when we run this program what we'll what we'll do is turn a list of IOs into an IO list. And once we get that IO list, we can run it using the unsafe run. So what you'll see is this function uh takes 3 seconds and it will print each word one at a time
And um So you might be wondering um why it um does them one at a time and whether we have any choice over that. Uh the answer is it doesn't have to be sequenced. It could be run in parallel. Um now we wouldn't be able to run it in parallel if we didn't have the opportunity to ditch monad, right? Because we we um we were quite happy with applicative. So what we can do is turn our IO uh from being um something that has a monad instance to something that only has an applicative instance. And we do that just by calling the the para constructor on it. So that turns an IO data type into um into the parallel IO data type. So it's essentially the same thing
Uh it just has a different implementation of applicative. So uh then we can just run the program and you'll see that the program now takes 1 second because all of the uh tasks are triggered at the same time. So you might be wondering how do we know when we have a typical program if something is going to be sequenced or if it's going to be parallel? So, there's a nice um nice pure pics about this called the monad applicative consistency law. Um or you might say uh once a monad always a monad. So, the idea is if something behaves like a monad, it should always behave like a monad. So, um if I change the type constraint of a program and then the program behaves differently, that means that people using my code have to they can no longer reason about the program as easily. If I change the data type, that's actually fine cuz that's something that I have to manually go in and do. And data types um represent um different ways of implementing behaviors
So, as a concrete example, let's look at um doing some data da- data validation. Uh so, we're going to use the either data type and to and the traverse function. So, we're going to take a list of numbers and um we have a function that takes each number and turns it into an either. So, if the data is valid, then we just return a right value. If the if there's something wrong with the number, then we'll return an error. So, you can see at the bottom the output for the success case is just a list and it's wrapped in a in a either right value. So, what we've done is we've just reversed um a list of eithers and turned it into an either list. Um here's the failure case
So, you can see that um this failed because we had a bad number and what it outputs now is no longer a list but just a left. So, it just says um I encountered a single thing that was wrong and here it is. And sometimes that might be the behavior you want. Um so, monads give you short circuiting. Uh monads give you sequencing. And yeah, sometimes that's good. But what about if we want to collect all the errors instead? So, this is an example of where changing the data type uh can change the behavior again. So, if we change um to validated, which you can think of as being a sort of parallel either, um and by parallel I mean it's uh not dependent on each other rather than necessarily running at the same time
Um but what validated does is either gives you a valid uh computation or it gives you an invalid. And it can actually um join the invalids together. So, in our case, when things succeed, we get a valid list. Um but when things fail, we actually get a list of all the failures. So, this is a great example of you want to change the behavior of the program, you just change the data type. And you can use traverse in both cases. An applicative. So, traverse is very flexible partly because of the flexibility of applicative
So, for example, if we use the uh ID monad, which is really just a simple wrapper, um you can run traverse on it and it turns uh into map. So, it really just lets us map over lists. Here's a slightly more interesting one. If you use the const data type, you can um append things together or fold things. So, what we're doing here is we just um run traverse on this list, we turn them into const data type, and all of the elements get folded using whatever monoid we happen to have around, which is going to be addition, so it gets the sum of the list. Um so, if you're not familiar with monoid, it just means um type that has a way to join uh join itself to other things of that type. Um we can also do a more complex example. So, this is a list of two poles, and um you can see that it's uh added the added the numbers and it's appended the strings
And that's just because these things have money instances, so they know how to join it join each other together. And uh it also knows how to join tuples together. So, um what we'll do uh is is uh finish up is look at a a more complicated example. So, because this talk is quite a quick one and I've had to talk really fast without breathing. Um what we'll do is uh um I'll I'll go through how the function works. You don't have to understand all the details, but you can just sort of understand the concept and uh you know, what it does. So, we have a function here that gets the time and that's an effect. And then we have another function that times an effect
So, you can use this to run an effect and it will return the result and also how many milliseconds the effect took. Um so, example IO at the bottom is a program that prints the starting message when it starts, then it waits for a period, then it prints a message when it's finished, and then it prints a a string. So, it's a simple program, but it's designed to be simple and illustrative of what we're going to do to it or do with it rather. All right, so there's a lot going on in the slide. Uh at the very top we're defining a type. Um this is going to be an accumulator uh type and we're just going to um turn each effect's result into this list of different things that we're interested in. And we're going to use const because we want our thing to when we traverse it, we want to do a fold. We want to fold everything together
Another thing that's going on here that's really important is we're using the nested data type. Um so, what nested is is uh I want to get the benefits of two data types and combine them. And applicatives compose completely mechanically. So, without writing any code, we can take any two applicative instances and nest them, and then we'll get the behavior of both uh without doing any extra work. Um then we're going to call the time function on our example IO. We're going to call the parallel constructor. Um and then we're going to map that to turn it into a const. So, what we ended up uh with here is taking our original pure values and traversing them and using this um one line of code to turn them into um a parallel, something that'll be executed concurrently, um and will give us some data that we can fold
And this is all in one traverse. So, the next thing we need to do here to to wrap it up, or rather unwrap it, is we need to unwrap the unwrap the program, then we need to run it, then we need to get the result. Um so, you put all those things together and you'll get output like this. So, you can see all of the effects started at the same time, um and the order is completely random. And then they completed uh one by one in the uh amount of time that they should have taken. And then at the bottom here, we've got all the different results. So, these are all results are all all these results are appended in in uh in in whatever uh monoid was available at the time. So, we got a sum of the total time of all the all the functions uh by adding together all the times
Uh we got the number of effects that we ran by just adding ones together. We got a list of all the return values, and we got a list of all of the uh runtimes for each function. So, uh it's a complicated example, um but you can see that there's a lot of power in in composition and a lot of flexibility um by combining traverse and applicative with different data types. So, some takeaways or ideas, um, pure functions just map values. They're simple mapping functions. Uh, functors, monads, and applicatives map effectful values. Um, data types can model behaviors at the type level. And composition at type level combines behaviors
All right. So, thanks thanks everyone that's um still alive and uh stayed awake for the whole talk. I have uh some some links here you can follow up on on the various things we talked about. And uh now I'll head into the spatial chat to take any questions.