Loop variant

In computer science, a loop variant is a mathematical function defined on the state space of a computer program whose value is monotonically decreased with respect to a (strict) well-founded relation by the iteration of a while loop under some invariant conditions, thereby ensuring its termination. A loop variant whose range is restricted to the non-negative integers is also known as a bound function, because in this case it provides a trivial upper bound on the number of iterations of a loop before it terminates. However, a loop variant may be transfinite, and thus is not necessarily restricted to integer values.

A well-founded relation is characterized by the existence of a minimal element of every non-empty subset of its domain. The existence of a variant proves the termination of a while loop in a computer program by well-founded descent.^[1] A basic property of a well-founded relation is that it has no infinite descending chains. Therefore a loop possessing a variant will terminate after a finite number of iterations, as long as its body terminates each time.

A while loop, or, more generally, a computer program that may contain while loops, is said to be totally correct if it is partially correct and it terminates.

Rule of inference for total correctness

In order to formally state the rule of inference for the termination of a while loop we have demonstrated above, recall that in Floyd–Hoare logic, the rule for expressing the partial correctness of a while loop is:

{\frac {\{I\land C\}\;S\;\{I\}}{\{I\}\;{\mathbf {while}}\;C\;{\mathbf {do}}\;S\;\{I\land \lnot C\}}},

where I is the invariant, C is the condition, and S is the body of the loop. To express total correctness, we write instead:

{\frac {<{\textrm {\ is\ well-founded}},\;[I\land C\land V=z]\;S\;[I\land V<z]}{[I]\;{\mathbf {while}}\;C\;{\mathbf {do}}\;S\;[I\land \lnot C]}},

where, in addition, V is the variant, and by convention the unbound symbol z is taken to be universally quantified.

Every loop that terminates has a variant

The existence of a variant implies that a while loop terminates. It may seem surprising, but the converse is true, as well, as long as we assume the axiom of choice: every while loop that terminates (given its invariant) has a variant. To prove this, assume that the loop

{\mathbf {while}}\;C\;{\mathbf {do}}\;S

terminates given the invariant I where we have the total correctness assertion

[I\land C]\;S\;[I].

Consider the "successor" relation on the state space $\Sigma$ induced by the execution of the statement S from a state satisfying both the invariant I and the condition C. That is, we say that a state $\sigma '$ is a "successor" of $\sigma$ if and only if

I and C are both true in the state $\sigma ,$ and
$\sigma '$ is the state that results from the execution of the statement S in the state $\sigma .$

We note that $\sigma '\neq \sigma ,$ for otherwise the loop would fail to terminate.

Next consider the reflexive, transitive closure of the "successor" relation. Call this iteration: we say that a state $\sigma '$ is an iterate of $\sigma$ if either $\sigma '=\sigma ,$ or there is a finite chain $\sigma _{0},\sigma _{1},\,\dots \,,\sigma _{n}$ such that $\sigma _{0}=\sigma ,$ $\sigma _{n}=\sigma '$ and $\sigma_{i+1}$ is a "successor" of $\sigma _{i}$ for all i, $0\leq i<n.$

We note that if $\sigma$ and $\sigma '$ are two distinct states, and $\sigma '$ is an iterate of $\sigma$ , then $\sigma$ cannot be an iterate of $\sigma ',$ for again, otherwise the loop would fail to terminate. In other words, iteration is antisymmetric, and thus, a partial order.

Now, since the while loop terminates after a finite number of steps given the invariant I, and no state has a successor unless I is true in that state, we conclude that every state has only finitely many iterates, every descending chain with respect to iteration has only finitely many distinct values, and thus there is no infinite descending chain, i.e. loop iteration satisfies the descending chain condition.

Therefore—assuming the axiom of choice—the "successor" relation we originally defined for the loop is well-founded on the state space $\Sigma ,$ since it is strict (irreflexive) and contained in the "iterate" relation. Thus the identity function on this state space is a variant for the while loop, as we have shown that the state must strictly decrease—as a "successor" and an "iterate"—each time the body S is executed given the invariant I and the condition C.

Moreover, we can show by a counting argument that the existence of any variant implies the existence of a variant in ω₁, the first uncountable ordinal, i.e.,

V:\Sigma \rightarrow \omega _{1}.

This is because the collection of all states reachable by a finite computer program in a finite number of steps from a finite input is countably infinite, and ω₁ is the enumeration of all well-order types on countable sets.

Practical considerations

In practice, loop variants are often taken to be non-negative integers, or even required to be so,^[2] but the requirement that every loop have an integer variant removes the expressive power of unbounded iteration from a programming language. Unless such a (formally verified) language allows a transfinite proof of termination for some other equally powerful construct such as a recursive function call, it is no longer capable of full μ-recursion, but only primitive recursion. Ackermann's function is the canonical example of a recursive function that cannot be computed in a loop with an integer variant.

In terms of their computational complexity, however, functions that are not primitive recursive lie far beyond the realm of what is usually considered tractable. Considering even the simple case of exponentiation as a primitive recursive function, and that the composition of primitive recursive functions is primitive recursive, one can begin to see how quickly a primitive recursive function can grow. And any function that can be computed by a Turing machine in a running time bounded by a primitive recursive function is itself primitive recursive. So it is difficult to imagine a practical use for full μ-recursion where primitive recursion will not do, especially since the former can be simulated by the latter up to exceedingly long running times.

And in any case, Kurt Gödel's first incompleteness theorem and the halting problem imply that there are while loops that always terminate but cannot be proven to do so; thus it is unavoidable that any requirement for a formal proof of termination must reduce the expressive power of a programming language. While we have shown that every loop that terminates has a variant, this does not mean that the well-foundedness of the loop iteration can be proven.

Example

Here is an example, in C-like pseudocode, of an integer variant computed from some upper bound on the number of iterations remaining in a while loop. However, C allows side effects in the evaluation of expressions, which is unacceptable from the point of view of formally verifying a computer program.

/** condition-variable, which is changed in procedure S() **/
bool C;
/** function, which computes a loop iteration bound without side effects **/
inline unsigned int getBound();

/** body of loop must not alter V **/ 
inline void S(); 

int main() {
    unsigned int V = getBound(); /* set variant equal to bound */
    assert(I); /* loop invariant */
    while (C) {
        assert(V > 0); /* this assertion is the variant's raison d'être (reason of existence) */
        S(); /* call the body */
        V = min(getBound(), V - 1); /* variant must decrease by at least one */
    };
    assert(I && !C); /* invariant is still true and condition is false */

    return 0;
};

Why even consider a non-integer variant?

Why even consider a non-integer or transfinite variant? This question has been raised because in all practical instances where we want to prove that a program terminates, we also want to prove that it terminates in a reasonable amount of time. There are at least two possibilities:

An upper bound on the number of iterations of a loop may be conditional on proving termination in the first place. It may be desirable to separately (or progressively) prove the three properties of
- partial correctness,
- termination, and
- running time.
Generality: considering transfinite variants allows all possible proofs of termination for a while loop to be seen in terms of the existence of a variant.

References

↑ Winskel, Glynn (1993). The Formal Semantics of Programming Languages: An Introduction. Massachusetts Institute of Technology. pp. 32–33, 174–176.
↑ Bertrand Meyer, Michael Schweitzer (27 July 1995). "Why loop variants are integers". The Eiffel Support Pages. Eiffel Software. Retrieved 2012-02-23.

This article is issued from Wikipedia - version of the 9/9/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.