In my exploration of Rust, I built an application that calculates Fibonacci
numbers (this was a suggestion from the end of
Chapter 3 of The Rust Programming Language by Steve Klabnik and Carol Nichols).
It helped me learn a bit more about the language and environment.
for loops- Statements vs. expressions
- Function returns (expressions)
checked_add to prevent overflow- Option enum (returned from
checked_add)
- Pattern matching on Option
- Result enum (to return error rather than panic)
.expect with Result- Pattern matching on Result
So let's walk through this project.
The code is available on GitHub: https://github.com/jeremybytes/fibonacci-rust, and branches are set up for each step along the way. We will only be
looking at the "main.rs" file in each branch, so all of the links will be
directly to this file.
Fibonacci Numbers
The task is to calculate the nth Fibonacci number. The Fibonacci sequence is
made by adding the 2 previous number in the sequence. So the sequence starts:
1, 1, 2, 3, 5, 8, 13, 21, 34. The 7th Fibonacci number (13) is the sum of the
previous 2 numbers (5 and 8).
For our application, we will create a function to generate the nth Fibonacci
number based on an input parameter. We'll call this function with multiple
values and output the results.
Step 1: Creating the Project
The first step is to create the project. We can do this by typing the
following in a terminal:
cargo new fib
This will create a new folder called "fib" along with the Rust project file, a
"src" folder to hold the code, and a "main.rs" file (in src) which is where we
will be putting our code.
The "main.rs" file has placeholder code:
fn main() {
println!("Hello, world!");
}
But we can use "cargo run" to make sure that everything is working in our
environment.
C:\rustlang\fib> cargo run
Compiling fib v0.1.0 (C:\rustlang\fib)
Finished dev [unoptimized + debuginfo] target(s) in 0.63s
Running `target\debug\fib.exe`
Hello, world!
Going forward, I'll just show the application output (without the compiling
and running output).
Step 2: Basic Fibonacci
Now that we have the shell, let's create a function to return a Fibonacci
number. Here's the completed function:
fn fib(n: u8) -> u64 {
let mut prev: u64 = 0;
let mut curr: u64 = 1;
for _ in 1..n {
let next = prev + curr;
prev = curr;
curr = next;
}
curr
}
There are several interesting bits here. Let's walk through them.
Declaring a Function
Let's start with the function declaration:
fn fib(n: u8) -> u64 {
}
The "fn" denotes that this is a function. "fib" is the function name. "n: u8"
declares a parameter called "n" that is an unsigned 8-bit integer. And the
"u64" after the arrow declares that this function returns an unsigned 64-bit
integer.
When declaring parameters and return values for functions, the types are
required. Rust does use type inference in some places (as we'll see), but
function declarations need to have explicit types.
Declaring Variables
Next, we have some variables declared and assigned:
let mut prev: u64 = 0;
let mut curr: u64 = 1;
"let" declares a variable.
By default, variables are immutable. This means that once we assign a value,
we cannot change it. For these variables, we use "mut" to denote that they are
mutable. So we will be able to change the values later.
The variable names are "prev" and "curr". These will hold the "previous
number" and the "current number" in the sequence.
The ": u64" declares these as unsigned 64-bit integer values. Fibonacci
numbers tend to overflow very quickly, so I used a fairly large integer type.
Finally, we assign initial values of 0 and 1, respectively.
Looping with "for"
There are several ways to handle the loop required to calculate the Fibonacci
number. I opted for a "for" loop:
for _ in 1..n {
}
"1..n" represents a range from 1 to the value of the incoming function
argument. So if the argument is "3", this represents the range: 1, 2, 3.
The "for" statement will loop once for each value in the range. In this case
the "_" denotes that we are not using the actual range value inside the loop.
All we really need here is to run the loop 3 times. All of the calculation is
done inside the loop itself.
Implicit Typing
Inside the "for" loop we do our calculations:
let next = prev + curr;
prev = curr;
curr = next;
This creates a new variable called "next" inside the loop and assigns it the
sum of "prev" and "curr". A couple of things to note. First, this variable is
immutable (so we do not have the "mut" keyword). The value is assigned here
and then it is not changed. Second, the "next" variable is implicitly typed.
Instead of having a type declaration, it is set based on what is assigned to
it. Since we are assigning the sum of two u64 values, "next" will also be a
u64.
The next two lines update the "prev" and "curr" values. We needed to mark them
as mutable when we declared them so that we could update them here.
This is a fairly naïve way of calculating Fibonacci numbers. If you'd like
to see more details on how the calculation works, you can take a look at
this article:
TDDing into a Fibonacci Sequence with C#.
Statements vs. Expressions
The last line of the function is a bit interesting:
curr
This returns the current value ("curr") from the function.
Rust does not use a "return" keyword to return a value. Instead, the last
expression in a function is what is returned. (As a side note, this is similar
to how F# works.)
What's the difference between a statement and an expression? A statement does
some type of work; an expression returns a value.
In Rust, a statement ends with a semi-colon, and an expression does not end
with a semi-colon. To make things more interesting, these are often combined.
Let's take a look back at a line of code:
let next = prev + curr;
Overall, this is a statement: it declares and assigns a value to a variable
called "next". And it ends with a semi-colon.
prev + curr
"prev + curr" is an expression that returns the result of adding 2 values. So
we really have a statement that includes an expression. (We can technically
break this down further, but we won't do that here.)
So, let's get back to the return value of the function. The "fib" function
returns a u64 value. The last expression in the function is:
curr
It is important to note that this line does not end with a semi-colon.
Because of this, the value of the "curr" variable (which is a u64) is returned
for this function.
Because of my coding history, I'm used to putting semi-colons at the end of
lines. So I'm sure that I'll mess this up many times before I get used to
it. If you get an error that says a function is returning "()" instead of a
particular type, it probably means that there's a semi-colon at the end of
the expression you meant to return.
Here's the full function:
fn fib(n: u8) -> u64 {
let mut prev: u64 = 0;
let mut curr: u64 = 1;
for _ in 1..n {
let next = prev + curr;
prev = curr;
curr = next;
}
curr
}
Using the "fib" Function
Now that we have a function that returns a Fibonacci number, it's time to
update the "main" function to use it.
fn main() {
println!("Fibonacci 1st = {}", fib(1));
println!("Fibonacci 2nd = {}", fib(2));
println!("Fibonacci 3rd = {}", fib(3));
println!("Fibonacci 4th = {}", fib(4));
println!("Fibonacci 5th = {}", fib(5));
}
This uses the "println!" macro to output a string to the standard output. On
each line, the set of curly braces represents a placeholder in the string. So
in the first statement, the curly braces will be replaced by the value that
comes back from calling "fib(1)".
So let's run and check the output:
Fibonacci 1st = 1
Fibonacci 2nd = 1
Fibonacci 3rd = 2
Fibonacci 4th = 3
Fibonacci 5th = 5
It works!
Well, it mostly works. We'll see a shortcoming in a bit.
Step 3: Testing More Values
Before looking at where we have a problem in the "fib" function, let's make it
easier to test for different values. For this, we'll add an array of numbers
to test, and then loop through them.
Here's an updated "main" function:
fn main() {
let nths = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
for nth in nths {
println!("Fibonacci {} = {}", nth, fib(nth));
}
}
Creating an Array
The first line sets up an array called "nths" and initializes it with the
values of 1 through 10. I use this name because our original task was to
calculate the "nth" Fibonacci number. This is a collection of all the ones we
want to calculate.
We're using type inference to let the compiler pick the type for "nths". In
this case, it determines that it is an array with 10 elements of type u8. It
decides on u8 because the values are used as arguments for the "fib" function,
and that takes a u8.
As an interesting note, if you comment out the "println!" statement, the
"nths" variable is an array with 10 elements of type i32 (a signed 32-bit
integer). This is the default integer type.
Type inference works as long as it can be determined at compile time. If it
cannot be determined at compile time, then an explicit type needs to be added.
Another "for" Loop
We use a "for" loop to go through the array. Instead of discarding the value
from the "for" loop (like we did above), we capture it in the "nth" variable.
Inside the loop, we have a "println!" with 2 placeholders, one for the loop
value and one for the result of the "fib" function.
Here's what that output looks like:
Fibonacci 1 = 1
Fibonacci 2 = 1
Fibonacci 3 = 2
Fibonacci 4 = 3
Fibonacci 5 = 5
Fibonacci 6 = 8
Fibonacci 7 = 13
Fibonacci 8 = 21
Fibonacci 9 = 34
Fibonacci 10 = 55
And now we can more easily test values by adding to the array.
Overflow!
As I noted at the beginning, Fibonacci sequences tend to overflow pretty
quickly (they increase the value by half for each item). We can see this by
adding a "100" to our array.
let nths = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100];
Here's the output when we run with these values:
Fibonacci 1 = 1
Fibonacci 2 = 1
Fibonacci 3 = 2
Fibonacci 4 = 3
Fibonacci 5 = 5
Fibonacci 6 = 8
Fibonacci 7 = 13
Fibonacci 8 = 21
Fibonacci 9 = 34
Fibonacci 10 = 55
thread 'main' panicked at 'attempt to add with overflow', src\main.rs:13:20
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
error: process didn't exit successfully: `target\debug\fib.exe` (exit code: 101)
This creates a "panic" in our application, and it exits with an error.
With a little experimentation, we will find that the 93rd Fibonacci number is
fine, but the 94th will overflow the u64 value.
Checking for Overflow
Now we can work on fixing the overflow. Our problem is with this line:
let next = prev + curr;
If "prev" and "curr" are near the upper limits of the u64 range, then adding
them together will go past that upper limit.
Some other languages will "wrap" the value (starting over again at 0). Rust
will generate an error instead (in the form of a panic). If you do want to
wrap the value, Rust does offer a "wrapped_add" function that does just that.
But we do not want to wrap, we would like to catch the error and give our
users a better experience.
checked_add
Instead of using the default "+" operator, we can use the "checked_add"
function. Here is that code:
let result = prev.checked_add(curr);
"checked_add" does not panic if the value overflows. This is because it uses
the Option enum.
Option Enum
The Option enum lets us return either a valid value or no value.
"Some<T>" is used if there is a valid value, otherwise "None" is used.
For example, let's say that "prev" is 1 and "curr" is 2. The "result" would be
"Some(3)".
If "prev" and "curr" are big enough to cause an overflow when added together,
then "result" would be "None".
Pattern Matching
The great thing about having an Option as a return type is that we can use
pattern matching with it.
Here is the inside of the updated "for" loop:
let result = prev.checked_add(curr);
match result {
Some(next) => {
prev = curr;
curr = next;
}
None => {
curr = 0;
break;
}
}
The "match" keyword sets up the pattern matching for us.
The first "arm" has "Some(next)" as the pattern. The "next" part lets us
assign a name to the value that we can use inside the block. In this case,
"next" will hold the same value that it did in the earlier version ("prev" +
"curr"), so inside the block, we can assign the "prev" and "curr" values like
we did before.
The second "arm" has "None" as the pattern. This will be used if there is an
overflow. If there is an overflow, then we set the "curr" variable to 0 and
then break out of the "for" loop.
Here is the updated "fib" function:
fn fib(n: u8) -> u64 {
let mut prev: u64 = 0;
let mut curr: u64 = 1;
for _ in 1..n {
let result = prev.checked_add(curr);
match result {
Some(next) => {
prev = curr;
curr = next;
}
None => {
curr = 0;
break;
}
}
}
curr
}
Here's an updated array to test valid values and overflow values:
let nths = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 90, 91, 92, 93, 94, 95, 96];
And here's the output:
Fibonacci 1 = 1
Fibonacci 2 = 1
Fibonacci 3 = 2
Fibonacci 4 = 3
Fibonacci 5 = 5
Fibonacci 6 = 8
Fibonacci 7 = 13
Fibonacci 8 = 21
Fibonacci 9 = 34
Fibonacci 10 = 55
Fibonacci 90 = 2880067194370816120
Fibonacci 91 = 4660046610375530309
Fibonacci 92 = 7540113804746346429
Fibonacci 93 = 12200160415121876738
Fibonacci 94 = 0
Fibonacci 95 = 0
Fibonacci 96 = 0
Setting "curr" to 0 is not a great way to handle our error state. For now, it
is fine because it gets rid of the panic, and our application keeps running.
Next up, we'll work on getting a real error that we can handle.
Using the Result Enum
In the last article, I wrote a bit about my first impressions of error
handling in Rust:
Initial Impressions of Rust. A big part of that involves the Result enum.
Similar to the Option enum, the Result enum represents exclusive states. For
Result, the options are "Ok" and "Err". Each of these can have their own type.
To update our "fib" function to return a Result, we'll need to make 2 updates.
Updating the Function Declaration
First, we'll need to update the signature of the function to return a Result.
Here's the new signature:
fn fib(n: u8) -> Result<u64, &'static str> {
}
The "Result" enum has 2 generic type parameters. The first represents the type
for the "Ok" value; the second represents the type for the "Err".
In this case, the "Ok" will be a u64.
The "Err" is a bit more confusing. We want to return a string, but if we try
to use just "str", we get an error that the compiler cannot determine the size
at compile time. And as we've seen, Rust needs to be able to determine things
at compile time.
Instead of using "str", we can use "&str" to use the address of a string
(Rust does use pointers; we won't talk too much about them today). The address
is a fixed size, so that gets rid of the previous error. But we get a new
error that there is a "missing lifetime specifier".
UPDATE Technical Note: '&str' is a string slice. This allows the Err to borrow the value of the string without taking ownership of it. (I've learned more about ownership since I wrote this article. It's pretty interesting.)
The good news is that the error also gives you a hint to consider using the
"static" lifetime with an example.
I'm using Visual Studio Code with the Rust extension, so I get these errors
and hints in the editor. But these same messages show up if you build using
"cargo build".
Returning a Result
Now that we've updated the function signature, we need to actually return a
Result. We can do this with some pattern matching.
Replace the previous expression at the end of the function:
curr
with a "match":
match curr == 0 {
false => Ok(curr),
true => Err("Calculation overflow")
}
This looks at the value of the "curr" variable and compares it to 0. (Again,
this isn't the best way to handle this, but we'll fix it a bit later).
If "curr" is not 0 (meaning there is a valid value), then we hit the "false"
arm and return an "Ok" with the value.
If "curr" is 0 (meaning there was an overflow), then we hit the "true" arm and
return an "Err" with an appropriate message.
Here's the updated "fib" function:
fn fib(n: u8) -> Result<u64, &'static str> {
let mut prev: u64 = 0;
let mut curr: u64 = 1;
for _ in 1..n {
let result = prev.checked_add(curr);
match result {
Some(next) => {
prev = curr;
curr = next;
}
None => {
curr = 0;
break;
}
}
}
match curr == 0 {
false => Ok(curr),
true => Err("Calculation overflow")
}
}
Side Note: In thinking about this later, I could have done the pattern
matching more elegantly. I started with an if/else block (which is why I'm
matching on a boolean value). But we could also write the pattern matching to
use the "curr" value directly:
match curr {
0 => Err("Calculation overflow"),
_ => Ok(curr),
}
This is more direct (but not really less confusing since 0 is a magic number here). Now the match is on the "curr" value itself. If the value is "0", then we return the Err. For the second arm, the underscore represents a catch-all. So if the value is anything other than "0", we return "Ok". Notice that I did have to reverse the order of the arms. The first match wins with pattern matching, so the default case needs to be at the end.
Both of these matches produce the same results. We won't worry about them too much because we'll be replacing this entirely in just a bit.
But since we changed the return type, our calling code needs to be updated.
Using ".expect"
One way that we can deal with the Result enum is to use the "expect()"
function.
Here is the updated code from the "main" function:
println!("Fibonacci {} = {}", nth, fib(nth).expect("Fibonacci calculation failed"));
After the call to "fib(nth)", we add an ".expect()" call and pass in a
message.
"expect()" works on a Result enum. If the Result is "Ok", then it pulls out
the value and returns it. So if there is no overflow, then the expected
Fibonacci number is used for the placeholder.
But if Result is "Err", then "expect" will panic. That's not exactly what we
want here, but this gets us one step closer.
With the "expect" in place, here is our output:
Fibonacci 1 = 1
Fibonacci 2 = 1
Fibonacci 3 = 2
Fibonacci 4 = 3
Fibonacci 5 = 5
Fibonacci 6 = 8
Fibonacci 7 = 13
Fibonacci 8 = 21
Fibonacci 9 = 34
Fibonacci 10 = 55
Fibonacci 90 = 2880067194370816120
Fibonacci 91 = 4660046610375530309
Fibonacci 92 = 7540113804746346429
Fibonacci 93 = 12200160415121876738
thread 'main' panicked at 'Fibonacci calculation failed: "Calculation overflow"', src \main.rs:5:53
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
error: process didn't exit successfully: `target\debug\fib.exe` (exit code: 101)
Because we get a panic when trying to fetch #94, the application halts and
does not process the rest of the values (95 and 96).
If we look at the output, we see both of the messages that we added.
"Fibonacci calculation failed" is what we put into the "expect", and
"Calculation overflow" is what we put into the "Err" Result.
But I'd like to get rid of the panic. And we can do that with more pattern
matching.
Matching on Result
Just like we used pattern matching with Option in the "fib" function, we can
use pattern matching with Result in the "main" function.
Pattern Matching
Here's the updated "for" loop from the "main" function:
for nth in nths {
match fib(nth) {
Ok(result) => println!("Fibonacci {} = {}", nth, result),
Err(e) => println!("Error at Fibonacci {}: {}", nth, e),
}
}
Inside the "for" loop, we match on the result of "fib(nth)".
If the Result is "Ok", then we use "println!" with the same string that we had
before.
If the Result is "Err", then we output an error message.
Adding an Overflow Flag
The last thing I want to do is get rid of the "curr = 0" that denotes an
overflow. Even though this works, it's a bit unclear. (And it can cause
problems since some implementations of Fibonacci consider "0" to be a valid
value.)
For this, we'll add a new variable called "overflow" to the "fib" function.
Here's the completed function with "overflow" in place:
fn fib(n: u8) -> Result<u64, &'static str> {
let mut prev: u64 = 0;
let mut curr: u64 = 1;
let mut overflow = false;
for _ in 1..n {
let result = prev.checked_add(curr);
match result {
Some(next) => {
prev = curr;
curr = next;
}
None => {
overflow = true;
break;
}
}
}
match overflow {
false => Ok(curr),
true => Err("Calculation overflow")
}
}
A new mutable "overflow" variable is created and set to "false". Then if there
is an overflow, it is set to "true". Finally, "overflow" is used in the final
pattern matching to determine whether to return "Ok" or "Err".
Final Output
With these changes in place, here is our final output:
Fibonacci 1 = 1
Fibonacci 2 = 1
Fibonacci 3 = 2
Fibonacci 4 = 3
Fibonacci 5 = 5
Fibonacci 6 = 8
Fibonacci 7 = 13
Fibonacci 8 = 21
Fibonacci 9 = 34
Fibonacci 10 = 55
Fibonacci 90 = 2880067194370816120
Fibonacci 91 = 4660046610375530309
Fibonacci 92 = 7540113804746346429
Fibonacci 93 = 12200160415121876738
Error at Fibonacci 94: Calculation overflow
Error at Fibonacci 95: Calculation overflow
Error at Fibonacci 96: Calculation overflow
This version no longer panics if there is an overflow. If we do have an
overflow, it gives us an error message. And all of the values will get
calculated, even if an overflow occurs in the middle.
Wrap Up
Calculating Fibonacci numbers is not a very complex task. But in this
walkthrough, we got to use several features of Rust and understand a bit more
about how the language works.
for loops- Statements vs. expressions
- Function returns (expressions)
checked_add to prevent overflow- Option enum (returned from
checked_add)
- Pattern matching on Option
- Result enum (to return error rather than panic)
.expect with Result- Pattern matching on Result
Quite honestly, I didn't expect to get this much out of this exercise. I've
calculate Fibonacci sequences lots of times before. I was surprised about what
I learned.
It's okay to do "simple" exercises. And it's okay to be surprised when they
don't go quite as you expected.
Happy Coding!
