May 2, 2021

Iteration

This post is about iteration, which is the ability to run a block of statements over and over again. We saw a kind of iteration, using recursion, in part five, Conditionals and Recursion. We saw another kind, using a loop, in part four, Turtles all the way down. In this post we’ll see yet another kind, using a while statement.

But first I want to say a little more about variable assignment.

Reassignment

As you may have discovered, it is legal to make more than one assignment to the same variable. A new assignment makes an existing variable refer to a new value (and stop referring to the old value).

fn main() {
    let x = 5;
    println!("x={}",x);
    let x=7;
    println!("x={}",x);
}

This works fine, but it’s a little confusing, and can lead to subtle bugs if you’re not careful. When we assign a binding with let, it’s reasonable to think it will last the whole function or block that it exists in.

We call assigning a new value to a binding with the same name with let again reassigning. It leads to shadowing of the old binding. So called since the new binding shadows the old, which is no longer reachable.

If you want to change the value of a binding, you should mutate it. This also means that you need to declare it as mutable in your original assignment:

fn main() {
    let mut x = 5;
    println!("x={}",x);
    x=7;
    println!("x={}",x);
}

The first time we display x, its value is 5; the second time, its value is 7. This looks like the same result that we got in the first program, but it actually isn’t. Here we only have one biding called x. In the original program we had two, but after we created the second, we could no longer reach the first.

At this point I want to address a common source of confusion. Because Rust uses the equal sign (=) for assignment, it is tempting to think that x=5 means that x and 5 are equal. But this interpretation is wrong.

First, equality is a symmetric relationship and assignment is not. For example, in mathematics, if a = 7 then 7 = a . But in Rust, the statement x=5 is legal and 5=x is not.

Also, in mathematics, a proposition of equality is either true or false for all time. If a = b now, then a will always equal b . In Rust, an assignment statement can make two bindings equal. But they don’t have to stay that way, as we saw above, as we can make them mutable (changeable) and then mutate (change) them:

fn main() {
	let mut a = 5;
	let b = a;
	a = 3;
    println!("a={}, b={}", a, b);
}

The third line changes, or mutates the value of a but does not change the value of b, so they are no longer equal.

Mutation of bindings can be useful, but you should avoid reassignment if you can. Shadowing bindings can make the code difficult to read and debug.

Frequent mutation of bindings can make the code difficult to read and hard to understand.

That is one of the reasons why bindings are immutable as a default. Only when you add the keyword mut will you be able to mutate them later.

Updating bindings

A common kind of mutation is an update, where the new value of the binding depends on the old.

x = x + 1;

This means “get the current value of x, add one, and then update x with the new value.” If you try to update a binding that doesn’t exist, you get an error. This is because Rust evaluates the right side before it assigns a value to x.

Before you can update a binding, you have to initialize it, in one of three ways:

with a simple assignment
by telling the compiler what its type should be
a combination of both:

let x: f32;     // just deciding on type for now
let y = 5;      // giving it a value, compiler infers type
let y: u16 = 5; // giving it a value, explicitly setting type

Updating a binding by adding 1 is called an increment; subtracting 1 is called a decrement.

The `while` statement

Computers are often used to automate repetitive tasks. Repeating identical or similar tasks without making errors is something that computers do well and people do poorly. In a computer program, repetition is also called iteration.

We have already seen a function, factorial, that iterates using recursion. Because iteration is so common, Rust provides language features to make it easier. One is the for statement we saw in post 4. We’ll get back to that later.

Another is the while statement. Here is a version of countdown that uses a while statement:

fn countdown(n: i32) {
    while n > 0 {
        println!("{}", n);
        n = n -1;
    }
    println!("Blastoff");
}

You can almost read the while statement as if it were English. It means, “While n is greater than 0, display the value of n and then decrement n. When you get to 0, display the word Blastoff.”

More formally, here is the ﬂow of execution for a statement:

Determine whether the condition is true or false.
If the condition is true, run the body and then go back to step 1.
If the condition is false, exit the while statement. Then continue execution after the block, at the next statement.

We call this type of flow a loop because the second step loops back around to the top. The body of the loop should change the value of one or more bindings. That way the condition should become false at some point in the future and the loop then terminates. Otherwise the loop will repeat forever, which is called an infinite loop.

In the case of countdown, we can prove that the loop terminates: if n is zero or negative, the loop never runs. Otherwise, n gets smaller each time through the loop, so we have to get to or below 0 at some point in the future.

For some other loops, it is not so easy to tell. For example:

fn collatz_sequence(n: u64) {
    while n != 1 {
        println!("n = {}",n);
        if n%2 == 0 { // n is even
            n = n/2;
        } else {
            n = n*3 + 1;
        }
    }
}

The condition for this loop is n != 1, so the loop will continue until n is 1, which makes the condition false.

Each time through the loop, the program outputs the value of n and then checks whether it is even or odd. If it is even, we divide n by 2. If it is odd, we replace the value of n with n*3 + 1. For example, if the argument passed to collatz_sequence is 3, the resulting values of n are 3, 10, 5, 16, 8, 4, 2, 1.

Since sometimes n increases and sometimes decreases, there is no obvious proof that will n ever reach 1. Nor that the program terminates. For some particular values of n, we can prove termination. For example, if the starting value is a power of two, n will be even every time through the loop until it reaches 1. The previous example ends with such a sequence, starting with 16.

The hard question is whether we can prove that this program terminates for all positive values of n. So far, no one has been able to prove it or disprove it! (See Wikipedias article on the Collatz conjecture.)

`break`

Sometimes you don’t know it’s time to end a loop until you get half way through the body. In that case you can use the break statement to jump out of the loop.

For example, suppose you want to take input from the user until they type Done!. You could write:

use std::io;

fn main() {
    let mut input = String::new();
    while true {
        io::stdin().read_line(&mut input_first).expect("Failed to read line");
        println!("{}", input);
        if input == "Done!" {
            break;
        }
    }
}

The loop condition is true, which is always true, so the loop runs until it hits the break statement.

Each time through, it prompts the user with an angle bracket. If the user types Done, the break statement exits the loop. Otherwise the program echoes whatever the user types and goes back to the top of the loop.

This way of writing while loops is common. It’s popular because you can check the condition anywhere in the loop (not only at the top). And you can express the stop condition with an affirmation (“stop when this happens”). Instead of with a negative (“keep going until that happens”).

If you tested the example in the Rust playground or on your own computer, you saw a warning:

warning: denote infinite loops with `loop { ... }`
 --> src/main.rs:5:5
  |
5 |     while true {
  |     ^^^^^^^^^^ help: use `loop`
  |
  = note: `#[warn(while_true)]` on by default

    Finished dev [unoptimized + debuginfo] target(s) in 0.10s

We usually write loops that stop with a break in a different way in Rust:

use std::io;

fn main() {
    let mut input = String::new();
    loop {
        io::stdin().read_line(&mut input_first).expect("Failed to read line");
        println!("{}", input);
        if input == "Done!" {
            break;
        }
    }
}

Since we use loop to start the loop, anyone reading the code will understand that it will stop as a result of some statement inside.

Square roots

We often use loops in programs that compute results by starting with a guess. Then improving on the answer bit by bit.

For example, one way of computing square roots is Newton’s method. Suppose that you want to know the square root of a. If you start with almost any estimate, x , you can compute a better estimate with the following formula: y=(x+a/x)/2

For example, if a is 4 and x is 3: y=(3+4/3)/2 making y≈2.166667.

The result is closer to the correct answer ( 4 = 2). If we repeat the process with the new estimate, it gets even closer (2.00641025641).

After a few more updates, the estimate is almost exact: 2.00000000003

In general we don’t know ahead of time how many steps it takes to get to the right answer. But we know when we get there because the estimate stops changing.

When y==x, we can stop. Here is a loop that starts with an initial estimate,x, and improves it until it stops changing:

let x: f64;
let y: f64;
let a: f64;
loop {
    println!("{}",x);
    y = ( x + a/x)/2.0;
    if y == x { break }
}

For some values of x this works fine, but in general it is dangerous to test float equality.

Floating-point values are only approximately right. This means they can’t be exact representations of most rational numbers. Like 1/3, or irrational numbers, like √2.

Rather than checking whether x and y are exactly equal, it is safer to check the difference. We can use the function num::abs to compute the absolute value, of the difference between them:

use num::abs;

fn main() {
    let mut x: f64=3.0;
    let mut y: f64;
    let a: f64=4.0;
    let max_difference = 0.00000000000000001;
    loop {
        println!("{}",x);
        y = ( x + a/x)/2.0;
        if abs(x-y) < max_difference { break }
        x=y;
    }
    println!("The square root of {} is {}", a, x);
}

Where max_difference has a small value that determines how close is close enough.

Running this in the playground yields a remarkably exact result very quickly:

3
2.1666666666666665
2.0064102564102564
2.0000102400262145
2.0000000000262146
2
The square root of 4 is 2

Algorithms

Newton’s method is an example of an algorithm. It is a mechanical process for solving a category of problems. In this case, computing square roots.

To understand what an algorithm is, it might help to start with something that is not an algorithm. When you learned to multiply, you may have memorized the multiplication table. In effect, you memorized 100 specific solutions. That kind of knowledge is not algorithmic.

But if you were “lazy”, you might have learned a few tricks. For example, to find the product n * 9, you can write n - 1 as the first digit and 10 - n as the second digit. This trick is a general solution for multiplying any single-digit number by 9. That’s an algorithm!

Other algorithms you’ve learned: Addition with carrying. Subtraction with borrowing. And long division. One characteristic of algorithms is that you can perform them without using intelligence. They are mechanical processes. Each step follows from the last according to a simple set of rules.

Executing algorithms is boring. But designing them is interesting, challenging, and a central part of computer science.

Some things people do without difficulty or conscious thought, are hard to express as algorithms. Understanding natural language is a good example. We all do it, but so far no one has been able to explain how we do it, at least not in the form of an algorithm.

Debugging

As you start writing bigger programs, you might find yourself spending more time debugging. More code means more chances to make an error and more places for bugs to hide.

One way to cut your debugging time is “debugging by bisection”. For example, if there are 100 lines in your program and you check them one at a time, it would take 100 steps. Instead, try to break the problem in half. Look at the middle of the program, or near it, for an intermediate value you can check. Add a println! statement to check the values in important variables (or something else that has a verifiable effect) and run the program.

If the mid-point check is incorrect, there must be a problem in the first half of the program. If it is correct, the problem is in the second half.

Every time you perform a check like this, you halve the number of lines you have to search. After six steps (which is fewer than 100), you would be down to one or two lines of code, at least in theory.

In practice it is not always clear what the “middle of the program” is and not always possible to check it. It doesn’t make sense to count lines and find the exact midpoint. Instead, think about places in the program where there might be errors and places where it is easy to put a check. Then choose a spot where you think the chances are about the same that the bug is before or after the check.

Learning Rust Series, part 7: Iteration