Proving partial correctness of the SetGCD algorithm in the hyperbook

54 views
Skip to first unread message

Jens Weber

unread,
Jun 23, 2016, 8:55:39 PM6/23/16
to tlaplus
Hello TLA community,

I am trying to prove partial correctness of the SetGCD algorithm in the hyperbook - but I am not successful. Does anybody have a solution here? I am currently stuck on showing that S' is a finite set. 

Thanks
Jens

Stephan Merz

unread,
Jun 24, 2016, 2:15:34 PM6/24/16
to tla...@googlegroups.com
I haven't tried writing a formal proof of that algorithm, and it is not entirely clear to me where you are stuck.

The (type) invariant contains the conjunct

  IsFiniteSet(S)

and you need to prove that this predicate is preserved by action Lbl_1. You'll need to use the standard module FiniteSetTheorems contained in the TLAPS distribution. (If you haven't done so yet, you should add the corresponding directory to the Toolbox search path.) In particular, the lemmas FS_AddElement and FS_RemoveElement will be useful.

Hope this helps,
Stephan


--
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 tlaplus+u...@googlegroups.com.
To post to this group, send email to tla...@googlegroups.com.
Visit this group at https://groups.google.com/group/tlaplus.
For more options, visit https://groups.google.com/d/optout.

Jens Weber

unread,
Jun 24, 2016, 2:30:09 PM6/24/16
to tlaplus
Thanks Stephan.
Yes, I also thought that I needed some axioms regarding removing and adding elements to finite sets. I didn't know about the FiniteSetsTheorem module though. I tried to define my own. Below is my current theorem. I'll look into the standard module now (but would still be interested in understanding why my axioms don't work.)

THEOREM ax1 == ASSUME NEW x \in Int PROVE IsFiniteSet({x})


THEOREM ax2 == ASSUME NEW x \in Int, NEW y \in Int PROVE IsFiniteSet({y-x})


THEOREM ax3 == ASSUME NEW S1, NEW S2,

                      /\ IsFiniteSet(S1)

                      /\ IsFiniteSet(S2)

               PROVE /\ IsFiniteSet(S1 \ S2)

                     /\ IsFiniteSet(S1 \cup S2)



THEOREM Spec => []PartialCorrectness

<1>1. Init => SInv

    BY InputOK DEF Init, SInv, TypeOK, PartialCorrectness

<1>2. SInv /\ [Next]_vars => SInv'

  <2> SUFFICES ASSUME SInv /\ [Next]_vars

               PROVE  SInv'

    OBVIOUS

  <2>1. TypeOK'

    <3>1. CASE Lbl_1

      <4>1. (S \subseteq Nat \{0})'

        BY <3>1 DEF SInv, TypeOK, Next, vars, Lbl_1

      <4>2. (S # {})'

        BY <3>1 DEF SetGCD, SInv, TypeOK, Next, vars, Lbl_1, SetMax, Divides

      <4>3. IsFiniteSet(S)'

        BY <3>1, ax1, ax2, ax3 DEF SInv, TypeOK, Next, vars, Lbl_1

      <4>4. QED

        BY <4>1, <4>2, <4>3 DEF TypeOK

      

    <3>2. CASE pc = "Done" /\ UNCHANGED vars

      BY <3>2 DEF PartialCorrectness, SInv, TypeOK, vars

    <3>3. CASE UNCHANGED vars

      BY <3>3 DEF Init, SetGCD, PartialCorrectness, SInv, TypeOK, Next, vars

    <3>4. QED

      BY <3>1, <3>2, <3>3 DEF Next

    

  <2>2. (SetGCD(S) = SetGCD(T))'

    BY InputOK DEF Init, SInv, TypeOK, Next, vars

  <2>3. PartialCorrectness'

    BY InputOK DEF Init, SInv, TypeOK, Next, vars

  <2>4. QED

    BY <2>1, <2>2, <2>3 DEF SInv

    

<1>3. SInv => PartialCorrectness

    BY DEF SInv, PartialCorrectness

<1>4. QED

    BY <1>1, <1>2, <1>3, PTL DEF Spec

Stephan Merz

unread,
Jun 24, 2016, 2:45:38 PM6/24/16
to tla...@googlegroups.com
Hard to tell without being able to replay the proof. (If you send me your TLA module by private email I can have a look.)

Note that ax2 is subsumed by ax1 since it asserts that some particular singleton set is finite.

Regards,
Stephan

Jens Weber

unread,
Jun 24, 2016, 2:54:16 PM6/24/16
to tla...@googlegroups.com

Yes,  I initially just added ax1 and ax3 (then called “ax2”) for my proof – but when that didn’t work (and I hadn’t any other idea as to why not) I added the additional axiom (ax2), despite feeling that it shouldn’t be needed.

 

(I am new to TLAPS – so I am still learning the ropes.)

 

I have attached the module.

 

By the way, your suggestion of using FS_AddElement and FS_RemoveElement worked.

 

Thanks

Jens

--
You received this message because you are subscribed to a topic in the Google Groups "tlaplus" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/tlaplus/c9kjW0Hv6Dc/unsubscribe.
To unsubscribe from this group and all its topics, send an email to tlaplus+u...@googlegroups.com.

SetEuclid.tla

Stephan Merz

unread,
Jun 25, 2016, 5:46:19 AM6/25/16
to tla...@googlegroups.com
Hello Jens,

I changed two things: first, generalized your ax1 to

THEOREM ax1 == ASSUME NEW x (*\in Int*) PROVE IsFiniteSet({x})

so that one doesn't have to prove that y and y-x are integers (this follows of course from the type invariant but probably you'd have to make this explicit in the proof). Second, helped the prover by inserting a step (the first level-5 step below) that asserts that the expression on the right-hand side of the assignment is again a finite set. With these changes, the proof of TypeOK works as follows:

  <2>1. TypeOK'
    <3>1. CASE Lbl_1
      <4>1. (S \subseteq Nat \{0})'
        BY <3>1 DEF SInv, TypeOK, Next, vars, Lbl_1
      <4>2. (S # {})'
        BY <3>1 DEF SetGCD, SInv, TypeOK, Next, vars, Lbl_1, SetMax, Divides
      <4>3. IsFiniteSet(S)'
        <5>. \A x \in S : \A y \in {s \in S : s > x} : IsFiniteSet((S \ {y}) \cup {y-x})
          BY ax1, ax3 DEF SInv, TypeOK
        <5>. QED  BY <3>1 DEF SInv, TypeOK, Lbl_1
      <4>4. QED
        BY <4>1, <4>2, <4>3 DEF TypeOK
(* -- subsumed by <3>3
    <3>2. CASE pc = "Done" /\ UNCHANGED vars
      BY <3>2 DEF PartialCorrectness, SInv, TypeOK, vars
*)
    <3>3. CASE UNCHANGED vars
      BY <3>3 DEF Init, SetGCD, PartialCorrectness, SInv, TypeOK, Next, vars
    <3>4. QED
      BY <3>1, (*<3>2,*) <3>3 DEF Next

I agree that one would expect these modifications to be unnecessary. Unfortunately, at this point, the backends need a little more help than we'd like.

Best regards,
Stephan

<SetEuclid.tla>

Reply all
Reply to author
Forward
0 new messages