Analyzing Functional Programs

scale.bythebay.io: David Cleaver, Analyzing Functional Programs

Recording: scale.bythebay.io: David Cleaver, Analyzing Functional Programs

you i'm dave cleaver Who am I I'm a senior principal software engineer at Comcast part of that role lets me have a lot of freedom to sort of play with fun stuff that I find kind of cool so you get to all suffer through the latest stuff that I found fun and kind of cool so we're gonna start at abstraction I love to abstract out stuff in code I find you know people who counsel you aren't gonna need it I've always needed it I've done it all the time abstracted things away found that I needed it later and when I was asked to like make a change I was able to say hey yeah it's easy it's all abstract it's done right so we want to separate the what from the how we want our code to be clean we don't want to see the underlying junk that that makes up how we actually get things done we want to see exactly what we're trying to accomplish we want to utilize simpler implementations for testing this is the examples you always see around you know I don't want a test in future I'd rather test in something that's synchronous and yeah oh my other life nice thing that I like to say that I didn't put up here I want to late bind everything everything I possibly can I want to make that decision as far down the pipe as I possibly can and that leaves me effects flexible to make that change later if I need to change that decision if I change my mind if I want to expand on it whatever I want to do I want to late bind as many decisions as I can I do that in code I do it in architecture everywhere I can put things off in terms of decisions I will do so so there's two techniques that I'll talk about today around this in functional programming tagless final and the free monad and we're gonna start we're going to start with tagless final so tagless final to work with that we're gonna we're gonna declare treat and we're gonna abstract out the effect type you know I know Rob talked yesterday about calling these things effect so we're gonna abstract out our effect and then we're going to write our operations what do we want to do in this case I based all my example on Paul Cleary's Scylla pet store I needed a domain and I said oh wait Paul has a domain and he already does a lot of this tagless final stuff that I want to work off of so our operations are to put an order get an order by ID or delete an order by ID pretty simple and then using this isn't that big a deal we're using it's actually pretty simple we look at we create an order service we have Strack tout the type again I don't want to make any decisions I'm gonna keep from doing that and we take in our order repository algebra as an argument and then we can write I actually I have to confess I added this to Paul's code because I needed a more complex example I write this update status method for example and in there you know I'm gonna take in the order ID the status I'd like to change that order to in this case I put a restriction on my effect it has to be a monad and the reason it has to be a monad is because I want to do this nice for comprehension that we see here right and it's going to return basically it either wrapped in my effect essentially that's what that either T says so I'm gonna return or either an order error or an order now we simply call the repo to get the order or we took return order not found or if we've got one we're gonna copy it change the status and then we're gonna put it back into the repo right what I want to say is all right here and I'm not concerned with how I get things out of the repo whether or not it's in future or tasks or just gotta you know cats effect or whatever I don't worry about any of that right and ultimately I yield out the updated order if I've completed everything successfully so that's how I use it now I want to actually at some point I do actually have to make decisions and it's unfortunate but you know so we write a production interpreter this is straight out of Paul's code this is our the do be order repository interpreter we're gonna extend our algebra and we are gonna put the restriction on our effect type again to say that it has to be monad because we do some nice for comprehension stuff in there and we're gonna take a little bit of information we need for do B and then you know I skipped some stuff that was in there that isn't all that important around setting up your transactions and and things like that and you'll see I eliminated the sequel I don't write sequel I don't want to claim that I do right so we have an implementation for our orders here's how we put an order for example and we're gonna you know build sequel we need we're gonna update with the unique generated keys we're gonna do everything we need to do to get this done and I'm sure we've all written this code at some point except me I don't write sequel so right and then the other thing we're gonna build is a test interpreter because we don't want to test in whatever effect we were running in we don't want to test with a real database all of that all of that jazz so that we do the same thing again this time Paul was a little looser with his restrictions we only need it to be applicable e we're not gonna do for comprehensions but we want to be able to do some some of the stuff that applicative gives us on our effect so we won't worry about it too much right worry this is all gonna be synchronous and I didn't show it but we have some you know setup of cache information some random number stuff you know and we and we write a very synchronous implementation that just sticks stuff into a memory cache pulls it out of the in memory cache when we need it and so on and so forth it's all pretty straightforward so what can we do with that we have that testing implementation we can write unit tests you know we can write our property based tests using Scala check if we want to but that has some some limits right we can test our known inputs those are our unit tests we can test our possible inputs those are our our scholar check tests right but we test these under what we considered normal conditions normal conditions are rare I put something in the database and I get it out again right those are those are the kinds of things that are normal conditions I don't know how many of you have actually worked in say a distributed environment sometimes you put things in and what you get out is not what you put in because somebody else put it in or you know the famous last Rite wins or as I started calling it the other day other writes lose right so we kind up and we can't want to be able to test that stuff too because that's the stuff that we're actually going to find it production that's the stuff we do find in production and have to solve so I want to talk about generating programs right we want to use Scala check we'd like to derive the possible outputs of our dependencies using gen given the inputs to those dependencies and that's using something in Scala check called cogent now what cogent gives you is essentially turns a value into a random seed to plug into a generator to give you basically a generator that's created from the value or dependent on the value that you were given and we'll see it's just doing that right so let's build a generating interpreter same code we had before kind of right we want to extend our algebra but we're gonna put it into gen now there's a nice Scala check cats compatibility library and that's what I use here to give me that monad instance that I kind of need later on and well we need to take in a gen that generates our options of orders and then a generator for our Long's that we're gonna have in there is IDs and then we want that cojan for our long inputs sometimes we given an order ID and we need to be able to generate an order based on that it's not really that difficult as it turns out we can take that order we can generate an ID here we just kind of say we're putting so we take the orders ID we make a constant generator for it otherwise we gen an ID from the long so if we basically this is saying our order has an optional ID so if we don't have an ID let's make one otherwise we'll just use the one we have and then we're just gonna copy and set the make sure we set the ID on that order we're not actually putting anything anywhere we're just gonna yield out that generator similarly on get here we want to actually take our input our long pass it to our coach n so we pass in our order ID and we pass in our response generator and that's going to generate us a generator for options orders that are based generally on whatever that order ID that we gave it is and the same thing delete looks pretty much the same so it's kind of fun code to write all the Scala check stuff all right but this maybe not so useful yet because we still don't know what we actually did all we know is we get some random output from our code so we don't know why we got that output we don't know what our code did so we need to go and trace the code a little bit so we're gonna look at create a new trait because you could trace in strings but yuck so we're gonna make it do treat for our order repository tracing we're gonna make some implementations and we're gonna capture our inputs to each operation and we're gonna capture what each operation was so we get our trace put we take the order in and we just extend our base trait trace repository our trace implementation tree so we have to take that now and do something with it because this doesn't do anything it's just data so we're gonna build a tracing interpreter this one's fun so we're gonna implement our algebra again this time we're gonna make our type coming out of the algebra we're gonna fix it - we're still gonna be we're gonna allow some underlying effect type that we don't care about ultimately it'll be Gen when we get there and we're gonna have writer T so what we want to write is a list of these traces right we want to generate a list of every one of these trace objects that we are going to create but we want to do that in whatever effect was and and in our type what we open to whatever the type of the operation is so I write a nice utility method right I want a log-log is going to take the whatever that trace operation is and then it's gonna take something in or effect some operation in our effect that returns an A and then we're gonna wrap it up so we'll tell the writer monad hey here's our our message here's what we did we'll get that result and we'll lift will basically lift that other program up so that it's in the right context and that'll be our result we'll return that and then we use this nice utility method to write everybody else all right put we make a trace put we wrap it up and we send it the wrapped puts operation so we always work off of this wrapped algebra so that we can be we could use this theoretically and trace our production interpreter if we really wanted to so get pretty much the same trace get take the order ID call the wrapper and see what happens so why would you want to do this so you're crazy maybe you want to test code properties so that code that I showed you at the beginning I could write something that actually says hey what are the I don't know do I ever call delete in this code are there any conditions under which things I don't want to happen could happen are there maybe I'm looking at you know sometimes you use dependent functions and it turns out that they all went and fetched the object from the database and you didn't realize so you called get like three times you could test that I never call getting more than once I never called delete so here's a you know we'll write a test never delete when updating the status now my code it was simple we could go back and look at it and tell that it never calls delete but if your codes much more complex it's gonna be a lot harder to tell so we're gonna build our interpreter right we want an order gen interpreter so we give it our gen option luckily Scala check is in use in the scallop pet store so we already kind of have an arbitrary instance of our order that we need we have basically we can generate orders whenever we want Scala check gives us the ability to generate options of things that we can generate we're good to go and also you know positive numbers pretty straightforward we'll build our trace interpreter wrapped around that gen interpreter so now we're generating random sets of these lists or we could generate random sets the lists we'll pass that into our order service that's what we want to actually test and now we have to build an arbitrary instance for these walks through our program so we're gonna have an arbitrary list of the trace objects that we're looking for and the way that we do that we'll call the method under test here I give it actual arguments set and fixed I could have generated the arguments as well given it random arguments and then what we get out of that method is ultimately going to be something you know either T wrapped around my writer tea with my trace stuff and my Gen so I got to do some unpacking so I start by getting the value that unpacks my my either t1 level and then I want to get the stuff that's written so that untaken it runs it and just gives me the written stuff it ignores the return value and then I can write my property I can say for all the walks in that code assert that none of them ever called the lead and and this runs and and luckily my simple code never calls delete although I did added the lead in there just to make sure that this would fail miserably in that case right so I I this is the stuff that got me excited right random walks through your programs testing I think you could extend this you could capture what the actual limb you captured the inputs and the operation but you could also capture the output of the operation and you could do further more complicated properties you could make richer interpreters if you really wanted to so you could make your interpreter do more reasonable things within the bounds of what your underlying dependencies gonna do for instance most of the time when I put something I'm gonna get it sometimes I don't I want to model that but I don't want to model complete randomness all the time for simplicity sake I modeled complete randomness so this generates for us these this is what walk is over a small number of runs right we have a trace get five trace get five we probably return none there and our code didn't error we have a trace get five and then we put now hey guess what puts we got a random order out this is where I said you could be reasonable and I wasn't we get a random order out so our IDs look funny but it's okay and and you see you know the code was simple so we get simple traces so what else can we do we talked about briefly we talked about free monad at the beginning as an abstraction technique so with the free monad we can encode our operations as classes we can wrap them up in the free monad and then happiness happens right so let's start with our free operations these are gonna look really familiar because they're almost exactly what I had for trace all I'm doing I've changed the name a little bit but I've added an output type to each one of these right so put op becomes pretty much the same as trace put but it adds that order type parameter to the end of the end of the tree and get up a similar and delete up is is also they add the option order output that I had so now I've got my free algebra these are my operations encoded as classes it turns out I already did that above but I've made a couple extensions that'll let me use the free monad so when I add the free monad into this you're probably thinking oh man we're gonna scrap all that junk that we did back when we did the final tag list right like all that's useless now but it turns out you can reuse it so I can make my order repository free and I can say I still don't want to know what my algebra is in F this is like a good free habit and I can extend my order repository algebra again and I can return a free monad with that algebra as its core right as part of the plumbing I'm gonna take this implicit inject Kay all right this allows me later on when I want to to combine algebra together this is the glue magic that allows me to combine a lot of algebra together so I could have just said I could have left off the F and just said it's always order a repository op but then I don't get a lot of options to mix things later and I want that power so what I'll do is for each operation I simply like free has this nice function inject which will inject my operator my int mic instantiation my instance of the operation into that algebra and all that's taken care of for me sorry done I do that for each one this is almost what we had for tracing so now how about the generating interpreter what's that gonna look like turns out I'm really lazy and I didn't want to take up your time reading a lot of the same code again so we're gonna create the order repository AAPIs gen and we're gonna cheat and we're gonna take the interpreter I already wrote in the final tagless and this time we have to do things for the free monad we're always gonna see these squiggly arrows and the squiggly arrow says take this type with a hole in it right it's a function from this type of a hole in it to another type of the hole in it essentially that space for what the return type is gets transferred through this function so I can take any order repository op a and generate a gen a from it and then I have to implement to implement the the squiggly arrow I have to implement the apply method that's gonna do that operation I want to match on any of my operations that I created and for each one I'm just gonna delegate to that interpreter I already wrote so that I don't have to write it again and so you don't have to see it again but this is kind of neat because I basically didn't make a decision I was late binding again right I chose final tagless in the beginning but at some point later on I decided hey I'd like to use free and nothing about the choice that I made at the beginning has stopped me from using free so the other reason I like free is when I write tracing when I write tracing with free I can be really super generic I can write a tracing function that will translate anything into a triest version of itself right so what I want to do is take any F that can be turned into a G and I want to trace it and so I implement I take in sorry I take in my squiggly arrow function for F - G and what I'm going to produce is one of those functions that returns my writer T that stores up all those operations it's gonna capture them all but it's still gonna give me a G out which is what I want ultimately so the apply is is really simple it looks a lot like the log method that I wrote before right except now the thing I'm logging is always passed in and that also is the thing I'm logging so I have some advantages so I can tell in the writer context I can say hey add this operation to my list and then lift the translation up into the writer so I run my a sub translation and I just lift it up and I yield out that result and that can use this for anything any algebra that I write can use this if we look back at what I wrote before for tracing I had to implement the final tagless interface so I had to implement the put method and the get method in the delete method and if I come up with another interface in another algebra I have to implement all those methods so I have to write trace many many times and I don't really want to do that if I can help it so oh here I broke down all that stuff I already told you about all right so I can go back and I can test my code properties again this is the exact same thing we tested before never delete an update made a couple modifications I make this Jen interpreter which I you know build up it pretty much the exact same way I did before I make my order repository free and I pass that into my order service and I need one other piece which is my interpreter for free so I need to take trace and I need to wrap it around my order repository op is Jen using my order Jen interpreter because I was lazy I won't stop pointing that out and then I build my arbitrary walk again this time it's a little bit weirder because I have to account for that a value but I just kind of say it's X I don't care what it is right this is a list of these things and I don't care what that what's filling that type hole and so now I create my I call my order service update status and I get the value out just like I did before but now I have to do something a little different now when I've gotten a value out now I have a free monad wrapped around this so I got the either I have now a free monad with an either inside of it kind of thing so what I call for free is fold map and when I call fold map I give it that interpreter I give it that function fold map a look at every single I basically have a big data structure in my program and it'll look at every single step in that data structure and it'll give it to my interpreter and say please turn this into what I need it to be and then it'll chain all of that together for me it does all the magic and so now what I have out is it is the gen I wrapped with my o my writer tea with my Gen in it and it's all scary so I need to get the written value out again when I'm all done that so now I now have like my writer T wrapped around my Gen with my list of operations and I need to get the written bit out I could also get the result if I cared in this code I don't really care right and then this code doesn't change my testing whether or not I delete opt all I did add that little extra bit of existential parameter at the end to say hey I don't care what's in this walk I'd like to know what you know I just want to check if the delete opps exist so we didn't really change this very much but some of the power that we gained is we gained the ability to combine free gives us the ability to combine interpreters and to combine algebra to gether so now if I have multiple of you know these order repository algebras you know maybe I have an order repository and I have a pet repository and I have a you know authorized users repository I can combine all of those algebra to gether using some of the free mechanisms right which unfortunately I don't have a slide for but I can combine them all together and I can trace them because the combination is still just data it's just Co products of values and then everything is stored in basically a bunch of either's that say like it's either you know from the order repository algebra or from the pet algebra or from anything else so I get lots of like left left right left rights but that's okay and when I combine them together I can still do these kind of tests I can still test over the combined algebras that's a little bit harder in the original final tagless as you can tell I like I love free probably more than I love final tagless it's a little bit harder because I'd have to come up with some I'd have to combine all of those trace objects together in a similar way I'd have to figure out all the left's and rights and figure it out and I think Katz gives me some mechanism to make that easier but I still have to to do the work to do that all right so this all went really fast so analyzing functional program so use tagless final or the free monad I don't think this is an either/or choice as I kind of pointed out in this whole presentation right start with tagless final it's a great way to abstract out what you're what from your house and to separate your implementations that have all the complex future taskstream whatever behavior from the code that just does business logic and you want that separation if you want to add the free mode ad later because you like to test and you think it's useful for testing or because it's just a better way to implement what you're doing then do it right add it in later and you don't have to change a lot of code to do that so test not just your inputs and outputs but exercise the behavior from your dependencies right you don't discover that stuff until you actually stick it out in production and you don't want to discover it when it's out in production and check what your code tries to do there's all I'm sure we could do a lot more complicated stuff than I did I did something super simple but I can imagine how many times do I call this method do I make sure I don't call it more than this number of times you know things like that and and by making these properties I ensure that those things remain true across the lifetime of the code when someone goes and modifies the code I'm not suddenly going to get deletes in the in the updating status method right nobody can add that without failing a test I highly encourage you to take a look at what Paul's done in the Scala pet store was very useful for me I needed to do domain he had a domain and it's he's got a lot of cool stuff that introduces at least final tagless he doesn't introduce free but he does introduce final tagless throughout kind of the whole construction of the scala pet store and then my example code you can find all the code in these slides at comcast samples Scala pet store analyze FP and so that does add the extra freak instructions it's got both of my versions of the test all my interpreters all of that information so you can find me on twitter and github at des cleaver and we're hiring so check out jobs Comcast any questions great ah yes I wish I knew no yeah I actually I believe it's because it was named when someone said oh I finally been able to make something tagless so tagless refers to the fact that under that implementation you're not creating classes so you're not creating objects that have like tagged information that's stored at runtime you can kind of avoid all of that stuff and so I think really it's named because someone said oh I'm finally tagless done that's what I'm gonna call it right names are hard yeah so Katz used to call it natural transformation now they call it function K so it is the same thing yeah I I I never asked right oh it's - the law Oh interesting so also you know really it is just function at like a higher kind of level so that was probably part of the reason to rename it as well and it you know I'm sure there was lots of jargon and other fun stuff that you may not understand in here like feel free to reach out to me on Twitter here at the conference will be here hopefully for most of the rest of the day feel free to come up and ask like I love to teach this stuff right I teach this stuff at work I'd love to teach it I love to explain it to people there's no dumb questions there's just asking the same question multiple times and that's not even necessarily bad so alright any other questions yes right if I'm running free how's it going to impact the efficiency of my life code I haven't done the tests I think a lot of times we we fight for efficiency in places we don't need to that was my I gave a nice love letter to free last year and that was my opinion then to write like a lot of times we worry about efficiency where we may not need to if it's not efficient don't do it like take it out do change it to something else but at least you have this tagless abstraction to kind of like still make your code clean but like hide the efficient stuff under the hood I hope that I kind of punt it a little bit but and there are there's freestyle I don't know if you've seen it they do a lot of stuff to try to make some of that pattern-matching stuff go away and be faster under the hood and they support this kind of tagless final style and free monads if you want it and they kind of handle all the combination and they and they try to do things much more efficiently if that's a concern cool great [Applause]