SBTB 2015, SF Scala @Nitro: Malcolm Greaves, A Type Class for Data of All Sizes

SBTB 2015, SF Scala @Nitro: Malcolm Greaves, A Type Class for Data of All Sizes

Recording: SBTB 2015, SF Scala @Nitro: Malcolm Greaves, A Type Class for Data of All Sizes

thank you ji ho so today I'm going to talk about this concept than I like to have been working on for a little bit and kind of in general the way I like to describe it is it's a type class for data of all sizes so a little bit about me that's my picture whew I am a computer science graduate from CMU I graduated about a year ago total barrier transplant grew up in the Midwest family is in Midwest and East Coast and as T Howe gave me and his lovely introduction I'm a research engineer nitro you know I love working about here as I read guitar a scala all day and i work with people who not only just a love folks functional program but they really get it and you know I get to apply that kind of functional programming code they get to write two different sorts of natural language and machine learning problems the motivation behind this talk is really about the scala collections library at the heart i think everybody raise your hand here if you've written a scholar program or done anything you know people I so have you ever written a program that didn't use map or flat map or fold or any one of those things keep your hand up if you did awesome that's wow this is a zero okay great so that that's you know that's a great kind of empirical sort of result right like ass there but in the audience everybody's used really familiar with these kinds of concepts and you know everybody's probably heard that these concepts for manipulating data work really well when you scale up right there you know for I found me a for different projects that are very high-profile that use these sorts of concepts you know spark as its resilient distributed data sets patchy flink has its data set concepts on bird and scalping which you write you know sort of functional code that uses these idioms that can work on you know hadoop and apache storm and i also have sort of inspired other library designs like the aqha streams library but that implements the reactive streams interface but you know unfortunately there's not really a single API that targets these different systems right you can imagine if you want to write a word count program you could write it and who would work on RT DS you could write in the work on a flank data set or it could work on sequencer traversable but you wouldn't be able to get that to work on anyone that one algorithm our code you write to work on everything you'd have to write a separate implementation where you just change the input parameter type and I'd be a little kind of in a sense it's a little weird right it's like it's doing the same things semantically out expected to why can't we just write my algorithm once and then just put anything and then it sort of behaves as the way especially the behave and keep running and that's exactly the you know motivation behind your if we limit ourselves to sort of a mini batch style processing you know idea can we make an expressive daily manipulating API that could target these different sort of platforms so specifically I'm just going to kind of limit it to the local skull collections and our DD and the data set from sparking flink respectively you know if you just really want to get kind of this all in one slide and get a nice visual for like what the motivation here you know it's really having one data API to rule them all that was me last night coding and I'm just kidding so I'll end this talk going forward we've already kind of covered you in with the problem solving but it'd be really quick kinds of high-level the API to sort of just reinforce things I'm sort of talking about spend a good chunk of time on the design decisions and the subtle nuances between inheritance or odd ad hoc polymorphism and then you know at the end would try to show you guys some code so you can kind of say she ate your you know desired to really you know know what's going on here and I hope the demo gods accept my sacrifice that I made and I'll go as well so jumping right along the high level API so we want to come up a set of actions you know they can be methods of functions will determine that later that are useful for data transformation manipulation they support concurrent processing there you know we want to try to keep this as small as possible and dryer to make them reusable and is general so in this year let's just assume your day is some kind of collection type you know it could be an RDD can be you data set we want to you know some very common methods of you might want to have or something like a map right if I have a collection of type a I want to be able to apply function every single element and convert it somebody Oh a flat map although the result i apply might be might have failed so i want to be able to sort of flatten that out and get it and get a result in collection for reduced and aggregate really similar ideas slightly different but you know at the end of day you want to have some function that you can sort of group all your elements together to give a single result out and zip is very you know very useful kind of high-level idea you have to these sorts of data set collections and you want to make another one where you take each element put them together you know again these are things probably everybody in this room is infinitely familiar with you know and so on there are a lot of other kind of methods that are actually in the the code that'll show later but these are just sort of kind of collecting the high like these are the sort of i feel really important kinds of data manipulation api or methods that you should have so now moving on some of the design decisions here i'm going to spend some time probably a big chunk of time of this presentation talking about the difference between subtyping and or choosing a sub having a subtype approach or going with the type class approach so in subtyping the ideas that you have polymorphism through inheritance so basically you know if you want to have different behavior which you can do is you have a child extend some class or be a subtype of that of that type and it can either kind of hone in on that behavior maybe specializes some more or it could completely override it and have a different sort of implementation you know everybody hears familiar with you know traversable is a you know extension versatile like and you have things like seek extend seek like and they all kind of go up in this the collections API has a big sort of subtyping hierarchy and contrasted type classes this council called ad hoc poem or fizzle I like to kind of think of it as the sort of you know duck typing from Python except assert its well typed right if it quacks like a duck it's a duck and I also compile to a duck right and another way I think of ad hoc polymorphism is it adds a constraint on its implementing type saying that this type is this yeah member of this type class because it I can demonstrate it has this behavior here you know ask Allah will use implicit to say you know I need to have some sort of evidence that this type here's the type class and you'll say I'll find that implicitly in a search when compiling some more differences in subtyping you have a concrete container type right it's always in if you think of like a list and an ArrayList Spektor you know Java days right an array list is like a very specific kind of list and it's a concrete container type it's generic because it's a parametric polymorphism it's inside type is generic where I could be an ArrayList or a list of any kind of type but in a type class you know both the kind of container type and the inner type or both general you know you're not really it's a little bit of a different sort of subtle difference and I want to kind of dive it int it into it with a really kind of sort of simple example code here so let's imagine we have this data type and we're sort of expecting outright little bit of code and we just have one method map and we're looking at the difference between a excuse me a sub typing approach on the left and a type class approach on the right so we ever on subtyping we have a trait and it has a spry memorized by the inside type a and our map function needs to have one generic router be because it has a function that is going to convert a and just some other type things going to you know pop out a an instance of data but where the inside tribe has changed and in the implementation let's say you have a class that wraps around a simple traversable it'll have to extend data right and then when we do map it's really simple we just you know take the inside traversable type call map on it with F and wrap it up again it's reversible in contrast in the type class approach you notice that it's actually parameterize by D and there's a little constraint on that saying that D has to be a higher kind of type basically like to think of this kind of as d has to be a donut right like you think of a donut it's it's kind of complete but there's a big hole missing of the center if you want to make it you know full well balanced breakfast you got to put a donut hole inside of it that donut and now it's a complete sort of type but so in this case right when you implement map you'll notice that both it has both an hanging a beer generic right because the very first thing you apply to map is an instance of that container type right you're saying I have a container type another container d I know it's inside of the container things of type a now if you give me that and then you also give me a function from A to B I'll know how to convert you know iterate over that thing or whatever be able to change every single inside from an a to it be and let's say if we implementing that with traversable 'he's right one thing that's difference we noticed that the implementation is an object it's not a class we don't need to make a new instance of this thing every single time we just need one because we just have a method and notice when we say we have map down there defined we have that the d-type has become very concrete right now writes very very specific it's traversable and we also returning a traversable type so we're not really actually one kind of nice approach with this is we're always dealing with that specific type it's never going to going back up and do a a type hierarchy right because that's kind of the central idea of a type class as it's a big town of separation of concerns is in subtyping right like we're creating a new type is going to be a sort of different way to look at the data it's not reversible it's a data of a right or it's not an RDD it's a data of a and a type class we're always we're keeping that that collection type the same we're just having sort of another set of methods around that we know can always work and operate and manipulate that specific type and it's a subtle difference and you know my my professional opinion is I like the type class approach more because I feel like it's a little more uh it's it's not only as a more transparent be but it's it's generic and has no ambiguity and they I'm going to show a problem in the next slide with subtyping of how when you have this type pyar ki its kind of opaque and you can run in some weird problems if you're not really careful with it so leading into then right what are some problems with subtyping well I kind of pointing out that I keep going on about you know when you return you return this sort of i'm calling it an opaque type we noticed in map go back here right map returns into the subtyping approach on the left it returns a data of B we're on the right in the type class it returns a specific instance of D so it's it's a little bit different right it's in the type class it's a traversable in the sub typing it's always the data so like you don't really know what the implementation is you just know it has these methods on it when it's a sub type and subtype b is nice because it gives you the subtraction over the specific collection so saying hey these are some operations you can have that work on it I don't really care about the implantation I'm sort of hiding that from you but I argue that that the cost of this hiding is bad and it creates a sort of leak leaky abstraction because you can do i'm going to show one thing you can do with if you're implementing zip how can go wrong you don't really know if you're what kind of things you're trying to zip you could be trying to zip you know a giant rtd in memory with a small traversable and that might make sense but you have to really kind of think like how would you do this sort of operation right when you have in subtyping when you have instances of the same same parent type interact with one another you can sort of lose sight of how they're supposed to interact when you use the type class approach you always have the specific type and so whenever you're interacting with them you're always saying okay yeah I have like a very specific instance of something that implements this type class and you know they're going to be the same type their generic but they're going to be the same type so let me try to move on here and see if I can make this a little more clear in the subtyping approach if you wanted to keep this specific type and not have it you know say I want to have a specific type of data that I'm returning right you'd have to you always would have to put that type in the as a caller you'd have to know the type you're supposed to get so you have to call map listing here's the the type B that's going to be to the inside type and we transforming into and then here's some other type D that's a subtype of data and I'm returning that specific one and it's kind of ugly sort of or both a little bit unnecessary you know an example if you had something like that you'd say well D is it specific concrete instance of a traversable data subtype and when I map over it i have to give it you know the inside type i'm changing as well as okay make sure you don't kind of promote it to the parent type make sure you keep it specific as a traversable of data you know or you could take this call collections library approach it definitely it works well everybody uses it it's less boilerplate and elegant but it's kind of complicated if you notice in the very last line right you see it says Matt be that so in this case like that is going to be the specific collection type you're returning you can look at this code if you go to like you know fire up any ID lied go jump to the Declaration of traversable like you'll see in traversable like it's parent type you'll see this def of this exact definition and Matt if you look at it and are really familiar what's going on like it is very weird right like map returns that like I thought I returned it traversable you know okay well this just can build from what'swhat's repper be that oh that's parameter is there like it comes very kind of hard to figure out like what is that type here right what we're like what's going on it's because you know kind of feel subtyping it can be very complicated to follow right here is the actual wow this dudes allowed here's the actual you know type of type kind of definition of our definition of a traversable and I also decided to pull in traversable like so you could see that repper right so it's this crazy hierarchy traversable is traversable like and Jenna traversable and its traversal once and it's also generic traversable template and a traversable like isn't any that also is a has oh sorry is also a has new builder it's also filter magnetic it's all such a versatile one once like this is this is getting a really kind of crazy I mean it's a testament that the scala collections library works really well it's very you know rich and expressive but if you're trying to kind of rebuild this yourself would be a major undertaking and still this approach you still have to parameterize the return type in this approach right instead putting the method we're now putting it into the trait right so like Rep her here is the type of a traversable if you look in the very top where it says traversable of a right here right it's in that case right traversable is saying it extends reversible like with a and rapper is traversable of a so you can't really get around the idea that if you want to have a specific return type you have to be able to account for it when you're calling it at least in some way shape or form so if we're going to kind of let's drill down a little bit on zip everybody's here familiar with zip right in the subtyping approach you have your data art is you right so it's inside of sort of in the closure or in scope of zip so you're zipping you know yourself with that and they're gonna come out with a supertype right like the parent type of data where we have the tuples a and B in the type class approach you are zipping two things a and B that are each a specific instance of the type D that obeys the type class and you're going to come out with another collection d collection same D collection that this very specific one it's not a supertype it's that one where you have the tuples and be so here's the problem in the subtyping case the type system allows us to have value to any very specific implementation at data right so if let's say this is the zip that's defined on the Charl that implements this sort of data type for an RDD it can be returning and we're trying to zip it with another data we don't know what kind of data that is we don't know if that's a traversable we don't know if that's another rtd you also don't know if that's like another flank data set instance right so we would have to do some sort of runtime type checking to sort of figure out how we can do this zip and I'll say that also kind of gets a sort of weird logic yet to say like well what does it mean to zip between two sort of instance types that are different in the type class type like this this doesn't exist right we're returning and always using this very specific type D so you never have to even make this kind of consideration of well how do you zip to DS together I mean it's sort of like this is supposed to the definition and you're never going to get a case where you could have maybe some weird logic coming in because you're trying to zip two different instances that they're both obey a type class but they're different types so I'm going to Claire success here when I say that type class is one you know subtyping is zero then type classes they provide a way to abstract over a collection as well as the inner type and I believe you know type classes make us make sure that we're as safe type safe as possible our implementations work with this this single specific collection type we're never going to be mingling or messing up our different limitations of the type class and trying to you know having problems with that and type class is nice because you can use them to retrofit existing classes without changing their code and you can also easily extend them and use them for new types in the future so now I'm going to go into some of the code and i hope the demo works here i think it will but one thing i wanted to point out is this is actually something i got at the skull by the bay conference there was this excellent presentation on that so Scylla liable it messes up simulacrum has this this macro this annotation called type class and what it does is it does a lot of a compile-time cogeneration that generates infix notation for a type class so instead of having to say at the top here I say you know if I have a method and I have you know the bound that d is a type data is like obeys the data type class then if I want to use it i have to say well implicitly you know find me that data instance for d and then get its map method and then apply to data and then apply the resulting function f to that you know a little bit more verbose than just saying data dot map bath like that's kind of that that's one of the nice things is sort of the object oriented in fixed approach really nice and if you want do it yourself you can it's just yet to generate all that by hand it's a boilerplate nobody likes boilerplate this is a you know one annotation you can put on it generates all that infix notation for you it's really great ok so now i'm going to go to some of the code here i realize i got 20 minutes already so not gonna be too long but wanted to show you guys what this data type class looks like here is this working ok and I'll zoom in so the so you see here this is this stuff actually compiles in this test it's like eighty percent code coverage or whatever pretty close to that so you can see here at the top right we have an annotation type class it's a trait data ever saying here's our d is a higher kind of type and we have a lot of methods here defined like map map partition because one of the things we want to use is sometimes we know it's may be more efficient to do something kind of to act to do a kind of map like operation but on a single partition of them before we send it off it's sort of one of the design constraints with well we want to make this kind of work well with distributed data processing systems and map partitions one of those things that doesn't exist in the Scala collections but it's quite nice if you're doing any kind of large data manipulation we also have some of the impure you know the devil functions for each or turning unit can be used for anything sometimes are useful and they're sort of nice to have around you know your filter your aggregate sort by take you know this is only maybe like ten are like 20 or so methods but really we've kind of been using them in house or a while and you find that it's you can do a lot with these right it's a very sort of expressive but small set of actions you can use to apply to your data and it's really great to just start thinking in these ways and when you manipulate data analyze it type safe but it kind of you sort of just start thinking in terms of fold and reduce and group buys and it's it gives you a lot of mileage so here is the i'm going to show here we're sure next okay so this is right it's kind of showing this earlier this is an example of an implementation of this type class for the traversable type and Scala right and you can kind of see the implementation here is like very kind of straightforward like how do you do map we say map how do you do map partition well you have a function that goes from an iterable of 8 an interval of be basically just apply that whole function on the the traversable and you make sure you keep return to traversal traversable type out nothing here for the diverse will type everything there's basically the kind of one lines don't worry about that that that little guy I want to worry about that little guy he's okay there's one of the one of the things that the Traverse this kind of approach is that when you have different kinds of inner collection types like a sequence or an index e corner array type class approachable will need to say like hey I need to know how to turn an ax I need to know how to manipulate an array so you need to do need to have like some specific type class of invitations for some of these like the very specific Scala collections types i'm actually that's currently work in progress to see how we can kind of make that problem going to go away and just sort of say like well we can i kinda always promote types to traversable and the collections library and operate on them not totally ready yet but we're working on it for the rdd it's a similar case like these things are very kind of implementations very straightforward like matt partition is just map partitions they have partitions for map and for each is for each i decided to get rid of the s on that nothing here is kind of too crazy and even the flink implementation is really not crazy at all the only kind of crazy thing is that flank decided to the flint project decided to define this thing called type information for trying to like understand the deal with the runtime erasure problem so they can do stuff like serialization instead of using like a class tag which is what spark uses so it's kind of weird because i figured out a way you can always generate type information from class eggs so i don't know why they're using that but there's some other things in here like you have to say basically for like the map right the B type in a flink data set this is the flink API here right your output function our needs an ally know that has a class tag but a type of information here so that's why here we making this little implicit like we have this little helper that figures out how to generate type info for be given you only have a class tag for be these limitations are a little bit more complicated i think flink is doesn't have the breath of methods that are dd's have so things like aggregate for example flink only lets you do aggregate on a field this it's kind of a weird sort of definition of aggregate so you can you can get through that by saying you can do basically the same thing partitions and you can reduce over them and also there the reducers kind of weird so returning a single value it or turns a data set of values again I think it's just the API has a little bit longer to go there's some problem with this right like flink doesn't implement a total sort and implements a partial sort so that's one of the things open things is implementing a total sort sort for flink that can work in this kind of a very easy sort of sort by a method to call also flank as of 0.9 doesn't have zip or zip with index but 0-10 does and that's out but it's not maven so this code doesn't have zip in zip with index implemented okay here so i'm probably coming up an edge a time here but when I want to show one thing is a implementation you're probably a lot of people is ever hear from the earth idea like word count for stuff show hands they have how many people here have heard of term frequency inverse document frequency okay so that's it's a heuristic not mathematically motivated but it's a way usually can kind of give you a better word count as a good way to think of it so it's kind of a proof i want to just sort of show that all this stuff works i decided to implement a really kind of simple a kind of tf-idf base word count program here well that sort of the objective is well i'll show you the objective here is if you have you know a couple of text files in the directory and you go through them and you just get all the words out of them where you keep sort of unique index for each file as it's sort of ID because you're going to treat the whole file as a document right let's just go through them and print the top 25 words according to a TF IDF waited a kind of word count and so I did this right I actually implemented this in terms of this kind of data type class right so this is something here that the definition here this is why this kind of type class is really nice and important is that this is a word count here and then this term frequency and verse document frequency other methods here they're not defined in terms of an RDD and they're not defined in terms of a traversable they're defined in terms of something that implements this type class right so that means i can apply it take the same code right this is a very simple word kind of code this thing kind of takes something that could be a map and sort of just turns it kind of reduces interns and into a map it's a helper function but the idea is right that I could run this on a huge data set or could run this on a couple of files on my laptop exact same code write once run many places and sort of kind of I know this is not going to be as satisfying to really kind of read and see all this stuff but there's also weird stuff with like macros and IntelliJ like not being able to figure out stuff about them so you see some kind of red lines but everything actually does compile and work but I like this is an inverse or term frequency right I'd be a word count and then I can get all the total counts and that kind of a function if you give me a word I'll figure it out to word count its proportion of this count of word / everybody else or just 0 similar idea for IDF and then term friggin z inverse document frequency is just well as down to the nice multiplication and so let's run this here so I have some let's show what this kind of data looks like like these are some news articles I pulled off of Google News like a couple of weeks ago they're little they're old but right if we shoot so these are just here's what do you know them walk like base um I think it's like ap here story about Milwaukee displayed his travels through throughout a six mil major league career bubble all right next story day after police killed two gunmen try to ambush garland and who try to ambush a garland texas event right so these just kind of normal newswire articles you'd read anywhere and we're going to run this would see out of these small articles right what are the top words according to a tf-idf waiting the top 25 words now that's pretty quickly there you go it's kind of interesting right we see that Milwaukee kind of comes up twice in the top 25 which is a little weird probably cuz it's not really a big data set but this is something right very very simple program kind of a toy program you wouldn't really use it in and of itself but just one of explaining the ideas of that here's a tf-idf waiting and like top word grabbing algorithm that you could run on many different kinds of collections and I hope that you guys you know these food ideas see as a powerful idea and kind of kind of can take something away from it and that's that's everything so this code is not totally ready for production or even public consumption there's still some other things going to work out but this URL and I can distribute the slides later has all the coda used in this talk so if you guys that will compile and you can work and play with it it's a patchy licensed we just have to do some housekeeping to make it a little bit easier for people to consume like put it on sonatype separate stuff out so you could you know pulling the spark dependencies about pulling and flank that kind of stuff and we'll announce it on these two different Twitter handles once it's already thank you guys for listening to being a great audience because of me yeah questions oh yeah uh yes what would you yeah yeah I puts a specific thing there is actually something I totally thought of doing and that's I think one of the reasons why this is not ready for public consumption because that's an approach I want to like take and see if we can you know have this data type class as kind of being expressed by these other sorts of type classes because that would be nice if you could do that originally I gotta be you know we gotta be honest I don't have a lot of experience with scholars e so I didn't really poke around in it when I was kind of bit doing this you know purely purely knowledge gap but that's a great question any others oh yeah that's just like a weird so the runtime erasure of the JVM right if you have a list of a when you compile your Scala code when you actually run it you'll just see it's a list you don't know what that a type is so there's like every everybody has a different way it seems to like solve the same problem like Scala has class tag and I'll says manifests and then there's another thing and it's like just 211 specific and spark the spark project uses class tags and be able to order say I'm going to save like save this object along with when I do it so when I do a map and I send this data off to know to my cluster and look at this I can figure out like what's that a type right because that's just going to be a race it's going to be you know you do a map it's just going to say I have a function one it's not gonna say have a functional one from A to B so that's that's the problem that class tag tries to help you solve and I was just kind of going off in the flink project it has a similar idea called type information but it requires both and I just want to point that's one of the kind of pitfalls is sort of when you integrate with some of these different projects right like the ideas you just want a nice map function definition but you might have to litter it with some class tags and stuff in order to kind of make your life a little easier and just kind of work have some interoperability between the different library this won't be ah icic yeah yeah it's probably big scholars that people want to keep it pure I get that right it's just that's probably there's probably I haven't looked in it it's probably answer your question i'm getting pulled out the stage here thank you guys very much