(1) I assume once the necessary mapping is invented, any Inv of the spec will do the job? My initial
interpretation is that finding the Inv will be key of finding the refinement mapping. Based on your
explanation, it seems like it's the other way around. Once we find the mapping, then with any Inv, we
could prove Implementation.
(2) If we will have to invent the mapping, I assume TLC will have to invent the mapping to be able to
prove implementation? I haven't study TLC yet, but I assume it works in a combinatorial way? How
could it be possible for TLC to figure out the refinement mapping, which is conceptual?
Thanks,
Oliver
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