Rust Programming Language RustFest 2016, 11 Nov 2016

Previous Meeting Next Meeting

⏯

youtube image

►

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

Description

“Any sufficiently advanced technology is indistinguishable from magic.” – Arthur C Clarke

This is a talk about magic. In particular: Rust has subtyping, but it may not be in the place where you thought it was. My primary goal is to explain that metaphorical sleight-of-hand, in two parts. My secondary goal is to convey that most of the time you need not think about subtyping, except when doing particularly hairy data structure development where questions arise around “variance.”

---
For more go to https://rustfest.eu or follow us on Twitter: https://twitter.com/rustfest

Help us caption & translate this video!

http://amara.org/v/2FiX/

A

So next we have our first keynote. Our speaker is somebody to get very excited about.

A

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.

B

Okay, secretly type in my password.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

B

So let me take care of that right now. Oh I knew that was gonna happen.

C

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?

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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?

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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?

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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?

C

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.

C

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.

C

Why it's the thing with static lifetime as the return value or we could pass back acts either. One works.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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!

C

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.

C

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.

C

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.

C

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.

C

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.

C

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?

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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?

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

C

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.

A

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.