A simple fix-point argument without the restriction to continuity (with A.J.M. van Gasteren)

A simple fix-point argument without the restriction to continuity.

Edsger W.Dyksfra and A.J.M.van Gaasteren

Introduction

Notation In this text, the letters $B,P,R,X$ ,and $Y$ stand for predicates on the state space of a program and square brackets are used as notation for univ- sal quantification of the enclosed over the program variables. The letter S stands for a statement and DO for the repetitive construct do $B \rightarrow S$ od (see [3]). (End of Notation.)

Requiring DO to be semantically equivalent to its first unfolding

i f B \rightarrow S; D O ] ¬ B \rightarrow s k i p f _ {i}

yields that ${wp}\left( {{DO},¬ B ∧ P}\right)$ is a solution of the equation in predicate $X$

(0) $\left\lbrack {X \equiv \left( {B ∧ {wp}\left( {S,X}\right) }\right) \vee \left( {¬ B ∧ P}\right) }\right\rbrack$

Explanation Equation (0) follows from the required semantic equivalence and

(i) the semantic definition $f$ skip, viz $\left\lbrack {{wp}\left( {{}^{\prime }{skip}^{\prime },R}\right) \equiv R}\right\rbrack$ for all $R$ ;

(ii) the semantic definition of statement concatenation, viz.

[ w p (^ {\prime \prime} S _ {0}; S _ {1}, R) \equiv w p (S _ {0}, w p (S _ {1}, R)) ]

For all ${S}{0},{S}{1}$ ,and $R$ ,

(iii) the semantic definition of the alternative construct, in particular

\begin{array}{l} [ w p (" i f B \rightarrow S 0 ] [ i B \rightarrow S _ {1} f _ {i} ^ {\prime}, R) = \ (B \wedge w p (S _ {0}, R)) \vee (¬ B \wedge w p (S _ {1}, R)) ] \ \end{array}

for all $B,S_0,S_1$ ,and $R$

For further details, see [3]. (End of Explanation.)

Notation and terminology With the exception of ${wp}$ , functional application is denoted by juxtaposition and iterated functional composition by exponentiation.

" X i s a t l e a s t a s s h r o n g a s Y " m e a n s " [ X ⇒ Y ]".

" p r e d i c a t e t r a n s f o r m e r f i s m o n o t o n i c " m e a n s

" [ X ⇒ Y ] ⇒ [ f X ⇒ f Y ] \mathrm {f o r a l l} X \mathrm {a n d} Y".

" p r e d i c a t e t r a n s f o r m e r f i s o r - c o n t i n u o u s" m e a n s

" [ f (\underline {{E}} n: n \ge 0: R _ {n}) \equiv (\underline {{E}} n: n \ge 0: f R _ {n}) ] f o r a n y

w e a k e n i n g s e q u e n c e o f p r e d i c a t e s R _ {n}, i. e. s u c h

t h a t (\widetilde {A} n: n ≥ 0: [ R _ {n} ⇒ R _ {n + 1} ]) ^ {\prime \prime}.

(End of Notation and Terminology.)

For monotonic predicate transformer $f$ ,the equation in $X \left\lbrack {X \equiv f{X}^{\prime }}\right\rbrack$ has a strongest solution (see [8]). If, in addition, $f$ is or-continuous, its strongest solution is given in closed form by

(1) $\left( {{E}_{n} : n ≥ 0 : {f}^{n}\text{ false }}\right)$

Proof sketch Let $Y$ be the strongest solution of $[X \equiv f[X]$ . Showing $[Y \equiv (\underline{E} n: n ≥ 0: f^n \text{false})]$ is done by showing separately

(i) $\left\lbrack {\left( {{E}_{n} : n ≥ 0}\right) \cdot {P}^{n}\text{false}}\right) ⇒ Y\rbrack$ and (ii) $\left\lbrack {Y ⇒ \left( {{En} : n ≥ 0 : {f}^{n}\text{false}}\right) }\right\rbrack$

The proof of (i) is by mathematical induction on n and relies on the monotonicity of $f$ ; it uses that $Y$ is a solution of $\left\lbrack {X \equiv {f}^{\prime }X}\right\rbrack$ .

The proof of (ii) consists in showing that (En: n≥0: $\mathfrak{p}^n$ false) is a solution of $[X \equiv fX]$ (of which $Y$ is the strongest solution); it relies on the or-continuity of $f$ (and on its monotonicity for the demonstration that the predicates $\mathfrak{p}^n$ false form a weakening sequence). (End of Proof Sketch.)

The predicate $w p\left( {{D0},7{B}^{ ∧ }P}\right)$ is (see [5]) defined as the strongest solution of (0). (Because ${w}{p}\left( {S,X}\right)$ is a monotonic function of $X$ ,so is the right-hand side of (0); hence its strongest solution exists.) If, in addition, ${w}{p}\left( {S,X}\right)$ is an or- continuous function of $X$ ,so is the right-hand side of (0),and an expression of the form of (1) gives a closed expression for ${w}_{p}\left( {{D0},7{B}^{ ∧ }P}\right)$ .

In programming terms, or-continuity of wpi is the same as nondeterminacy being bounded. The assumption of bounded nondeterminacy is a usual one to make: the closed form for

wp (DO, ¬B ∧ P), which is then available, is traditionally considered an advantage because it readily caters for the avoidance of fancy -and in practice cumbersome (see [1,2])- techniques like transfinite induction.

Since unbounded nondeterminacy cannot be implemented, the restriction to or-continuity has for a long time been regarded as quite reasonable. It has, however, led to theorems in which the restriction to or-continuity has been introduced not because the theorems demanded it but for the sake of their proofs. The restriction also became a nuisance in the mathematical treatment of abstract programs. Firstly, an abstract program may well contain the as yet unrefined statement "establish $P$ " where $P$ , viewed as equation, may have infinitely many solutions, an observation we owe to [0]. Secondly, the modelling of concurrency as a "fair" interleaving of atomic actions introduces unbounded nondeterminacy (see [6]).

We are therefore very pleased to show for the main theorem about the repetitive construct an elementary proof that, though not relying on or-continuity, does not require transfinite formalisms.

The theorem

Notation In the sequel, $x$ and $y$ stand for elements from a set $D$ . Set membership will be denoted by the infix operator "in"; our convention can thus be summarized by $x$ in $D$ and $y$ in $D$ . Function $t$ is a mapping from the state space (of a program) to $D$ , i.e. in each point of the state space the value of $t$ is an element of $D$ , a state of affairs that can be summarized by $[t$ in $D]$ . Let $C$ be a subset of $D$ ; note that then $t$ in $C$ stands for a predicate that may be true in some points of the state space, and false in others. (End of Notation.)

For the notion "well-founded" we refer to the appendix in which we show that well-foundedness is the same as the validity of a proof by mathematical induction. (For that reason, the design of a well-founded set that does the job is a regularly recurring theme in arguments about algorithms.)

After the above preliminaries we are ready to formulate our - well-known-

Theorem Let $\left( {D,k}\right)$ be a partially ordered set; let $C$ be a subset of $D$ such that $\left( {C,r}\right)$ is well-founded; let statement $S$ ,predicates $B$ and $P$ ,and function $f$ on the state space satisfy

A v G 38 / EWD 886-5

the predicate transformer $w p\left( {S,?\text{ }}\right)$ is mono-

[\left\lbrack {f \downarrow \downarrow }\right\rbrack D]

(2) $\left\lbrack {P ∧ B} \right\rbrack ⇒ f\underline{in}C}$ (3) $\left\lbrack {P ∧ B ∧ t = x ⇒ {wp}\left( {S,P ∧ t < x}\right) }\right\rbrack$ for all $x$ .

Then

(4) $\left\lbrack {P ⇒ {wp}\left( {{DO},¬ B ∧ P}\right) }\right\rbrack$ , where ${wp}\left( {{DO},¬ B ∧ P}\right)$ is defined as the strongest solution of (0).

In the above, the well-informed reader will recog- nize in $P$ the "invariant" of the repetition and in $t$ its "variant function", which is the vehicle for the termination argument.

The proof

The proof consists of three phases. In the first phase, we derive two lemmata we need for the justification of manipulations in the sequel. In the second phase, we massage the proof obligation so as to make it amenable to a proof using mathematical induction (since that is the only way of exploiting the well-foundedness of $\left( {C, < }\right)$ ). In the third phase, we carry out the inductive argument.

Conclusion (4) is proved by proving $\left\lbrack {P ⇒ X}\right\rbrack$ with $X$ any solution of(0).

(i) To begin with we observe for any $R$

\begin{array}{l} [ P ∧ R ⇒ X ] \tag {} \ = {\mathrm {s i n c e}, f r o m (0), [ X \equiv X \vee (¬ B \wedge P) ] } \ [ P ∧ R ⇒ X \lor (¬ B ∧ P) ] \ = {\text {p r e d i c a t e c a l c u l u s} } \ [ P \wedge (B \vee ¬ P) \wedge R ⇒ X ] \ = {\mathrm {p r e d i c a t e c a l c u l u s} } \ [ P ∧ B ∧ R ⇒ X ] ( ) \ = {(2) } \ [ P \wedge B \wedge + \underline {{i n}} C \wedge R ⇒ X ] \ = {\mathrm {L e m m a} 0 - \mathrm {s e e b e l o w - w i t h} R := + \underline {{i n}} C \wedge R } \ [ P \wedge + _ {\underline {{\operatorname {i n}}}} C \wedge R ⇒ X ] ( * *) \ \end{array}

From $(\star)$ and $(\star \star)$ we conclude

\mathrm {L e m m a 0} [ P ∧ R ⇒ X ] \equiv [ P ∧ B ∧ R ⇒ X ] f o r a n y R.

From $()$ and $(**)$ we conclude

\begin{array}{r l} {\underline {{\mathrm {L e m m a}}} _ {1}} & {[ P ∧ R ⇒ X ] \equiv [ P ∧ \underline {{t i n}} C ∧ R ⇒ X ]} \ & {\mathrm {f o r a n y} R.} \end{array}

(ii) Next we massage our demonstrandum:

\begin{array}{l} [ P ⇒ X ] \ = {\mathrm {L e m m a} 1 \mathrm {w i t h} R := \mathrm {t r u e} } \ [ P ∧ f _ {\ln} C ⇒ X ] \ = {\mathrm {p r e d i c a t e c a l c u l u s} } \ [ P \wedge (\exists x: x \underline {{i n}} C: t = x) ⇒ X ] \ \end{array}

Avg38/EWD886-7

$= {$ definition of $⇒$ and de Morgan $}$

[ ¬ P \vee (¬ x: x \in C: ¬ t = x) \vee X ]

$= {$ disjunction distributes over universal quantificiun $}$

[ (\underset {\sim} {A} x: x \mathrm {i n} C: ¬ P \vee ¬ t = x \vee X) ]

$= {$ definition of $⇒$ and de Morgan $}$

[ (¬ x: x \mathrm {i n} C: P _ {\wedge} + = x ⇒ X) ]

$= {$ interchange of universal quanltificatiOns $}$

(5) $\left( {\underline{A}x : x\mathop{\ln }\limits_{{C}} : \left\lbrack {{P}_{A} + f = x ⇒ X}\right\rbrack }\right)$

Remark As an aid to the reader, the above derivation has been carried out in smaller steps than usual.

(End of Remark.)

In view of $C$ ’s well-foundedness,(5) is proved by deriving -For any $x$ in $C -$

(6) $\left\lbrack {P ∧ f = x ⇒ X}\right\rbrack$

under the hypothesis

(7) $\left( {{A}_{y} : y\overset{\ln C}{ = }C ∧ y < x : \left\lbrack {P ∧ t = y ⇒ X}\right\rbrack }\right)$

(iii) To this end we observe:

(7)

$= {$ interchange of universa) quanifiCations $}$

[ (\underline {{A}} y: y \mathrm {i n} C ∧ y < x: P ∧ t = y ⇒ X) ]

$= {$ range manipulation $}$

$= {$ one-point rule $}$

\begin{array}{l} [ (\underline {{A}} y: t = y: P \wedge y \mathrm {i n} C \wedge y < x ⇒ X) ] \ [ P \wedge^ {\prime} + \underline {{\operatorname {i n}}} C \wedge + < X ⇒ X ] \ = {\mathrm {L e m m a} 1 \mathrm {w i t h} R := + < x } \ \end{array}

\begin{array}{l} [ P ∧ \vdash x ⇒ X ] \ ⇒ {\omega p (S, ?) i s m o n o t o n i c } \ [ w p (S, P ∧ t < x) ⇒ w p (S, X) ] \ ⇒ {(3) } \ [ P \wedge B \wedge f = x ⇒ w p (S, X) ] \ = {\text {p r e d i c a t e c a l c u l u s} } \ [ P \wedge B \wedge f = x ⇒ B \wedge w p (S, X) ] \ = {\text {p r e d i c a t e} \text {c a l c u l u s} } \ [ P \wedge (B \vee ¬ P) \wedge t = x ⇒ B \wedge w p (S, X) ] \ = {\text {p r e d i c a t e} \text {c a l c u l u s} } \ [ P \wedge f = x ⇒ (B \wedge w p (S, X) \vee (f B \wedge P) ] \ = {(0) } \ [ P ∧ f = x ⇒ X ] \ \end{array}

hence (6) has been derived under hypothesis (7).

Remark Also the above derivation has been given in smaller steps than usual. (End of Remark.)

Conclusion

To the best of our knowledge, Floyd (see [4]) has been the first one to formulate termination arguments in terms of well-founded sets; he did, however, restrict himself to deterministic programs, for which the natural numbers suffice.

In the fix-point theory that became envogue during the seventies, continuity was strictly adhered to, with the result that again the natural numbers sufficed (see [7]).

To the best of our knowledge, the above argu- ment is the first one to connect well-foundedness in its full generality directly to a non-operational notion of termination, i.e. to the strongest solu- tion of a fix-point equation. Its simplicity should dispel the myth that the restriction to continuity for the sake of convenience is justified.

Finally we would like the reader to regard the effectiveness and austere rigour of our argument as a plea for the calculational proof method employed.

Acknowledgements

We are greatly indebted to C.A.R. Hoare for his formulation of antecedent (3), which he showed to lead to a shorter proof than our original formulation, to C.S. Schohen for simplifying the formulation of the induction hypothesis, and to the Tuesday Afternoon Club for strengthening the theorem by weakening antecedent (2).

A short appendix on well-foundedness

In the following,

$\left( {C, < }\right)$ is a partially ordered set ,

$x,y $ are elements of $C$ ,

$S$ is a subset of $C$ ,and

Q is a predicate on $C$ ,

where $S$ and $Q$ are coupled by

(8) Q _ {x} \equiv ¬ (x \in S), \mathrm {o r} S = {x | ¬ Q x }.

As a result we have

(g) S = \phi \equiv (\underline {{A}} x: x \in C: Q x)

" $x$ is a minimal element of ${S}^{\prime \prime }$ means

x \in S ∧ (A y: y < x: ¬ (y \in S))

"C is well-founded" means that any non-empty subset of $C$ contains a minimal element.

We observe

\begin{array}{l} " C i s w e l l - f o u n d e d" \ = {\mathrm {d e f i n i t i o n s o f w e l l - f o u n d e d n e s s a n d m i n i m a l e l e m e n t} } \ (\underline {{A}} ^ {\prime} S: (S ≠ \varnothing) = \ (E x: x \in C: x \in S ∧ (A y: y < x: ¬ (y \in S))) \ = {\mathrm {p r e d i c a t e c a l c u l u s , d e} M o r g a n \mathrm {i n p a r t i c u l a r} } \ (A S: (S = \phi) \equiv \ (A x: x \in C: ¬ (x \in S) \vee (\exists y: y < x: y \in S))) \ = {\mathrm {r e n a m i n g t h e d u m m y w i t h} (8) \mathrm {a n d} (9) } \ (\underset {\sim} {A} Q:: (\underset {\sim} {A} X: x \in C: Q \underset {\sim} {X}) \equiv \ (A x: x \in C: Q x \vee (E y: y < x: ¬ Q y))) \ = {\mathrm {d e f i n i t i o n o f m a t h e m a t i c a l i n d u c t i o n} } \ " m a t h e m a t h i c a l i n d u c t i o n o v e r C i s v a l i d". \ \end{array}

Among mathematicians, well-foundedness is not as well-known as it deserves to be: there is, for instance, after half a century not yet a Dutch name for it. One cannot escape the impression

that Emmy Noether, besides being Jewish and female, had the additional disadvantage of having been preceded by Georg Cantor with his stress on countability.

References

[0] Back, R.J.R., Correctness preserving program refinements: proof theory and applications. Mathe-matical Centre Tracts nr. 131, Amsterdam 1980. [1] Back, R.J.R., Proving Total Correctness of Nondeterministic Programs in Infinitary Logic. Acta Informatica vol. 15, Fasc. 3, 1981, pp. 233-249. [2] Boom, H.J. A Weaker Precondition for Loops. ACM Transactions on Programming Languages and Systems, vol. 4, 1982, pp. 668-677. [3] Dijkstra, Edsger W., A discipline of program- ming. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1976. [4] Floyd, R. W., Assigning meanings to programs. Amer. Math. Soc. Symposia in Applied Mathematics, vol. 19, 1967, pp. 19-31. [5] Park, David, On the semantics of fair parallelism. Lecture Notes in Computer Science, vol. 86, Springer-Verlag, Berlin-Heidelberg 1980, pp. 504 - 526. [6] Park, David, Concurrency and automata on

infinite sequences. Lecture Notes in Computer Science, vol. 104. Springer-Verlag, Berlin-Heidelberg 1981. [7] Slay, J., Denotational Semantics: The Scott-Strachey Approach to Programming. MIT Press, Cambridge, MA, 1977. [8] Tarski, A., A. Lattice-theoretical Fixpoint Theorem and its Applications. Pacific Journal of Mathematics, vol. 5 (1955). pp. 285-309.

drs.A.J.M.van Gaasteren BP Venture Research Fellow Dept. of Mathematics and Computing Science University of Technology 5600 MB EINDHOVEN The Netherlands

13 June 1984 prof. dr. Edsger W. Dgksra Burroughs Research Fellow Plataansstraat 5 671 AL NUENEN ne Netherlands