For the loop below, state a suitable loop invariant and decrementing function. V
ID: 3789365 • Letter: F
Question
For the loop below, state a suitable loop invariant and decrementing function. Verify your answer with Dafny. Show your Dafny code. {x greaterthanorequalto 0 && y greaterthanorequalto 0} int s = x; int i = y; while (i != 0) {s = s - 1; i = i - 1;} {s = x - y} Write a loop that computes the minimal value in a non-empty array of integers. {arr != null^arr.Length > 0}/* Precondition using Dafny syntax */i = 0; z = arr[i]; while (...) {...} What is your loop invariant? What is your decrementing function? Verify your answer with Dafny. Show your Dafny code.Explanation / Answer
According to our assignment it has been requested to explain the loop invariant and decrementing function.
What is loop variant?
Loop invariant is an expression that holds upon entering a loop, and after every execution of the loop body. It captures something that is invariant, i.e. does not change, about every step of the loop.
Example :
var i := 0;
while i < n
invariant 0 <= i
{
i := i + 1;
}
When we specify an invariant, Dafny proves two things:
the invariant holds upon entering the loop, and
it is preserved by the loop
var i: int := 0;
while i < n
invariant 0 <= i <= n // <= i from the loop guard and 0 <= i <= n from the invariant
{
i := i + 1;
}
assert i == n;
According to the above program ,the point of the loop is to build up the Fibonacci numbers one (well, two) at a time until we reach the desired number. After we exit the loop, we will have that i == n, because i will stop being incremented when it reaches n.
According to our assignment the while condition states that while(i!=0)
if the loop guard is written as i != 0 then the negation of the guard immediately gives i == 0 after the loop, regardless of the loop invariant. Change the loop guard to i != 0 and delete the invariant annotation.
var i := y;
while i !=0
i==0
{
i := i - 1;
decreases i
}
When we verify the same with Dafny codes .
It requires a termination proof , when methods or functions are recursive. Similarly to looping forever, these methods could potentially call themselves forever, never returning to their original caller.
When Dafny is not able to guess the termination condition, an explicit decreases clause can be given along with pre- and postconditions.
Dafny can guess this condition on its own, but sometimes the decreasing condition is hidden within a field of an object or somewhere else where Dafny cannot find it on its own, and it requires an explicit annotation.