Moves and Borrowing In Rust

Adam: Welcome to CoRecursive, where we bring you discussions with thought leaders in the world of software development. I am Adam, your host.

Intro

Jim: Basically, in my experience, and I’ve talked to some friends of mine about this, it really is something that you can internalize, just as well as the other things. And it really does correspond to the costs of the computation you’re doing in a better fit than the C++ world. C++ is trying to give you the illusion of value-oriented world where assignment just means that you’ve got a copy.

But that’s not actually the world that we live in. We live in a world where we care about memory, where we care about time spent copying things. The mismatch with reality is actually on C++, this side here. And what Rust is doing is it’s simply taking the real costs that you are always paying, and making them show up in the type system.

Adam: Hey, this is the second interview with Jim Blandy, co-author of Programming Rust. Today, we get into the details of borrowing and ownership. If you haven’t listened to the first interview, you should probably check it out first. Today, we get down into the actual weeds of how Rust handles ownership, and borrowing, and how it’s different from other languages. There’s also at least one joke about linear algebra that went way over my head. Enjoy. So, Jim, thanks for coming back to the podcast.

Jim: Yeah, thanks for having me.

Adam: So, last time, I think you did a really good job of explaining, I think, why Rust is important and what job it’s trying to solve. And for me, to understand how that actually works, I think it’s great to actually, talk about examples, and see how that works in practice down at the actual level of coding, and memory mapping. So, yeah, I want to dive into some of that today. I feel like this is becoming maybe the world’s smallest book club, where I just bring you on, and ask you questions as I read the book.

Jim: Yeah. Well, as long as people have a good time, that’s fine.

Adam: First of all, it made it further through the book. And the book now has a coffee stain on it, which I think shows that I’ve actually… that’s how you know it’s been used.

Jim: It’s a mark of honor, yeah, it’s got to be frayed a little bit, and somebody put something on Twitter that shows that a picture of their kid drooling on it. And I think that’s pretty good, too.

Rust’s Memory Management Strategy

Adam: So, yeah, for our listeners, if you haven’t listened to the first episode, I recommend you go back to it. And we’ll just jump in with the specifics. So, memory management strategies. What I’m used to pre-reading this Rust book is there’s languages like C, where have to free the memory yourself. And then, where I spend most of my time, which is in garbage collective languages, where the freeing just happens, and I don’t even worry about it. It’s like a runtime properties. So, where does Rust fit in this spectrum?

Jim: Okay. So, Rust actually, threads a third way between those two extremes. The premise, both C and the rest of the languages, both C and C++ versus the rest of the language, they both have the same problem, which is that you want to make sure that the thing that’s getting pointed to outlives the pointer. And there are actually two ways to phrase that.

You can say the reference has to outlive the pointer or you can say that the pointer must not outlive the reference. And so, the way that almost every language solves this, is by saying, look, we’re just going to periodically scan all of your memory, and find every pointer that could possibly be used, and make sure that we only recycle the things that are never pointed to, and that’s garbage collection.

And garbage collection has this really nice property, which is that it guarantees that you never have a pointer that’s pointing to memory that’s been recycled. And that’s essential for security. And Java was the language, where garbage collection went mainstream. [inaudible 00:04:28] had it from the beginning. But until that point, people were uneasy about it, and they weren’t sure whether the garbage collection was suitable for use in a serious systems programming language.

But then, Java showed that it was something that could really be made workable. And one of the reasons was they wanted Java. Java was designed to be a language that could be shipped across the network, and it could run on your web browser, it could run on a handheld device. And so, they needed that security property and garbage collection is a way to satisfy it.

Now, the problem with that approach is that the way it goes wrong is if you have a pointer sitting around to something that you’ve forgotten about. Then, even if your program is never actually going to use it again, the garbage collector can’t tell that, or often can’t tell that. And the garbage collector will blindly retain everything that that pointer points to, and anything that can be reached from that pointer.

So, if you’ve got some like, what happens in JavaScript all the time is somebody will set, you’ll set an event handler on something, and you’ll forget about it. Event handlers and JavaScript are kind of like, it’s really easy to lose track of them. And so, you’ve got event handler sitting around, and the event is never going to happen. And it’s pointing to a closure that it’s going to run if this event never happens. And then, that closure happens to have closed over some other variable that you weren’t expecting.

And suddenly, the next thing you know, you’ve been trained the entire text of the Encyclopedia Britannica. And it’ll never go away, and you don’t know this. And so, there are tools in JavaScript for saying, “Hey, who is holding on to this? Why is this thing reachable?” That the modern web developer tools provide five ways to answer questions like that, because that’s the problem you run into.

You run to what amounts to leaks. But leaks are safer than dangling pointers. In C++, the programmer gets to decide when something gets freed. And what that means is that if they are wrong, if then they free something, while this unexpected pointer is still around, then that pointer is now a live wire, it’s a bomb waiting to go off. And you end up with crashes, or security holes caused by people accidentally using pointers to memory that’s been recycled.

And so, there’s this tension. One, you want to make sure that the language is trustworthy, and you want to keep objects around for a long time, or you want to keep objects around as long as they could be used. But then, two, you want to leave the programmer in charge of how much memory they’re using. If the programmer believes that their copy of the Encyclopedia Britannica is no longer necessary, it should go away at that point.

And so, basically, C and C++ give you the second property that you are in control of when memory gets used, and when it gets freed. And basically, all the other languages fall on the side of safety. And then, the failure mode is that you don’t get dangling pointers, but the failure mode is that you get leaks. And so, neither of those compromises are acceptable for Rust. Rust has to be a safe language.

And it also has to as a systems programming language, it also has to leave the developer in charge of when memory gets freed, and when it goes away. And this is actually really nice. Because when I work in JavaScript, I actually feel really uncomfortable. If I’m going to build up some big table, or some big map, I’m always concerned that if I don’t manage it very carefully, that I’m going to end up creating something that’s going to blow over time, the longer you have this page open, or the longer you have this applet open or whatever, the more memory it’s going to consume.

And so, I ended up going over my code of the fine-tooth comb to look very carefully at what I’m retaining and what I’m pointing to. And in the end, that kind of care looks a lot like the same kind of care that a C++ programmer has to invest in making sure that their pointers are valid. And so, it’s actually just two sides of the same coin. It’s just that I and the JavaScript case, or in the GC case, the failure mode is relatively benign.

Adam: I’m not sure that a lot of JavaScript programmers are as concerned. Maybe they should be, but-

Jim: Yeah. Well, the evidence suggests that many people are not too concerned about this. So, neither of those compromises is acceptable for Rust. And so, Rust has to actually A, make sure that your programs, make sure that your pointers are always legit, while B, still leaving you in control of when memory gets freed. There’s a two-level approach.

The first step is to make sure that every value in the system has a very clear and obvious owner. We are accustomed to thinking about the heap in a language like Java, or a language like Haskell, or language like JavaScript. We’re accustomed to think of a heap of stupid graph of objects. And you can build any kind of structure in that graph you want.

But what that means is that it’s not clear to the system at all, and there was no source level indication of how long different parts of that graph are supposed to live. And so, Rust says that every value must have a clear owner. And usually, and basically, all of these owners are rooted in local variables. Variables that are local to a call. Rust has global variables, but their use is very restricted.

And they’re actually a pain. So, for most intents and purposes, you can say that Rust doesn’t use global variables. And that means that the ownership of every object in a Rust system is rooted somehow somewhere in some local variable. Now, that means that if you’ve got a local variable to type string, well, it’s pretty obvious that the local variable owns that string.

But what if you have a hash table entry? Well, you have a big table of strings. Well, then you’d say that the hash table owns the keys and values that are stored in it, and then something else owns the hash table. But the keys and values are uniquely owned by the hash table, and the hash table is uniquely owned by something else.

You can go up and up from the owned value back to its owner. And eventually, you find yourself rooted in some local variable. And what this means is since every value, okay, so maybe I didn’t say this, but everybody also has a unique single owner, which is a little weird-

Adam: Just one on?

Jim: Just one. There’s always a very clear, single owner. And that there are ways to break out of that. There’s actually an explicit reference counted pointers type. And that’s something where, obviously, if you have many of these reference-counted pointers, it’s only when all of them go away that the object gets freed, that the things that are pointed gets freed.

But that’s something that you have to ask more explicitly. And so, the usual behavior in Rust is that every value has a unique owner. And when that owner goes away, when that variable goes out of scope, or when that element is removed from the hash table, or when the vector has that element deleted from it, when the owner goes away, the value is freed at that time.

And so, that’s how you get control over the use of storage. Your variables go out of scope at the end of the block if you’re not returning them. When you delete an element, or when you remove element from a data structure, that its contents get freed. Freeing memory always happens in response to some specific thing that you did in your program.

And so, that’s the way Rust puts the developer in control of the lifetime of the values. Now, that model has the merit of simplicity, but it’s really limited, and you can’t actually write real programs that way. And so, there are two ways that Rust relaxes the constraints on this. And the first way is that you can move values from one owner to another.

Vector Moves

For example, a vector, so you probably got a vector of strings. The vectors pop method, it takes the last element, or removes it from the vector, and it returns it to you. Okay. When it returns that value, that’s not simply… it’s not just like returning a pointer to it. It’s actually moving ownership of the value from the vector, the vector no longer owns it, and it transfers ownership to the color of pop.

So, whoever called pop, now they are the owner of that element. And so, if you imagine you’re popping off an integer, and this is silly to talk about, but imagine you’re talking about a vector of strings, and the strings would be really big, then it makes sense to say, “Oh, now, I own this string.” And I’m responsible for deciding how long it lives, or a vector.

You get a vector of anything. You get a vector of gigantic hash tables. So, in all these situations, moving ownership is something that makes sense. And it preserves this property of unique ownership that the value it used to be owned by the vector, and now it is owned by the color of pop. But it had a single owner at every moment.

Adam: I think he picked pop for a reason. So, I’m imagining pop, you have some sort of memory, where the array is, and now we’re taking off the last element, but what about something in the middle?

Jim: Okay. Yeah. So, it turns out that Rust does not have any primitives, which would allow you to move a value out of the middle of a vector. And so, this leads us to the third kind of access is that there are various ways that we relax it. The first is move, that you can move ownership of value from one thing to another. And whenever we build up complicated values, we’re basically building them up one move at a time.

The second way that we relaxed the rules is that we let you borrow values. There is a way to leave the owner of a value undisturbed, the owner doesn’t change, but you get to temporarily grant access to that value to somebody else by borrowing a reference to the value. And so, when you refer to an element in the middle of a vector, what you get when you subscript a vector, the subscripting operator returns a reference to that element.

It borrows a reference to that element. Now, references, they are pointers, but they are constrained. They are constrained by their type to not outlast the thing that they are borrowed from. So, if you have a vector, and then you refer to some element of that vector, the type of that reference that you get to that element says, marks it as something that must not outlast the vector.

So, if the vector goes out of scope, the reference that you borrowed to its element has to have gone out of scope first, or if the vector gets moved away, you can’t move that vector to some other owner until the reference that you borrowed to its element has gone away. So, references are statically constrained to only live for a certain restricted part of the program.

And that’s how Rust makes sure that references are always… they’re always still pointing to something that’s still there. So, you’ve got owning things, and owning references, owning pointers can last forever. You can move them around. But references are constrained to live within a certain lifetime. They can’t outlast the thing that they point to.

Move Example

Adam: Actually, maybe it would make sense to talk about an example. So, just for movement, there’s this example in your book, where you went through… so you had a Python example with array of strings. And then, you had a C++ example. Maybe, could you describe that for us?

Jim: Yeah, sure. What this part of the book is after is it’s talking about this ownership thing. And one of the things that I wanted people to notice was that even the very simple idea of assignment, assigning one variable to another variable, is actually something that where the meaning of that varies a lot from one language to another. In Python, all of your variables are reference counted.

So, the example that I use, I say, “Well, let’s say that we have a list of strings.” Well, okay, the list has three elements. And it’s got this little array of three elements that’s allocated in the heap. And then, each one of those elements points to a string, and the string has this text that’s allocated in the heap. And the list has a reference count on it that says, how many things are pointing to it.

And so, when you first create this list, the reference count is going to heck, it’d be one. And then, the reference counts and all the strings that it points to are going to be one because the region pointed to by the vector’s elements, or by the list’s elements. Now, if you assign that list to another variable, the only thing that happens in memory is that the reference count, the pointer gets assigned to the new variable, and then the reference count on the list gets bumped up.

So, now, it says, “Okay, I’ve got two pointers to me.” If you assign that list to a third variable, then the reference count will jump up to three. And what that means, the way Python has done this, it means that assigning from one variable to another is very efficient. You’re just copying a pointer over, and incrementing a reference count. But it does mean that deciding when to free a value is complicated.

You can have pointers into this structure from anywhere in the program, and any one of them will actually keep the structure alive. And although Python does use reference counting for most of its management, it does have to fall back on a garbage collector in order to decide when to get rid of things in the end, because there are certain structures that reference counting doesn’t handle correctly. Okay.

Adam: So, you need a garbage collector to handle this willy-nilly reference pointing to the same-

Jim: In general, in general.

Adam: In general.

Jim: Not in this particular example, but in general, you’re going to have to use, or you’re going to have to look over the entire program’s memory to decide whether anything’s pointing to this. And so, that means you got to have a garbage collector. So, if you write the equivalent program now in C++, the story is very different.

Let’s suppose you have a standard vector of standard strings, okay. And you create it, and it’s got three elements, or whatever. And at first, this looks exactly like the Python situation, you’ve got a heap allocated array that’s got three elements. And each one of those elements points to a string, and each string has a buffer in memory, heap allocated buffer in memory.

Now, in C++, when you assign that vector to another vector, the rules of C++ say that assigning a vector makes a fresh copy of the vector. And making a fresh copy of the vector means making a fresh copy of each of those elements. And then, C++ says that making a fresh copy of a string these days, it says making a fresh copy of a string makes a fresh heap copy of that string.

So, if you take that list of three strings, and you assign it to two other variables, you will have copied the entire thing over twice. And so, you will end up with three different vectors and nine different strings. And so, this is surprising because you’d think that… I mean, assignment is such a primitive operation, and it’s the same for passing values to functions, or building data structures.

These are all, these fundamental assignments, like operation, and in Python, it’s really cheap to assign. But then you have to have a complicated thing to track when to get rid of things. And at C++, assignment can consume arbitrary amounts of time in memory. Now, the benefit of C++ is that when one of those variables goes out of scope, it always clears away, it always frees everything that it owns. And so, the copying is expensive, and the copying is expensive, and the lifetimes are simple.

Adam: And there’s observable behavior differences here. Because in Python, I can make a change to my copy, and the original one is also changed.

Jim: Yes, exactly. The sharing is evident. The sharing is visible to the program. And it’s actually, this implicit copying behavior in C++ is surprising to programmers a lot, because one, it’s not what most other languages do. Most languages behave like Python, Java behaves the same way, JavaScript is the same way. And so, C++, it’s a foot gun in C++ that you may end up inadvertently making expensive copies of something that you hadn’t expected to be making a copy of at all.

It turns out that at one point, somebody measured an allocator activity in Google’s Chrome browser that turned out that half of its calls to malloc were from standard string, or save cost by copying standard strings around, which is responsible for half the malloc traffic. And I’m not saying that it’s not the memory consumption, but it’s just a number of calls to malloc.

So, this ends up, and that certainly wasn’t really necessary. It wasn’t what they had intended. It’s just the way that things ended up as a consequence of the stock behavior of C++.

Adam: So, you say that this C++ copy is unintuitive. But I found the recipe of your unintuitive.

Jim: Okay. Well, so the Rust behavior navigates a middle path between these two things. It doesn’t want to use a garbage collector. It doesn’t require that you do something. The garbage collectors are unpredictable in practice. People love them when they work. And then, when they don’t work, it’s bewildering. And Rust wants to leave the programmer in control of the performance of their program.

And so, it doesn’t use a garbage collector. And it doesn’t want to do the copies that C++ does. So, what Rust does is when you assign a vector of strings, you can have exactly the same type, it looks exactly like the C++ in memory. But when you assign that vector to a new variable, it will move the value that is when you say S equals T, you’re moving the value of T into S.

T becomes uninitialized. It no longer has a value. As far as the compiler is concerned, that is now an uninitialized variable. And S now has taken over the value that used to be in T. It’s taken ownership. And again, it’s preserving this single-owner property. Like I say, it’s the middle way, because ownership is still clear. Now, S owns the value. If S goes out of scope, and you haven’t moved to seeing someplace else, that’s when you free it.

That’s when you free the value. But at the same time assignment is cheap. All you did is you copied over the header of the value. In the case of a vector, you’ve got these three words that say here’s the pointer to the heap allocated buffer, and then here’s the capacity, the amount of actual space it’s got available. Here’s the actual length, the number of elements stored in that presently.

And when you do a move of the vector, it’s only those three words that get moved over the memory and heap. The memory and the heap, the elements just sit where they are. So, the assignment is cheap, ownership remains clear. And the only consequence, the only downside is that you can’t use the source of the assignment anymore. It’s had its value moved out, and it’s now uninitialized.

Linear and Affine Types

And so, yeah, I guess that is counterintuitive. These are called linear types. Because the idea is that you don’t have the forking of where a value suddenly splits into two values, or a value suddenly has two owners. Every value makes a linear flow through time. It’s actually fine types. But that’s a type theory con. We probably shouldn’t talk about.

Adam: It’s upon, sorry, no, we shouldn’t talk about it now.

Jim: Okay. So, here’s the idea. So, you have these linear types. And these linear types were invented as a simplification or as a restriction of logic. It originated as people were talking about logics. And okay, if you know that A implies B, and B implies C, then you can prove that A implies C. And so, people just, I don’t quite know what the motivation was.

But somebody invented something called linear logic, which where you only get to use a fact once. If you know that A implies B, and then you use that fact in a proof, you can’t use it again. It doesn’t correspond to anything in logic at all. Because if something is true then it’s true. But the nice thing is that it does correspond to values in memory.

That is, if you have big array, and you modify, you store a value, and some element of it. The prior value of the array is no longer available, you can’t use it. And so, if you want your logic to serve as a backing for a type system, then that’s exactly the property that you want. You only get to use this value once because you’ve side affected it. And now, the old value of it is gone.

You do a destructive update to something, well, something got destroyed. And that’s what the linear type says. And so, then somebody else… and so, linear types, were like I say, they were a restricted version of the logic, and they’ve also required that every valuable be used once.

Adam: Oh, I see, you had to use it.

Jim: Right. Yeah, you have to use it exactly once. And that’s why it’s linear. If nothing collapses, nothing gets doubled. And so, if you didn’t want to use it, you can always just pass it to a function like drop. But the idea was that, again, this is going to be used to model values like arrays that needed to be updated disruptively.

And if they were big, heavy, expensive things to allocate, you wanted to make sure that when people freed them, they did so knowingly. And so, the idea was that you would require them to drop things explicitly, too. And then, it turns out that people don’t really care about that. As long as a value doesn’t get used twice, it’s clear why you can’t use… why disruptive update means that you can’t get at the old value anymore.

But it’s actually fine if you just let the system go and clean up things if you don’t happen to use it at all. And so, when you relax linear types, and allow people to just drop values on the floor, well, it’s like linear do it better. Well, okay, so in linear algebra, you can have a linear transformation, which is just like say, if you’re doing it two space, it’s a two-by-two vector.

But then, you can’t do translations in linear transformations. You can’t actually move the origin to a different spot. You can’t move things around. So, if you do want a transformation that can move things around, you need to use what’s called an Affine transform. And this is a two-by-three vector or a three-by-three vector in homogenous coordinates.

And so, an affine transformation in linear algebra is a generalization or relaxation of a linear transformation. And so, an affine type system is a relaxation or a slight generalization of a linear type system. And so, it’s this stupid in-joke. So, strictly speaking, Rust has an affine type system in that if you don’t use a value when you get to the end of the block, if you didn’t use it, it gets freed.

Adam: I shouldn’t have asked you a joke where the punch line involves knowledge of linear algebra.

Jim: That one is pretty weedy.

Assignment in Rust

Adam: So, to bring it back, so I’m not saying it’s bad that assignment is different, but I think there’s a information theoretic perspective in which what you find surprising about a language is probably the most important thing. And certainly, this is a surprising thing. Did Rust change what assignment means?

Jim: Yes. Well, okay, so in my defense, in Rust’s defense, first of all, I’ve pointed out that Rust, that Python and C++ already disagreed drastically on what it meant. And so, if Python and C++ are allowed to do drastically different things with assignment, then I think it’s perfectly legit for Rust to choose yet a third way. But yeah, I think you’re right that what’s surprising is an indication of where the most information is being conveyed.

The thing is when you think about it, C++ is a mature language. You’ve got a lot of people putting a lot of energy into pushing that idea as far as it can go. And you know how local maxima are, right? You’re not going to get significant advances from something as polished as C++, something as mature as C++. You’re not going to make significant advances along one axis without giving up something else along another axis.

And so, this is just Rust’s… one of the bets that Rust makes is that, actually, this is something that people can learn to use, and something that people can be productive in. And learning to program wasn’t really easy to begin with. When you were learning to program, you learn to internalize a whole lot of really strange stuff. And why does it always have to be the same strange stuff?

Why can’t we have some new strange stuff? And basically, in my experience, and I’ve asked, I’ve talked to some friends of mine about this, it really is something that you can internalize just as well as the other things. And it really does correspond to the costs of the computation you’re doing in a better fit than the C++ world. C++ is trying to give you the illusion of a value-oriented world, where assignment just means that you’ve got a copy.

But that’s not actually the world that we live in. We live in a world where we care about memory, where we care about time spent copying things. And so, the mismatch with reality is actually on C++ aside here. And what Rust is doing is it’s simply taking the real costs that you are always paying, and making them show up in the type system.

Uninitialized Values

Adam: That makes sense. Back to your example, when I did this assignment, and so now it’s a move. So, my previous value is now uninitialized. So, aren’t I now reintroducing the C++ problem of being able to access something that’s uninitialized or that’s been freed?

Jim: Well, so one of the things Rust forbids you to use an uninitialized variable. You can declare a variable without setting its value. You can say vector, I want V to be a vector of strings. And you don’t actually have to provide an initial value at that point when you declare it. But Rust does require that every use, every read of that variable, you must be unable to reach that read from the declaration without first going through an assignment to it.

That’s every path from the declaration, the variable to what use the variable has to be preceded by something that initializes it. And so, Rust is already doing a certain amount of flow sensitive detection of, “Hey, is tracking,” or where in this function, at which points is this value initialized, at which point is this variable not initialized? And when you do move, that variable becomes uninitialized at that point. And so, you get a static error, if you try to use it, you get a compile time error if you try to use a variable whose value you’ve moved from.

Adam: And that’s really something that that’s something I haven’t seen. The table stakes on compilers have had been lifted up here, I think, to a higher level than I’m used to.

Rust as a Sound Language

Jim: Yeah. What’s going on is that Rust is really trying to say, we want to be a sound language. People talk about memory management as the big thing. But really, what’s going on is that Rust wants to be a sound language, where if a variable has a type, or if an expression has a type, that every value, which could ever appear there as the value of that expression, or as the value of that variable really has that type.

And that sounds like a really modest promise. It’s almost tautological. Except, C++ doesn’t make that promise. And so, the tracking of what’s initialized and what’s not initialized is really just in service of making sure that the language is sound. Obviously, an uninitialized variable has a type, but it doesn’t hold a value that’s been properly initialized at that type.

And the memory stuff is really just again, it’s just a way of serving the principle of soundness. If you want dereferencing, a pointer to have the type that the language says it does, you’ve got to make sure that that pointer is valid. And the soundness is really what it’s all aimed at.

Adam: So, I’m not sure about C++, but Java, for instance, has nulls. And they just say that’s just part of the set of possible types that this can be. So, this is an object, and one of the possible object values is null. How does Rust handle that?

Nulls Are Not Great

Jim: Well, so Rust actually takes a page from Haskell and ML. And I think another number of other languages like this. And it says the pointers can’t be null. Rust’s safe pointers are never null. And if you want to have a nullable pointer, you just have to say it explicitly. There’s an option type, which I think it’s maybe in Haskell. And I think it’s also option in ML.

And what that means is that you don’t have when you’ve got a nullable pointer, the type of that value is not pointer, it is option of some pointer type. And so, you actually have to match on the option, or you have to do something to check whether the pointer is actually present before you can use it. And so, this is a funny thing, because unlike the moves, and the borrowing, and the references, that stuff is really heavy, complicated, strange, new type theory.

Option, making pointers non-nullable, and then require people to use option when they do want to know of a pointer, that’s really straightforward. There’s no way to create a null pointer. And when you do want to have something that may or may not be there, you have to wrap it in option. It’s really easy to understand. But it makes a huge difference in the code.

One of the things that I find now when I work in C++ is I still work on Firefox, and Firefox has this huge C++ code base. Is that it’s actually pretty scary, how often there are implicitly nullable pointers that really are sometimes null under certain circumstances. And there’s no indication of this. If you want to find out whether a pointer is safe to dereference in C++, you’ve got a hunt around.

If somebody left you a comment saying this pointer is always non-null, then that’s really awesome. But for the most part, you have to hunt around, you have to try to guess, you have to see if other people are checking for it to be null elsewhere. But that’s dicey because maybe they are always, maybe they already know, maybe they checked previously. It’s not a sure thing.

And so, C++ code is really riddled with all of these invisible option values everywhere, and you don’t know which ones they are. And it really makes the language a lot harder to work in. Whereas, when you’re in Rust, if there isn’t an option in that thing, then you know it’s there. And it’s much, much simpler. And when you do put an option in Rust code, then suddenly, every time you use it, you have to check it.

And it’s a little bit of a pain. But what it does is it pushes you to say, “Well, wait, do I really need this to be optional. Maybe I can, instead of using an option here, maybe I can just simplify my type, and guarantee that the value is always there.” And now what you’ve done when you do that is you’ve taken your type, and it used to have two variants. It could exist in either of two states.

Maybe the pointer is there, maybe the pointer is not there. And when you say wait a second, no, I’m not going to do it, I’m just going to guarantee you that the pointer is always there. Now, you’ve halved the state space of your type. And that it’s really a big help. So, I think what’s going on is that nullable pointers, implicitly nullable pointers, like you’ve got in Java, and like you’ve got in C++, invite programmers to create types with many variations.

They could be in many, many different states, which need to be handled distinctly in a way that is invisible, and that the reason that we have, null pointer crisis as a problem, or null pointer exceptions in Java, the reason that we have that kind of thing showing up so often is because it confuses people. And the JavaScript has the same problem you get, defined as not a function, or you get these things showing up in consoles across the web.

Adam: I forget the man’s name who came up with the null concept and said it was like his biggest mistake ever or?

Jim: Tony Hoare is his name. It’s actually the same last name as Graydon Hoare, who’s the inventor of Rust, or the original designer of Rust. Yeah. Tony Hoare called it his billion-dollar mistake, introducing null pointer into ALGOL. And the funny thing was that, basically, he said it wasn’t something that he thought through very carefully. It was just like as a draft. Yeah. Well, I guess you could just make zero via legitimate value, and then you could have a check for it. And sure, yeah, seems fine. Well, throw it in. Thirty years of people losing track.

Adam: Oh, it’s a plague, for sure. Once you don’t have it, I think it’s… well, yeah, you still have options. So, we have to be explicit. And I think it’s such a great change to have an explicit rather than anything anywhere.

Jim: Yeah, yeah. Option is such a boon. And like I say, it’s super low tech, this is not complicated type theory. This is just an enum with two variants, and that’s it. And it’s such a help.

Copy Types

Adam: So, in Java, in C#, in lots of other things, we have values that can’t be uninitialized. Like an int is not going to be null in Java. It’s going to be value of zero or something. So, how does that work in Rust? Do they move? Are they defaulted?

Jim: Okay. So, yeah, for Java to have the security properties that it wants to have, it has to make sure that your variables are always initialized. So, it’s got the same kinds of rules that Rust does. So, there are certain types, I think what you’re getting at is copy types that there are certain types that are so simple, that it’s ridiculous that moving them would leave the source uninitialized.

If I’ve got an integer in a variable, by the time I have moved that value to another variable, I’ve already made a complete independent copy of that value. You’re just moving 64 bits from one spot to another, and there’s no reason to mark here, or the source of that assignment as uninitialized, because it’s perfectly usable. Now, that’s very different from a string.

If I have a string, a string has a pointer to a heap allocated buffer. And when I move it from one variable to another, treating both of those as live values is actually dangerous, because you’ve got two pointers to the same value. And it’s not clear, two pointers are the same, heap allocated buffer, and it’s not clear when that heap allocated buffer should be freed anymore.

So, it’s only types where the act of doing a move effectively gives you a working copy of a legitimate copy of the value. And so, that’ll be types like int, or floating-point values, or care, Booleans. And also, if you just have a structure that only includes such types, if I’ve got a struct of two ints, then certainly assigning that could legitimately… I’ve effectively made a copy.

So, what Rust does is it says that there’s a special class of values called copy values. And when a type is copy is as the way we say it, when a type is copy, that means that assigning a variable of that type to another, or assigning a value of that type, or passing to the function does not move the value, it copies the value. And so, integer types are copy, like I say, all the primitive types are copy.

And so, if you pass an integer variable to a function, then that integer variable still has its value. If you assign that integer variable to some other variable, then it still keeps its value. And this is a ease of use thing, because it’s just silly to make people explicitly copy or clone values when they’re trivial. Now, when you declare your own type, like I say, the example I gave before, was it, what if you make a struct of two values, like say, you’ve got a point that’s got an X and a Y coordinate.

You may want that type to itself be copy, and you can ask Rust to mark it as such. And as long as your type doesn’t have anything, as long as your type consists only of members that are copy themselves, Rust will say yes, your value can be copy. But if you’re tight contains anything that owns resources, like a string, or a vector, or a file descriptor, or anything like that, then Rust refuses to make it copy.

And so, copy is really restricted to things where a bit-for-bit duplication is all you need. And if you need to do any kind of resource management, then you can’t make a copy. But you can implement the clone trait, and clone is just the implements the clone method, which makes a deep copy of the object. And so, for example, if you wanted to get the C++ behavior of assignment, or you really didn’t want three copies of your array with strings, then you could actually call clone.

And then, you could get the C++ behavior. But, but basically, you couldn’t declare, you can’t take something like that, and make it a copy type. Copy is only for simple things, where a flat copy is all you need.

Adam: I think that doesn’t seem that strange to me coming from Java, or C#, or whatever, where everything is a reference type, except for these certain fixed size primitives, which act a little bit different.

Jim: Yeah. It’s pretty much the same idea. Well, let’s see. The trick is that with those languages, the reference types, in Java and C#, objects types, or vector types, I guess they’re arrays, they call them arrays. Object types and array types are reference types. And so, you can assign one of those, but then now, you’ve got two references to the same thing. And you started to make it ambiguous who the owner of that value is. And then, that’s the thing where you start needing to have a garbage collector for that.

References

Adam: Yeah. Earlier, I guess, right at the beginning of our interview, you talked about references. So, if I have my earlier example, my vector of strings, and I want to print it out. So, I have a print function, and it takes in a string, and then at whatever console writes it. It will become the owner of the string I pass into it, and then it will print it out, and then it will fall out of scope. And then, it will be free. So, if I print my vector, it ends up empty at the end. If I loop over and print it, is that correct?

Jim: Yeah. That if you do it the wrong way, then that’s correct. So, like I said, we started off with everything as a single owner. And then, we said, “Well, that’s a little bit too restrictive to make everything a single owner. Let’s let you move things around.” And then, we said, “Okay, well, moving things around is helpful for building things, and tearing things down.

But a lot of times, we want to temporarily grant access to something without changing its owner.” And that’s where references come in. So, if you write say your printing function, and the type of that printing function, its argument, to type the value password is simply string, well, then that’s a move. And when you call that function, you are moving ownership of the string into the printing function.

And then, either it’s going to have to return it back to you, which is a pain, or it’s just going to consume it, which is silly. And so, what you can do instead is you can borrow a reference to it. And then, with the argument type of that print function is reference to string, then what that means is that you borrow a reference to the string, and the ownership remains with whatever owns the string to begin with.

And then, the print function gets to temporarily have access to the string. And go ahead, and do whatever formatting and IO that it wants to do. And then, when it returns, that reference has gone out of scope. And the owner is now free, again, to do what it likes with it. But while a value is borrowed, if it’s… there are two ways to borrow a value. You can borrow a shared reference to a value, which just lets you look at it, you can’t modify it.

But you can make as many shared references to something as you want. You can have 20 things all pointing the same thing. Or you can borrow a mutable reference, which is exclusive. You can only have one mutable reference to something at a time. And that grants the ability to modify the value. So, for example, if you wanted to call a function that stuck stuff onto the end of your string, you’d have to pass it to a mutable reference to the string.

And then, while that function is running, it has exclusive access to that string. Nobody else can even look at it. Not even the owner can look at the string. But when it returns, that mutable reference goes out of scope. And then, the owner again, has access to it. And again, these are ways to grant access to temporarily let, say, a printing function, examine a string, or to let a formatting function, add stuff onto the end of the string. And then, when that borrow is done, the owner gets control back.

Adam: And these are static guarantees. So, if I understand then, at runtime, these are just pointers, like it might as well be C. But to actually compile it, then we’re doing static analysis, and making sure that these rules hold.

Jim: Right. Yeah. Certainly, at runtime, these are just ordinary pointers. The runtime inclination is just exactly like what you find if you’re passing something by reference in C++. But the different, and the only difference is that a reference type, the type of a reference value, has a lifetime attached to it, which represents the section of the program over which this reference is valid.

So, for example, if you have a string, that’s not a reference yet. If you have a local variable string, it’s local to some block in your program. The lifetime of that string is from the point of declaration to the end of the block, or from the point of declaration to the point that it gets moved, the value gets moved someplace else. But until that point, the value is sitting right there. Okay.

When you borrow a reference to that string, the type of that reference says, this type may only be used within the lifetime of that value until it gets moved or destroyed, or the things that it calls. And so, if you ever try to assign a value of that reference type to something outside the lifetime of the underlying string, that’s a compile time error, that’s a type error.

When you call a function, the function actually has to take parameters. It has to take their like type parameters, their compile time parameters that represent the lifetime of the thing that’s being passed to it. And the function has to be okay, with getting an object of a restricted lifetime. And so, it’s really nice.

If a function is going to go and store a pointer to something in some big data structure at some pointer, then in the type of that function, the reference that it accepts, it’s going to say, “By the way, I need a really big lifetime.” And so, if you try to pass to it a reference to some local variable, you get a compile time error, because you’re trying to call a function and pass at a reference.

And the function, it says that it needs a reference of this really big, long lifetime, unconstrained lifetime. But then, that’s not the lifetime of the value, the reference that you’re passing it doesn’t satisfy that. And so, you get a compile time error if you try to pass a pointer to one of your locals to something that’s going to try to retain it for longer than that.

Implicit Lifetime Parameters

Adam: So, in the simple case, so I take my current function, and now it takes the reference of string into it, and it prints. So, where’s the lifetime parameter there, or is it-

Jim: There is a lifetime parameter there. But a lot of times you don’t have to write it. For example, if you just have a print function, maybe that print function takes a single argument string of type, shared reference to string. Okay. And it doesn’t return any value. That type signature is really simple. And you could write out the lifetime in that signature, and name the lifetime that that reference has.

But because functions like this are really common, Rust has a shorthand. When it look over the signature of the function, and if like, say, if it’s very obvious from looking at the signature of the function, what the lifetimes involved need to be, then it will actually go and stick them in for you. But the lifetimes really are there. They’re just being elited.

Adam: There is a type parameter, I guess, and that type parameter is the lifetime that this will run. And when it infers it, I’m assuming it just infers it to be that the lifetime of the thing I pass in must be… I’m just I’m having trouble picturing how it infers it, I guess.

Jim: Okay. Well, so let me actually spell out what the real signature. What you write out in your code, what you actually put in your code is you say print, and you say open paren S colon ampersand string close. And that means that there’s this function print, and it takes a parameter named S whose type is shared reference to string. And then, it doesn’t return any value.

What that is shorthand for is print, and then in angle brackets, you say tick A, like a single quote A. And that means the lifetime name is A, and these are angle brackets. So, this is a type level parameter, this is a compile time parameter. And then, the argument type is actually ampersand tick A, lifetime A, string. So, in other words, and what this declaration means is, for any lifetime A outside the call, I’m going to take a reference to, I can take a reference restricted to that lifetime to a string.

And then, I’m not going to do anything. I’m not going to return anything. And so, when you write this function, Rust will look at that and say, “Well, okay, tick A, this lifetime that you put in, it could be very tightly wrapped around the point of the call.” Maybe this variable is created just before we did the call, and it’s going to be destroyed just after we do the call.

So, you can’t assume that this lifetime A is any longer than pretty much the call, the point of call and the caller. And so, if you try to actually store that reference someplace that lives longer, that won’t work. You’ll get a compile time error. So, the callee makes conservative assumptions about what the lifetime could be. And if you try to do something over ambitious with that reference, then it will say, I’m sorry, your ambitions are not supported by the constraints that we have on this lifetime.

Explicit Lifetimes

Adam: I get it. So, I think this clicked for me. So, the default is any lifetime. And then, what that has to mean is that it can’t do anything with it outside. It can’t store it anywhere because conceivably, after it’s called then the thing passed in could fall out of scope, and therefore be uninitialized, right?

Jim: Yeah. The default isn’t quite any lifetime. The default is any lifetime that encloses the call.

Adam: Any lifetime that encloses the call.

Jim: Right. If I’m taking a reference as an argument, then clearly that argument must have been live when I was passed it. At the point of the call, that reference must be legit. And so, therefore, I can assume that it is legit for the duration of this call, but not any time before or after that. But yes, otherwise, the effect is just as you said.

Adam: So, a lot of the times, you don’t even have to worry about this lifetime, because what I’m trying to come up with an example is when we’re returning one argument, but the lifetime of the two parameters could vary, right? Is that-

Varying Lifetimes

Jim: Right, right. Okay. So, imagining, let’s take a function that takes references to two values, and randomly returns a reference to one or the other.

Adam: Well, that sounds even more complex. I was just thinking of, if these two variables have two lifetimes and we return one, then we would need to specify that the returning one which lifetime it had.

Jim: Okay. You can do that. But actually, that one works out okay. And I’m trying to see if I can actually explain why it’s okay. So, the lifetimes that show up in a function signature get used in two ways. One, they get used to check the body, the definition of the function itself. And two, they get used to check the call of the function.

So, it’s clear that in this particular case, where we’re going to take for the body of the function, for the definition of function, we’re going to take two references, and then one of them is going to… we’re going to return reference to one of them. Well, it’s pretty clear that the function can’t. It’s not storing it anywhere. It’s just handing it back. And so, that’s legit.

And so, you’re not going to get any problems, the definition of that function. Where things get interesting is in the caller. The caller is going to pass into references to things with different lifetimes. And then, it’s going to get back a reference. Those two references that get passed in are initially from the caller side, they could be anything.

This call doesn’t impose., basically, it’s not going to restrict that. And so, it’s not to restrict those two lifetimes very much. And what it will do is it will actually say, “Well, okay, you passed in…” if you treat them both as having the same lifetime, it will say, “Well, okay, which lifetime works for both of them?” The largest lifetime that works for both of them is the smaller of the lifetimes, the two things that you borrowed references to.

Adam: So, it picks the most restrictive.

Jim: It picks the largest one that is still safe. And so, what you will get is a reference to… which the reference that it returns will be usable within the smaller of the two lifetimes. You have two objects with different lifetimes. You borrow references to each of them, and then you call this function. The reference that you get back will be restricted to lie within the lifetime of the object that has the shorter lifetime.

Adam: So, with your previous example of like returning randomly one, then it still can just pick the most restrictive lifetime?

Jim: Yeah, yeah.

Adam: So, yeah, somebody told me before, it’s good to have a technical podcast, but you shouldn’t talk about code. Well, I’d say I’ve broken that rule.

Jim: We’ve totally broken that rule. I’m not sure. I hope this is going to be okay without a whiteboard or something.

Adam: I think it’s great. To me, so it’s great. I hear lots of things about Rust, and people complain about the borrow checker and whatever. But if you don’t have examples, you don’t really understand it. So, I think the things we’ve talked about are very small pieces of code, but they help to highlight what it actually means when people say they’re fighting with the borrow checker, right?

On Not Fighting the Borrow Checker

Jim: Yeah. So, just so you know, I don’t really fight with the borrow checker much anymore. I can anticipate how it’s going to bathe, and how it’s going to think, and I have co-workers who don’t really fight with it. A lot of what’s going on is not so much learning to deal with the borrow checker. But rather, learning to structure the way that you use your values in a way that is compatible with the borrow checker.

And I think that that’s actually why people feel like they’re struggling with it is that they are having their ideas about how they wanted to structure their program pared back, and trimmed back to this very restricted model that Rust pushes you into. And of course, when you’re being told that you can’t do something that you’re pretty sure is fine, you’re going to chase against that.

But it turns out that really, almost everything that you want to do, you can fit into the model pretty well, with exceptions, and then there are workarounds for it. I think I mentioned tin the first podcast, I had lunch with a friend, and they said it looks to me, like Rust doesn’t let me create cycles. And I said, “Well, yeah, cycles have ambiguous ownership.”

And he says, “As a programmer, I need cycles. I use them all the time.” What he’s saying is legit. But it turns out that you can actually do fine. There are other approaches that you can take. And the payoff that you get is a static judgment about the viability, and correctness of your program. And that’s really nothing to shake a stick at. It’s really something that I really miss when I have to go back to C++.

So, it’s a challenge, and it’s a worthwhile challenge to do. So, I don’t feel like the borrow checker is really something you have to fight with. The borrow checker is simply, it’s the discipline that you’re learning. And this discipline is a valuable way to structure programs.

On Being Explicit

Adam: The lifetimes portion, at first glance, it seems a little complicated. But then when I think of the idea that if I call something that’s going to store what I pass into it globally, you can’t hide that from me. Because I think a lot more time get spent maintaining code or debugging issues. And to have this explicit information right there in the signature, you don’t even have to dig into what it does.

Jim: It’s incredibly valuable. Right now, at work, I’m dealing with something where we have workers that send messages to each other, and I need to have some of those messages be delayed. For example, something is being debugged, it better not be delivering its messages while you’re sitting at a breakpoint.

And that means that I’m changing when these messages get delivered. And it turns out that it’s very possible to change it so that the messages get delivered after the thing that we’re delivering to is gone. And so, here’s something where it absolutely would be a type error in Rust.

Or at least it would be something that the channel, the communications channel would recognize and cope with properly. But in C++, not only do I get a crash, which is it’s not unfamiliar. I had debug crashes before, but it’s like, I have to hunt it down. In Rust, it would have just told me. So, it’s kind of a pain.

Adam: So, I think you’ve made a case that there’s a style to Rust, and as a C++ developer, if you can adopt it, there’s big payoffs.

Jim: Right.

Adam: But as a developer who’s never too far from a garbage collector, I’m used to building more… I’m used to not worrying about references, and having things point to things all the time. So, is there a benefit to these constraints for somebody from a GC world?

Jim: Yeah. It’s surprising, the restrictions on borrowing actually have valuable for even simple single threaded code. One thing that’s bugged that you have cropping up in complicated systems from time to time is where you have a function that is say, you have a function that’s traversing some data structure, or it’s operating on the elements of some data structure.

And for each thing it does, it’s going to call out to somebody. You will occasionally come across these bugs where you’re calling out to somebody, and then they go do something else. And then, they invoke an operation that goes back and modifies the very data structure that you are traversing. Okay. And so, the way the stack looks is you’ve got this iteration in one of the callers.

It’s iterating this data structure, and then one of these callees is modifying the data structure as it’s being iterated over. Now, in general, it’s really difficult to specify exactly what you want from situations like that. And in Java, there’s something called the concurrent modification exception, which you’ll get if you try to do this. And in Rust, those bugs simply can’t occur.

There’re compile time problems that get reported before your program ever runs. And so, Rust is actually pushing you towards structures that always make it clear when modifications and things could ever happen. It gives you like a really nice sense of confidence. When you get a mutable pointer or something, you know that you have exclusive access to it.

And that while you were working on it, nobody else anywhere in the system is going to come in, and change it, or modify it. And I think that that’s actually a really valuable thing to have in function signatures, or in data structures. Some promise that either you are looking at something that’s being shared amongst a lot of people, and it won’t change, or you are going to modify this, and you’re the only person who can see your modifications.

And it’s a property that I miss when I go back to GC languages. And so, yes, it is more flexible to be able to lean on the GC, just create whatever references you want. But I think I do feel like I’m missing information that I wish I had. And that Rust requires you to provide.

Adam: There’s a theme, and Rust is making a lot of things explicit in the type system. You talk about the option types, like that one, other languages have seen that make it explicit, if something can be none or nothing. But also, now, we’re taking it, and we’re saying all these lifetimes have to be explicit.

Jim: Who has access to the thing? Who could be modifying this thing? What mode of access is it in at this point in the program that’s also explicit? And that’s just super valuable.

Adam: Well, thanks for coming on for another interview, Jim. It’s been great.

Jim: Sure. Yeah, it was fun.

Support CoRecursive

Hello,
I make CoRecursive because I love it when someone shares the details behind some project, some bug, or some incident with me.

No other podcast was telling stories quite like I wanted to hear.

Right now this is all done by just me and I love doing it, but it's also exhausting.

Recommending the show to others and contributing to this patreon are the biggest things you can do to help out.

Whatever you can do to help, I truly appreciate it!

Thanks! Adam Gordon Bell

Support The Podcast