87:
From a programming methodology viewpoint, the loop invariant can be viewed as a more abstract specification of the loop, which characterizes the deeper purpose of the loop beyond the details of this implementation. A survey article covers fundamental algorithms from many areas of computer science
125:
is at least 1. Comments are provided at lines 3, 6, 9, 11, and 13. Each comment makes an assertion about the values of one or more variables at that stage of the function. The highlighted assertions within the loop body, at the beginning and end of the loop (lines 6 and 11), are exactly the same.
509:
1454:
1842:
1702:
2642:
Loop-invariant code may induce a corresponding loop-invariant property. For the above example, the easiest way to see it is to consider a program where the loop invariant code is computed both before and within the loop:
1076:
3040:
1222:
83:
properties). The loop invariants will be true on entry into a loop and following each iteration, so that on exit from the loop both the loop invariants and the loop termination condition can be guaranteed.
2305:
clauses, each of which corresponds to a clause in the postcondition. The fundamental difference is that each clause of the loop invariant identifies the result as being correct up to the current element
372:
875:
673:
745:
1504:
1263:
1733:
1598:
806:
586:
551:
908:
2301:
require that the returned value is: (1) not smaller than any element; and, (2) that it matches at least one element. The loop invariant is defined inductively through two
1334:
1227:
While this triple can be derived formally from the rules of Floyd-Hoare logic governing assignment, it is also intuitively justified: Computation starts in a state where
342:
has been incremented in line 10. However, when loop invariants have to be manually provided for formal program verification, such intuitively too obvious properties like
2639:
is a loop invariant for both the original and the optimized program, but is not part of the code, hence it doesn't make sense to speak of "moving it out of the loop".
1319:
1143:
775:
1567:
1289:
1113:
1538:
318:. While this change in code intuitively shouldn't make a difference, the reasoning leading to its correctness becomes somewhat more complicated, since then only
1738:
2840:
1603:
2362:
clause in Eiffel. Often, run-time checking can be switched on (for debugging runs) and off (for production runs) by a compiler or a runtime option.
2865:
126:
They thus describe an invariant property of the loop. When line 13 is reached, this invariant still holds, and it is known that the loop condition
2397:
consists of statements or expressions that can be moved outside a loop body without affecting the program semantics. Such transformations, called
977:
99:. In fact, the loop invariant is often the same as the inductive hypothesis to be proved for a recursive program equivalent to a given loop.
2293:
function determines the largest element in an integer array. For this to be defined, the array must contain at least one element. The
2376:
can be used to detect loop invariant of given code automatically. However, this approach is limited to very simple invariants (such as
1151:
95:
programs, proving partial correctness of loops with invariants is very similar to proving the correctness of recursive programs via
2827:
and Sergey Velder. "Loop invariants: analysis, classification, and examples."ACM Computing
Surveys. vol. 46, no. 3, February 2014(
504:{\displaystyle {\frac {\{C\land I\}\;\mathrm {body} \;\{I\}}{\{I\}\;{\mathtt {while}}\ (C)\ \mathrm {body} \;\{\lnot C\land I\}}}}
1861:
programming language provides native support for loop invariants. A loop invariant is expressed with the same syntax used for a
815:
613:
2804:
2780:, indicating that the values computed before the loop agree with those computed within (except before the first iteration).
1942:
programming language also provides first-class support for loop invariants. Loop invariants are expressed using one or more
693:
17:
2850:. Mathematical Aspects of Computer Science. Vol. 19. Providence, RI: American Mathematical Society. pp. 19–32.
1869:
must be true following the loop initialization, and after each execution of the loop body; this is checked at runtime.
812:
is true. If this relation can be proven, the rule then allows us to conclude that successful execution of the program
88:(searching, sorting, optimization, arithmetic etc.), characterizing each of them from the viewpoint of its invariant.
3030:
2974:
Pearce, David J.; Groves, Lindsay (2015). "Designing a
Verifying Compiler: Lessons Learned from Developing Whiley".
917:
With some variations in the notation used, and with the premise that the loop halts, this rule is also known as the
1462:
57:
80:
1939:
1858:
3088:
2789:
1230:
3062:
2898:
3021:
2794:
2398:
2389:
31:
2369:-shown Floyd–Hoare rule, that a given loop code in fact satisfies a given (set of) loop invariant(s).
2873:
1707:
1572:
1449:{\displaystyle \{x\leq 10\}\;{\mathtt {while}}\ (x<10)\ x:=x+1\;\{\lnot (x<10)\land x\leq 10\}}
780:
560:
525:
884:
2828:
2406:
2347:
108:
3104:
2373:
748:
1298:
1122:
754:
3109:
1546:
1268:
1145:
is appropriate. Under these assumptions it is possible to prove the following Hoare triple:
1092:
921:. As one 1970s textbook presents it in a way meant to be accessible to student programmers:
303:
751:
on machine states. It holds whenever starting from a state in which the boolean expression
3008:
96:
1517:
8:
2402:
1511:
610:
are guaranteed to be false and true, respectively, after the execution of the whole loop
359:
326:
holds, that condition has to be included into the loop invariant. It is easy to see that
64:
2890:
1837:{\displaystyle \{\mathrm {true} \}\;{\mathtt {while}}\ (x<10)\ x:=x+1\;\{10\leq x\}}
3026:
2918:
2894:
53:
3012:
3004:
2983:
2882:
2310:, whilst the postconditions identify the result as being correct for all elements.
46:
38:
3077:
334:
in line 6 can be obtained from the (modified) loop condition in line 5, and hence
1862:
1600:
is another one. Applying the above inference rule to the former invariant yields
72:
49:
2987:
3073:
3016:
2954:
2824:
2520:
can be moved before the loop, resulting in an equivalent, but faster, program:
2294:
1697:{\displaystyle \{0\leq x\}\;{\mathtt {while}}\ (x<10)\ x:=x+1\;\{10\leq x\}}
687:
In other words: The rule above is a deductive step that has as its premise the
60:. Knowing its invariant(s) is essential in understanding the effect of a loop.
3052:
Dynamically
Discovering Likely Program Invariants to Support Program Evolution
2365:
For 3., some tools exist to support mathematical proofs, usually based on the
3098:
2961:
965:
The following example illustrates how this rule works. Consider the program
1071:{\displaystyle \{x\leq 10\}\;{\mathtt {while}}\ (x<10)\ x:=x+1\;\{x=10\}}
2861:
2799:
688:
3051:
2886:
3036:
2927:
An
Introduction to Programming: A Structured Approach using PL/1 and PL/C
2922:
2329:
355:
68:
314:, in order to avoid endless looping for illegitimate negative values of
363:
111:
3041:
A note on a standard strategy for developing loop invariants and loops
3050:
Michael D. Ernst, Jake
Cockrell, William G. Griswold, David Notkin. "
92:
76:
2351:
1569:
is another invariant of the example loop, and the trivial property
940:
is true after it. Then the invariant relation theorem holds that
130:
from line 5 has become false. Both properties together imply that
2944:. Hoboken, New Jersey: John Wiley & Sons. pp. 156–157.
1217:{\displaystyle \{x<10\land x\leq 10\}\;x:=x+1\;\{x\leq 10\}}
2346:
For 2., programming language support is required, such as the
1510:
is less than or equal to 10, but it is not less than 10) is
138:, that is, that the correct value is returned from line 14.
2325:
to be checked within in the code, e.g. by an assertion call
2318:
A loop invariant can serve one of the following purposes:
30:
For the computer programming optimization technique, see
52:
that is true before (and after) each iteration. It is a
2929:. Cambridge, Massachusetts: Winthrop. pp. 198–200.
2383:
870:{\displaystyle {\mathtt {while}}\ (C)\ \mathrm {body} }
668:{\displaystyle {\mathtt {while}}\ (C)\ \mathrm {body} }
75:
and used to prove properties of loops and by extension
2942:
Software Error
Detection through Testing and Analysis
1865:. In the sample below, the loop invariant expression
1741:
1710:
1606:
1575:
1549:
1520:
1465:
1337:
1301:
1271:
1233:
1154:
1125:
1095:
980:
887:
818:
783:
757:
696:
616:
563:
528:
375:
777:
is true and successfully executing some code called
740:{\displaystyle \{C\land I\}\;\mathrm {body} \;\{I\}}
3025:, Second Edition. MIT Press and McGraw-Hill, 2001.
3078:Strengthening Invariants for Efficient Computation
1836:
1727:
1696:
1592:
1561:
1532:
1498:
1448:
1313:
1283:
1257:
1216:
1137:
1107:
1070:
902:
869:
800:
769:
739:
667:
580:
545:
503:
322:is known in line 13. In order to obtain that also
3096:
3056:International Conference on Software Engineering
2405:programs. A loop-invariant code example (in the
366:is governed by the following rule of inference:
117:returns the maximum value in its argument array
2838:
1984:// Requires at least one element to compute max
1847:
971:One can then prove the following Hoare triple:
2913:
2911:
2848:Proceedings of Symposia in Applied Mathematics
2194:// (2) One or more items seen so far matches m
2866:"An axiomatic basis for computer programming"
2005:// (1) Result is not smaller than any element
1499:{\displaystyle \lnot (x<10)\land x\leq 10}
2973:
2378:0<=i && i<=n && i%2==0
1831:
1819:
1759:
1742:
1691:
1679:
1619:
1607:
1443:
1410:
1350:
1338:
1211:
1199:
1179:
1155:
1065:
1053:
993:
981:
734:
728:
709:
697:
495:
480:
427:
421:
416:
410:
391:
379:
285:// m equals the maximum value in a, and i==n
27:Invariants used to prove properties of loops
3033:. Pages 17–19, section 2.1: Insertion sort.
2917:
2908:
2152:// (1) No item seen so far is larger than m
2776:A loop-invariant property of this code is
2053:// (2) Result matches at least one element
1818:
1762:
1678:
1622:
1409:
1353:
1198:
1182:
1052:
996:
932:is true before the sequence of statements
808:, the machine ends up in a state in which
727:
712:
479:
430:
409:
394:
330:, too, is an invariant of the loop, since
71:, loop invariants are expressed by formal
2335:For 1., a natural language comment (like
2313:
1119:has to be guessed; it will turn out that
914:in this rule is called a loop invariant.
1328:loops permits the following conclusion:
1946:clauses, as the following illustrates:
955:P { DO WHILE (c); seq END; } P & ¬c
310:in line 5 should better be modified to
91:Because of the similarity of loops and
14:
3097:
3072:Yanhong A. Liu, Scott D. Stoller, and
2366:
2939:
2860:
2778:(x1==x2 && t1==x2*x2) || i==0
2401:, are performed by some compilers to
2340:
1844:, which is slightly more expressive.
1777:
1774:
1771:
1768:
1765:
1637:
1634:
1631:
1628:
1625:
1368:
1365:
1362:
1359:
1356:
1258:{\displaystyle x<10\land x\leq 10}
1011:
1008:
1005:
1002:
999:
968:while (x < 10) x := x+1;
833:
830:
827:
824:
821:
631:
628:
625:
622:
619:
445:
442:
439:
436:
433:
2384:Distinction from loop-invariant code
1291:is true. The computation adds 1 to
349:
2805:Weakest-preconditions of While loop
1540:, which is what we wanted to show.
102:
24:
2998:
2337:// m equals the maximum value in a
1755:
1752:
1749:
1746:
1721:
1718:
1715:
1712:
1586:
1583:
1580:
1577:
1466:
1413:
888:
863:
860:
857:
854:
794:
791:
788:
785:
723:
720:
717:
714:
661:
658:
655:
652:
574:
571:
568:
565:
539:
536:
533:
530:
483:
475:
472:
469:
466:
405:
402:
399:
396:
278:// m equals the maximum value in a
265:// m equals the maximum value in a
231:// m equals the maximum value in a
191:// m equals the maximum value in a
25:
3121:
1324:Under this premise, the rule for
1265:is true, which means simply that
3047:, vol 2, pp. 207–214. 1984.
2841:"Assigning Meanings to Programs"
877:will lead from a state in which
56:, sometimes checked with a code
3082:Science of Computer Programming
3045:Science of Computer Programming
2976:Science of Computer Programming
2635:In contrast, e.g. the property
1728:{\displaystyle \mathrm {true} }
1593:{\displaystyle \mathrm {true} }
1321:is still true (for integer x).
801:{\displaystyle \mathrm {body} }
581:{\displaystyle \mathrm {body} }
546:{\displaystyle \mathrm {body} }
3084:, 41(2):139–172. October 2001.
2967:
2948:
2933:
2854:
2832:
2817:
1797:
1785:
1657:
1645:
1481:
1469:
1428:
1416:
1388:
1376:
1031:
1019:
903:{\displaystyle \lnot C\land I}
847:
841:
645:
639:
459:
453:
13:
1:
2810:
747:. This triple is actually a
557:holds after the execution of
306:paradigm, the loop condition
2790:Invariant (computer science)
2328:to be verified based on the
1848:Programming language support
1459:However, the post-condition
910:holds. The boolean formula
881:is true to a state in which
134:equals the maximum value in
7:
3069:, 3(1):56–69. January 1986.
3063:Programming with Invariants
2988:10.1016/j.scico.2015.09.006
2783:
2355:
1704:. Applying it to invariant
1115:. A useful loop invariant
79:that employ loops (usually
65:formal program verification
10:
3126:
3087:Michael Huth, Mark Ryan. "
3022:Introduction to Algorithms
2846:. In J.T. Schwartz (ed.).
2795:Loop-invariant code motion
2637:0<=i && i<=n
2399:loop-invariant code motion
2390:Loop-invariant code motion
2387:
960:
919:Invariant Relation Theorem
32:Loop-invariant code motion
29:
3089:Logic in Computer Science
3058:, pp. 213–224. 1999.
2874:Communications of the ACM
1933:
1852:
679:was true before the loop
522:is preserved by the code
2839:Robert W. Floyd (1967).
2645:
2522:
2411:
2343:example) is sufficient.
1948:
1871:
1314:{\displaystyle x\leq 10}
1138:{\displaystyle x\leq 10}
770:{\displaystyle C\land I}
140:
2512:where the calculations
2374:abstract interpretation
1562:{\displaystyle 0\leq x}
1284:{\displaystyle x<10}
1108:{\displaystyle x<10}
338:holds in line 11 after
2407:C programming language
2314:Use of loop invariants
1838:
1729:
1698:
1594:
1563:
1534:
1500:
1450:
1315:
1285:
1259:
1218:
1139:
1109:
1072:
904:
871:
802:
771:
741:
669:
582:
547:
505:
346:are often overlooked.
121:, provided its length
2959:Eiffel: The Language,
2940:Huang, J. C. (2009).
2887:10.1145/363235.363259
2388:Further information:
1839:
1730:
1699:
1595:
1564:
1535:
1501:
1451:
1316:
1286:
1260:
1219:
1140:
1110:
1073:
905:
872:
803:
772:
742:
670:
583:
548:
506:
304:defensive programming
3009:Charles E. Leiserson
2964:, 1991, pp. 129–131.
2330:Floyd-Hoare approach
1867:x <= 10
1739:
1708:
1604:
1573:
1547:
1533:{\displaystyle x=10}
1518:
1512:logically equivalent
1463:
1335:
1299:
1269:
1231:
1152:
1123:
1093:
978:
885:
816:
781:
755:
694:
614:
561:
553:—more precisely, if
526:
373:
69:Floyd-Hoare approach
3091:.", Second Edition.
2395:Loop-invariant code
1295:, which means that
945:P & c { seq } P
360:partial correctness
67:, particularly the
45:is a property of a
18:Loop-invariant code
2322:purely documentary
1834:
1725:
1694:
1590:
1559:
1530:
1496:
1446:
1311:
1281:
1255:
1214:
1135:
1105:
1068:
900:
867:
798:
767:
737:
665:
578:
543:
501:
2372:The technique of
1802:
1784:
1662:
1644:
1393:
1375:
1036:
1018:
924:Let the notation
852:
840:
650:
638:
596:held beforehand—
518:If some property
499:
464:
452:
356:Floyd–Hoare logic
350:Floyd–Hoare logic
54:logical assertion
16:(Redirected from
3117:
3013:Ronald L. Rivest
3005:Thomas H. Cormen
2992:
2991:
2971:
2965:
2952:
2946:
2945:
2937:
2931:
2930:
2915:
2906:
2905:
2903:
2897:. Archived from
2870:
2864:(October 1969).
2858:
2852:
2851:
2845:
2836:
2830:
2823:Carlo A. Furia,
2821:
2779:
2772:
2769:
2766:
2763:
2760:
2757:
2754:
2751:
2748:
2745:
2742:
2739:
2736:
2733:
2730:
2727:
2724:
2721:
2718:
2715:
2712:
2709:
2706:
2703:
2700:
2697:
2694:
2691:
2688:
2685:
2682:
2679:
2676:
2673:
2670:
2667:
2664:
2661:
2658:
2655:
2652:
2649:
2638:
2631:
2628:
2625:
2622:
2619:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2586:
2583:
2580:
2577:
2574:
2571:
2568:
2565:
2562:
2559:
2556:
2553:
2550:
2547:
2544:
2541:
2538:
2535:
2532:
2529:
2526:
2519:
2515:
2508:
2505:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2460:
2457:
2454:
2451:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2427:
2424:
2421:
2418:
2415:
2379:
2361:
2338:
2309:
2304:
2300:
2292:
2285:
2282:
2279:
2276:
2273:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2240:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2177:
2174:
2171:
2168:
2165:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2102:
2099:
2096:
2093:
2090:
2087:
2084:
2081:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1952:
1945:
1929:
1926:
1923:
1920:
1917:
1914:
1911:
1908:
1905:
1902:
1899:
1896:
1893:
1890:
1887:
1884:
1881:
1878:
1875:
1868:
1843:
1841:
1840:
1835:
1800:
1782:
1781:
1780:
1758:
1734:
1732:
1731:
1726:
1724:
1703:
1701:
1700:
1695:
1660:
1642:
1641:
1640:
1599:
1597:
1596:
1591:
1589:
1568:
1566:
1565:
1560:
1539:
1537:
1536:
1531:
1509:
1505:
1503:
1502:
1497:
1455:
1453:
1452:
1447:
1391:
1373:
1372:
1371:
1327:
1320:
1318:
1317:
1312:
1294:
1290:
1288:
1287:
1282:
1264:
1262:
1261:
1256:
1223:
1221:
1220:
1215:
1144:
1142:
1141:
1136:
1118:
1114:
1112:
1111:
1106:
1088:
1077:
1075:
1074:
1069:
1034:
1016:
1015:
1014:
956:
946:
939:
935:
931:
927:
913:
909:
907:
906:
901:
880:
876:
874:
873:
868:
866:
850:
838:
837:
836:
811:
807:
805:
804:
799:
797:
776:
774:
773:
768:
746:
744:
743:
738:
726:
678:
674:
672:
671:
666:
664:
648:
636:
635:
634:
609:
605:
595:
591:
587:
585:
584:
579:
577:
556:
552:
550:
549:
544:
542:
521:
510:
508:
507:
502:
500:
498:
478:
462:
450:
449:
448:
419:
408:
377:
345:
341:
337:
333:
329:
325:
321:
317:
313:
309:
298:
295:
292:
289:
286:
283:
280:
279:
275:
272:
269:
266:
263:
260:
257:
254:
251:
248:
245:
242:
239:
236:
233:
232:
228:
225:
222:
219:
216:
213:
210:
207:
204:
201:
198:
195:
192:
189:
186:
183:
180:
177:
174:
171:
168:
165:
162:
159:
156:
153:
150:
147:
144:
137:
133:
129:
124:
120:
116:
103:Informal example
39:computer science
21:
3125:
3124:
3120:
3119:
3118:
3116:
3115:
3114:
3095:
3094:
3061:Robert Paige. "
3001:
2999:Further reading
2996:
2995:
2972:
2968:
2955:Meyer, Bertrand
2953:
2949:
2938:
2934:
2919:Conway, Richard
2916:
2909:
2901:
2881:(10): 576–580.
2868:
2862:Hoare, C. A. R.
2859:
2855:
2843:
2837:
2833:
2822:
2818:
2813:
2786:
2777:
2774:
2773:
2770:
2767:
2764:
2761:
2758:
2755:
2752:
2749:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2716:
2713:
2710:
2707:
2704:
2701:
2698:
2695:
2692:
2689:
2686:
2683:
2680:
2677:
2674:
2671:
2668:
2665:
2662:
2659:
2656:
2653:
2650:
2647:
2636:
2633:
2632:
2629:
2626:
2623:
2620:
2617:
2614:
2611:
2608:
2605:
2602:
2599:
2596:
2593:
2590:
2587:
2584:
2581:
2578:
2575:
2572:
2569:
2566:
2563:
2560:
2557:
2554:
2551:
2548:
2545:
2542:
2539:
2536:
2533:
2530:
2527:
2524:
2517:
2513:
2510:
2509:
2506:
2503:
2500:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2476:
2473:
2470:
2467:
2464:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2425:
2422:
2419:
2416:
2413:
2392:
2386:
2377:
2359:
2336:
2316:
2307:
2302:
2298:
2290:
2287:
2286:
2283:
2280:
2277:
2274:
2271:
2268:
2265:
2262:
2259:
2256:
2253:
2250:
2247:
2244:
2241:
2238:
2235:
2232:
2229:
2226:
2223:
2220:
2217:
2214:
2211:
2208:
2205:
2202:
2199:
2196:
2193:
2190:
2187:
2184:
2181:
2178:
2175:
2172:
2169:
2166:
2163:
2160:
2157:
2154:
2151:
2148:
2145:
2142:
2139:
2136:
2133:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2103:
2100:
2097:
2094:
2091:
2088:
2085:
2082:
2079:
2076:
2073:
2070:
2067:
2064:
2061:
2058:
2055:
2052:
2049:
2046:
2043:
2040:
2037:
2034:
2031:
2028:
2025:
2022:
2019:
2016:
2013:
2010:
2007:
2004:
2001:
1998:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1962:
1959:
1956:
1953:
1950:
1943:
1936:
1931:
1930:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1882:
1879:
1876:
1873:
1866:
1863:class invariant
1855:
1850:
1764:
1763:
1745:
1740:
1737:
1736:
1711:
1709:
1706:
1705:
1624:
1623:
1605:
1602:
1601:
1576:
1574:
1571:
1570:
1548:
1545:
1544:
1519:
1516:
1515:
1507:
1464:
1461:
1460:
1355:
1354:
1336:
1333:
1332:
1325:
1300:
1297:
1296:
1292:
1270:
1267:
1266:
1232:
1229:
1228:
1153:
1150:
1149:
1124:
1121:
1120:
1116:
1094:
1091:
1090:
1086:
998:
997:
979:
976:
975:
969:
963:
954:
944:
937:
933:
929:
925:
911:
886:
883:
882:
878:
853:
820:
819:
817:
814:
813:
809:
784:
782:
779:
778:
756:
753:
752:
713:
695:
692:
691:
676:
651:
618:
617:
615:
612:
611:
607:
603:
593:
589:
564:
562:
559:
558:
554:
529:
527:
524:
523:
519:
465:
432:
431:
420:
395:
378:
376:
374:
371:
370:
352:
343:
339:
335:
331:
327:
323:
319:
315:
311:
307:
300:
299:
296:
293:
290:
287:
284:
281:
277:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
230:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
181:
178:
175:
172:
169:
166:
163:
160:
157:
154:
151:
148:
145:
142:
135:
131:
127:
122:
118:
114:
105:
73:predicate logic
35:
28:
23:
22:
15:
12:
11:
5:
3123:
3113:
3112:
3107:
3105:Formal methods
3093:
3092:
3085:
3074:Tim Teitelbaum
3070:
3059:
3048:
3034:
3017:Clifford Stein
3000:
2997:
2994:
2993:
2966:
2947:
2932:
2907:
2904:on 2016-03-04.
2853:
2831:
2825:Bertrand Meyer
2815:
2814:
2812:
2809:
2808:
2807:
2802:
2797:
2792:
2785:
2782:
2646:
2523:
2412:
2385:
2382:
2333:
2332:
2326:
2323:
2315:
2312:
2295:postconditions
1949:
1935:
1932:
1872:
1854:
1851:
1849:
1846:
1833:
1830:
1827:
1824:
1821:
1817:
1814:
1811:
1808:
1805:
1799:
1796:
1793:
1790:
1787:
1779:
1776:
1773:
1770:
1767:
1761:
1757:
1754:
1751:
1748:
1744:
1723:
1720:
1717:
1714:
1693:
1690:
1687:
1684:
1681:
1677:
1674:
1671:
1668:
1665:
1659:
1656:
1653:
1650:
1647:
1639:
1636:
1633:
1630:
1627:
1621:
1618:
1615:
1612:
1609:
1588:
1585:
1582:
1579:
1558:
1555:
1552:
1529:
1526:
1523:
1495:
1492:
1489:
1486:
1483:
1480:
1477:
1474:
1471:
1468:
1457:
1456:
1445:
1442:
1439:
1436:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1412:
1408:
1405:
1402:
1399:
1396:
1390:
1387:
1384:
1381:
1378:
1370:
1367:
1364:
1361:
1358:
1352:
1349:
1346:
1343:
1340:
1310:
1307:
1304:
1280:
1277:
1274:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1225:
1224:
1213:
1210:
1207:
1204:
1201:
1197:
1194:
1191:
1188:
1185:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1134:
1131:
1128:
1104:
1101:
1098:
1081:The condition
1079:
1078:
1067:
1064:
1061:
1058:
1055:
1051:
1048:
1045:
1042:
1039:
1033:
1030:
1027:
1024:
1021:
1013:
1010:
1007:
1004:
1001:
995:
992:
989:
986:
983:
967:
962:
959:
958:
957:
952:
951:
950:
899:
896:
893:
890:
865:
862:
859:
856:
849:
846:
843:
835:
832:
829:
826:
823:
796:
793:
790:
787:
766:
763:
760:
736:
733:
730:
725:
722:
719:
716:
711:
708:
705:
702:
699:
685:
684:
663:
660:
657:
654:
647:
644:
641:
633:
630:
627:
624:
621:
601:
588:whenever both
576:
573:
570:
567:
541:
538:
535:
532:
512:
511:
497:
494:
491:
488:
485:
482:
477:
474:
471:
468:
461:
458:
455:
447:
444:
441:
438:
435:
429:
426:
423:
418:
415:
412:
407:
404:
401:
398:
393:
390:
387:
384:
381:
351:
348:
141:
107:The following
104:
101:
43:loop invariant
26:
9:
6:
4:
3:
2:
3122:
3111:
3108:
3106:
3103:
3102:
3100:
3090:
3086:
3083:
3079:
3075:
3071:
3068:
3067:IEEE Software
3064:
3060:
3057:
3053:
3049:
3046:
3042:
3038:
3035:
3032:
3031:0-262-03293-7
3028:
3024:
3023:
3018:
3014:
3010:
3006:
3003:
3002:
2989:
2985:
2981:
2977:
2970:
2963:
2962:Prentice Hall
2960:
2956:
2951:
2943:
2936:
2928:
2924:
2920:
2914:
2912:
2900:
2896:
2892:
2888:
2884:
2880:
2876:
2875:
2867:
2863:
2857:
2849:
2842:
2835:
2829:
2826:
2820:
2816:
2806:
2803:
2801:
2798:
2796:
2793:
2791:
2788:
2787:
2781:
2644:
2640:
2521:
2410:
2408:
2404:
2400:
2396:
2391:
2381:
2375:
2370:
2368:
2363:
2357:
2353:
2349:
2344:
2342:
2331:
2327:
2324:
2321:
2320:
2319:
2311:
2296:
1947:
1941:
1870:
1864:
1860:
1845:
1828:
1825:
1822:
1815:
1812:
1809:
1806:
1803:
1794:
1791:
1788:
1688:
1685:
1682:
1675:
1672:
1669:
1666:
1663:
1654:
1651:
1648:
1616:
1613:
1610:
1556:
1553:
1550:
1543:The property
1541:
1527:
1524:
1521:
1513:
1493:
1490:
1487:
1484:
1478:
1475:
1472:
1440:
1437:
1434:
1431:
1425:
1422:
1419:
1406:
1403:
1400:
1397:
1394:
1385:
1382:
1379:
1347:
1344:
1341:
1331:
1330:
1329:
1322:
1308:
1305:
1302:
1278:
1275:
1272:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1208:
1205:
1202:
1195:
1192:
1189:
1186:
1183:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1148:
1147:
1146:
1132:
1129:
1126:
1102:
1099:
1096:
1084:
1062:
1059:
1056:
1049:
1046:
1043:
1040:
1037:
1028:
1025:
1022:
990:
987:
984:
974:
973:
972:
966:
953:
948:
947:
943:
942:
941:
928:mean that if
922:
920:
915:
897:
894:
891:
844:
764:
761:
758:
750:
731:
706:
703:
700:
690:
682:
642:
602:
599:
517:
516:
515:
492:
489:
486:
456:
424:
413:
388:
385:
382:
369:
368:
367:
365:
361:
357:
347:
305:
139:
113:
110:
100:
98:
94:
89:
85:
82:
78:
74:
70:
66:
61:
59:
55:
51:
48:
44:
40:
33:
19:
3110:Control flow
3081:
3066:
3055:
3044:
3020:
2979:
2975:
2969:
2958:
2950:
2941:
2935:
2926:
2923:Gries, David
2899:the original
2878:
2872:
2856:
2847:
2834:
2819:
2800:Loop variant
2775:
2641:
2634:
2511:
2394:
2393:
2371:
2364:
2345:
2334:
2317:
2288:
1937:
1856:
1542:
1458:
1323:
1226:
1082:
1080:
970:
964:
923:
918:
916:
689:Hoare triple
686:
681:(lower line)
680:
598:(upper line)
597:
514:This means:
513:
353:
302:Following a
301:
106:
90:
86:
62:
42:
36:
3037:David Gries
2982:: 191–220.
926:P { seq } Q
675:, provided
81:correctness
3099:Categories
2811:References
936:run, then
364:while loop
112:subroutine
77:algorithms
2895:207726175
2360:invariant
2354:, or the
1886:invariant
1826:≤
1686:≤
1614:≤
1554:≤
1491:≤
1485:∧
1467:¬
1438:≤
1432:∧
1414:¬
1345:≤
1306:≤
1250:≤
1244:∧
1206:≤
1174:≤
1168:∧
1130:≤
988:≤
895:∧
889:¬
762:∧
704:∧
490:∧
484:¬
386:∧
97:induction
93:recursive
58:assertion
2925:(1973).
2784:See also
2403:optimize
2352:assert.h
2350:library
1987:requires
1951:function
1089:loop is
749:relation
2514:x = y+z
2358:-shown
2339:in the
2056:ensures
2008:ensures
1735:yields
1085:of the
961:Example
949:implies
344:i<=n
336:i<=n
328:i<=n
324:i<=n
320:i>=n
47:program
3029:
3015:, and
2893:
2281:return
1940:Whiley
1934:Whiley
1859:Eiffel
1853:Eiffel
1801:
1783:
1661:
1643:
1392:
1374:
1035:
1017:
851:
839:
649:
637:
463:
451:
358:, the
332:i<n
312:i<n
288:return
2902:(PDF)
2891:S2CID
2869:(PDF)
2844:(PDF)
2409:) is
2367:above
2356:above
2341:above
2303:where
2299:max()
2291:max()
2260:items
2242:items
2224:items
2197:where
2185:<=
2182:items
2155:where
2146:items
2134:while
2128:items
2089:items
2080:items
2044:<=
2041:items
2032:items
1993:items
1969:->
1963:items
1944:where
1898:until
1892:<=
1326:while
1087:while
362:of a
209:while
161:const
115:max()
3027:ISBN
2708:<
2585:<
2516:and
2438:<
2289:The
2245:>
2200:some
2140:<
2059:some
1999:>
1938:The
1910:loop
1904:>
1874:from
1857:The
1792:<
1652:<
1476:<
1423:<
1383:<
1276:<
1238:<
1162:<
1100:<
1026:<
606:and
600:then
592:and
308:i!=n
244:<
128:i!=n
50:loop
41:, a
3065:."
3054:."
3043:."
3039:. "
2984:doi
2980:113
2883:doi
2690:int
2684:for
2567:int
2561:for
2518:x*x
2420:int
2414:for
2380:).
2297:of
2158:all
2119:int
2107:nat
2011:all
1975:int
1960:int
1954:max
1928:end
1514:to
934:seq
354:In
194:int
176:int
164:int
152:int
146:max
143:int
63:In
37:In
3101::
3080:.
3076:.
3019:.
3011:,
3007:,
2978:.
2957:,
2921:;
2910:^
2889:.
2879:12
2877:.
2871:.
2765:t1
2729:x2
2717:++
2678:x1
2672:x1
2666:t1
2648:x1
2624:t1
2594:++
2543:t1
2447:++
2278://
2239:if
2227:==
2215:..
2209:in
2173:..
2167:in
2131://
2104://
2092:==
2074:..
2068:in
2026:..
2020:in
1916::=
1907:10
1895:10
1880::=
1823:10
1807::=
1795:10
1683:10
1667::=
1655:10
1528:10
1494:10
1479:10
1441:10
1426:10
1398::=
1386:10
1348:10
1309:10
1279:10
1253:10
1241:10
1209:10
1187::=
1177:10
1165:10
1133:10
1103:10
1063:10
1041::=
1029:10
991:10
268:++
235:if
218:!=
2990:.
2986::
2885::
2771:}
2768:;
2762:+
2759:i
2756:*
2753:6
2750:=
2747:a
2744:;
2741:z
2738:+
2735:y
2732:=
2726:{
2723:)
2720:i
2714:;
2711:n
2705:i
2702:;
2699:0
2696:=
2693:i
2687:(
2681:;
2675:*
2669:=
2663:;
2660:z
2657:+
2654:y
2651:=
2630:}
2627:;
2621:+
2618:i
2615:*
2612:6
2609:=
2606:a
2603:{
2600:)
2597:i
2591:;
2588:n
2582:i
2579:;
2576:0
2573:=
2570:i
2564:(
2558:;
2555:x
2552:*
2549:x
2546:=
2540:;
2537:z
2534:+
2531:y
2528:=
2525:x
2507:}
2504:;
2501:x
2498:*
2495:x
2492:+
2489:i
2486:*
2483:6
2480:=
2477:a
2474:;
2471:z
2468:+
2465:y
2462:=
2459:x
2456:{
2453:)
2450:i
2444:;
2441:n
2435:i
2432:;
2429:0
2426:=
2423:i
2417:(
2348:C
2308:i
2284:m
2275:1
2272:+
2269:i
2266:=
2263:i
2257:=
2254:m
2251::
2248:m
2236::
2233:}
2230:m
2221:|
2218:i
2212:0
2206:k
2203:{
2191:}
2188:m
2179:|
2176:i
2170:0
2164:k
2161:{
2149:|
2143:|
2137:i
2125:=
2122:m
2116:1
2113:=
2110:i
2101::
2098:}
2095:r
2086:|
2083:|
2077:|
2071:0
2065:i
2062:{
2050:}
2047:r
2038:|
2035:|
2029:|
2023:0
2017:i
2014:{
2002:0
1996:|
1990:|
1981:)
1978:r
1972:(
1966:)
1957:(
1925:1
1922:+
1919:x
1913:x
1901:x
1889:x
1883:0
1877:x
1832:}
1829:x
1820:{
1816:1
1813:+
1810:x
1804:x
1798:)
1789:x
1786:(
1778:e
1775:l
1772:i
1769:h
1766:w
1760:}
1756:e
1753:u
1750:r
1747:t
1743:{
1722:e
1719:u
1716:r
1713:t
1692:}
1689:x
1680:{
1676:1
1673:+
1670:x
1664:x
1658:)
1649:x
1646:(
1638:e
1635:l
1632:i
1629:h
1626:w
1620:}
1617:x
1611:0
1608:{
1587:e
1584:u
1581:r
1578:t
1557:x
1551:0
1525:=
1522:x
1508:x
1506:(
1488:x
1482:)
1473:x
1470:(
1444:}
1435:x
1429:)
1420:x
1417:(
1411:{
1407:1
1404:+
1401:x
1395:x
1389:)
1380:x
1377:(
1369:e
1366:l
1363:i
1360:h
1357:w
1351:}
1342:x
1339:{
1303:x
1293:x
1273:x
1247:x
1235:x
1212:}
1203:x
1200:{
1196:1
1193:+
1190:x
1184:x
1180:}
1171:x
1159:x
1156:{
1127:x
1117:I
1097:x
1083:C
1066:}
1060:=
1057:x
1054:{
1050:1
1047:+
1044:x
1038:x
1032:)
1023:x
1020:(
1012:e
1009:l
1006:i
1003:h
1000:w
994:}
985:x
982:{
938:Q
930:P
912:I
898:I
892:C
879:I
864:y
861:d
858:o
855:b
848:)
845:C
842:(
834:e
831:l
828:i
825:h
822:w
810:I
795:y
792:d
789:o
786:b
765:I
759:C
735:}
732:I
729:{
724:y
721:d
718:o
715:b
710:}
707:I
701:C
698:{
683:.
677:I
662:y
659:d
656:o
653:b
646:)
643:C
640:(
632:e
629:l
626:i
623:h
620:w
608:I
604:C
594:I
590:C
575:y
572:d
569:o
566:b
555:I
540:y
537:d
534:o
531:b
520:I
496:}
493:I
487:C
481:{
476:y
473:d
470:o
467:b
460:)
457:C
454:(
446:e
443:l
440:i
437:h
434:w
428:}
425:I
422:{
417:}
414:I
411:{
406:y
403:d
400:o
397:b
392:}
389:I
383:C
380:{
340:i
316:n
297:}
294:;
291:m
282:}
274:;
271:i
262:;
259:a
256:=
253:m
250:)
247:a
241:m
238:(
227:{
224:)
221:n
215:i
212:(
206:;
203:1
200:=
197:i
188:;
185:a
182:=
179:m
173:{
170:)
167:a
158:,
155:n
149:(
136:a
132:m
123:n
119:a
109:C
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.