The basis of designing a loop program are the following.

1. 1.

   Design a state of computation that leads to the desired result.

2. 2.

   Set up variables that hold the computation state, and the progress of computation.

3. 3.

   Write a code to iteratively update the variables until the desired result is obtained.

A program that sums up 1 through n can be designed as follows.

• •

  the state of computation: $s=i*(i+1)*...*n(1\le i\le n)$

• •

  variables：$s,i$

• •

  update code: $s:=s+1;i:=i-1$

This design yields the C function fact in Section 7.15.

This way of designing an iterative computation is not limited to procedural languages. A code to update the current state can be understood as a function that takes the current state and generate the next state. Then a loop program is represented a recursive function that takes the current state and call itself with the generated next state. The loop code of the C function fact can be written as the following ML code:

  fun loop (0, s) = s
     | loop (n, s) = loop (n - 1, s * n)
  fun fact n = loop (n, 1)

This form of recursion is called tail recursion, which is evaluated efficiently.