scala.bythebay.io: Oscar Boykin, Algebird and the coming Grand Unification
Recording: scala.bythebay.io: Oscar Boykin, Algebird and the coming Grand Unification
so talk talk is algebra and unification the unification in this case refers to like unifying several different libraries not some crazy like type unification or anything like that so if you're like already freaked out about too many M words like there they'll be not too many scary M words here so also I'm it straight now algebra of course was developed while I was at Twitter where we had to name everything contractually after birds don't know what to do really now but we're still thinking about it so the first part it talks could have come in three three parts first I'm gonna talk a little bit about algebra so here we go if you don't if you haven't done anything but like addition in the past you're probably fine so so here's like the main thing that like so okay so my background is mostly dealing with data so dealing with you know machine learning I'm on the machine learning infrastructure team at stripe now so we're dealing a lot of times with building features that we want to use for to make predictions and sadly as much as it sounds all fancy usually that's just like counting and adding things up so like grouping with a word count right you've seen it a million times and the cool thing that I noticed their Twitter years ago that like almond really interesting things had the property that addition has that this is a really useful property its associativity so it doesn't matter whether or not if I'm adding one plus two plus three if I first add three or you know to two or if I first or if I go one plus two I'm gonna get the same result in the end six right so this is called associativity it's one of the most important properties that was that we're interested in these like algebra libraries and it just means that you can put those parentheses wherever you like you probably know other things that have that that structure so like you know string concatenation also has that structure so I can add either you know hey you and then a to on me to the end or I can you know push you know you to to and then at hey on the front so it doesn't really matter so the lesson there is that like you can put the parentheses wherever you want that's a really cool property so this actually comes up all the time so this is given a name so really uh people talk about mono it's a lot actually when you're dealing with data you all you always have one of them so you actually don't need that zeros quite as much so the semigroup is a thing that that really has this first property you might think there's like semi mono it might have been a better name for it but you know there's algebra has a long history so so it's called semigroup anyways and one cool thing once you have a semigroup if you're dealing with distributed computing is that you can well you can do a parallelism like the commutativity that you might want to think about it has an application but just the semigroup alone just the associativity gives you the ability to do parallelism because you can break this expression up into a tree and then you can you know let's see we've got a latency here of like four combined operations if at maximum parallelism so that's the cool thing that's why you should be pumped about associativity so when you see when you're when you're dealing with some objects some data objects you're putting them together and you want to do like trillions of them like associativity is a really nice property you have for that reason so it comes up super often when you're dealing with like really concrete things this is a pretty simple abstraction like if you were just at the matryoshka talk like we're not going to get anywhere near like how the morphisms or Khadem or visions or an amorphous it's pretty straightforward stuff that you can wrap your mind around so like men max or integer addition you can you can think of a lot of these to set Union set intersection you can really spend a lot of time this is a really weird one it actually comes up in like one case which all just point to like even harmonic sums turn out to form semi group their associative eating that weird formula there and then you can compose so if you have products like to Paul's case classes if each of the thing in the in the product is has a semi group then the product has a semi group so that kind of standard composition you can kind of go all day with that so like one cool thing is like a bloom filter so here's something a little bit non-trivial and these are the kinds of things that we are interested in in the algebra library is like kind of interesting data structures that have this kind of property that we can kind of you know combine them in a nice way so a bloom filter I like to say it's like an approximate set it's something that can tell you membership like with some probability it can say I like this is definitely not a member of the set or it may be a member of the set that's the kind of approximate part of the bloom filter so the way that the bloom filter works is it's just a product again and remember that products like already have this kind of nice like if you have a semi group and we take two things and glue them together you can still make it semi group so you've got a product of bits or boolean values and then when I want to kind of merge things in I use this or operation so I have a new item here I comes in I hash it a few times and I produce a new very sparse vector so this is a super sparse vector of like all zeros and they're like three ones and I combined it with my existing vector by doing a bitwise or so that whole process everything I've just described they were still semigroups right or as a semigroup the products are semi group so the bloom filters are semi group so I can go through and in parallel produce you know bloom filters no problem yeah I can add more to it whatever so to read from this thing interestingly you check so to write into it you do one one semi group warm on in this case it's a mono a two but you don't really care so much um you do or right you go through and you or these things in to read from it to check out something's there you actually interestingly and this is like a little you know bit of trivia almost I I haven't really seen how far you can push this generalization but um you use a different similar curve which is and if you want to read from the bloom filter for instance vona read to check the GA is it present I read each of these I produced the sparse vector for J and then I go through and I and one with this one with that one with that all them together and if that returns true then I it may be a member so there's two different semi groups to play if you want to understand bloom filters so there we go man like sorry for the autocorrect like I probably corrected it like four times I don't know what a mono DS is but kept wanting to convert it to Muniz or something or Moody's or whatever so this structure came up several times and it was really interesting so an algebra you can use these these the one you get the data structures but two you get them in a way that you can compose them in a really nice manner so I've talked about bloom filter to more approximate data structures which are really interesting our hyper log law gets another approximate set bloom filter is mostly talking about set membership though you can use it for counting size of a set hyper log log is really focused on an approximate estimation of a size of a set so if you have say you know Twitter wants to count how many unique users they have and you know it's a route like you know it could be they know the maximum user ID they've allocated but because not everybody maybe is active in a particular month that's not the number of users they actually have so they want to go through all the data and see how many people have logged in in each month so if they just made a giant vector of like you know you know 100 billion or something because you know that's like all the ideas that would be really inefficient and like you know only say around 300 million or so of those bits will be one right instead with hyper log-log they can make a really compact data structure like around 10 kilobytes or so and get a very accurate estimate of the number of unique users that were present that's pretty cool and the way that works is by basically doing a product or using a max a bit about like we saw it in bloom filter you do a product of ors hyper log-log winds up being a product of max's and you read from it using another mono ad which is like a weird curiosity this harmonic sum which turns out to be money that's it's really cool countenance catch is a way of doing I don't want to see how many unique items I have I want to get an approximate like count so I want to know how many times each user came to the site I don't really care how many unique users so I want to produce a data structure and then you can ask me a question and I can kind of query it and see like well it looks like you know you know Sarah showed up you know 14 times plus or minus like whatever I can smear bars that's also a monolid so anyways so these are the kind of things we got interested in that's what you can use algebra for we got a couple we got many others cute tree is an approximate histogram it's also forms a nice associative it's actually a mono eyed structure average value if you have two numbers and you want to know the average well the sum is clearly like you're coming to me jerk reach for it example of a semigroup right for like like I put up on the first slide one plus two plus three right but the average value also like clearly that would be associative as well because I could just keep a side count of like well I've seen one thing and here's X I've seen another thing and here's x2 so I can clearly put them together but the nice thing there's actually stable algorithms for computing the average that are numerically more stable than just summing up and then dividing that's a that's going to get you to trouble with overflow in some cases and you know there's some other like properties about it you don't like so even the nice stable algorithm forms a monolid which is pretty cool decayed value I love this one it's exponential moving average it happens to be that the exponential moving average which is something that's like waiting over time like you probably seen it in stock charts or something like this these can be combined associatively and commutatively so like there's a lot of really nice stuff top K applications I want to see the most frequent don't domains that refer to my website that's a top K application they can also be built in this way so this algebraic like framework I'm more of a like a math background than like computer science like category theory so I hear some people kind of lumped them together I don't really think of them so much that way these like very algebraic kind of like concrete abstractions have a lot of applications in data prediction ml etc so that's algebra gives you these you can use them pretty easily with with spark with scalding and and that's pretty cool but like what more can we do so that's part one are there any questions at this stage I've talked about because some of these things before so I kind of wanted to just give you you can find a lot of other talks and other people talking about these things in detail on the web but we're gonna move on now to a little bit of the category theory I was just trying to bad-mouth and like kind of side is it a second ago that's it all right let's do it so well we have all these like semi groups and monoids so in people talk about these you know everyone loves the the monad and you can't you can't go to talk here without hearing one of these abstractions so so one interesting abstraction that came up which follows a pattern called applicative which we'll see is this notion of like how do I go from my type that I really care about to this type I've talked about so I was talking about hyper log logs well like your your your like access logs don't have hyper local logs in you I was tripping over the fact that log appeared in that like excess log and hyper log log so it was a bad example but so your axes logs don't have balloon filters in them right they've got user IDs so that's a bummer so you've gotta like convert somehow from your access logs which maybe you have like some user ID to some bloom filter or some count min sketch so I'm over here you're talking about oh there's this cool thing but you don't have those things you've got like numbers or strings so how do we do this so this is Bootsy Collins from the legendary band Funkadelic we want the funk so you got to have the applicative functor here at this point in time so how would we calculate the list the size of a list if you are constrained in MapReduce so you like if you go and join a company and you're working in like machine learning or analytics you can compute anything with MapReduce your whole life is just writing all algorithms as MapReduce so how do you do it well you first map everything over to one and then you reduce that's which that's all you've got you got map and reduce so turns out the length of this list is seven and we had our nice associative structures so we can do parallelism in two phases here we have total parallelism trivial parallelism and the associativity still gives us parallelism on the other side so everything's awesome super fast we can scale it life is good that's why MapReduce is so awesome because you can separate the system kind of question of how do we parallelize from the logic in a very very clean way it's like I'll give you this MapReduce abstraction you go to town logically but the system's folks can still optimize the hell out of it and that's what that's the power of any great abstraction so we've got the semi group that showed up but what we really wanted in this case was a map plus a semi group want to glue it together because I wanted to have this one function of like lit length right so length is not a semigroup length is like two things it's like map plus this semi group okay so what if I want the average of these numbers though if I wanted the average of these numbers in a naive way I was first I could maybe map each number to count one plus itself like identity function lissa 1 into 1 & 3 1 in 5 etc right now I can go reduce them all together using a point wise like addition and I get seven items in the total sum is 58 but I'm still not of the average yet I've got some weird tuple and no one wants that tuple they want the average right ain't nobody got time for that so at the end I'm gonna like just divide you know tumor it to a double okay great so what I really want is an abstraction that's like map plus a semigroup plus a map glued on the end and so we're not trying to be too highfalutin we just call this aggregator and the Haskell were all it turns out coincidentally we did not know when they when we saw this but like you know good abstractions have been discovered like a thousand times each they call this fold em but this we call this an aggregator so this aggregator has like a function that comes in the front we call this prepare again cuz gotta sell it to people who don't really want to hear about cattle morphisms and and morphisms all day sometimes unfortunately but hopefully we can sell them on that - we do our semigroup and then we do a present function that converts at the final at the end so what's so cool about this well one cool thing is that you can start to write calculations that look a lot more like sequel because a lot of sequel is actually kind of already encapsulating these kinds of things so here's like an example some table I've got some order IDs up here this is like standard business logic this it makes us all legitimate and validates our interest in functional programming so the sequel is just like okay I want to select the count from the orders and once you have these aggregators you can kind of glue up in one abstraction a lot of your computations so here's like the scalding representation but the spark is pretty much the same now you say let me get the size aggregator from we got several of them predefined and then just from my like typed pipe is like basically RDD in skull and or like a distributed list if you like just aggregate it give me the size boom I've got I've got the size what if I want to do the count where the customer name is Smith right well I can take the count aggregator and say count this predicate so count where customer name equals Smith and boom so the count also fits into this model of being an aggregator which has this map semigroup map structure and you can you know group by so in this case we're gonna group by whatever that's not so particular to the aggregator construct but you can keep going with this you can really take it a long ways so why should you be excited about this so what's the cool thing about this so the cool thing was boots Collins playing the bass talking about applicative functors right so that's the cool thing so once we have this this is a little picture that can draw of what the aggregator looks like you've got your map your reduce and your present right the cool thing is well as my former colleague Dan Rosen says does not compose is the new quote is a piece of crap so and aggregators compose so that's awesome so how do they compose so we can glue another function on the front and I still have an aggregator right well functions compose so since I can compose a function on the front I can still get an aggregator so I like in a really silly kind of a quasi like a pseudo mathematical way a function glued onto the front of an aggregator still an aggregator so it composes that way if I glue a function on the tail end of it by the way what quiz time you everybody talk what what what do we call this like in more of a category theory like this is yeah it's contravariant functor and the first it's contra map yeah so cool we can glue a function on the end of it and we've still got an aggregator no problem there right cuz like these things are yellow they clearly I can just glue them together like no problem you know so that's that's called that's called map we usually we things that we can glue a function on the end of it we still have that thing we call call those functors but more than that I could kind of like glue them together product-wise I could have like first been pulling into one then into the other at the same time and then output something else I like this representation of applicative functors sometimes people call these Manoa mutton the my know it'll I don't really think that should be worried but monoidal functors but anyways I can kind of like glue them together so the zipping kind of thing like you can kind of zip two lists together or you can kind of join two futures together where you have a future of a feature of being glue them together like you have that zip operation that's the applicative functor with some other stuff and some other laws so we've got that so aggregators are these applicative functors so which is pretty cool so we've got a map method that's the thing on the end we've got this zip method we do not have the flat map so there's no there's no great way to make in there's some nice reasons why moon ads are just too much you know just just going just just take it back a step and there are really nice things about applicant functors so that's pretty cool cool so that's the story with aggregators and applicative functors so you can use this with the algebra project has algebra spark you can just kind of like grab that thing off me then you can pretty much take your RTD and you know aggregate and use all these nice abstractions so that's cool so if you're using scalding they're kind of built in it's like it was really pulled out of scalding to make it more portable and together use it in more context any questions about that yeah yes I will repeat the question the question was when you want to compose these aggregators and I can apologize a little bit I've decided you know I didn't show so much code is I just kind of talk about concepts so this would be easier to talk about if I put the code up if I compose these two aggregators they have to be in the same shape so you want to there's actually two ways to compose these things that look pretty similar to zipping them together one would be and I wish I had a chalkboard or so what yeah I think we got time so I'm just gonna like come over here to the text editor so let me increase the font size okay so one of them is you have aggregator ABC and aggregator let's see if you know like combined right okay and you also over here you have a Grenadier or a 1 B 1 C 1 okay so I can compose these into something like this that's aggregator a a1 that's one way to compose them this is not exactly what we mean generally when we say and applicative functor so I'm just kind of like I can like do this at the same time so if you were to bring me a list that had a and you know a1 I could just like yank one out and put it through one and one out and put it through the other and go through so that's one way to compose let's combine it sounds bad because it sounds like something else so I'm gonna say compose one another way to compose is this so they compose in many ways I guess is the answer that I'm going for but I'm just going to be concrete about the two ways that they can Bo's that are that are most interesting this is maybe the more interesting way that if you bring me a list of a I can you know and this is the one that looks more like the this is the one that you would implement an actual applicative for in cats or Scalzi that that second composition does that question was that was that a reasonable answer that question okay so so that's that's that part of the story so what's the whole unification part of the story so a couple years ago yeah so here's the part three here comes four three so like everybody's got a mono a like every I think every single talk I've been to in this in this in this conference they've mentioned the word poised and like it takes you like you know literally it's like four lines of code with the parentheses and everything so it's like it's like that's not like some such some big contribution to the world you know so you know here's like algebra annoyed and you've got spires got a monolid up there and scalzi has Mahanoy and like actually there's eight thousand nine hundred ninety five just Scala hits two mono eight on github so like like that's like like you know that's like a bummer man you know it's like there's just too many of these things you know so in a slow going I remember it's like three I was like three years ago like I was thinking like this is a bummer Eric work with notch gripe he's like yeah we shouldn't do that we should have one thing and we're like yeah miles what do you think yeah I don't know if miles remembers us asking he's like no that's not a bummer just like you know like have implicit conversions between the ones you want you don't need to have one big mono to rule them all but um you know so anyways but then you know later we decided like let's give this a try so we had this algebra project okay so the idea of algebra was now we're gonna veer off into like history of like Scala community at this time like there was this guy Laura she was running this project called Scala Z and so Lars and like Scala Z and like Eric with spire and you know avi and I with algebra we had this like video thing we're gonna like get together we're gonna have one set of these basic abstractions that are just so simple you just can't like you're not gonna get them wrong like you're gonna agree to them and they could really be kind of hopefully frozen and the algebra ones really kind of feel that way so that was the kind of goal we kind of probably drag our feet on this because there's also one problem in the scala community if you're working at a big company there's a large code base you start to become very anxious about binary and compatibilities and I'm sure everyone has been bit by bi diamond dependencies of like very commonly used libraries so a library such as this which are proposing to put like like it's like it's like the xkcd thing it's like there's too many standards so I've got it I've got it like one more standard right and not only that you're gonna jam it at the very bottom like let's jam it underneath spire let's jam it underneath like you know one of our core algebra libraries at Twitter let's jam it underneath Scala see so it took us a long we wanted to be really sure we kind of gotten it right before we jam it in and then like I think we really before MIMO is so much of a thing but so now there's Nima a tool to help you like at least know when you've broken binary compatibility which unfortunately is not perfect so anyways so that's the story but we dragged our feet too long and then you know then miles again causing problems was like look like like you guys that was fine but like I'm just gonna need to take like those those things and take a copy and put them in type level we should just do that in the type level cats thing so we then we did we did that so let's see where we got so these were the main abstractions that were most commonly used so we talked about semigroup and Monroy today and I've talked a lot about what associativity means the rest of these maybe are like they're simple order properties certainly similar to check you know commutativity just means they're commutative it just means if it's you know a and B combined it's same as being a identity means you've got some element that I can combine that doesn't do anything inverse means that I can uncombined so if I've combined in like a I can also uncombined and get back where I was before right in item potent which is super useful for the distributed system folks out there if you have a lossy Network and you're working with akka and you're gonna send messages it would be really handy to know that as long as it gets there at least once like you can do your thing and that's what idempotency is all about so people talk a lot about semigroups monoliths I wish everyone would also like if if you hadn't heard of similarities before take those home and think that might be useful for something I'm doing so these types all made it into something that wind up being called cats Colonel and cats Colonel is a part of cats that cats itself depends on so if you use cats mono it it's actually just a type def of cats Colonel which came from this whole effort and that's pretty cool there's like Mila has locked that down pretty much and you know it that one's been pretty stable so that one doesn't move and so that's the one that we've kind of now we now the algebra project depends on that so we're nice guys we can you know when we've lost so cats is like people like cats that's cool so so now the algebra project depends on cats kernel cat the there's more to algebra than just mono it's right in fact if you've you know you you know everyone you're in a cryptography or coding theory you might be in two fields these are the these are great they have a bunch of other properties so with the ring like and lattice like like kind of thing they usually have two operations these don't come up so much in category theory so cats doesn't have so much of a use case for this that I know of maybe some people who are better experts at category theory can tell me wrong but we have addition we have multiplication that's what like kind of the ring world is all about not the science fiction book so there's these two things RNG it's a ring without an identity element and you get it you know rig is a ring that doesn't have the subtraction no negation you know so there we go so there we have these nice tables and these are all in algebra so now algebra depends on cats kernel and the algebra project here are all these other types these are really getting kind of like specialized like if you think of lattices they have a lot of analogous structures like if we think of the actual type lattices that come up you've probably seen tops and bottoms and they have upper bounds and lower bounds those can be related to meet and join lattices you might have some use cases for but now there are PRS finally years later against both spire and algebra to replace all their type classes with these they will be merged very shortly Eric and I now work at the same company so where can we have we're more motivated to unify these things and at that point when you see mano aid in any of these projects cats algebra at spire algebra you're talking about the same time so if you want to go and use like so what can you wind up doing then so expire what's the difference so you might think they're actually really well factored so spire is really about numerix really fancy awesome numerix like it I there's really no almost no question where you say should I be using spire or algebra because there come they're covering totally different domains so it's really great that they can use the same type classes and work together so spire can give you an awesome rational type that is really efficient it's very fast Eric it writes amazingly fast code really high performance but with some beautiful abstraction Tom Switzer who also works with us now at strike rota this awesome computable real implementation so real numbers we normally think of them as being like you know you can't rip it they're like doubles right but many reals can be computed like square root of two I can like I can't write down all of square root of two but I can give you an algorithm that would produce the in spit of the square root of two likewise for pi right so they have some awesome like classes to deal with these kinds of things polynomials polynomials form a field even so you can divide polynomials you could multiply polynomials really cool stuff that comes up in coding Theory actually on the other hand algebra as we talked about before it's more about these big approximate approximation data structures so that's kind of the state of affairs so the take-home message that I want you to know about is that one thing is it's a cool abstraction that I don't see a lot a greater is that kind of applicative functor of like a semi group with a map really really useful if you're into accounting analytics building machine learning features you should build reviews allow brer ease of this or use algebra recommend algebra it has many well-tested I mean they're there correct someone someone get got on my case I don't know if they're here about like the bloom filter being too slow and algebra so here's the dirty secret we actually don't ever use we never use bloom filters to Twitter and that was a contribution and I'm a nice guy and I take contributions so like whatever man but um so number three we now very shortly I promise you before the end of the year there will be one one mono way to rule them all one one ring to bind us right you know on cats algebra inspire so that's it there's algae bird I'm a stripe there's my email address that's me on twitter follow me on Twitter always in a competition with Peter Sabo see who can have the most common followers he's doing abuse at Twitter now so he's like pulled ahead of me because because for obvious reasons and anyways and spy stripe is always hiring and look at all these fun people you could be working with there's Eric there's Sam Richie there's Tom Switzer there's avi Bryant there's myself look at all those Scala projects so come talk to me that's my whole talk [Applause] sure yeah I'm happy to take questions I think we've got some time starting to speed it up there and get a little looser at the end so yes I so the question was what would I suggest using for complex numbers spire has awesome complex numbers they have attorney ins you can do complex numbers over integers complex numbers over doubles complex numbers over computable reals so it's got some really cool complex number handling yeah next question all right thank you for coming to my talk [Applause]