Scale By The Bay 2018: Oscar Boykin, Immutable APIs and mutable internals: a Scala design case study
you okay thank you very much for coming to my talk I hope it's I hope it's fun for you as it's gonna be for me it's mostly entertainment for me so this is a talk about really what happened was also just uh please please please follow me on Twitter actually I'll tell you the inspiration to talk so I you know how he does some some great and I think quite idiosyncrasy or sink radically syntax libraries but he has a great talk about like parsers and he talks about like how I think in general like people don't like kind of parse enough it's not that hard people shy away from things they don't like right languages and things is like as often as it could partly because of like they perceive parsing as a hard problem so he made fast parsing you talked about how you can make it fast and then he makes this off here comments like well you know how to make it fast like a lot of ugly mutable hats and like moves on with his life and that can kind of sometimes sound like some sprinkling likes sugar on something it's like oh I got mutable and now it's gonna be fast that he wasn't very clear about like what exactly did he do how much faster did that thing get him and so that's kind of got got me thinking and so I wanted to kind of see in this example of exactly parsers what they look like how is it work and how could you make a somewhat principled transformation to get the performance actually haven't bothered to read through I mean I think my tongue oh never mind anyone ever get in trouble if you record it but uh so so we'll talk about the parser example I'll give a little bit of like some FP we got to do our like you know monads etc so do that um we'll talk about a simple and kind of probably nice immutable implementation and then we're going to do a transformation of that in a you know like I said a somewhat principled way to a mutable one and then we're gonna see how much faster that is that's kind of what the talk is all about so what are parsers so here is a very toy version of what a parser is right it's really just a function from a string this is a very very tight parser a function to a string to an option string in a so what does all of this mean so a string comes that you want to parse and the option is you either parse it or you don't and if you parse it there's some rest that kind of follows after it all the stuff you didn't parse yet that people are gonna continue to go on parsing and you've parsed your thing your a there you go okay so that's parser great now this is a really bad parser but it's like probably good enough for a lot of cases a better parser might be like a you know an either like type that's gonna tell you like where did you exactly go wrong this is either like you know it's like a terrible compiler that like you know you try to compile a code and it just says no you know you know so but you might want to know like a better error like where is it that things went wrong but you know this is this is good enough for our talk so you know an example implementation of this if you want to you know and Scala it's all about encoding things that we wish we had in a nice language and we encode it in some terrible way and so here's that like like you know pretty function encoded in a case class and in Scala so here's an example I want to parse some string this is like my parser is just like parse the word hello right and so there's hello and when we run this is a function one this is like a terrible literal way of making a function one rather than a lambda you get the string in if the input starts with what I expect good news we return some otherwise we return none okay so there's like a very simple parser and you can start to go imagine how would this object kind of compose that kind of thing they are composed is pretty nicely so there's many many different you know compositions you can make many Combinator's you can make many type classes that can implement you know so you know that's a monad yeah great you can implement pure for this thing you know you know pure just means like I can lift something as a parser it's like if you give me the a I could just like not parse it like you know I just look great it's like you want to parse in return you know five here you go here's five like done right so the string comes in you don't do anything to it you consume nothing you spit out the value great flat map is a little bit only very slightly I mean like syntactically it's ugly but like like semantically it's very clean like to parse a and then based on that a you decide what you want to parse next right so how would you actually implement that in this function it'd be well you parse a based on a you would decide what next to parse and you would feed it what is left to parse and because flatmap is working on the option like you know if if that was a nun you got a nun if this one was a nun flatmap you know that's it you know options too so like you can actually there you go you pretty much with the three classes that we've seen you can have a very anemic and actually like pretty workable in many cases parsing library that can like not be totally terrible if you like so if you want to like relate it to concepts that are interesting if you're good if you're if you're sure you know I got some guys in the front row that are like man I'm giving this talk 30 times myself and like self only apologies but if you if you're not familiar with a couple of core monads the reader monad the writer monad state monad these are really good patterns to see and you can see them in a lot of code that you might write and in fact what we've described here is very similar to what's called the state monad and the state monad is just a name for the function that takes in some state computes a new state and returns a value also and this composes in much exactly the same way that we've already seen it's actually I'm a little short on time this today so I well I mean here's an example of what state could kind of do if you don't want to like muta bleah modify a pount err you might have you define your thing is like there's a counter environment and also a value a and you can read the current counter environment that's gonna return the end or you can increment the counter environment you could do other things too but you can see how like actually these are just little functions that are gonna go through and it's functional programming now an enhancement to this and there's actually more enhancements to go deeper than this but an enhancement to this is that you don't just have state you have some other context in which the state is operating and if your new new word Escala this this looks maybe like funny it just means that M is a type that itself is that you know it's a type constructor it takes another site it can be like list not list event okay so in our example then if you take s in this environment M we're going to produce the new s and you get a and actually if you look it this way parser is exactly the cheap you know poor person's parser that we've set up here is exactly the state T in the option context operating on a state of string and returning like the value a ok so that's a little bit of like okay you know we did some functional programming today so how does this have to do with parsing because the monad is not a parser it's not like if you give me any monad I can parse write like that that's not enough you need to do something more so let's add a few more things that we actually normally want with parsers so the basic thing that we want with parser the kind of like 0 that's kind of like if you don't have this you're not really parsing is if you give me a character I can either find that when I'm looking or I can't so that's like not something that exists in like all Munez of course so you have to put that it so this is like exact character or string matching at the current position that's like something you might want to add a very important thing that we often have in parsers though not all parsers is this notion of alternation like I'm a parse at this point thing or I'm a parsing B if you're writing like a JSON parser you might be about to look to see if the first character is like a bracket you're about to see a list if it's a curly brace you're about to see a mapping right so you don't know until you look at the character and then you're gonna dispatch so maybe you parse a list maybe you parse an int maybe you parse a dictionary that's alternation product that's like look I'm gonna parse you know you know like a parsing a tuple - I'm gonna parse the first thing and then I must parse the second thing I can't like just parse the first thing and kind of sort of go on with life it's a tuple - it has to have the two things so this is like a product operation negation is an interesting thing with parsers it also kind of composes in a nice way like don't find the following things like should don't match foo at the current position so this has some nice algebraic properties as well and lastly and IC lastly because actually it turned out like for performance you really just don't want to use this one it's like monads like the first level of enlightening like monads are cool the next level you know and there's like you know is like wait a second monads are way too much like like like step back you know maybe you can use this simpler like a like a less powerful thing and you often don't need sequencing in parsing but an example of sequencing a parsing would be like parsing this HTML you're as far as I know you're going to need sequencing here or really some fancy fancier tricks that I covered sequencing is a nice encoding of this that you parse start and then based on parsing start you know that the end thing has to also contain start but without parsing start you don't really know what that other thing on the other side has to be so it's like you're computing the the thing you're gonna find later from the thing you just sound okay very often you don't need this for JSON you can parse JSON without like like this monadic notion so you remember we're trying to make something principled here remember the goal how he says like oh you just make it mutable so but how do we do that so on the step the step one of like Boykins like how a emulation like like method is to define a lawful type class for the thing you're really trying to do that is nice and beautiful and immutable cell so we haven't really done any we haven't got the immutability yet so this just describes that previous slide we set a bunch of English text that we wanted to and now we've encoded that English text into function so I can parse a particular character actually I didn't mention this but I can also just parse any character like you know just in return like whatever i parse i need to be able to run my parser so if you give me a parser and a string I'd be able to run it and like yours like negation and I actually like extended some big batch of like things I like I like not having the moon addict one so I'm probably not going to really mention that too much again but I there's a type class called alternative which is a little bit more powerful than applicative and that is something really nice it basically includes all those properties that we talked about before this soft really isn't about like like you know the tech class of pedia you can find this in cats it's called Z and Haskell and everything else so if you're interested in that you can see it but if you go back and you think about all the things we wanted to do they correspond to these methods so again take the Engel texture or other human language text you write and translated in jollof all function signatures that's step one here so now we go through and I'm gonna make the immutable implementation of this of this parser so it's not pretty this is not very difficult you can do this this could be this can be an interview question like go crank this out like probably get it done in 45 minutes if you just you know hustle so how do you how do you implement the any care parser well or sorry this is not any care so this is the any care parser but I forgot it should be a case object not a case class so if I can parse anything just like as long as the string is not empty I'm good to go and whatever it is I just take the head of the string and I return the tail is like what's left to parse good knock down one out I said copy pasted right so I copy pasted this one forward so sorry if I parse a particular character I'm looking to see if the character at that position is zero I'm good to go I get the tail and because I actually know what the character is done parsing I don't really want to return a value but you could like or you could decide to return care again I chose to return unit here because like there's only one value it kind of could be given that you first not parser is pretty straightforward you know if I have a parser and I parse and I get something well then not of that is nothing and if I get nothing well okay I've parsed I haven't consumed anything so what's left to parse is still all the rest of the string but then we go on so like it's like super easy to write all these this code right so like all these things are like a few lines of code you've got like a decent parser on your hands at that point but it turns out and this is like a super news flash to many of the functional programmers in the room it turns it out allocations not free actually so it can actually and I know this is like heartbreaking here can slow us down if you go back to all those things that I met you have to add allocate these tuple twos all over the place we have to box them up an option all over the place the option the the thing itself might be box there's just like a ton of allocation that has to go on even the stream have to get reallocated but Eric good friend of my Eric a sign tells me but I could not verify I look into the code the very recent versions of the GBM copy the whole string on substring but j8 and earlier and other ones don't copy the whole string they do leverage they keep the same backing array but only update the pointer so the substring operation used to be kind of like it could keep things penned in memory but it was very very fast the newer ones might you know not keeping zip into memory but like require copies so these are all examples where you're allocating like crazy to implement our a little simple parser so what if we mutate you know we don't like this is anathema and we like you know it's like you even propose it and like you know your prints jump all over your PRS and you're you know immoral person but what if we do so we could change our parser to not be the kind of state monad we could explicitly have a mutable state and I feel dirty even writing this as a type because what this isn't a function it's like going to reach in here and do nasty things to that thing but whatever let's like it Scala we can do some nasty things and our seat here now is an immutable string will never change the string will never reallocate but we will keep a variable pointer into that string ourselves okay and we're started at zero and I'm not gonna use option anymore you know it's like if this were Java or go we got it we don't have option we've got like a error and it's no if it's if result not equal no I'm good to go right so so here's my error message like what has gone wrong and if it's know I had nothing's gone wrong I guess so that's what my new parser is but nobody would want to use this this is a monstrosity we can't show this to people so what we would do instead is the following we make a seal trait or a sealed abstract class sealed is a great is like my favorite thing about Scala probably you know it's like it's like you know it's hard to say with so few favorites but but like that's like a really good one and so so with seal plus this protected method I know that nobody else is going to reach in and call this function so in one file I can like this is where it's like you know I guess we have to earn living I have to manually improperly with tests verify that it's correct but none of my users have to worry about that they don't have to worry about using this method correctly they cannot access it they cannot subclass and access it it's sealed we're good to go so from the users point of view they may judge me for making this choice but it will not impact their choices and then I have a final method which is what parse does it has the same signature this is a nicer version of the signature it's got the either error etc they they're gonna use it just like they would the immutable parser and I'm going to allocate a new state I'm gonna run the mutable parser on it if it didn't fail I do my null check if error not not equal to no I'm good I really I'm going to do one allocation based on the offset of the string and I'm gonna get the result the result came out no matter what even if it failed I can just like return null or something other nasty thing you know for whatever no one's gonna see that otherwise if it failed I get the error message so now I have to instead of writing my Combinator's on this immutable nice pure function signature I write my Combinator's on this mutable signature but I'm gonna verify that I don't mess it up ok so that's step I guess we're at step three of the Boyken how we emulation method where are you secretly but carefully implement a mutable Combinator okay so now that's the key the key thing here I want to reiterate the key is that it's protected you don't actually let this get out into the wild you don't expose this to the users I'm not advocating for that and you attain that install a bye to protected with the shield okay so the next thing is that the immutable state I just want to like jump at me now about that it's allocated here and I've liked all these things are actually stateless themselves all the state lives in the states so we can kind of inspect that the state can ever escape anywhere else so the the region of mutability is bounded to this call and it ends at this point there's no moodle mutable like no bits have been harmed at the end of the day so here I insert some whistle thing about like this is kind of the main trick that's making Russ fast all over the place rusts type system can like help you like type check these kinds of things I'm going to have a bounded window of mutability and let's use it safely okay Scala could have that by the way we could expand the type system and make this pattern even even safer so now we can go through and we can reimplemented before and we can so like the any care parser this one just parses any character like I could make this a little more beautiful but it like it's not much it's still pretty ugly we look into and see if the input strings length is longer than the offset if so we're in bad shape we have a little helper method call fail that will set that null pointer to some string otherwise we increment the state notice I don't capture the return it's a mutation City baby and then I return but now look I've actually not allocated anywhere here now some of these calls may have internally allocated but I've removed all the need to allocate at this point and so that's the goal I'm gonna keep trying to write these combinators in a way that they themselves don't allocate occasionally we're gonna have to allocate but almost never so here we have not like care at is gonna return an unbox character and there's like no no no allocations they're good to go fast we can do the same thing with care P it's like pretty like pretty much the same kind of Combinator I get the character out if it matches what I expect good I increment it returns unit already so no problem and I can go through and do these things now this one is where it gets kind of interesting i I called this zip rather than product because if it's like shorter but it's like the same notion of two pulling product if I've got a parser this a mutable parser of a an immutable parcel RB a very nice Combinator is to glue them together so that I could parse a than B but if we look through again it has the same property that I only allocate in the one place I kind of have to allocate I'm going to return a tuple I've got it there's no mutable tuples I don't want to go that far like I did not have to deeply somehow copy at the end to get back to immutable world so I do have to reality to return an immutable to poles but otherwise I'm good I call the put this doesn't allocate ya directly it mean internally as absolutely necessary I've got the result if that fails I don't even allocate the tuple like I can return like you know null would some some kind of a single tuple even it doesn't matter so on all the the failing branches they don't even allocate so backtracking can be very fast too because they don't like allocate a bunch of stuff just to throw it away back up as I get further down my my combinators here's a look a little bit more this is the kind of alternation combine K you know method this is like this or that or the other thing like I just went fully fully nuts here I got the array up there it's like you know you're like oh it's immutable but it's sealed and it's a private class no one can see that it's gonna be okay I don't mutate it inspect notice there's no mutation we're good actually so I wish the type system would help me more but but it's it's great that I get like what Martin mentioned this earlier today I've been so excited about opaque tights for a long time if I had an eye array here I'd be in good shape okay but anyway so you can kind of go through and do all this and so but does it actually work and so that was my question it's like there was an article of faith that this is probably what how he was talking about like would it work so I had my parser type class I implemented a JSON parser in terms of my parser type class then I go and have two implementations in my parser type class my immutable one and my mutable one and I actually even did a farce pass that fast parse back you could go go nuts although you can go add it back in for it for your type class if you really want to go slow and the authors in the front a little dig so but yeah so the answer is yet works so in my crappy example which was like the most direct immutable implementation and then we do the JSON parsing and this is like parsing like some like randomly generated but stabili generated the same way both times things that can have like arrays and dictionaries inside of them in numbers and strings and we get about 7 to 10 times faster these are like some scale parameters of how about helping the data was so 7 to 10x is like kind of work you know like 10x is pretty much like it's like these are the kind of things that's worth it so the take-home message here Eric awesome who's a co-author of spire and one of the founders of cats he has this thing that you know usually you know makes me a little bit uncomfortable but he like in this case he's kind of right but like I was like functional programming and large and imperative programming the small so he'll like it he likes a nice functional API on top but he's like perfectly happy to write bars and while loops and even returns which I'm like dude return but anyway don't go crazy but yeah so in the pro the approach is you design your clear API that doesn't compromise that has a beautiful immutable API at the top level and you represented ideally with a lawful type class something that people can reason about and once you've got that very clear lawful thing you can implement it if you like with an immutable one or a mutable one and you can test the hell out of it because these laws are very clear and you're like really really sure that they agree in this example I have some code that you can see there's a new he repo I kind of had the idea of like maybe making a good parser type class and then like implementing backends I think we someone should do that but man I'm just getting kind of like like burned down on all this you all but it's like a lot of work to maintain all these like libraries and stuff you know it's so we got to figure something out with that but um but I think this pattern works really well for like state like patterns which are actually pretty common that you have this bounded mutable state that you're gonna monkey with and then discard it and kind of snapshot it into a an immutable view and return it so I hope that this kind of tutorial style talk might be useful for you it might give you something to think about to improve the performance of some of your libraries and thank you for coming to my talk I think about time for one or two questions or like jabs you can like any return blows you wanted to live her alright well thanks a lot for coming out I'll be around a little bit later also also I'm sorry I said the Scala team and stripe would love it if you all would come join we're like building out the Scala team if you're interested in Scala dev tooling but also data and ml they'd like it too but we'd super like people to come work on the Scala team so come talk to you about that too