For the computer programming optimization technique, see Loop-invariant code motion.
In computer science, a loop invariant is a property of a program loop that is true before (and after) each iteration. It is a logical assertion, sometimes checked with a code assertion. Knowing its invariant(s) is essential in understanding the effect of a loop.
In formal program verification, particularly the Floyd-Hoare approach, loop invariants are expressed by formal predicate logic and used to prove properties of loops and by extension algorithms that employ loops (usually correctness 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.
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 [1] covers fundamental algorithms from many areas of computer science (searching, sorting, optimization, arithmetic etc.), characterizing each of them from the viewpoint of its invariant.
Because of the similarity of loops and recursive programs, proving partial correctness of loops with invariants is very similar to proving the correctness of recursive programs via induction. 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.
^Carlo A. Furia, Bertrand Meyer and Sergey Velder. "Loop invariants: analysis, classification, and examples."ACM Computing Surveys. vol. 46, no. 3, February 2014([1]
In computer science, a loopinvariant is a property of a program loop that is true before (and after) each iteration. It is a logical assertion, sometimes...
the exit condition and the loopinvariant are satisfied. Loopinvariants are used to monitor specific properties of a loop during successive iterations...
whose value doesn't change during program execution Loopinvariant, a property of a program loop that is true before (and after) each iteration A data...
computer science, code motion, also known as code hoisting, code sinking, loop-invariant code motion, or code factoring, is a blanket term for any process that...
B\wedge P\}}}} Here P is the loopinvariant, which is to be preserved by the loop body S. After the loop is finished, this invariant P still holds, and moreover...
once before the loop begins, if the resultant quantity of the calculation will be the same for every loop iteration (i.e., a loop-invariant quantity). This...
values of current_sum seen so far, cf. line 7 of the algorithm. As a loopinvariant, in the j {\displaystyle j} th step, the old value of current_sum holds...
each time through the loop. Loopinvariants are essentially constants within a loop, but their value may change outside of the loop. Induction variables...
relation by the iteration of a while loop under some invariant conditions, thereby ensuring its termination. A loop variant whose range is restricted to...
multiplication by a loop index with addition. Loop optimization acts on the statements which make up a loop, such as a for loop, for example loop-invariant code motion...
of a struct component in the loop body has to be down-coerced at loop re-entry to meet the typestate of the very first loop entry, viz. ⊥. A related problem...
or throw an exception. invariant Defines an invariant property of the class. loop_invariant Defines a loopinvariant for a loop. also Combines specification...
Concepts Curry–Howard correspondence Loopinvariant Refinement Side effect Soundness and completeness Specification Languages Verification Logics Hoare...
empty, or do-nothing command. There is no need for a loopinvariant or least fixed point. Loops with multiple intermediate shallow and deep exits work...
category. It required the user to input pre/post specs, loopinvariants, and resource invariants for locks. It introduced a method of symbolic execution...
stall, which is a detriment to performance. Additionally, loop inversion allows safe loop-invariant code motion. i := 0 L1: if i >= 100 goto L2 a[i] := 0...
course on distributed systems in Munich. It assumed that properties are invariant under stuttering. The formal definition of safety given above appears...
problem of computing dependencies within loops, which is a significant and nontrivial problem, is tackled by loop dependence analysis, which extends the...
people Outliner, filter for viewing In computing, hoisting may refer to: Loop-invariant code motion, a compiler optimization Variable hoisting, scope rule in...
Global Information