scala.bythebay.io: Owein Reese, Don’t Blow Your Stack: Recursive Functions for Beginners in Scala
you all right rock on all right so I'm Owen uh I'm from mediamath we're an ID tech company we have offices all over the place I'm from New York though and we do a lot of cool stuff with Scala we have you know your standard big data not like the we're building something and once we get enough customers big data we're talking like you know we actually have petabytes of data but my team we handle a lot of we have ad servers so we're doing things with millions of requests a second and latency requirements on those requests I'm the order of milliseconds as probably one of the reasons why I came to the company and you know years I've been there I've been enjoying things I've been working with things in Scala and one of the aspects are one of the things that that I've used in this code is is recursion and some of these concepts so when I come to these conferences i often see a lot of really cool talks I really enjoy going to some of the more advanced stuff because you know these guys are doing really amazing things and I I get to feel really stupid listening to it but you know I often feel that there aren't enough talks therefore for a lot of the people that are rather new to scala like they doing a lot of o languages and they haven't really had concepts like like this like just here's recursion and here's what it is and here's no difference between recursion and tail recursion and why you might want to do this so this is going to be one of those talks where introduce a concept that's relatively easy to grok once you see it but it's very powerful because it it's sort of as a gateway drug into some some higher level abstractions things that I I won't get into but we're going to look first at a small example we're going to we're going to set up a situation we're going to see some imperative code how to look at that imperative code much you what you would see there then we're going to take that code and we're going to compare it to a recursive version of that code and then we're going to contrast it again to a tail recursive version of that code and we're going to talk what you know we were doing with tail recursion and why it's different from all these how the compiler season how it it can change and do what's called tell a tale called transformation and then we're going to sort of move into another thing which is a plugin I've been working on which adds a feature that language doesn't have which is mutual tail recursion so each one of these is going to build upon the other but I'm putting this up because if you have computers and you want to open up and work with this I'm actually introduced some live coding here and if you want to follow along i have it set up at this repo all you need is SBT and of JVM which if you're out a scala you know you are i should say conference you probably already have and there's actually a couple other exercises in there if you want to do on your own and you know if you want to speak to me afterwards or find me online or something i will actually help you I don't mind taking some time out to to go over this stuff if you have questions so let's start so we we're going to set up a situation where we have just a tree a tree structure and we're going to make an assumption that this tree structure is not empty that there's always at least a node so even if you have no of an empty empty that's what you're going to have we're also going to make the assumption that there are no loops it's a straight up tree so what we'd like to do is we'd like to to walk this tree and figure out all the leaves which ones are the furthest or not which ones are the furthest but what is the furthest point from the root node at and if i do this imperative lee i get this function of this function i'll just call longest at and if you're used to this style it's relatively simple you're setting up your search space you're setting up the value that you've seen and then you're going to you iterate through as long as as long as that search space has things to look at you're going to pull out the eyes or the value at the current place the note at the current and then you know you're going to leave whatever sales there and you're going to look at current you're going to say okay if I'm empty I'm I nothing more to look at and if I have something on the left to the right or both just just sort of append it to the front of this search so you are doing a this is sort of a depth-first traversal the tree and then I just compare what's my value now with the value that I've seen and take the greatest I could put this at the node or at the i should say the leaf valued if I really want to optimize but Max's and it's just like an if statement you know so that's it I mean this is the imperative version you know probably grew up you know if you're you're you know steep to know Oh doing exactly this in the languages that you've worked in up but I'd like to contrast that with what the recursive version and if you're counting that's half the lines of code we just went from 11 lines of code to five and they both produce the same results and yet if I look at this one I know exactly what's doing right away I mean this this is doing nothing but exactly what the algorithm says it's doing I'm finding the longest as a matter of fact you know if if you're looking at things in this state or i should say in this manner look at look at the boilerplate I mean in order to do this I'm setting up two things i'm setting up how to manage state the value that i've seen most of and what I've got to search through them because I'm changing what I'm searching at each step I have to sort of freeze where I am and capture that before I can move on whereas here you know I get my state management effectively for free if I'm at the root ode notempty empty and that's all it is well length is zero I'm no distance from that node and if there's something else to go well I'm just one more than the longest length of the child tree and if there's both the left and right well I'm just one plus the greatest longest length between either my left side of my right side and so if if i'm looking for a bug this being half the lines of code I'm probably going to make half the mistakes as a matter of fact when I was setting this up I wrote this one after i wrote the imperative one I looked at my unit test and I had a mistake my imperative code so yeah all right so tell gershon at this has some some sort of similarities to what we've seen in the imperative but you can see it's it's actually quite different I've I've set longest the way it is to keep the the signature the same but I'm actually doing an interaction to this this method i'm just calling find a lot of times you'll you'll nest the function within your call and then recall it that way but here it is again i'm just i have a search space and at each point i am looking to see you know what value in my act and am I at a final right or a leaf of this tree and when i get to a leaf i do the max comparison i say like you know is this this value greater than i've seen before great to take that that's that's the value that I want and when I've run out of search space I just returned the value so in many cases what what you're really doing or what you're looking at and this sort of style or or or handling is you're setting up a structure and your structure looks like this a function with some arguments I have a predicate on those arguments have I have I reached my end okay if I have returned a value based upon those arguments otherwise change the arguments a bit and call the function again and if you really want to think about it at a true level in terms of like how you would think about it with imperative code is that I really have two sets of arguments i have my arguments which are fixed and don't change between each call and the state I'm trying to manage or or or handle so one of the things that you know is difference between the recursive and a tab recursive method is the fact that there is in many cases and explicit handling of state like you would with an imperative code but that state is managed at the argument level so that you don't have to set up or do a lot of the boilerplate when you're looking at the direct logic they at that state management moves to how you call the function and you know this this has a nice structure that's so nice that Scala can actually your Scala seat can can do something with it and it can do this this tail call transformation you'll often hear people say like tail call optimization that's that's a misnomer it's it's actually transformation what we have is we we effectively have a looping structure here so the JVM allows these things called labels and if you ever read the JVM spec about these labels they have like three paragraphs where they go yeah this looks like a go to but we have all these rules which make it not a go too but yeah it's a go to straight up so here we are we've got we've got again our predicate the value else change the state and go to our label we keep doing this until BRR we're ready to exit and and that's it you don't need to do too much more than that but if you look at how this condition was set up or how we were managing this stuff what you see is is if you were to look at the call stack without doing this transformation what you would see is you'd see function call function call function call a function call a function call and the only thing changing is the arguments whereas if we look at this structure what you're seeing is it's one plus the function call and that plus is actually a function itself that's a function call so the call stack looks like longest + longest + longest + longest + so that's why you can't actually optimize this stuff because the actual result depends not only upon the longest function evaluation but then the evaluation of that result and so you know we have this tale rec annotation and notice that you know I hadn't done that previously to the thing I called tail like was entail call positioner or kale called function and that's because this TELRIC technically isn't required if you want to do tail recursion you can write it as long as it is the compiler will happily optimized or transform it for you but if somebody else comes along and you know they don't know or they aren't familiar with the language or they didn't realize what you were doing they can screw it up and it's going to happily compile them and you know a couple weeks later you're going to get a stack overflow and things will go to heck if you add this though the compiler is actually going to go come in and that's going to make a rigorous check and it's going to say okay you know did you do this like is this really a tail call function is every function call back to itself in tail call position so what I'd like to do is I'd like to I'd like to take us over and go right into some some code here I'll try and move this over here and minimize this I realize this thing oh how to minimize something in a mac i actually really don't know how to make my stuff in a mac man all right you know what I can do I can open another another window here sublime file open this open great and bring this over here right wonderful awesome so now since I can't actually see this i'm going to have exercised one here so this what i'm doing here is i am god why you know that's the one thing i don't like about scholars like you know java did all these like nested folders like why why would you do that you know other languages like Python you just say like here's my package name done sorry I've got this imperative code here as imperative code is again trying to deal with a tree structure and alright cool that's why so what it's trying to do is it's actually going in i'm giving it a tree structure and this tree structure is going to be traversed again same way but in this case what I'm looking for is I'm looking for the largest weighted path in other words like if I bigger all right bigger wow that's awesome yeah so I'm going to look through all these things this tree is going to have an actual value it's not going to be an empty tree and I'm going to look through this tree and i'm going to say like all right finding all the weights in this tree i'm going to add them all up and i want to turn you the list of all those things that added up or sum up to the greatest value that so I've looked at tree and it's really more than just just a class here and I added some sort of map because I could we're actually not going to use that map but if you think of it it it's just a bunch of leaves which your list and you know a value at at each node and this is the this is the imperative version this this looks great wonderful if you're a big oaf an or working out oh land and you probably written something like this again I'm sitting at my search space I've setting up a list of values that I've seen this is the actual result that's eventually going to be returned and I'm just going to do this thing that sums up and holds things so as long as I get to the leaf I will I'll actually take a look in and evaluate these things so can anyone under everyone understand what this is doing before I move on to the next slide because next slide I'm imash gonna write is anyone actually following along with this and doing it locally no all right well good that makes my job a little easier all right i'm gonna do a git checkout gonna change things slightly all right so here's this recursive version so if you were following along right here writing code with me uh you'd be able to go home to like your wife or your husband or boyfriend a girlfriend or whatever be like hey hon look at this I wrote a recursive function and they'd look back at you and go wow that's amazing this is the most amazing thing ever matter of fact this is so amazing you know that sports car you've been looking at you know what you why don't you go out and buy it like it's totally cool so once we get done with this you're gonna be able to go home do that show her and be like this is cool or him at and they're gonna love it so you know this is not recursive this is not going to work this is not gonna going to pass muster so how would i change this what what am I effectively trying to do with this and you know what i need to do or what I what I need to recapture in this is is that sort of state management for free I need to be able to pass in a tree at each cottage point right and then take a look at what I've got and handle it that way so the first thing I should do is I should come up with a way of looking at sort of my search space i should say all right awesome alright so I'm going to want to redo this and use this as a guide so what I really want is I want to make sure that my tree is is doing something right actually this is not the tail recursive version have to get that fancy i can do is i can say okay look I've got I've got a set of children right and trees got leads so these are the things I'm going to search i'm going to assume again that this is not an empty empty tree it's got a set of leaves and if i want to get the longest value out of this well i'm just going to do this right I don't have to get any fan sir like now I've got the longest set of things for my children and so far it's recursive and that's actually recursive but it's not it's not returning the result that I need so now i can take this with this lovely set of values and i could say all right tree value because that's the first element here and i'm going to append this to the children longest and now what I want to get out of this is the greatest value here so if you were look at the actual salt type this is a list list of int and to do this to just get it out I might do something like this if left that sum is equal to left dot or right that's some return left or turn right else left right this this sort of works right this is going to return a list of strings does that make sense so I've just I've just taken this list of lists and I've chosen one that sums up to the greatest value I've appended it to tree value and I've returned that and I'm done this this is all of what three lines of code versus I don't even know how many lines code so i can take this erase this call this longest get really happy and I walk over to Tess I have a bunch of tests here that I can run and now wrapping this and dragging it over here and continuing to drag it over and somehow not dragging over but still dragging it over the love of all right I'm gonna run this here and then we'll see what happens so I run tests and these will all pass I know this because I've done this before but what's actually going to happen is that when I come down to this crazy test here that is going to fail so this crazy test looks at something and it fails and it fails because i'm actually not capturing a condition that i want to capture in this recursive method that's because if i have an empty list or something that has a negative value list dot that some is actually less even if it's even if it's a longer a longer set so that's in other words of saying that i could walk down the tree and if the final beef of that tree is like a negative value i'm going to ignore it so that's a mistake and if i want to salvage it I just do case nil right that's it and this works and this is the actual final result and this is this is all of all of all of everything that you saw over here so if you count this up this this file has 21 20 min lines and this as 12 again like half of everything that I wanted to do and I don't know about you but i find this much much easier to read and if i can drag this over here you're going to see that all the tests actually pass oh and i have no idea how to get out of full screen so i'm a mac newbie by the way i've been using it for like two years I like Linux I've just never been able to figure out Mac yet sorry alright cool awesome so I let me see oh awesome good that losses on to mutual tail recursion I'm not going to do the tail recursive version because we're going to run out of time it is an exercise I do have a couple branches if you do feel like doing it there's another case later on but mutual tail recursion alright so we talked about tail recursion we sell what it was and we showed how we can impress our friends and relatives and things like that now we're going to talk about mutual tail recursion and skull itself doesn't have this this is something that I had to do was compiler plugin I call it two tails as a matter of fact before I came to this conference these slides look different and I went over to Adrienne and then I went over to a couple other people from light Bend that actually work on Scala see and I actually got it working for a general case and so I moved these slides which drove just kind of mention at the end be like oh if you want to play around or anything here you go up front because this I think this is really great I don't know about you but I think recursively like I actually don't like thinking in while loops or fours or anything more than shall we say a 4 comp over a moment at or something like that so mutual tail recursion it's very similar to the tail Breck I mean here we have ping we have pong pong calls both itself and ping and pinkles pong and without this compiler plugin if I were to write this the way it is you get a stack overflow if you chose something more than 65,000 it would just blow up and there's nothing you can do about it but with this compiler plugin this works and actually behind the scenes converts it all into a tail rekt function and then I let Scala see handle the real heavy lifting but the question is like you know well okay that's cool but but why why why do you want to do that and you know the difference between the imperative code and the recursive code is one of conciseness you know I think if you open up your algorithms book like the CLRS or something like that almost all of those things are defined recursively and I hope that it's not the publisher looking at the professor and saying like no no more code means more Inc no make a smaller I'm hoping that it was actually something like this is the way we we look at it and think about it because it is so concise and being concise means that in general it's more readable and more readable code is more maintainable code so if you are writing tail recursive functions and you start needing to add in a lot of business logic a lot of times what happens is each of those individual cases that you want to handle like we had before like a node with empty empty and I know two left node with the right or no bud left right each of those starts taking on more and more business see logic so if there is a mistake in it and that code grows large I have to I have to sort of Traverse down this stuff and find just that group of logic around everything else but if I use with mutual recursion I can dig that code and I can stick each individual case in its own function and therefore you know it's it's free of the clutter of the logic of business that it doesn't care about so in this case pong only cares about itself paying only cares about itself and if it needs pong being called plum and that's it so I'm using it is very similar to tail wreck the one caveat being is if you want things to be mutual recursive they have to have the same type signatures other words here as a function of air d1 and a function of arity to these guys can't be tail wreck and since they don't call themselves and they have no even recursive structure outside of up the way they've been set up here this this will fail compilation but that doesn't mean you you have to in one class or one object or something stick to a single like arity or single signature they will automatically group so one in two since their mutual occur cert they'll form their own mutually recursive group and foo and bar will form their own group as well and the compiler will treat them separately and and will actually compile and just just sort of work and so if this does look cool and you're interested in this and you want to get it out the codes there but this is up on maven and you can you can add it simply like that just include it into your library and or i should say your code and and go around and play with it as a matter of fact i really hope some people will go and play with because I'm sure there's more corner cases that I haven't uncovered I've tried to be as explicit as possible but you know I've sort of ran out of ideas of ways this could go wrong so I need people to do things that I would never think of and then turn back to means go here's a bug at and and if that works and everybody's happy with it you know there's potential that taking from a compiler plugin maybe we could even bring it back into the language itself if I convince Adrian and one of those guys like hey you know this is something we actually want in Scala proper and that would be awesome so let me go with a working example so I'm gonna get stash or do i need against ash do I have yeah I need to get stash it's tash get check out master awesome if I go over here and if i go over your presentation I can look here and we can actually see wow I really can't see this should all about that main test it has awesome so I have this I can take this we can bring it over to command line here and since I suck at awesome make this really really big let me know if you can't see and then awesome I want got any questions so far anyone ready to fall asleep yeah go for it I guess it's compiler plugin so so yeah so it's compiler plugging it should do something with these functions it should rearrange them around or do something there so what is really doing under the hood is it's it's taking your your code and your functions themselves and it's taking the bodies of those functions and it's it's sort of stapling together in a synthetic function that I i recreate and then I'm putting tail wreck in front of that so that that does have I should say that it does have like two unfortunate sort of negative impacts if you will the first being that if you are writing something that is a large method you can wind up not allowing the JIT compiler to to do some really cool optimizations if that method gets close to that 65,000 like white limit it won't even try and do certain things and I have to look at addressing that in the next version of the compiler plugin the second thing is yeah I mean much like pattern matching it explodes so you can actually get a really weird compiler error where it says like the method is too large and again you know I got have to handle that but I've got a working thing so that's you know baby steps the next next part is is getting this stuff going but and poor presentation am I in the wrong I need to be in the project project okay here we go awesome so yeah it is doing some magic however you the visible to to your functions themselves they don't change like it sees it sees nothing you can you write them you call them you deal with in the same way it does the transformations actually in a new phase compiler that I put in before pattern matching and tail wreck and so you know you're oblivious to it and that's part of the reasons i made as a plugin compiler because you can't you can't sort of achieve the things i want to do using macros or not easily do it the way I wanted to or I wanted to have it look in a macro context awesome so I'm an import presentation and then I'm going to say about you t equals new mutual recursion and i'm going to say fact that i call this mutual tail recursion this is where i wish i had an ax night man so i can make a really big thing in it and it works this is great this is cool but equals its new without plug in WP dot ping 76 yeah that's pretty cool let's have more of that alright so i actually have i have a couple more slides but you know i put them up in case we didn't even get this far so I just wanted to talk briefly about about this so you know recursion is pretty cool there are use cases for it there are use cases where you want to avoid it and sometimes working with these sort of constructs are what you want to avoid but in this case you know I look at this and I see you know an imperative style thing up down and I see something that's a lot easier to reason about at least recursively but there are cases where you just can't you can't sort of do something like this cleanly in our curse or imperative manner as if like you're working with a flat map or you're working with you know something along that nature where you you really do want to sort of try and make some logical switch based upon the value contained within your container object so you know we can look at some other things like tail recursively but you know just because you can write something tail recursively doesn't mean that it's it's better this is this is a lot more code now this is a lot less code and it's actually this this to me is a lot easier to reason about and think about so you know things with the future if somebody really does put in something like more than 65,000 times or what is it to to the whatever power like that's just stupid no one's going to retry stuff that many times just you know be sensible about it and choose like recursion over a tail recursive manner don't don't try and be like super cool and and really awesome and go home and like impress your friends and relatives and things like that no no parents going to sit down with like another parent and look at them and say like off my child wrote recursion how about yours no no it's not going to happen so you know I guess closing remarks what I want to say is is you know be judicious with this stuff I've got another example another exercise in here that I knew we wouldn't have time to do what is up there it's up there on this this you know git repo and like I said if you guys have questions you want to play around with this and for those looking at the video if you also want to play around with this you know here's my twitter handle i will help you out but i'm also you know busy so if i push it to stack overflow it's because i'm busy so do we have any more questions before before we're done is that it awesome well thank you very much you [Applause] you