Re: [tlaplus] Re: How to understand the concept "step simulation"

Ah, my mistake, I should have read the entire thing. Nevertheless, for clarity I might have preferred it said something like "Formula (5.3) is then proved by finding an invariant Inv of Spec satisfying Init => Inv and Inv /\ [Next]_vars => Inv' such that <the two formulas he has>

Thanks

On Wednesday, December 18, 2019 at 11:44:06 PM UTC-8, Stephan Merz wrote:

Hi again,

the sentence that you cite says "Formula (5.3) is then proved by finding an invariant Inv of Spec such that ...". As explained on the preceding page, an invariant Inv of Spec is a state predicate such that

Init => Inv and Inv /\ [Next]_vars => Inv'

hold. The formula "..." does not repeat these conditions but only states the proof obligation for showing step simulation.

Stephan

On 19 Dec 2019, at 01:50, ss.ne...@xxxxxxxxx wrote:

hi Stephan, thanks for the informative example. I am familiar with inductive invariants, my sticking point is that the formula in question does not require Inv to be initially true. Here's how it appears
<formula.jpg>

So as it stands, it seems to me we can establish the 2nd conjunct by setting Inv to False. Or am I still missing something?
thanks

On Thursday, December 5, 2019 at 1:44:46 AM UTC-8, Stephan Merz wrote:
Let me try another attempt for explaining the issue. To make things simpler, let's leave aside the issue of refinement mapping, that is, consider just the identity refinement mapping. We want to prove

(0) InitL /\ [][NextL]_varsL => InitH /\ [][NextH]_varsH

Obviously, this can be reduced to proving

(1) InitL => InitH
(2) NextL \/ varsL' = varsL => NextH \/ varsH' = varsH

However, the obligation (2) is very likely going to be unprovable because really, we only have to prove that implication for all reachable states (i.e., reachable in runs of the low-level spec) rather than for completely arbitrary states, and that's where the invariant comes in.

Let's look at a stupid example: our high-level specification has one variable initialized to zero and that keeps growing while remaining an even number:

Even == {n \in Int : n % 2 = 0}
InitH == x = 0
NextH == x' > x /\ x' \in Even

Our low-level specification has two variables x and y that evolve as follows:

InitL == x = 0 /\ y = 0
NextL == x' = x+y /\ y' = y+2

Condition (2) now requires us to show

(x' = x+y /\ y'=y+2) \/ (x'=x /\ y'=y)
=> (x' > x /\ x' \in Even) \/ x' = x

but this implication is not true and therefore cannot be proved: we have no information about the "types" of x and y, so they could be strings for example. Even if they are integers, we could have x=42 and y=7, x' = 49 and y'=9, and the right-hand side will be false. And indeed, such a state cannot be reached because the low-level spec ensures that x and y are always even. Therefore we define

Inv == x \in Even /\ y \in Even

and relax our proof obligations to be

(1') InitL => InitH /\ Inv
(2') Inv /\ (NextL \/ varsL' = varsL) => Inv' /\ (NextH \/ varsH' = varsH)

which still implies our high-level goal (0). I leave proving (1') and (2') for our example as an exercise to you.

Indeed, Inv can be an arbitrary state predicate and has to be "invented" by the system designer / verifier. But it must be an invariant of the low-level specification, and FALSE is unlikely to be one.

You may also want to read section 6.8 of the Hyperbook.

Hope this helps,
Stephan

On 5 Dec 2019, at 09:58, ss.ne...@gmail.com wrote:

I have to admit I'm a bit confused by the explanation in the text too and don't quite see what Inv is representing. For example, can I set Inv to anything that allows me to prove the formula, what if I set it to False?

Thanks

On Sunday, March 10, 2019 at 12:52:43 PM UTC-7, Leslie Lamport wrote:
(1) If we remove the Inv from the formula Inv /\ Next => ..., it would assert
    that a step starting in any state that satisfies Next satisfies "..." --
    for example a state in which memQ is a sequence of imaginary numbers.
    I have no idea if that assertion is true for such a starting state.
    However, it suffices to prove the assertion for steps starting in a
    reachable state. Conjoining the invariant Inv allows you to prove
    the assertion only for reachable states. You have to choose Inv so
it asserts what is true about reachable states that makes the
implication true. To do this, you have to understand why the theorem
you're trying to prove is true.

(2) That mapping isn't derived; you have to invent it. The sentence
    beginning "Intuitively" that starts on line 9 of page 63 tells you
    what condition that substitution must satisfy.  To be able to choose
the necessary mapping, you need to understand why the theorem you're
trying to prove is true .

Leslie

On Wednesday, March 6, 2019 at 10:53:35 PM UTC-8, Oliver Yang wrote:
Hi All,

In Section 5.8 of book "Specifying Systems", the "Proving Impl" is introduced. I have a rough understanding of refinement mapping, which
essentially maps states of Spec A to the states of Spec B. However, I have a hard time understanding "step simulation".

1) What's the purpose of introducing the invariant Inv in Formula 5.3? What are we trying to achieve here?
2) How do we derive the mapping: omem = vmem, octl = ..., obuf = buf? It looks like we jumped to the conclusion without showing any proof?

Thanks,

Oliver

--
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tla...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/369feaf8-c1ad-49c5-9915-d13e8687105c%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tla...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/3475e834-0050-40a3-b13f-647c8762c04d%40googlegroups.com.
<formula.jpg>