My first walk into Rust
It’s 2017 and we’re all about the high-level languages, right? We don’t mind paying some costs for our day-to-day abstractions and we rather code as far away from the metal as possible.
Web development is all the rage and we don’t have time to manage memory manually anymore. Hell, we don’t even mind letting go of most static guarantees that our code makes sense. We just need it to be done fast and sort of probably work for the time being.
I’ve been working with startups for a few years, so this mindset is rather frequent in my daily life. It is reflected in our programming languages preferences too: most notably Javascript but even Ruby or Python come to mind.
It really caught my attention to see Rust being ranked as the most loved language for the last two years on the well-known StackOverflow Developer Survey (2016, 2017). Why would a low-level language that aims for safety and performance get this much attention and love from the community even though the startup mindset has seemingly taken over?
So the story begins.
My intentions
I’m a reinforcement learning enthusiast and earlier this year I coded a simple Javascript library that implements the main abstraction for this kind of algorithms in a didactic straightforward manner. It wasn’t intended to be state-of-the-art or fast (or even usable in real problems). Since then I’ve been wanting to make another implementation that is all those things and Rust seemed to be the perfect fit.
The intent of this story is to point out my initial conflicts with Rust’s type system, how I got through them and what I learned from them. Rust is pretty strict in its static checking. Allied with most people’s unfamiliarity towards memory management, this makes the learning curve pretty steep for practically anyone.
Full disclosure, I don’t intend to teach you Rust. Hell, I couldn’t if I wanted to, this is literally my first compiling code! What I want is to tell the tale of how this code came to be and comment on the reasons the compiler is so uptight sometimes. Spoiler alert: it is for your own good.
Let’s get to it
Reinforcement learning is about the exploration of an environment. What can be done in each step is called an action. How one action is chosen from the list of possible ones is called a policy. The actions are weighted by the learned memory until the current step. A higher value means the learning agent remembers the action being better from previous experiences.
This simple concept is all we need to start coding, so I’m gonna write it as I would in a more relaxed typed language.
interface Policy<A> {
choose([[A, number]]): A;
}This looks simple enough. A policy for some kind of action has to know how to choose an action from a list of weighted actions. This is valid Typescript and we wouldn’t have any more problems with it. Now let’s try porting it directly to Rust.
trait Policy<A> {
fn choose(&self, [(A, f64)]) -> A;
}That doesn’t look so bad.
The first difference is that the interface becomes a trait, which is more or less the same thing but with a cooler name. Secondly, we have to mark the function as being a method with the &self parameter, whereas in the previous version it was implied. Lastly, our tuple is now actually a tuple since Rust does have first class tuple support.
This compiles just fine, so we’re done for the day.
Meet the compiler
The problem arises when you try to implement the trait, so let’s implement a policy that ignores the weights and returns the last action from the list.
struct Last;impl<A> Policy<A> for Last {
fn choose(&self, avs: [(A, f64)]) -> A {
avs[avs.len()].0
}
}
From here we get our first run in with the compiler.
[(A, f64)] does not have a constant size known at compile-time. — said the compiler
Arrays are stored in the stack and therefore need their sizes to be defined at compile-time. A policy has to choose from a list containing any number of actions, so using a static size array won’t work for us.
Fortunately, there are collection structures that are stored on the heap for exactly this kind of situation, like a vector. Let’s see how it looks like.
trait Policy<A> {
fn choose(&self, Vec<(A, f64)> -> A;
}avs[avs.len()].0: cannot move out of indexed content. — said the compiler
The compiler is right. You can’t give away something that isn’t yours in the first place.
Rust cares a lot about private property and it really keeps track of who owns what at all times, just like the government. It is called ownership and it’s one of Rust’s most distinct and awesome features.
In our case, the vector owns all data it contains. In order to return anything from the vector, you’ll need to take ownership first by removing it from the collection.
impl<A> Policy<A> for Last {
fn choose(&self, mut avs: Vec<(A, f64)>) -> A {
avs.pop().unwrap().0
}
}Now what you’re doing is first removing the data from the vector so you own it, then returning it from the method. Rust is immutable first, so if we want to mutate the data, it makes sure we’re explicit about it in with a modifier so our intentions are clear for the caller.
Also, you probably noticed the extra unwrap call in the code above. It’s used to force the Option (aka maybe), returned from the pop method to become the value inside of it. This is considered a bad practice and will be addressed later in this article.
For now, let’s rejoice at our compiling code that does what we want! That wasn’t that hard, was it?
Refining the solution
The problem with this code is that it takes ownership of the vector, which has ownership of the underlying actions and numbers. That means that when this function exits, the vector and all the data associated with it will be cleared from memory (with the exception of the returned action of course).
That’s a weird behavior for a function that should just make a choice, right?
Further, moving the memory from stack to heap isn’t ideal either: we’re doing things safely, but we’re once again sacrificing performance to make our life simpler.
We’re Rust now, we can do better.
We don’t need to be owners of the vector, we just need to borrow it for a second. On that note, we also don’t need to give an action back, we just need to point out which one of the actions in the borrowed vector we chose.
We actually couldn’t return an actual action even if we wanted to in this scenario since the vector would be borrowed and we can’t take ownership of something we borrowed from someone.
We can denote this whole idea in Rust using the borrowing semantics, which is an abstraction over raw references.
trait Policy<A> {
fn choose(&self, &Vec<(A, f64)>) -> &A;
}The ampersand means I can read and use the object, but I cannot change it in any way since it’s borrowed. One cool thing about borrows is that they are fixed-size and thus stack allocated. Mind you that the vector still isn't, but the reference to it is. Do you see what this means?
trait Policy<A> {
fn choose(&self, &[(A, f64)]) -> &A;
}We’re back to a regular array! To be fair, it’s not actually an array as it is a slice. There’s some Rust semantics to be learned on slices, but the point is the method isn’t gonna own the data at any point, so it doesn’t care where it’s stored (stack or heap). Let the owner figure out those things. It could indeed be an array, or a vector or even a stream for all we care. The only thing that matters for the method is that it can borrow a slice of the data for a while.
Here is what the current implementation looks like.
impl<A> Policy<A> for Last {
fn choose(&self, avs: &[(A, f64)]) -> &A {
&avs.last().unwrap().0
}
}We don’t need to mutate the collection anymore, so that modifier is gone. The ampersand on the start means we are pointing out the action we chose from the ones inside the collection, but we aren’t returning any actions per se.
We’ve come a long way, right? This looks quite different from the Typescript initial version. We’re almost at the end but bear with me. We just reached the final boss.
Outta lifetime
Compiling this doesn’t throw errors, it throws a tutorial explaining why this isn’t enough to make the guarantee Rust requires. It’s almost like Rust knows people will be pissed and wants to make perfectly clear his good intentions.
What it says is that the reference returned (action) cannot outlive the reference received (vector). Well, that’s fair, right? We’re taking the vector and choosing an action from it, but the vector still owns the action. So if we return the action we chose, it’s only valid as long as the vector is valid.
This makes sense and it’s rather obvious, but what Rust is complaining about is that it’s not explicit in our code. Although the compiler has a good understanding of what we meant, it can’t assume. It respects us too much. We have to tell it straight, so let’s do it.
trait Policy<'a, A> {
fn choose(&self, &'a [(A, f64)]) -> &'a A;
}This might look alien to you (as it did to me), but it’s not that bad. Alongside our generic type A, we also need a generic lifetime 'a. A lifetime is a constraint on the validity of a value over time. We use the syntax &'a to denote the reference should be valid for that much time.
When we add the lifetime constraint on both the vector reference and the returned action reference, we’re telling the compiler exactly what we wanted: the returned reference is only valid as long as the received one is.
The previous implementation now compiles just fine, with no compromises over performance nor safety. Or is it?
Optional boss
We’re just missing one little thing. Remember when I told you that unwrap should generally be avoided? Well, let’s delve a little deeper in that so we can finish up this implementation.
The problem is that .last is not always able to properly function. I mean, if the list turns out to be empty, what is its last element? Exactly. To answer properly, the function doesn’t return the element, but an Option of the element. It might be an element, or it might be nothing.
When we ask the Option to be unwrapped, what it means is: make this be the element, I guarantee that there is an element there. If you’re lying and there isn’t, the program will panic and die.
The thing is, we’re not sure if there is an element or not because we get the list as a parameter. We don’t want to risk the program panicking and dying and we also don’t know what to do when the caller asks us to choose an action from zero actions.
The solution is passing up the responsibility. We’re not going to unwrap the option. Since the caller can make the last method fail, it’ll have to deal with the failure himself.
trait Policy<'a, A> {
fn choose(&self, &'a [(A, f64)]) -> Option<&'a A>;
}struct Last;
impl<'a, A> Policy<'a, A> for Last {
fn choose(&self, avs: &'a [(A, f64)]) -> Option<&'a A> {
avs.last().map(|av| &av.0)
}
}
Welcome to Rust
Now, that’s the stuff. We’re done, we made it. Although there are a lot of new syntax and concepts to get used to, Rust has a sane approach to memory management. It doesn’t want to pay performance costs, but it also doesn’t want to inherit the unsafety we get from manual management.
Don’t you dare come back to the Typescript implementation to compare them (please do)! Rust’s looks much more complicated and even for versed programmers the signature could be quite hard to read at first glance. What is important here is to know when to apply each approach (and language).
Sure, there are a lot more things to care about when writing Rust code compared to some more high-level languages. But we did our part and the code works, so we gain safety enforced by the static checker and performance, both in speed and memory.
That’s (some of) what this language brings to the table.
There’s much much more to talk about Rust, but I’ll leave it to another story. I hope I was able to bring some important Rust concepts to the table for people that are interested in the language but didn’t come around to trying it yet.
As for me, did I mention I’m in love with Rust?
