Is Rust a Functional Programming Language?

Update: There was a delightful discussion about functional programming and the nature of Rust at lobste.rs.

Some quotes...

The book Programming Rust introduces Rust as...

not really an object-oriented language, although it has some object-oriented characteristics. Rust is not a functional language […] It’s probably best to reserve judgement about what sort of language Rust is, and see what you think once you’ve become comfortable with the language.

Time for judgement has come! In the following I will lay out my view on how Rust’s language features influence programming style. I do agree with the aforementioned quote that Rust is not a single-paradigm language. Yet, the code written in idiomatic and safe Rust shares quite some similarities with code of functional programming languages.

“Functional programming language” is not a clearly defined term. From the various properties that are typically associated with functional programming I only want to focus on one: “Immutability” and referential transparency. Immutability means that data structures can be treated as values - once you have them, they will not change underneath you. If you want to express modification, you can construct a new data structure, maybe reusing (unchanged) parts of existing data. This enables referential transparency: If a function (or method) cannot change anything internally, its output only depends on its input. Given some input the function evaluation and the result it returns can be treated as the same. The function is said to be pure.

Immutability is often regarded as a very positive property:

• Pure code is deterministic and considered to be easier to reason about as the number of possible state combinations is limited.
• If a function only depends on explicitly defined parameters, testing it is often easier.
• Immutable data can be passed to concurrent code without worrying about synchron^izing access.
• And it is free of cycles (unless you allow lazily evaluation), making it easier to serialize and deserialize.

Now Rust clearly allows for data to be mutable. Rust also does not provide persistent data structures in its standard library (although there are third-party options) which are typically used to model immutable data efficiently. Yet, Rust’s rules around ownership require full control over what can be changed and when. To the extent that I have been working with Rust, a lot of it feels quite similar to programming Clojure from the point of view of designing programs.

Ownership, sharing, exclusivity

Each piece of data in (safe) Rust has exactly one owner. In the following example the variable val owns the String:

let val = "Hello World".to_string();

Using val we can create references to the string:

let val_ref = &val;
// both val and val_ref can be used to read the string value:
println!("{}", val);
println!("{}", val_ref);

However we cannot modify either val or val_ref:

// cannot borrow `val` as mutable, as it is not declared as mutable
val.push_str(" World");

// error: "cannot borrow `*val_ref` as mutable, as it is behind a `&` reference"
val_ref.push_str(" World");

So in order to change val we need to declare it mut:

let mut val = "Hello".to_string();
val.push_str(" World"); // OK

But now we cannot take a reference at the same time anymore:

let mut val = "Hello".to_string();
// error: cannot borrow `val` as mutable because it is also borrowed as immutable
let val_ref = &val;
val.push_str(" World");

And similarly we can write to the reference if we declare it mut but then we cannot get another reference at the same time:

let mut val = "Hello".to_string();
let val_ref = &val;
// error: cannot borrow `val` as mutable because it is also borrowed as immutable
let val_ref2 = &mut val;

This example demonstrates Rust’s ownership rules: We can get multiple shared (read-only) references to one piece of data but as soon as we indicate to modify the data by declaring either the owning variable or a reference as mut we cannot hold shared references at the same time. mut means first and foremost exclusive access to the underlying data (and only secondarily mutable).

Similarly, functions that want to modify parameters (or self in case of methods) need to indicate that they need exclusive access. This means that the caller can only use this function it has exclusive access to the parameters to be passed as mut:

fn add_world(val_ref: &mut String) {
    val_ref.push_str(" World");
}
// ...
add_world(&mut val);

All this is to say: Mutability in Rust needs to be explicitly declared and the rules around exclusive access are statically enforced. A thing can only change if no one is looking — reducing the number of accidental state combinations and highlighting the parts of the code base that can introduce change clearly. A Rust function that only accepts shared references and owned values (that do not provide interior mutability) and that does not use unsafe code¹, is referentially transparent.

Interior mutability

There are a number of use cases where not being able to modify shared references can become very limiting. For example consider this GTK+3 app:

The implementation for this looks something like this:

let container = gtk::Box::new(gtk::Orientation::Vertical, 2);
// A label that will be modified
let label = gtk::Label::new(Some("Button not yet clicked"));
let button = gtk::Button::with_label("Click me");
// We clone label so we can send it into the closure.
let label_clone = label.clone();
button.connect_clicked(move |_| {
    label_clone.set_label("Button has been clicked!");
});
container.add(&button);
container.add(&label);

As you can see the label is added to the container so that it gets displayed and is bound inside the closure where it gets modified.

Rust uses two mechanisms in combination for that to work: The Rc<RefCell<T>> pattern². First, a reference counted pointer std::rc::Rc that is quite similar to C++’s shared_ptr. Rc takes ownership of another object. Rc implements Clone that will increase the ref count and hand out a new pointer. Those can be passed freely around. Inside of the ref-counted pointer a RefCell can be placed. It will allow to request exclusive access to the data owned. I.e. it will — at runtime! — produce a mut reference to the object wrapped and check that it is indeed not borrowed somewhere else. Should this not be the case, the borrow will fail (and possibly panic if borrow_mut() was used).

For more details about the internals of smart pointers and interior mutability I can highly highly recommend this screen cast by Jon Gjengset that walks you through possible implementations of (among others) Rc and RefCell.

So Rust provides ways³ around the statically enforced access rules that normally restrict modification of data. This provides enough abstractions to even implement an interface to an object-oriented system such as Glib / GTK+. Following that, you might argue that Rust is supporting multiple paradigms, and I will agree. Yet, similar to Clojure that provides “interior mutability”-equivalents like atoms I will point out that overly relying on those features is not considered idiomatic. In Clojure the best practice is to use atoms sparingly. Mostly at the outside of the app, extracting state that is passed into the inner layers of the app that will then transform the state immutably into a new derived version. Atoms then clearly highlight where state changes can be expected. In practice, this then provides a good compromise. In case of stateful bugs, you only have to have a limited amount of possible sources to check and possible combinations of state transitions are still limited to simplify reasoning.

The Rc<RefCell<T>> pattern is also not all that ergonomic. Yes, you can define type aliases like Glib does, Rust still makes it easier to not have nested, cyclic relationships between objects. To say it with book Programming Rust again (from the section “Taking Arms Against a Sea of Objects”):

When everything depends on everything else like this, it’s hard to test, evolve, or even think about any component in isolation. One fascinating thing about Rust is that the ownership model puts a speed bump on the highway to hell. […] It works unreasonably well: not only can Rust force you to understand why your program is thread-safe, it can even require some amount of high-level architectural design.

And this is exactly the point I would like to convey with this article and the reason why I’m personally so fascinated with Rust: The set of features it does (not) provide are forcefully guiding the design of systems you build. This is quite contrary to how a lot of programming languages that attempt to provide a high degree of flexibility work (looking at you, Scala).

And then this is my claim: The ownership model, standard library, emphasize on iterators, and numerous other things do lead to code that is usually most idiomatic when written in a functional style. It will unlikely be completely equivalent to a solution written in Haskell or Clojure. Of course it also depends on the programmer, the problem domain, libraries, and frameworks. But applying best practices and designs from the functional realm are effective in Rust and the positive properties listed above can be built into Rust programs, and, to a degree, are even statically enforced by the compiler. For me, that is a joy!