SBTB 2014, Bill Venners: Equality for All

SBTB 2014, Bill Venners: Equality for All

Recording: SBTB 2014, Bill Venners: Equality for All

alright so I wanted to talk about equality because I'm doing some work to enhance equality and Scala tests and galactic and I just thought I would sort of show you my work in progress and maybe if anybody's here tonight we could talk about it if you want to and I wanted to start by kind of describing what equality is from the set perspective in mathematics basically there's this notion of an equivalence class it a set has a bunch of members and if you take all those members and put them in groups like we could take the people in this room and put them in groups by their birth month so all the people with January birthdays would be over here and you put it around them all the people with februari birthdays would be over hearing to put a little circle around them then you can make a relation between people who have the same birth month as right so that's an equivalence relation and what equality is is it's when when you have an equivalence relation where every equivalence class has just one element in it so for example for the set of integers there's equivalence class it just has 41 in it there's an equivalence class that just has 42 in it there's an equivalence class that just has 43 in it and the relation is 41 is equal to 41 42 is equal to 42 right and then that relation is reflective symmetric and transitive so that's what it is from math and so one of the challenges when you bring that to programming is there's there's actually lots of different ways and say 42 in code right you can just say 42 but you can also say 42 l and that's actually different type you can say too short to bite get even smaller ones there's a big and 42 there's a bigdecimal 42 the the character asterisk character actually has Unicode value 42 so that's another way to save 42 there's all these Java rapper types java.lang the bite double integer long character float short you can say 42 and those guys Java has a big a big integer and a big decimal that those guys can say 40 tune you can make your own types like I made a complex number type and a digit string type and those guys can say 42 right so one of the things that you have to decide is like who can actually be equal to whom and what Java did is they just make this equals method in java.lang.object that takes another object and then the you can see there they have reflective reflexive symmetric and transitive that's part of the the laws you're supposed to obey when you implement equals but they have two extra ones that weren't sort of in the mathematics one of which is consistent because objects can mutate in Java on the JVM so what consistent says is like between mutations it should act like an immutable object so the equals should always return the same same thing given the same input and then there's another thing that's kind of not in the math is is null you can't you know something can be no Lin on the Java platform so they just say only know can equal no no non null object can say that it equals no and that's job as equals Scala has this double equals method that takes in any that kind of fixes an inconsistency in javas double equals and pretty much does the same thing and it's called Universal equality but a lot of people because because anything can be paired with anything right so one thing that allows is all these things could be compared with each other you can actually pass anything to any other equals method so they could actually say they're equal to each other if you wanted so it turns out that scala fixed some inconsistencies in java in this area and all these these types that are dark purple up there scala makes them cooperatively allow them to equal each other so you can actually say 42 equals 42 l with double equals and it's true you can say a bigdecimal 42 equals asterisk and it is true right because they both are the the value 42 so there's a lot of different ways to say you can it even magically makes the wrapper types know about the other ones it never calls the actual equals method on java.lang float it just sort of magically fixes it so a java.lang float can be says it can be equal to a short so it now will actually work nested so you can have these deeply nested things containers and weep down inside there could be a for long and a four-point-oh double and those things can still equal each other and you don't actually have to convert anything so it's actually an efficient way to compare things like that if you really just are trying to say if all you care about is it's the concept 42 this allows you to efficiently determine that ok so what people have asked me for in Scala tests over the years there's basically two things they wanted one is they wanted an alternate way to well a way to specify an alternate equality then the built-in one so some examples are arrays by default there double equals method just says does identity comparison are these two the two exact same instances and what you usually want is a structural comparison does it contain the same elements so that's one example of an alternate equality another one is XML XML actually it makes sense that it does this it is a compares about it cares about white space if there's a little white space difference in the two XML like node seeks it'll be false right button tests a lot of times people don't care about white space and they'd like another equality that actually ignores white space the default equality for bigdecimal java's bigdecimal actually cares about scale so if I mean I think that's backwards they have another method that doesn't care about scale I think it should be that you know by default 42 means 42 means 42 but since that's the case the alternate equality is one that actually doesn't care about scale sometimes you actually don't care about you kind of want a fuzzy equality for real numbers or four doubles and maybe you want in a case-insensitive comparison for Strings for quality right these are all different alternate equalities you might want and the other thing people wanted was type errors because because I can pair anything with anything then i can say 42 the string equals 42 the integer and that will always be false it's all it's almost certainly a bug but even if it isn't a bug if you and to say that it's better to replace that with false it's a clearer when you're reading the code right so and it can sometimes not be very obvious because this deeply nested structure is false because there's a long and a string deep down in the same spot right so so it makes sense that people would like that too just not compile but the question then for me was how do I decide what should and should not compile so what my intuition was is like well if it if it can equal if it can be equal then maybe it should compile but if it can't ever equal like a string can never equal in anthon maybe it should not compile so you can get a type error in Scala tested since 20 or sky lactic for things like strings compared with ants right but big in and bigdecimal they actually can equal each other because scala does that magic and cooperative actually this isn't magics just the equals method of bigint knows about bigdecimal and the equals method of big jesibl knows about bigint right so that is allowed to compile and you actually let it be true or false so that's that's one thing but then there's also things that could always be false right so too empty seeks I mean I'm to seek of nothing right if you see a list of nothing and a vector of nothing you know those have to be empty that means there'll always be true they'll always be equal so maybe that should actually not compile and a better way to write that is true right because that's always going to be true but the only way to really do that in the in with implicit is to make ambiguous in places like to turn them off because I'm it's not the only way but it's what you'd normally want to do with lists or for seeks to say any two seeks can be compared if the inner types can be are sensible to compare so if you once you do that the only way to turn off empty ones is with ambiguous implicit and I really don't like that so I actually implement it just so I could get this error message that's kind of ugly and then I took it out because I don't think probably that's what I'm going to do but if you have an imp like a vector of nothing and a list of inch that actually should definitely compile because the list event could be empty which means the answer would be true work be non-empty which means the answer would be false so if it's interesting if it could be true or false then then I think it should compile so that was my first candidate rule just like seat-of-the-pants rule is if it's an interesting comparison it should you know maybe it should be allowed to compile and definitely if it's a boring comparison it's always gonna be true we're always going to be false it probably shouldn't be allowed to compile okay so that's a that's one rule or one idea but what about implicit conversions because another thing you could all those different types a lot of them have implicit conversions between them like there's an implicit conversion between int and long all right so that's maybe how you could think about why those guys should be allowed to compile so i made this complex type well type well the simple type for complex numbers on top there and i made an implicit conversion from into complex right so should that should i now allow it ends to be compared with complex numbers so my my intuition here was well sometimes it makes sense but sometimes it doesn't make sense if I wasn't sure you know when it would and when it wouldn't in Scala test 20 I actually made this thing called conversion checked triple equals because people actually asked for that they said sometimes I actually want to be able to compare things and have it magically implicitly convert one to the other and then compare but I over time decided I think that's kind of too blunt and instrument because it turns on all implicit conversions and sometimes it's going to make sense sometimes it doesn't make sense so what I've moving to is that you actually have to enable explicit implicit conversion so the new stuff in in three auto I think conversion check triple equals will be deprecated and you'll actually have to enable specific implicit implicit conversions so I can just say enable the quality between int and complex that picks up this implicit conversion from into complex and now I can compare them but you know definitely there's implicit conversions that don't make sense like there's this implicit conversion that adds should everything and matches so a should wrapper of one of aunt I don't think that should be compared to int and there's actually a lot of things that it just doesn't really make sense to compare but it's like I was having a hard time figuring out what kind of rule i would use to decide and this Paul Snively actually tweeted a link to a paper a few weeks ago that gave me something that was sort of more formal it's john reynolds using category theory to design implicit conversions and generic operators and what he said is it's okay to do it if it if it's an injection and what an injection is is it is a implicit conversion that doesn't lose information so when you convert from int to long all the possible values event fit in a long so you can't lose anything so it would make sense to allow equality comparisons between integer and reels because inner serves fit inside reels between reels and complex numbers because reels fit inside there but there's this thing called digit string which it doesn't make sense it's okay to have an implicit conversion but you don't want to actually let them be compared for equality because you lose information so what you can lose is you lose how many zeros are in front right so all the digit string is is a string of digits and it's enforced that it's it's a valid int and the implicit conversion just converts it to int and when I compare 42 with 0 for 2 that's false but if i convert them to int it's true so that gave me confidence that you know if something is an injection if something is a widening conversion it actually should be ok to allow them to compare but so this is it's like not very simple rules but here's the yes if it's interesting it may be able to compile and if it's in some implicit should be allowed to compile and definitely things that aren't injections you probably shouldn't be allowed to compile so then there's the question of subtype super type and subtype super type is it you can think of it as an implicit conversion because whenever a supertype is asked for you can pass in a subtype and what you can think of that as is it's converting the subtype to the supertype and passing it in right and there's actually this symbol Stan Colvin less than that you can use that is a implicit evidence that the left side is a subtype of the supertype it's also an implicit conversion from the left side to the PI me from the left side to the right side so this from the subtype to the supertype so essentially it it actually passes both of those previous rules it is interesting something can equal or not be equal to a supertype or subtype and it's actually a injection right you don't lose information it's actually the same object so I didn't lose anything so here I have an option event being compared with a some of Aunt which is a subtype I have well in both directions and then I have some event compared with itself and and this subtype super tight relationship is reflexive so that actually is also you can think of it as being converted by this this funny little operator but is it always desirable so I went to give two examples where I mean I think there's a lot of times where it isn't always desirable so one example is this method eqv which takes two teas and then calls triple equals was just like say Scala tests or selecting strip illegals and there's actually almost certainly a bug in that line of code because I forgot because triple equals takes it a quality of tea and I forgot to pass it in so it should actually be there should be an implicit equality of tea being asked for by eqv in the first place but it goes it compiles because scholar will and for any and any is a super type of everything so to let anything compared with anything right so they'll actually will allow one to be compared with unit and that's that's a problem and then here's two functions that will they're both extensional e equal because if you pass in the same int you'll get the same output and they're intentionally equal because they're actually implementing the exact same way but scala it's in programming it's not really practical to actually do that comparison because it to implement an equals method to check that i would need to go from minute to mak stand and make sure both of these functions return the same thing so we just don't do it we just make it you use the default equality that the Java gives you that says these two are the same instance but and we just don't we don't we never called the Bleak walls on that so if we do call double equals maybe it shouldn't compile because it's possibly a bug I mean probably a bug but even if it isn't a bug a better way to say that is with the EQ operator because it's more obvious to the reader the code that this is being compared for identity equality actually let me take questions at the end but don't forget that one because i'm not sure it'll take me a while to think about it but anyway the sort of where I was heading right now there's these three equality policies that you use there's triple equals which doesn't check anything there's type check triple equals which does subtype supertype and there's conversion check triple equals which enables all convert implicit conversions and so those will continue to work but they'll be deprecated and these would be the new ones that I think will come which is unchecked equality checked equality and enable the quality and so what enabled equality is is that you have to enable things and basically the way to fix these is to force you to actually say I really am meant to do that right so the benefit is now these guys don't compile if you use enabled equality so you get a type error which is a good thing the bad thing is is if you can't create a case class person you can't compare two persons for equality until you actually say you mean to do that right so it's more kind of boilerplate code but it's just one line you say I want to enable quality for person and now i can compare two persons so i think that's it's like a dial you turn the unchecked equality is the fastest to compile because these guys are going to be doing implicit search is to prove this it's okay to actually say this equals that which is slightly slower but worth it for a lot of people the enabled equality is actually the best error checker but it has a little bit extra it's like the highest maintenance one it asks you to write all that stuff so what one change i'm going to make the Scala test is equal in B will become also checking a little check for sensible equality comparisons right now only this should triple equals does so that's one change before be actually didn't I was basically called double equals so now I need one of those so I'm going to add be underscored double equals so that means i just called double equals i don't do a type error type check I don't do any kind of customizable equality or anything so that'll again that'll be the fastest compile one but allow you to compare very quickly compile a comparison from a string to an end right and then the contained matchers will also be or are there already doing this in master they give you a type error if for nonsense well for suspicious quality comparisons we're not actually quality but containership comparison it's all of the matches should contain but should contain one of none of all of the same elements as all those things and then I want to add this operator or actually this is also a master up it's a containership check for production code since everything has contain on it already you can't just like make a new contain so I switched it around so instead of saying does this list contain this element you say is this element in that list so one is in list one two three works but a string is in list 1 2 3 doesn't it gives you the compiler okay so I'm going to actually go to this extra bonus slide and just briefly kind of talk about how it's different from what's out there already like scalzi inspire and haskell have a a type class that is takes one type parameter and that's how they do two things with that one is they allow you to decide to say what equality means for that type and they use the presence or absence of that well they use the presence of it to enable the comparison right so when you when you bring that into Scala it has this issue with implicit conversions it in one when the implicit conversion goes from right to left it actually enables the comparison when it goes from left to right it doesn't compile so what I did is actually made two constraints there's two reasons for that one is it you can either make this both compiler both not compile which I think it's nice that it's symmetric because the quality is supposed to be symmetric but the other thing that allows when you have two types is you can do you can allow a bigdecimal in a big int to be compared directly right whereas when you just have one type parameter you you can't say that because the only type of those two guys well actually I'm not sure what they're super types are let's say let me go to primitive types double an int you can allow those to be compared directly and the only super type also is a super type of unit which you don't want to enable right so I think that's useful on the Java platform because it's going to be a it's not that time consuming to convert it into a long but if you have a list event to compare that with a list of long you actually have to convert the list of if you didn't like to have this cooperative equality going on you'd have to convert the list event to the list of long and that can take a long time right and it would take twice as much memory so so anyway that is my talk so I think do we have how much time do I have for questions any okay anybody have a question why don't we go with you because you did you remember you mean which one was it which was the context was it the function one yeah I think that's trying a bit hard but yeah it might be possible it might be a good project for you anybody else 60 seconds going once going twice all right thank you very much