9.4.2 Imperative control structures

The imperative style of programming makes progress by using assignments to manipulate state. In many cases, solving a problem requires repeated operations. With functional programming, this is done using recursive definitions. We make progress towards a base case by passing in different values for the operands with each recursive application. With imperative programming, we can make progress by changing state repeatedly without needing to pass in different operands.

A common control structure in imperative programming is a while loop. A while loop has a test condition and a body. The test condition is a predicate. If it evaluates to true, the while loop body is executed. Then, the test condition is evaluated again. The while loop continues to execute until the test condition evaluates to false.

We can define while as a procedure that takes as input two procedures, a test procedure and a body procedure, each of which take no parameters. Even though the test and body procedures take no parameters, they need to be procedures instead of expressions, since every iteration of the loop should re-evaluate the test and body expressions of the passed procedures.

(define (while test body)
  (if (test)
      (begin (body) (while test body))
      (void))) ; no result value

We can use the while procedure to implement Fibonacci similarly to the fast-fibo procedure:

(define (fibo-while n)
  (let ((a 1) (b 1))        
    (while (lambda () (> n 2))
           (lambda () (set! b (+ a b))
                      (set! a (- b a))
                      (set! n (- n 1))))
    b))

The final value of b is the result of the fibo-while procedure. In each iteration, the body procedure is applied, updating the values of a and b to the next Fibonacci numbers.

The value assigned to a is computed as (- b a) instead of b. The reason for this is the previous assignment expression has already changed the value of b, by adding a to it. Since the next value of a should be the old value of b, we can find the necessary value by subtracting a. The fact that the value of a variable can change depending on when it is used often makes imperative programming trickier than functional programming.

An alternative approach, which would save the need to do subtraction, is to store the old value in a temporary value:

  (lambda ()
    (let ((oldb b))
      (set! b (+ a b))
      (set! a oldb)
      (set! n (- n 1))))

Many programming languages designed to support imperative programming provide control constructs similar to the while procedure defined above. For example, here is a version of the procedure in the Python programming language:

def fibonacci (n):
   a = 1
   b = 1
   while n > 2:
       a, b = b, a + b
       n = n - 1
   return b

We will use Python starting in Chapter 11, although you can probably guess what most of this procedure means without knowing Python. %The point of the example is to give you a sense what other programming languages look like, and how similar control structures are across different languages.

The most interesting statement is the double assignment: $a$, $b = b$, $a + b$. This assigns the new value of $a$ to the old value of $b$ and the new value of $b$ to the sum of the old values of $a$ and $b$. Without the double assignment operator, it would be necessary to store the old value of $b$ in a new variable so it can be assigned to $a$ after updating $b$ to the new value.

Exercise 9.11. Define the mlist-map! example from the previous section using while.

Exercise 9.12. Another common imperative programming structure is a repeat-until loop. Define a repeat-until procedure that takes two inputs, a body procedure and a test procedure. The procedure should evaluate the body procedure repeatedly, until the test procedure evaluates to a true value. For example, using repeat-until we could define factorial as:

(define (factorial n)
  (let ((fact 1))
    (repeat-until
     (lambda () (set! fact (* fact n)) (set! n (- n 1)))
     (lambda () (< n 1)))
    fact))

Exercise 9.13. Improve the efficiency of the indexing procedures from Section 8.2.3 by using mutation. Start by defining a mutable binary tree abstraction, and then use this and the MutableList data type to implement an imperative-style insert-into-index! procedure that mutates the input index by adding a new word-position pair to it. Then, define an efficient merge-index! procedure that takes two mutable indexes as its inputs and modifies the first index to incorporate all word occurrences in the second index. Analyze the impact of your changes on the running time of indexing a collection of documents.