Felix Klock - Subtyping in Rust and Clarke's Third Law

so next we have our first keynote our speaker is somebody to get very excited about he works from the Zilla research works on the compilers and language team for for rust and the one thing that I'm most excited about for Felix's talk is that it really combines sort of something very unique about rust the ability to really have your head in the clouds and thinking and things like category theory and advanced type systems but at the same time having your toes nestled wrestle around inside the bits so I think everybody here is going to enjoy what Felix o'clock has to say so welcome to the stage okay secretly type in my password alright I'm really happy to be starting this thing off it's the first time I've given the first talk at a conference which means I get to like actually pay attention to all the other talks it's the first time my life have been able to do that I'm really looking forward everyone else's talk so this is this talk all the slides are already online so if people want to take a screenshot you know a photo you can go to this link here and get ahead of me if you want or follow the links that are in there I recommend you do so now because this URL is not on any other slide huh so this is the time to do that so having said that I'm not going to go forward so this is a talk I was invited to give a talk about a technology talk and I took that as a challenge and so there's and interesting thing about technology is that arthur c clarke has this this law his third law that any sufficiently advanced technology is indistinguishable from magic that's kind of an interesting thing that we'll talk about a little bit there's also this important second law which is that the way to actually discover limits are the possible is to push the boundaries until you hit the impossible and that has lots of different interpretations here we'll explore this by learning about what the limits are of the technology and rust by actually trying things out and seeing where do we break things where does the compiler stop accepting our program there's also a first law but it's not relevant to my talk it's something about impossible statements and elderly people so there's a lot of interesting technology in rust there's lots of things I could have potentially talked about the borrowed checker or our interesting trade system and how the static polymorphism of traits interacts with dynamic dispatch its object system there's destructors which I'm kind of crazily obsessed about that dynamic destructor semantics and drop and whatnot and then there's match which you wouldn't think is all interest interesting but there's there's some interesting details there so all of those can look like magic but subtyping is a really interesting thing it's a little bit more like a magic show in that everyone knows what subtyping is if you already know what it is then it's a lot easier to sort of get fooled and you know see interesting things happen that you didn't expect so a little comment about magicians so I had that I heard this great statement from Penn Jillette who here has heard of Penn & Teller okay great great so the Penn Jillette's an interesting guy he's the one who speaks between Penn & Teller tellers the one in silent Penn actually talks a lot and so Penn is this quote he talks about when he first started learning magic as a young child or young adult I should say and he actually had a turning point where he came to hate magicians cuz he disguised these people are up there on stage lying and he was devoted to telling the truth all the time he thought I can't do this I can't lie to my audience and he attributes James Randi with giving him the idea of a turning point here where he said you don't have to lie you can be honest the whole time and still be a magician or rather you can be you can lie as entertainment but still be honest and moral but what Penn does is he tells the truth the whole time he's talking and lets the audience lie to themselves in their heads I'm gonna try to do the same thing I'm gonna try to be honest during this whole presentation but I might make some mistakes hopefully I won't but usually the trick is gonna be getting you and your heads to make you know to lie to yourselves um since this is a magic show I'm obliged to show you there's nothing up my sleeves so let me take care of that right now oh I knew that was gonna happen there's something behind my back of course but nothing up my sleeves all right quick Paul just so I can understand who the audience is what the audience is like raise your hand if you know what the playground is if you know a play wrestling the dorg okay great great so how about if you know the difference between a slice and a Veck of tea raise your hand for that great and finally do you know what phantom data of tea is raise your hand that oh wow okay that's more than I expected great maybe just be a boring talk um so let's let's ask ourselves what is sub what is subtyping anyway we are I claimed earlier that we already know what it is well the important thing about subtyping is that it's meant to be this thing where if you don't have subtyping if your compiler insist that you're expected type always map is the exact type that you're providing the type of the expression you're giving you require those things always match the compiler will often reject programs that seem obviously well-behaved so there's intuition here that comes into play about the provided type somehow being compatible with the expected type and so we can think of some examples in rust where this seems to come up if I have a mutable reference to a vector but I want a slice those seem like they might be compatible maybe I can just pass that in or I have a string and this thing takes a string slice aster or I need to return an error io error that's what I have an IO error in my hand but my function itself returns results with a parse error and the interesting thing is that in rust you often come to just try out just passing along and find out if you get that kind of compatibility if it turns out that you know this thing seems like a subtype of another so this talk is gonna be all about trying out things and seeing they just happen to work whenever there's blue in my talk it means there's a link to a playground session or some other page but usually playground so you can try out yourself if you're following along on your phones or whatever but since not everyone has their phones will actually show you the examples so here we have something that might have been in the compiler at one time or some point in the future where it's a phase phase compiler so that phase one and we get the abstract syntax tree and we're gonna produce Mir as an intermediate result and then phase two we're gonna take the mirror and produce output and each of those phases has distinct errors there's the phase one possible phase one errors possible phase two errors the question is if they can pose if I compose these two things can I do that and have an end-to-end error of some kind it turns out that you can just run this code it'll compile and be just fine this seems like it could be subtyping maybe phase one error and phase 2 error are subtypes of end-to-end error we'll be looking a little bit more at this later this particular example and I mentioned before vectors and slices that also kind looks like subtyping we've got a vector and we have a we need to have a slice of T so what happens then so I have a specific program here where it's this little dummy little rotate program that takes a slice of integers 32-bit integers and all it does is it saves the first one then shifts all the other ones up and then it stashes that first one at the very end so really is just rotating the whole slice by one elements and you can just try this out and see if this compile is I make a vector try passing it in does this compile and in fact it doesn't compile but it doesn't compile because of some incompatibility it compiles that you often if you forget in rust you probably had this experience of trying something out and it turns out oh there's some small things changes I need to make right I had to make the V mutable and I have to actually you know grab a mutable reference to be by doing ampersand mute V this bottom one is the version that works but still we're seeing this phenomenon where I can take a Moodle reference to a vector and pass it to a context that's expecting a slice a mutable slice that's that's interesting for all these other examples in the talk though you may have noticed it took me a little while to explain the rotate function and what it does and that's gonna be a bit of a waste of time when we're just talking to focus on subtyping so like good scientists we're gonna try to reduce ourselves to a model to explore so here I'm just gonna try to always strip my examples to this minimalist form where in this case I talked about I have something I want to provide to somebody else so I have a mutable reference to a vector that's what the provide function has anyone I want to pass it to a contest a context that's expecting something else is expecting a mutable reference to a slice of integers and so I've got that up here that's the kind of code that is really presenting this idea of these things being compatible and it's also in pictorial form with taking a mutable reference to a vector and passing it into the expect function and the overall idea is that if these things compile they work I'm not gonna worry I'm here I'm not gonna worry about it running if you try to run these code you'll get an error because there's the unimplemented macro in there so of course you're gonna get a run time there the whole point is just to see does the compiler accept this code right now that's the name of the game so another example of a place where you might see some some compatibility relationship is when you have a mutable reference to some type T and you need a normal reference an immutable reference to T and so maybe there's some sort of compatibility relationship there again we can just try it and see using the same kind of skeletal form stripped-down form I just showed where we have we've been we're providing a mutable reference to some slice of integers and we're gonna pass it to something expecting an immutable reference again this compiles and now we're gonna go through and see some other examples involving methods so methods and rust if you have in the keyword cell for the capital S self though either those kinds of self then you're usually talking about some sort of method and I what I want to do is I want to talk about all the possible combinations of either taking something by value with just self itself or taking something by reference or taking some by mutable reference and seeing the way you can combine these things and we're gonna be looking at methods on char arrays but Before we jump into that I want to just review something for people who don't necessarily know about this particular programming pattern if you have a built-in type like char and you want to add methods to it you can do that in rust by making a trait here I'm giving an example of a trait ASCII inker and I'm trying to add this incremented to all chars and so I'm just saying this thing all it does is increments salt by one units so for example take the letter A and throw it to the letter B in ASCII at least and so the way it's implemented for char is this code here doesn't really matter the details about the important thing is this sort of works you know I have a little test here showing that I start with a I call anchor I get out B this is I'm just reviewing how method extension works in terms of using a trait to add new methods to a type so having said that I will now want to show you a different trait where again the whole point is just to focus in on can I pass one thing into another place that's expecting something else so I've made this this dummy trait receiver and all I'm trying to do here is demonstrate three different kinds of methods there's a method where you take self by reference there's a method where you take self by mutable reference and I met three take self by value you can see the three different kinds of cells there with the ampersand self ampersand mute self and the by value self and they understand at all and then I've got the implementation of this method are the implementation of this trait for char for a char array we're all its gonna do is print out which case we're in and its gonna then print out then it's gonna try to modify the second element of the array for the cases where we can do that when we get something by mutable reference or when we get something by value we can actually mutate the input so here's a sanity check first just to make sure we understand what this trait does where I'm just gonna show you I create three different char arrays and then I pass and then I call it three different methods so I create a char array a that's just the array itself being passed around by value there's no references involved there's B which is a reference to a char array there's C which is a mutable reference to a char right and then I call a by Val be by ref see by me these are the things that match up exactly to what the original type is and what the expected type is there's no interesting compatibility issue here it's just inputs match the outputs and when we run this you get exactly what you expect it prints out I called Val I called ref I called mutes and then I obviously have these three arrays at the end may not be obvious why that's the case but that's not really the important thing here the important thing is just that these cases are compatible and you may have noticed the very interesting layout that I chose for this code for it's got this diagonal that's going across and that's because there's not just three cases to consider there's nine cases to consider I want to try every possible input value immutable reference mutable reference with every possible expected input have all three methods we could call so that's a three by three grid which looks like this and the interesting thing here is that if we if we were to fill in all of the elements of this grid it wouldn't compile but if you remove one of the elements the grid the B by mute I've got that comment there that's comes it out that elements that that cell at the bottom there where you see there's the middle column and something's missing this now compiles the only case that's rejected by the compiler is B by mute and that's kind of interesting because this means it seems like you can go from an immutable reference going from in an immutable reference to a mutable one that's disallowed but for some reason going from a value to a mutable reference is allowed and perhaps even more strangely going from our reference to a value is allowed and so on all those other cases are allowed so you might ask yourself wait how is this actually happening here what what is going on are these things subtyping at all what are we talking about so so to get from the point of view a person who's experienced doing Java VM runtime hacking or other kind hacking for other kinds of dynamic languages you might say look the representation of these two types avec is represented by three words directly inline like embedded in this in your stack frame and the slice is represent by two words and the layouts aren't even compatible each other like the Len is at the wrong place so how could these things possibly be subtypes of each other if you're if you're thinking about the runtime representations and how things work that doesn't make any sense at all you can't just pass in a slice wherever a Veck is or you can't just pass in a Veck with three words into the spots that are expecting a two word slice that doesn't make any sense at all but I I have to take a moment here and point out ie I myself had that initial reaction and then I started reading textbooks about subtyping to double check whether my thinking was right about this and the textbooks in subtyping they're like oh no no there's other semantics where you like talk about coercion x' between things where that's can be considered subtyping so so-called coercion based semantics ok so let's wonder for a second here is this is this subtyping and what I'm going to do is I just spent a little while talking about those examples and now I'm gonna put them aside temporarily we'll come back to them to tell you to first explore this textbook notion of subtyping so a classic example of subtyping in the textbooks is they'll talk about records they'll talk about anonymous Records and they'll say oh if I've got and if I've got 17 fields in what's my struct and I want to pass it somewhere to a place that expects just two fields but they have those right names the right types there could they should be compatible rust analog to this would be if I had a tuple of three elements and passed it to a place that expects just the first two does that work and the answer is no it doesn't this does not compile there's interesting questions as to why that might be a good idea to not allow this to compile and another example of textbook subtyping the more sort of fundamental one for the academics is what happens we have functions so if we start off with an assumption that we're gonna have some basic type like integers and reals and we're talking about like in the mathematical sense here I don't mean real like floating-point numbers I mean real like you know supporting representing things like pi exactly like you know being able to generate all the digits of pi - whatever precision you want etc so there's interesting questions then when you have that kind of subtyping where you say okay well I have a function that's of type real arrow int and I want one that takes real to real is that legal or how about a function that takes into int can I pass that to a place that wants a function that goes from real real surreal so let's talk about that last example first I have a function that takes integers to integers and the I want to pass it someplace that needs a function that takes reals into Rails is this gonna work and the answer is this won't work because the integer to integer function it assumes its input type is always integer and so you're gonna break things if you pass it to a client that wants an a real the real function because that client might pass it a real number my function wasn't written to support that so here I have an example where we have a twice function that applies its first argument twice to this - it's some inputs and there's a none divisors function that assumes that's good an integer it's gonna give you the number of divisors for that integer I give to some example example inputs and results for that function and the point is that if you try to apply num divisors using the twice function you get nonsense you're gonna try to eventually apply num divisors to two point three and that doesn't make sense you can't talk about the number of divisors in a sense of a way of a number like two point three it doesn't make sense so the point here is just to show that definitely no matter what int arrow int is not a subtype of real arrow real it does not work okay but there was another example I gave if I have a function from reals two ends and I want one that takes real Cerrillos does that work so in this case this actually works out it's something where you can't have a function that takes reals two intz and pass it to something that wants real surreal I give an example here of passing a ceiling function this this modified ceiling function that into the twice function and it all works out in terms of the you plug the types together and there's no errors along the way and this just kind of makes sense if we ignore what I was saying before about one time representations and then let me be compatible mathematically this seems like it should make sense and the reason it makes sense is because the client is saying I handle any real number so if you give me something as enough I I'll give a real number and I'm gonna handle any real number back so if I give a function that is guaranteed to turn reals into integers that's fine the clients able to handle integers it's said I can handle any real in fact that I get out from this function so it's obviously fine they're narrow that to just integers in terms of the function I hand to it okay so how about this example I have a function my hands that takes reals integers and I want one that takes reals - reals I just talked about this didn't I um right now II what I just talked about but I want to show you what this looks like in Java so in Java you could encode this by having a class real and then methods on it that return reals and the point is you then have a subclass int extends real you can have methods that return inst Java compiler compiles this just fine and actually if I want to encode this more accurately I would really talk about real fun that turns reals - reals an int fun that turns reals - intz but actually the interesting thing here is that Sun didn't originally support this code it only added it in 2004 with this thing called covariant return types and that's the first occurrence I think we've heard the word covariance we'll talk about that in little bits so to try to reason about these kinds of relationships to be able to argue why int arrow int and real and a real arrow real are not subtypes but while those other examples are subtypes type theorists often use these things called deduction rules while they write a precondition in a post condition with a line between them so for example of one of these would be hey if a is true and B is true then the statement a and B is also true that's the kind of reasoning you can do using these rules and so a rule for function values would be if I can prove that Y is a subtype of X then I could also be approved that a arrow Y is a subtype of a arrow X and this is the other way of stating this is that the arrow operator is covariant with respect to its return type so the example here that we've been talking about is if int is a subtype of real then real arrow int is a subtype of real arrow real so again it's just the reasoning all the caller can do is get out an X from calling the function so it's safe to narrow it and say I'm gonna definitely always you'll give you a Y and the caller is fine with that they can handle wise because they can handle X's and Y's a subtype of X ok now we turn things on their head and say ok well what about if I have a real arrow int and I want a function that takes instants and this is known as contravariance the idea here is the client is saying i will only feed integers into the function and if you give me something that takes they can handle reals as well that's gravy not all languages actually support this that example I gave you before where I encoded the code the covariant return type in Java you try to encode this example it won't work because Java has overloading on its input types and so it doesn't work out the same way in terms of these things being subtyping but having said that this is what the type theorist would write down they would say look in fact if I could have these two distinct relationships Y is a subtype of X and B is a subtype of a then a arrow Y is a subtype of B arrow X Kovarian which puts a return type and contravariant with respect to argument type and again this just be repeating myself they died ideas the caller can feed in a specific D and get out the more general X and it's safe to be more liberal and provide a function that then can accept any a at all generalizing the potential inputs and narrowing the potential outputs to Y and it's a quick aside here that will come up later what happens if you restrict the domain and range with you want to have Y arrow I and X 0 X what should the top of the line be what should the precondition be think about that for a little bit in the back your head so now we might ask the question well does rust have these properties does rust have these this kind of variance property that I've been describing well we could try plugging in those types I just showed at the very beginning all those examples I gave of compatibility Bowl types so here I have a slice of reference to a vector and a reference to an integer and I showed how on the left-hand side of this picture how these things are compatible but if I trying to generalize that to vit this variance type stuff in terms of functions and actually make a function type that returns a vector and pass it to a thing that wants a function that returns an integer slice it turns out this doesn't compile the RUS compiler rejects this so there's something funny going on here that the first the left-hand side compiles but the right-hand side does not likewise by encode another one of my examples that thing where I talked about a mutable reference to a slice and passing into a context that expects an immutable reference to a slice again the higher-order generalization where I've made these functions that return a mutable reference and it wants a function that returns an immutable reference again code does not compile so from these examples it sounds like we might conclude that rush does not have variants doesn't have covariant return types it seems like so having gone in deep into this topic I'm now gonna do a magic thing and totally misdirect you and talk about something completely different to make you not think about what I've been talking about for a while so here's a little story from one of the server my interactions one of the servo developers so Simon's szczepan was actually here right now you can talk to him more about this and see if he remembers this he came to me and said I have some code that doesn't compile I don't understand why it doesn't compile but I worked on my own so I decided to reduce the code down to a minimal thing that I could understand so I came up with this minimal example that used the standard library type cell but I didn't even understand that I didn't understand understand why I didn't compile so I decided well I don't understand the source code to sell but I can look over it quickly I'll make my own version of cell as well maybe that will help me understand why this doesn't compile so Simon made his own version of cell and when he did that the problem went away and his code started compiling so let's try this ourselves let's make the standard library cell ourselves so here we have my cell and just stores it has some type T it stores an instance of T within itself just embedded directly within its and what you can do you can create a cell all you need to do is call new and past one of these teas you can get the value from the cell this is this makes sense because tea is copy so it's safe to do get and just copy out the value within the cell itself it makes a new copy of it and then the interesting thing is the set method and what the set method does is use a little bit of unsafe code to say let's grab a reference to that embedded value and then use the unsafe method pointer colon colon writes to write in the new value that's going to go in there so this is some code that seems to behave the way that cells should and a fundamental question right now is is this sound' is this version of this code sound is this use of unsafe sound and the answer is that this is actually completely and totally broken please do not do this please do not go and take this code and use it in your own projects it does not work it is bad bad bad um there's many reasons for this one reason is that there's secret information that the compiler makes use of that the standard library cell knows about and this code does not that can expose brokenness with respect to parallel parallel execution and aliasing stuff that's one reason but even in a single-threaded case this is still broken and that's what we're gonna be talking about right now so there's another subtle reason that this broken so let's talk about this why is this broken here's some code now don't panic this is complicated code and I don't expect you to understand it immediately although I do have a link to it as usual so you can go and follow that don't panic linked to the code we're kind of step through it but the important thing is I want to point out there's two printout statements there's a printout statement where we print out the value of the of this thing the cell at at the point in the execution where it's at the end of step one and then we also print out the value at the end so we do that twice and you may notice here that there's two interesting numbers that occur in this program there's a number 10 at the very top where we define that the static variable X and there's number 13 that occurs when we have this local variable Val inside of step 1 when we run this code it prints out 13 for the value at the time of step 1 and then on my machine it printed out 28,000 672 for the value at the end when you see this kind of thing this is usually a sign of something terrible's happens when you have random purrs just pop up so you see garbage like this that's usually a sign something is very wrong but I want to explain how this is happening so again this is the same code except I reduced it a little bit to fit on the slide um we're gonna create a cell this micelle thing we're gonna call step one and then step so here let me show you a picture so here's a picture where we have the cell itself and it starts off with a pointer to the static data area starts with a pointer to X that's what we created the initial step one call we're creating a reference to or the initial cell let's L equal call is creating a cell with a reference to X then the next line we're gonna call step one so the news there's a new stack frame now below it on the stack and it passes in a reference to the cell so we took a reference to the cell that's what our c1 is on this diagram and there's a reference to the cell itself as well as the value we've created on the stack frame the value thirteen then we call step two with a reference to the value so now we have another stack frame that points to the Val and we have another reference to the cell our c2 then we call set with our Val so we've moved the pointer so that cell now points to Val on the stack frame we pop the stack once and we ask hey are c1 what you hold and it says oh I hold 13 that's the first line that we saw on the output and then we pop the stack again and we have a dangling pointer so this is no good this is the kind of bug that Russ is supposed to stop we aren't supposed to have daling pointers anymore so either my cell is broken or the russ compiler is broken or the rest language is broken you know where my belief is here so the question here is that okay well wait is cell also broken and the easy way to test this is plug in cell into that same code again we plug in cell into the same code the exact same code I just showed you that compiler rejects it if IO tells you no no we're not allowed to take the reference to Val when you make that call to step one it doesn't live long enough it has to live as long as some lifetime a and but the value the value borrowing doesn't live that long so the compiler is smart enough to reject this when you use cell and the question is why is this happening what is the difference between my cell and cell I went to the source code and found out look my cell says it has a value and cell says it has an unsafe cell an unsafe cell says it has a value what's the difference here of course the difference is that there's this special my unsafe cell the compiler knows about but still why are we rejecting why are accepting the my cell code and rejecting the cell code and the answer tada is subtyping in parents that thing I tried to get you to snot think about for a while now so yes rust does have subtyping it arises from references and it rises from the region relationship between lifetimes so that's the crucial place where the language developers realized we need subtyping in the language so here's an example of a place where subtyping is put into play this pick function is gonna take two references one is a reference to some lifetime but his lifetime a and another one is a reference to data that has static lifetime and the crucial thing is it's gonna return a reference that has lifetime a points to make lifetime a but we can pass back why this is a place where we can pass back why it's the thing with static lifetime as the return value or we could pass back acts either one works this is a place where there's that compatible again compatibility but at a deeper level in terms of what the compiler knows about so the whole big idea here is that the static reference that's something where we know it it's safe to pass that back and make it and pretend that it's something that has a reference of lifetime a because when you say that a reference has a certain lifetime you're not making any statements about when it will die you're just saying it lives at least this long you're not making any guarantees that it actually expires at the end of that lifetime a so yeah this is me repeating myself um so yeah the reference is able to return and it's sound to do this and there's the syntax in the language for describing this by we say you see that one lifetime out lives another by writing down lifetime : other lifetime and we pronounce that out lives so here we can say static lifetime out lives is lifetime a what about the other direction what if we try to take a reference of lifetime and pass it back as if it had static lifetime and that's definitely rejected by the compiler the Pilar definitely rejects that because it's not sound it would not be sound to take something of short lifetime or potentially short lifetime and act like it has a longer lifetime this is that would be how you get dangling pointers so the crucial thing here is to see for any type T and any lifetime a clearly a reference of static lifetime T should be valid anywhere that a reference of the lifetime a of T is so this is again something we can make that stripped-down example like I've been showing you before where we pass in a static reference into a place that expects a non static reference or we could write it down using against and style rules we say that the light static lifetime out lives the lifetime a then the static reference should be a subtype of a reference with lifetime a more generally we can just not talk about static and all and just say okay if we have two lifetimes be an a and b out lives a then there's a subtyping relationship between the two references the one where the reference of lifetime B is a subtype of the reference of lifetime a and furthermore we've already established that a static lifetime a reference of static lifetime is a subtype of a reference of lifetime tick a what if we go a little further what if we have a reference to a reference should a reference of lifetime a that points the static data be a subtype of a reference of two references of lifetime a mmm I don't know but intuitively all you can do when you have an immutable reference is read the data from it by that intuition by the same logic that for functions all you can do is call them and read their return types so you're getting something out same intuition applies here you could say look for immutable references all I can do is pull things out of them I can't store new things in in principle and thus that's what leads to an arguments that if Y is a subtype of X then in fact yes a reference to Y is a subtype of reference to X which allows us to conclude that this claim this question mark up here above is the reference to static data or reference to a reference of static lifetime a subtype of a reference to a reference and the answer is yes they are and a way of saying this is that a reference to X is covariant with respect to X ok that's immutable references but what about mutable ones should a mutable reference to a static reference be a subtype of a Moodle reference to a non-static reference well we can take that same example from before except now we don't have my cell we take that same example and just use static data and make a reference to reference one of static lifetime and one with non static lifetime and in fact the compiler rejects this if the compiler allowed this we could build the same picture that I showed earlier the same stack frame layout and the same effects in terms of the dangling pointer you'll get when you run this code so it's important the compiler reject this and therefore it's important that when you have this kind of situation then when you have a reference a mutable reference to some data X it's something where you can't have a subtype you cannot use a subtype Y in that place and to me the intuition behind this is that once you allow a mutation via a reference once you have that level indirection allow mutation the type has to remain fixed you can't start trying to narrow the type at that point and the easiest way for me to see this is by looking at other languages like Java so here's some code and Java quick show of hands who thinks this code compiles this is a array of numbers and I'm doing is I'm storing in a float a new float that I create from and I hint here float is a sub type number who thinks this compiles ok interesting it does compile and also Java arrays are covariant with respect to T array of T is covariant with respect to T which means that you can actually create this function that creates an array of integers and passes it into the modify array function which takes an array of numbers and then stores a float into the array of numbers which was secretly an array of integers so now you have an array of integers that has a float hidden in it which sounds bad and it is bad Java compiles this code but gives you a runtime exception when you run it the array B for a potentially infamous array store exception so there's actually a dynamic checks that happen in Java to ensure that you don't get unsoundness because they instead they just fail it's like their equivalent of panic right this is this is the rut this is the Java answer when Russ we say panic and in Java they say runtime exception this is an old historical artifact of Java predates their support for generics where they have better ways that deal with these kinds of problems so going back to our earlier question then that test that was using where I was talking about variants and looking at those examples and saying well is this code this covariance apply here and I said for all those examples I showed before this example is not compiling this example is not compiling but now in this situation with this subtyping relationship where the reference to static data and a reference to non static data you can do the generalization where you plug in to the return type and pass along one function to another and the compiler accepts it so here's the place where we see covariance of the return of a return type when we pass along these higher-order functions this compiles you can follow the link to prove it and in fact rusts functions are even contravariant with respect to their argument type and rust I mentioned contravariance before and that's kind of interesting the reason that a reason that this works for rust and that rust can support this because we don't have method overloading so the same conflict that comes up for languages like Java where it conflicts with that other language feature we don't have that language feature so there's no conflict here so I want to dive a little bit in and explain this very instant a little bit more and how it works so where does it come from the answer is the compiler deduces the variance of your data structures it does so by recursively traversing the structure of your types so here I have an example of this outer inline data and it has two fields instance of t on the field one and it has an inner field that just is a embedded inner inline object that itself has another instance of T and the crucial thing is that the compiler when it analyzes each of these structures it reverses their structural definition and recursos into any other structures that are there to infer ah these are both covariant with respect to T which is interesting this is that isn't that sound it is sound to do this but if you do something like add a mutable reference then things change so here I've now changed things so that the outer ref that first field one stores a mutable reference to a tee while in ER does not inner still has an immutable reference to T or an inner now has an immutable reference to T and so now the compiler infers ah there's potential mutation happening through this reference which means that we are now invariant with respect to T our F is invariant with respect to T while inner ref is covariant with respect to T so there's some interesting things that happen that are very much underneath the hood in terms of you may not even realize the compiler is always doing this analysis for you to ensure soundness to ensure that we don't get those dangling pointer examples that I showed earlier and another detail here that the people who raised their hand for phantom data earlier might already know if the compiler sees a phantom data a phantom data is at zero size type it doesn't occupy any space in the type it's L in the structure itself it's just there to act pretend like you had an instance of this data in order to get to get the various relationships that you want that's one reason for that it's there it's for variance relationship and it's also for stuff with destructors which you can come talk to me about afterwards if you care there's some really grew grotty details about destructors and forcing them to run at the right times and not have dangling pointers and your destructors so going back to our cell and unsafe cell example the unsafe cell is known to the compiler it's a language item the compiler knows about so the compiler treats its treats especially and says this is invariant with respect to T because of that that property bubbles out to cell when it recursively descends into cell verses my cell where the structural definition alone the compiler infer that it was covariant with respect to T and the method that I showed the set method breaks the rules associated with that so that was the fundamental problem is that the set method was not sound it was an incorrect use of unsafe because the structure definition has implications for the relationship between T and my cell that are not preserved by the set method because the structure should be proposing an invariance relationship my cell should be invariant with respect to T the same way that the cell data type is so one solution to this would be to use phantom data again you can actually use phantom data and input an input a function from t to t remember earlier where i was talking about what if you have a why arrow Y and an X arrow X and you want to what is the relationship that M that implies that Y arrow Y is is a subtype of X arrow X and the answer is Y has to equal X they have to be invariant with if they have to be non subtypes each other actually actually have to be equal so a function from T to T is a way of saying this thing has to be invariant with respect to T so that's one way to accomplish this is to use a phantom data but forget I said that if you get nothing else out of this talk I really need to be careful about this if you remember nothing else from this talk it is don't do the mysel example the way I showed you use unsafe cell because it's gonna get it right it's really important to think about that ahead of time if you're gonna at least we're going to use any unsafe code once you start using unsafe code you need to really think hard about do I use be using unsafe cell instead of what other magic um you might be using okay so now I want to go back to those examples I showed at the beginning where I talked about all these examples that seem like they might be subtyping and I'm calling those duck subtyping in a sense that there's duck typing where if it walks like a duck and quacks like a duck it must be a duck here my argument is in fact the opposite where I'm saying yeah those walks and quacks like subtypes subtyping relationship but in fact they're not because they missed that crucial variance thing with how functions are handled so how what are they if they're not subtyping what's going on so yeah here's where I show you the the secret behind the magic and you know what's going on behind the scenes so what is actually happening there and the answer is a whole stuff there's a whole collection of different technologies that are interacting to get those effects that I showed you earlier so there's coercion 'z that are happening in particular when you have a method call X dot M or a field dereference the compiler actually will magically insert either a borrow of X or as many d references of X that it needs to in order to find the member that you asked for so this is a reason that rust who here program ins has program in C++ or C for that matter okay good so there's this distinction in C and C++ between the dot operator and the arrow operator right you would do sometimes you do X dot F and other times you need you um Y arrow F and that always bugged the heck out of me before I understood what it was you know the difference and what they were expressing rust doesn't need the two syntaxes because it's basically magically using dot all the time and figuring out oh we're you needed to have an arrow I'll just let you use dot and I'll put in the dereference and in fact I'll put in multiple D references as many times as I need to there's a stack overflow question that documents how this works pretty well that I linked it to so this that phenomenon of this automatic borrowing or D referencing is what explains the grid I showed earlier with that character right the fact that you're able to pass in a value into something that wants a reference or once a mutable reference that's explained by the fact that will automatically borrow and likewise the factory will pass in reference to something that wants a value that's explained by the fact Abul automatically dereference one note here this special coercion this particular coercion only applies to things that are the receiver of a method call or a field access the X dot something the dot is special there and that if you have a argument that occurs somewhere else in the argument list they don't get this particular treatment and the main argument for why that's the case and why we don't attempt to do is automatic borrowing dereferencing is that basically we there's cases where it's you don't want to infer it you don't want to implicitly be borrowing things because one the aramis's you get you fit when you can't find an appropriate borrow dereference could become pretty bad so it's hard to make good compiler error messages and also a lot of people prefer to have the borrower's be explicit in order to just see in the code oh I'm actually taking a reference here for some reason I don't quite have a good argument for this for some reason this that that disconnect where people want to see the explicit borrows on arguments for some reason that doesn't quite apply the receivers and I don't understand understand the psychology here all I know is I agree with it like my own self so maybe maybe in you know 50 years some will do some cognitive science experiments and figure this out okay another kind of coercion is drf gorshin if I have a reference to a Y and I can dereference Y to get an X out the compiler actually will automatically coerce a reference to Y into a reference to X by automatically inserting dereference operations and that is what explains the ability go from Veck to a slice and then there's automatic ari borrows as well if you pass a mutable reference into an expression context that's also expecting a reference the compiler actually will automatically insert a rebar oh and a dereference and it does this in a lot of places the compiler actually inserts these a lot in lots of places just based on the fact that says oh there's an expected reference here and I'm passing in a reference let's go ahead and rebar oh it here the reason that it does this is that um lots of times when you pass in a reference to a tea you don't really want to move away that reference to the argument you'd rather have it be a new reference that has a shorter lifetime so that you can go ahead and modify the tea modify the reference afterwards there's a great blog post on called stuff the identity function does we're literally blessed just writes down the function that takes in value and you know takes a T and returns a T and you would think that that's a silly function what would you use this for but he points out that that's a there's a issue here where it causes an interesting effect that interacts with this phenomenon so I recommend reading that post if you have not already then we have protocols you have things like that phase one phase two where I was turning an ast into Mir and then Amir into output and the question was well we have two different kinds of error and yet we somehow got end-to-end air that was that code again where we have two different kinds of errors phase 1 phase 2 and we compose the two functions and we somehow got end-to-end error out so our phase 1 error and phase 2 error subtypes of end-to-end error you probably already know the answer the answer is no the answer in this case is the magic is all hidden behind the try macro in particular the try macro actually expands into this little match expression and part of that match expression calls the standard convert from function so oh and there's this question mark form that you know is in the nightly compiler it's the same it behaves the same as try I showed you try because I can easily show you the macro expansion of try but question mark does the same thing in this case the important thing is that there's the conversion being inserted so that the error gets converted from one air into another automatically based on the context so in this case we have that particular arm where we got an error and we have the conversion there that combined with these things I didn't show you I didn't show you the from implementation for the two kinds of errors for phase one air and phase two air at these this is the magic sauce that's allowing us to just compose those two functions about any extra effort finally there's some gotchas I want to note here I went over these things about coercion x' and automatically borrows in order for them to apply the compiler actually has to know what the expected type is it actually has to know what the thing is being coerced to if the compiler doesn't have that information then it can't do the coercion so the example I have here is that there's a process function that wants a slice and gets and gets that reference to a vector and that works it compiles but process to its generalized it says I take any input at all where the input trait is implemented for for a slice for a you know idea Sun sized array of I 32 and the compiler rejects this bottom case even at least two things look like they should both work in principle the reason this doesn't work well the first case is obviously as I said before of reference to a vector can be coerced into a reference to a slice but the second case the compiler has to decide what is the type I and it infers the type I must be Becca by 32 it does this type inference unification thing and determines it to commit early on says I must be a Becca by 32 and once it decides that then it goes and says well let me go find an implementation of the input trait which of course doesn't exist here and that's why the cam fails you have to here you have to actually do the coercion yourself manually have to add in something like an as slice call and already get that effect okay so those are all my examples and whatnot I'll take questions I think in a moment pop quiz so what's the relationship between these references here you know who knows is that is the static reference a subtype of a reference of type of lifetime a what about a reference to a reference when the thing you're pointing to is static and what about a mutable reference to a static well one answer is that how often do you actually ask this question hey maybe you shouldn't worry about too too much subtyping and rest doesn't have to be in the forefront of your mind in fact and I have other arguments for why subtyping can't possibly be that important in rust but I won't talk about it here but in case you're curious what the answer is it's yes yes no okay so and what about this variance thing and the answer is that getting covariance and invariance right does matter it matters a lot for soundness properties I already showed you the example of a dangling pointer but you don't need to think about it unless you're writing on save code so because once on C if you don't any unsaved code then it's the compilers job to get this right I already said before they can pilers inferring the variance of the various types so you don't need to think about invariance think about variance if you're not doing unsafe and in fact it turns out I'd argue you don't need to think about variants even if you are doing unsafe as long as not unsafe with generics it's when you start mixing unsafe with generics when you get to start having those um those reference types getting thrown in there secretly you didn't that you didn't anticipate that you need to then worry about in terms of the dangling pointers that arise but if you're doing on safe code where the types involved aren't generic they're always just arrays of integers for example there's no references then you probably can get it right without thinking too hard about this okay there's more information about all these topics namely in the RCS like the DRF core are see the book I don't know Steve if the book covers this topic and that much detailed but you can look there and find out and the rusty nomicon does delve deeply into a number of these things but I did notice it basically has a to do for the thing about how method dispatch goes and the automatic borrows andrey borrows and d references so not only look at them but contribute back to them go ahead and you know see if you can find some way to express these properties and get it back to that give back to the community and finally uh so yeah this sort of the theme of this talk was to ask questions the whole time and so you don't wonder about subtyping and explore it so you know explore through code but also make sure you do the experiments properly you know don't just assume that you understand what's going on try small variations like I said with the art ii clark law you need to push the boundaries in order to discover what the impossible things are do that and finally you know the magic and rust it's as real as you want to be if you want there to be no magic then go ahead and learn about the compiler learn about how everything's implemented but it's okay to believe in magic so you don't have to learn how the compiler works in all cases you can trust the magic underneath the hood that's all thank you very much unfortunately we don't have enough time for questions right now we're running a bit late so we're going to take a ten minute break right now I'm sure Felix is available for questions during the break

Channel: Rust

Views: 12,289

Rating: 4.8938055 out of 5

Keywords: rust, rustfest

Id: fI4RG_uq-WU

Length: 53min 42sec (3222 seconds)

Published: Fri Nov 11 2016

Reddit Comments

[u/[deleted]]

This is good: if you've seen words like "covariant" and "invariant" in RFCs and wondered what that means, Felix explains!

This video is essential to understanding the nomicon page if your brain often goes numb when reading dense technical documentation like mine does.

[u/RustMeUp]

That was really great and I enjoyed it. I still haven't quite interned variance but at least I can follow along if I stop to think long enough.