FP Complete

Menu

Is Rust functional?


In the past few months, and in particular in the past two weeks, I’ve gotten a number of people asking me the question: Is Rust a functional programming language? This makes sense: I’m a big advocate of functional programming, I work at a company with FP in its name, my primary programming language is Haskell, and yet I use and enjoy Rust. So is Rust consistent with everything else in my FP-centric world, or is it my dirty vice to get away from it all?

Learn more about Rust at FP Complete

To give an executive summary to people who want a headline to run off with:

Alright, let’s expound on those points.

What is functional programming?

I’ve answered this question in at least one talk in the past, but to my recollection I haven’t done so in blog post form yet. I don’t believe there is any universally agreed upon definition of what makes a language “functional.” To demonstrate:

The definition is quite malleable. And frankly, it doesn’t help anyone to harp on these definitions. Let me show you why.

Imperative Haskell

I wouldn’t be surprised if there is 100% consensus that Haskell is a functional programming language, by just about any definition of the term. So please observe this beauty of functional programming:

import Data.IORef

main :: IO ()
main = do
  putStrLn "I'm going to calculate a sum, hang on a sec"
  totalRef <- newIORef (0 :: Int)
  let loop i
        | i > 100 = pure ()
        | otherwise = do
            oldTotal <- readIORef totalRef
            let newTotal = oldTotal + i
            writeIORef totalRef $! newTotal
            loop $! i + 1
  loop 1
  total <- readIORef totalRef
  putStrLn $ "The total is " ++ show total

FP at its finest, am I right? We’re using types like IORef and IO to ensure that this code is, in fact, purely functional. However, despite that, it has a distinctly imperative flavor. I’d argue that the end result is code that is worse than idiomatic code in an imperative language, e.g.:

print("I'm going to calculate a sum, hang on a sec")
total = 0
for i in range(1, 101):
    total += i
print("The total is " + str(total))

Or in Rust:

fn main() {
    println!("I'm going to calculate a sum, hang on a sec");
    let mut total = 0;
    for i in 1 .. 101 {
        total += i;
    }
    println!("The total is {}", total);
}

Obviously that Haskell code is highly non-idiomatic. But you’d be hard pressed to convince me that, because that code is written in Haskell, it magically gains the benefits of functional programming. It’s an identical algorithm to the imperative Python and Rust!

Idiomatic Haskell

Alright, I’m beating up on Haskell, sorry about that. Let’s show some idiomatic, functional, beautiful Haskell:

main = print $ foldl (+) 0 [1..100]

(Side note: in real code, please use foldl' instead of foldl. I’m using the bad function to avoid an extra import in these examples.)

This is using beautiful functional concepts like folds. This program leverages laziness of lists to avoid using up too much memory, and introduces no mutability, making it easier to understand. And yes, there’s a sum function as well, but I wanted to be explicit about the folding.

But wait a second, a wild Rust appears!

fn main() {
    println!("{}", (1..101).fold(0, |x, y| x + y));
}

Huh, this Rust version has immutability, higher-order functions, and folds. We get the necessary benefits of laziness with iterators. Can we really argue that this Rust solution isn’t functional?

Functional style

With that roundabout introduction, I can now present my thesis on functional programming:

If you still find the term “functional programming language” useful, don’t let me stop you. But for the rest of this post, I’m going to switch the original question to a pair of questions I feel more comfortable asking:

Immutable over mutable

Mutability is a necessary component of software development. At the lowest level of software, machine code is inherently mutable (mutating memory and register values). We layer abstractions of immutability on top of that, such as the fact that in C you write x = y + z instead of something like (psuedo-assembly):

mov R1, $y
mov R2, $z
add R3, R1, R2
mov $x, R3

Higher level languages, including Java, Python, and Haskell move immutability higher up the chain, including immutable strings. Haskell goes much further: all variables are immutable, and you have explicit wrappers than add in mutability (IORef, MVar, TVar, etc).

So how about Rust? It’s not as draconian as Haskell, but Rust programs certainly make use of functional patterns that take advantage of immutability.

Immutable by default

Remember this code?

fn main() {
    let mut total = 0;
    for i in 1 .. 101 {
        total += i;
    }
}

We had to explicitly say mut total to indicate that we wanted to be able to mutate the value. If you leave that off, you’ll get a compile-time error.

Move semantics

Let’s look at a different version of the code above that looks like it violates mutability by using a move:

fn get_sum(mut total: u32, mut i: u32) -> u32 {
    if i > 100 {
        return total;
    }

    total += i;
    i += 1;
    get_sum(total, i)
}
fn main() {
    let total = 0;
    let total = get_sum(total, 1);
    println!("{}", total);
}

This looks like a hot mutable mess! We created an immutable total variable, but then we pass it to get_sum which mutates it, and finally update total. Don’t let my bad code fool you though. In reality, the original immutable total value gets moved out of main into the get_sum function. In my opinion, this adheres to functional principles: the value is fully immutable in main, and then disappears from main, so that you cannot be tricked into thinking your value has remained the same. We then grab a new total value from the result of get_sum.

Inside get_sum, we are in fact fully mutable. But this is similar to Haskell’s ST type, which allows for local mutation. This is the same concept of layering immutability on top of mutability I mentioned above. We get the primary benefit we want from immutable-by-default: mutable code is explicitly called out, so you know where to look for bugs.

Verdict: Rust adheres to the functional principle of immutability.

Recursion

Rustaceans are probably cringing at that last example I just provided. Ignoring integer overflow for a bit, what happens when I change the code to add up to a really large number?

fn get_sum(mut total: u32, mut i: u32) -> u32 {
    if i > 10000000 {
        return total;
    }

    total = total.wrapping_add(i);
    i += 1;
    get_sum(total, i)
}
fn main() {
    let total = 0;
    let total = get_sum(total, 1);
    println!("{}", total);
}

I get the output:

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Abort trap: 6

Currently, Rust provides no means of tail-call optimization (TCO). This is quite intentional, as I was helpfully taught by the Rust community a year or two ago. Automatic TCO is brittle and has the potential to be broken by moving code around. This would lead to silently broken performance expectations and potential runtime failures. I buy the argument, and look forward to something like the become keyword being added for explicit TCO.

But this gets at a root difference with functional programming. FP encourages usage of recursion over iteration. Rust does not encourage this.

Verdict: Rust does not adhere to the functional principle of recursion.

First class functions/higher-order functions

When we say a language has first class functions we are referring to the ability to pass functions around as values. This generally means that you can pass function-values as arguments to other functions. Functions which themselves take functions as arguments are commonly called “higher-order functions.” Rust checks both of these boxes nicely. There are three related concepts:

Let’s demonstrate this a bit. In Haskell, you can double all of the values in a list, sum it, and print the result with:

main = print $ foldl (+) 0 $ map (* 2) [1..100]

* 2 is an operator section, and applies the binary operator * to a single argument, creating a new anonymous function which takes a single argument. Doing the same in Rust is more involved:

fn main() {
    println!("{}", (1..101).map(|x| x * 2).fold(0, |x, y| x + y));
}

Also, notice how in Haskell we use (+) as the first argument to foldl. We’re able to explicitly refer to the operator as a function. In our Rust code, we’re using a lambda to do the same thing. This isn’t actually necessary, we can refer instead to the add function underneath the + operator:

fn main() {
    println!("{}", (1..101).fold(0, std::ops::Add::add));
}

However, as you may have noticed, this is slightly more verbose than the original lambda-ified version.

Finally, it’s a bit unfair for me to compare Rust’s facilities here against Haskell. Haskell’s handling of lambdas, closures, first class and higher-order functions is best-in-class, since it’s explicitly the goal of the language. If you compare Rust to most other languages out there, like Javascript, Ruby, or Python, Rust compares even more favorably.

Verdict: Rust mostly does adhere to the functional principles of first class and higher-order functions. However, some aspects of value lifetimes and syntax add a bit more friction than a language like Haskell.

Pure functions

In a mathematical sense, a function returns the same value for the same input. Addition is a great example: add(1, 2) will always return 3.

With that definition, is random() a function? The answer is no, it isn’t. Most programming languages that have “functions” do not have mathematical functions. Instead, they have subroutines. This is because they allow effects to interleave in their functions.

Haskell is a purely functional language, in that all effects are listed in the type signature (ignoring unsafe functions that provide an escape hatch for that immutable-over-mutable layering mentioned above). However, Rust does nothing like that. You are free to mutate variables, read files, make network connections, or anything else you’d enjoy doing in a function.

You are of course free to make your functions pure in many cases, but the language will do nothing to help you ensure this.

Verdict: Rust does not adhere to the functional principle of pure functions.

Total functions

Total functions state that, for every valid input value, there is a valid, terminating output value. In contrast to a total function, a partial function may result in an infinite loop, program crash, or runtime exception for some input.

Here’s an example of a partial function:

ages = {}
ages["Alice"] = 25
ages["Bob"] = 30
print(ages["Charlie"])

ages["Charlie"] throws a runtime exception. Dictionary indexing is partial because it throws an exception on input which does not appear in the dictionary. (There’s also the total get method.)

In a turing-complete language, it’s impossible to prevent infinite loops, and therefore Rust allows for partial functions. However, the more common case of partiality are the crash and runtime exception cases. Here, Rust is even more functional than Haskell:

Rust does have the panic! mechanism, which works like a runtime exception, but isn’t intended to be used as a control flow mechanism, and instead should be used for accounting for programmer errors, not unexpected input. (A good example of this would be if an internal invariant of a data structure has somehow been violated.)

Haskellers may argue that the same applies to bottom values in Haskell: they shouldn’t be used in general. Though I’d agree with that, unfortunately in Haskell today that’s not the case. The standard prelude, for instance, still exports functions like head and readFile. Typeclasses like Enum use partial methods like succ and pred.

And at the language level itself, Haskell will happily compile code with incomplete pattern matches, while Rust will complain. Compare this partial Haskell code:

data Color = Red | Yellow | Blue

sayColor color =
  case color of
    Red -> "red"
    Yellow -> "yellow"

main = putStrLn (sayColor Blue)

Versus the following Rust code, which will fail to compile:

enum Color {
    Red,
    Yellow,
    Blue,
}

fn say_color(color: &Color) -> &'static str {
    match color {
        Color::Red => "red",
        Color::Yellow => "yellow",
    }
}

fn main() {
    println!("{}", say_color(&Color::Blue));
}

Verdict Not only does Rust adhere to the functional principle of total functions, it does a better job than most other functional languages, excepting dependently typed languages.

Advantages of Rust over FP

Overall, Rust does in fact adhere to many FP principles, though not all. I would be remiss to leave this blog post implying that there wasn’t a good reason for those deviations. Keep in mind that Rust has the stated goal of high performance, memory safe systems programming with no garbage collection.

One example of deviation above was the lack of tail call optimization. But this fits in perfectly with Rust’s goal of predictable, high performance.

Rust could certainly add tracking of effects like Haskell has. However, this would add signifiant friction around mutation, which is far more common in Rust to avoid creation of extra garbage data. Again, this is a performance trade-off that I believe the creators of Rust have consciously made.

This lack of a runtime and garbage collection also simplifies the programming model in Rust. In Haskell, for instance, you occassionally need to make decisions about storable versus unboxed vectors, paying attention to how the garbage collector treats them differently. This is a problem that disappears in Rust.

Finally, the lack of runtime exceptions in Rust certainly simplifies code significantly in many cases. For Rust’s use cases, I’m bought into the idea that the language is simply better without the exceptions. In languages like Haskell, I think the jury is still out, and things like asynchronous exceptions complicate the story a lot, adding both advantages and disadvantages to them.

Conclusion

I’ve devoted a lot of my professional career to functional programming. I think it’s a powerful approach to programming, and helps make better code in general. When I write Rust, I tend to write in a functional style.

In my opinion, programmers in any language should be familiar with functional style, and try to use it in their language-of-choice whenever possible. Some languages, like Rust and even Javascript, make this much easier. Other languages, like Java and C#, are actively adopting these approaches. Others, like C, are not moving in that direction, and so FP will be much harder to achieve there.

At the risk of sounding biased, I believe the best way to learn to adopt these functional programming principles is to learn Haskell. As long as you’re using a language where an imperative or object oriented approach feels natural, you’ll tend to gravitate back to that way of thinking. Haskell kicks out the training wheels of for loops and the like.

FP Complete provides a Haskell syllabus online for those interested in learning more. We also provide commercial Haskell, Rust, and DevOps training.

If you’re interested in our professional consulting services, check out our consulting page, and learn more about our Rust offerings.

Subscribe to our blog via email

Email subscriptions come from our Atom feed and are handled by Blogtrottr. You will only receive notifications of blog posts, and can unsubscribe any time.

Tagged