imported>Cedar101: \mathtt

2021-08-24T08:05:26Z

\mathtt

New page

In [[computer science]], a '''loop variant''' is a [[function (mathematics)|mathematical function]] defined on the [[State (computer science)|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 [[Loop invariant|invariant conditions]], thereby [[Termination analysis|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 number|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 '''[[Transfinite induction|well-founded descent]]'''.<ref>{{cite book|last=Winskel|first=Glynn|title=The Formal Semantics of Programming Languages: An Introduction|year=1993|publisher=Massachusetts Institute of Technology|pages=32–33, 174–176}}</ref> A basic property of a well-founded relation is that it has no [[infinite descending chain]]s. 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 [[Partial correctness|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:
:<math>\frac{\{I \land C\}\;S\;\{I\}} {\{I\}\;\mathtt{while}\;C\; \mathtt{do}\; S \;\{I\land\lnot C\}},</math>
where {{mvar|I}} is the ''[[loop invariant|invariant]]'', ''C'' is the ''condition'', and ''S'' is the ''body'' of the loop. To express total correctness, we write instead:
:<math>\frac{< \text{ is well-founded},\;[I \land C \land V=z ]\;S\;[I \land V < z]}
{[I]\;\mathtt{while}\;C\; \mathtt{do}\; S \;[I\land\lnot C]},</math>
where, in addition, ''V'' is the ''variant'', and by convention the unbound symbol ''z'' is taken to be [[Universal quantification|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
:<math>\mathtt{while}\;C\; \mathtt{do} \; S</math>
terminates given the invariant {{mvar|I}} where we have the total correctness assertion
:<math>[I \land C ]\;S\;[I].</math>
Consider the "successor" relation on the state space {{math|Σ}} induced by the execution of the statement ''S'' from a state satisfying both the invariant {{mvar|I}} and the condition ''C''. That is, we say that a state {{mvar|σ′}} is a "successor" of {{mvar|σ}} if and only if
* {{mvar|I}} and ''C'' are both true in the state {{mvar|σ}}, and
* {{mvar|σ′}} is the state that results from the execution of the statement ''S'' in the state {{mvar|σ}}.
We note that <math>\sigma' \neq \sigma,</math> 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 {{mvar|σ′}} is an ''iterate'' of {{mvar|σ}} if either <math>\sigma' = \sigma,</math> or there is a finite chain <math>\sigma_0, \sigma_1,\,\dots\,,\sigma_n</math> such that <math>\sigma_0 = \sigma,</math> <math>\sigma_n = \sigma'</math> and <math>\sigma_{i+1}</math> is a "successor" of {{tmath|\sigma_i;}} for all {{mvar|I}}, <math>0 \le i < n.</math>

We note that if {{mvar|σ}} and {{mvar|σ′}} are two distinct states, and {{mvar|σ′}} is an iterate of {{mvar|σ}}, then {{mvar|σ}} cannot be an iterate of {{mvar|σ′,}} 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 {{mvar|I}}, and no state has a successor unless {{mvar|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 relation|well-founded]] on the state space {{math|Σ}}, 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 {{mvar|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 '''{{var|ω}}<sub>1</sub>''', the [[first uncountable ordinal]], i.e.,
:<math>V:\Sigma\rightarrow\omega_1.</math>
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 '''{{var|ω}}<sub>1</sub>''' is the enumeration of all [[well-order]] [[Order type|types]] on countable sets.

==Practical considerations==
In practice, loop variants are often taken to be non-negative [[integer]]s, or even required to be so,<ref>{{cite web|url=http://archive.eiffel.com/doc/faq/variant.html|title=Why loop variants are integers|last=Bertrand Meyer|first=Michael Schweitzer|date=27 July 1995|work=The Eiffel Support Pages|publisher=Eiffel Software|accessdate=2012-02-23}}</ref> but the requirement that every loop have an integer variant removes the expressive power of '''[[μ operator|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 [[Recursion (computer science)|recursive function call]], it is no longer capable of full '''[[μ-recursive function|μ-recursion]]''', but only '''[[Primitive recursive function|primitive recursion]]'''. [[Ackermann's function]] is the canonical example of a recursive function that cannot be computed in a [[For loop|loop with an integer variant]].

In terms of their [[Computational complexity theory|computational complexity]], however, functions that are not primitive recursive lie far beyond the realm of what is usually considered [[tractable problem|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 [[Gödel's incompleteness theorems|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_(programming_language)|C]]-like [[pseudocode]], of an integer variant computed from some upper bound on the number of iterations remaining in a while loop. However, [[C_(programming_language)|C]] allows side effects in the evaluation of expressions, which is unacceptable from the point of view of formally verifying a computer program.
<syntaxhighlight lang="c">
/** 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;
};
</syntaxhighlight>

===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.

==See also==
* [[While loop]]
* [[Loop invariant]]
* [[Transfinite induction]]
* [[Descending chain condition]]
* [[Large countable ordinal]]
* [[Correctness (computer science)]]
* [[Predicate_transformer_semantics#While_loop | Weakest-preconditions of While loop]]

==References==
{{reflist}}

[[Category:Formal methods]]
[[Category:Control flow]]

Loop variant - Revision history

imported>Cedar101: \mathtt