Converting TLA+ spec to PlusCal

[Deividas Bražėnas]

Hello all,

I have a TLA+ spec that I'd like to convert to PlusCal, but I'm facing some issues as I don't know how to convert a few parts of the specification.

1. I want to have this predicate as a process, but I'm not sure how to convert this part "\E n \in CN, p \in BOOLEAN :"

UpdatePredicate ==

\E n \in CN, p \in BOOLEAN :

/\ predicate[n] => p \* Only monotonic updates are make the algorithm to terminate.

/\ predicate' = [predicate EXCEPT ![n] = p]

/\ UNCHANGED <<bcNode, bcValue, output, msgs>>

2. I want to specify global variable bcValue in Init based on the set of bcNode

/\ \/ bcNode \in CN /\ bcValue \in Value

    \/ bcNode \in FN /\ bcValue = NotValue

Thanks a lot!!

[Stephan Merz]

Hello,

TLA+ is more general than PlusCal, and a systematic conversion to PlusCal is unlikely to yield idiomatic results, if it is possible at all: you will probably end up with a single while loop containing all possible actions. It is a bit like the normal form theorem in computability theory.

On 18 Dec 2022, at 13:24, Deividas Bražėnas <deividas...@trafi.com> wrote:

Hello all,

I have a TLA+ spec that I'd like to convert to PlusCal, but I'm facing some issues as I don't know how to convert a few parts of the specification.

1. I want to have this predicate as a process, but I'm not sure how to convert this part "\E n \in CN, p \in BOOLEAN :"

UpdatePredicate ==

\E n \in CN, p \in BOOLEAN :

/\ predicate[n] => p \* Only monotonic updates are make the algorithm to terminate.

/\ predicate' = [predicate EXCEPT ![n] = p]

/\ UNCHANGED <<bcNode, bcValue, output, msgs>>

In PlusCal you could represent this as

with (n \in CN, p \in BOOLEAN) {

  await (predicate[n] => p);

  predicate[n] := p

}

2. I want to specify global variable bcValue in Init based on the set of bcNode

/\ \/ bcNode \in CN /\ bcValue \in Value

    \/ bcNode \in FN /\ bcValue = NotValue

You could perhaps write

variables

  bcNode \in CN \union FN,

  bcValue \in (CASE bcNode \in CN -> Value [] bcNode \in FN -> {NotValue});

Stephan

[Deividas Bražėnas]

Thank you, Stephan!!

I'm also wondering how I could write the following in PlusCal.

I have these global variables:

peers = {n_1, n_2, n_3, n_4}

msgs = [node_id \in peers |-> {}]

I want to add [t |-> "PROPOSE"] message for every peer in a process.

I've tried to do it like this, but it does not work as expected. What may I be doing wrong?

        print <<"with">>;

        with peer_id \in peers do

            print <<"peers", peers, "peer", peer_id>>;

            msgs[peer_id] := msgs[peer_id] \union {[t |-> "PROPOSE"]};

        end with;

        print <<"msgs", msgs>>;

I get the following output:

<<"with">>

<<"peers", {n_1, n_2, n_3, n_4}, "peer", n_1>>

<<"msgs", (n_1 :> {[t |-> "PROPOSE"]} @@ n_2 :> {} @@ n_3 :> {} @@ n_4 :> {})>>

<<"peers", {n_1, n_2, n_3, n_4}, "peer", n_2>>

<<"msgs", (n_1 :> {} @@ n_2 :> {[t |-> "PROPOSE"]} @@ n_3 :> {} @@ n_4 :> {})>>

<<"peers", {n_1, n_2, n_3, n_4}, "peer", n_3>>

<<"msgs", (n_1 :> {} @@ n_2 :> {} @@ n_3 :> {[t |-> "PROPOSE"]} @@ n_4 :> {})>>

<<"peers", {n_1, n_2, n_3, n_4}, "peer", n_4>>

<<"msgs", (n_1 :> {} @@ n_2 :> {} @@ n_3 :> {} @@ n_4 :> {[t |-> "PROPOSE"]})>>

Where I would expect:

<<"with">>

<<"peers", {n_1, n_2, n_3, n_4}, "peer", n_1>>

<<"peers", {n_1, n_2, n_3, n_4}, "peer", n_2>>

<<"peers", {n_1, n_2, n_3, n_4}, "peer", n_3>>

<<"peers", {n_1, n_2, n_3, n_4}, "peer", n_4>>

<<"msgs", (n_1 :> {[t |-> "PROPOSE"]} @@ n_2 :>  {[t |-> "PROPOSE"]}   @@ n_3 :>  {[t |-> "PROPOSE"]}   @@ n_4 :>  {[t |-> "PROPOSE"]}  )>>

[Stephan Merz]

In PlusCal, "with x \in S do ..." expresses non-deterministic choice, not a loop. The body of the "with" instruction is executed for some peer, then TLC backtracks and explores the remaining choices. Remember that TLC is a model checker that explores all runs of an algorithm, not an interpreter that generates one run. Therefore, "print" instructions are often hard to interpret.

I am not sure what exactly you are trying to achieve. The end result can of course be obtained by writing

msgs := [pid \in peers |-> [t |-> "PROPOSE"]]

Stephan

The content of this email, including all attachments, is confidential. If you are not the intended recipient, please notify us immediately and delete this email. Any disclosure, copying, distribution or any other use of its content is strictly prohibited.

-- 
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 view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/3fb78eb2-9d83-4e1b-b747-29a683469f7an%40googlegroups.com.

[Deividas Bražėnas]

Hey Stephan, thanks for the clarification and answer.

Sorry for not explaining correctly, but I want to simulate the messages sent for peers. So basically, in the end the variable msgs should look like this

msgs = [n_1 |-> {[t |-> "PROPOSE", v |-> "v_1], [t |-> "ECHO", v |-> "v_1]},

               n_2 |-> {[t |-> "PROPOSE", v |-> "v_1], [t |-> "ECHO", v |-> "v_1]},

               n_2 |-> {[t |-> "PROPOSE", v |-> "v_1], [t |-> "ECHO", v |-> "v_1]}]

And there will be a several processes like SendPropose or SendEcho that would append to set of messages. So sadly your proposed solution will not work :/ 

I've made loop like this work, but I'm wondering whether it would be possible to make it look more pretty

            while index <= Len(SetToSeq(peers)) do

                peer_id := peers[index];

                msgs[peer_id] := msgs[peer_id] \union {[t |-> "PROPOSE",  v |-> input]};

                index := index + 1;

            end while;

Deividas

[Stephan Merz]

You can rewrite your loop as follows:

while peers # {} do

  with p \in peers do

    msgs[p] := @ \union {...};

    peers := peers \ {p};

  end do;

end while

Note that unlike your version, this loop iterates through peers in a non-deterministic order, and that this will generate more states when you use TLC for model checking.

Stephan

To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/1b6b78c3-0887-4e54-8490-f55f500b3b04n%40googlegroups.com.

[Deividas Bražėnas]

Thanks for the answer, Stephan!

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/9Qe7gvU1rqI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to tlaplus+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/0BB14F11-2274-45EF-9121-7CBE50F61AA1%40gmail.com.

[Deividas Bražėnas]

I'm also wondering, maybe it would be possible to do that in a more simpler way? e.g. something like this:

msgs := [peer_id \in peers |-> msgs[peer_id] \cup {[t |-> "PROPOSE", v |-> input]}];

But this one gives me a syntax error at first "|->" operator when generated to following TLA+:

msgs' = [peer_id[self] \in peers[self] |-> msgs[peer_id[self]] \cup {[t |-> "PROPOSE", , v |-> input[self]]}]

[Stephan Merz]

The two commas look wrong: this could be an error in the PlusCal translator. If you can confirm this, could you open a GitHub issue? Could you share the entire TLA+ module?

What happens if you write something like

with m = [t |-> "PROPOSE", v |-> input] do

  msgs := [p \in peers |-> @ \cup {m}]

end with

Stephan

To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/7763e691-1bdd-4326-a748-e54194e5a189n%40googlegroups.com.

[Deividas Bražėnas]

Sorry, that was my typo, PlusCal translation seems to be alright.

Talking about your proposed solution, what does "@" means here? I get the following error during TLC "@ used where its meaning is not defined."

Deividas

[Stephan Merz]

Within a form [f EXCEPT ![x] = g(@)] (to which a PlusCal assignment f[x] := ... translates), `@' designates f[x]. `@' has no meaning in the right-hand side of an expression [x \in S |-> ...], sorry for the syntax error.

Stephan

To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/c02fcd12-1f74-4a15-a78c-bee89f45c968n%40googlegroups.com.

[Deividas Bražėnas]

Hey Stephan,

I'm a bit confused after your previous answer - what would be the correct way to write that with statement in my case?

Sorry if that is a dumb question 🤦‍♂️.

Deividas

[Stephan Merz]

with m = [t |-> "PROPOSE", v |-> input] do

  msgs := [p \in peers |-> msgs[p] \cup {m}]
end with

Apologies for the confusion!

Stephan

To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/9ceea054-2c8a-4dda-8af4-46d5927b6996n%40googlegroups.com.