[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Question on Inductive Invariants (page 44)?
Working through the Inductive invariants for Euclid, I've encoded them as follows:
\* PC means `PartialCorrectness,' but it's a lot easier to write and read.
PC == (pc = "Done") => (x = y) /\ (x = GCD(M, N))
TypeOK == /\ x \in Nat \ {0}
/\ y \in Nat \ {0}
Inv == /\ TypeOK
/\ GCD(x, y) = GCD(M, N)
/\ (pc = "Done") => (x = y)
InductiveInv == /\ Inv
/\ (pc = "antanaresis") => (x /= y)
I1 == Init => Inv
I2 == Inv /\ Next => Inv'
I3 == Inv => PC
In the model checker, I can check them all except I2, which generates the following error (I labeled my while loop "loop"):
In evaluation, the identifier pc is either undefined or not an operator.
line 32, col 23 to line 32, col 24 of module ExtraSimpleEuclid
While working on the initial state:
/\ x = 30
/\ y = 18
/\ pc = "loop"
Which I interpreted as the checker trying to evaluate Inv /\ Next in when state Init is TRUE and getting undefined pc.
Fair enough, I modified I2 to be
I2 == ~Init /\ Inv /\ Next => Inv'
and I check in the model to ONLY verify the ivariant I2 (PC, Inv, InductiveInv, I1 and I3) are unchecked lest I get other more mysterious errors).
I get the error that "Invariant PC failed." But I didn't ask it to check PC? And if I uncheck I2 and check PC, it succeeds. I'm stumped, and I'd be grateful for advice.
My entire model is as follows:
------------------------- MODULE ExtraSimpleEuclid -------------------------
EXTENDS Integers, GCD
CONSTANTS M, N
ASSUME {M, N} \subseteq Nat \ {0} \* `subset' doesn't seem to work
(***************************************************************************
--fair algorithm Euclid
{ variables x = M, y = N;
{ loop: while (x /= y)
\* The Greek word for the following process of repeated subtraction
\* is `antanaresis.'
{ antanaresis: if (x < y) { y := y - x; }
else { x := x - y; }
}
} }
***************************************************************************)
\* BEGIN TRANSLATION
VARIABLES x, y, pc
vars == << x, y, pc >>
Init == (* Global variables *)
/\ x = M
/\ y = N
/\ pc = "loop"
loop == /\ pc = "loop"
/\ IF x /= y
THEN /\ pc' = "antanaresis"
ELSE /\ pc' = "Done"
/\ UNCHANGED << x, y >>
antanaresis == /\ pc = "antanaresis"
/\ IF x < y
THEN /\ y' = y - x
/\ x' = x
ELSE /\ x' = x - y
/\ y' = y
/\ pc' = "loop"
Next == loop \/ antanaresis
\/ (* Disjunct to prevent deadlock on termination *)
(pc = "Done" /\ UNCHANGED vars)
Spec == /\ Init /\ [][Next]_vars
/\ WF_vars(Next)
Termination == <>(pc = "Done")
\* END TRANSLATION
\* PC means `PartialCorrectness,' but it's a lot easier to write and read.
PC == (pc = "Done") => (x = y) /\ (x = GCD(M, N))
TypeOK == /\ x \in Nat \ {0}
/\ y \in Nat \ {0}
Inv == /\ TypeOK
/\ GCD(x, y) = GCD(M, N)
/\ (pc = "Done") => (x = y)
InductiveInv == /\ Inv
/\ (pc = "antanaresis") => (x /= y)
I1 == Init => Inv
I2 == (~Init) /\ Inv /\ Next => Inv'
I3 == Inv => PC
=============================================================================