Symmetry sets

[Philip White]

Hello, TLA enthusiasts,

I'm having trouble understanding when it is safe to use symmetry sets.

This documentation at https://tla.msr-inria.inria.fr/tlatoolbox/doc/model/model-values.html says:

> The expression {{v1, v2}, {v1, v3}, {v2, v3}} is symmetric for the set {v1, v2, v3} -- for example, interchanging v1 and v3 in this expression produces {{v3, v2}, {v3, v1}, {v2, v1}}, which is equal to the original expression.

then it says:

> `CHOOSE x \in {v1, v2, v3} : TRUE` is not symmetric for {v1, v2, v3}.

I cannot reconcile these two statements. Suppose the original CHOOSE expression gives v1. After the same substitution as in the first quote, the CHOOSE expression gives v3. Is that not "equal to the original expression", in the same way that the tuples above are equal?

What is unique about CHOOSE that it is "the only TLA+ operator that can produce a non-symmetric expression”?

Thanks for any insights.

—
Philip

[Stephan Merz]

Hello Philip,

I cannot reconcile these two statements.  Suppose the original CHOOSE expression gives v1.  After the same substitution as in the first quote, the CHOOSE expression gives v3.  Is that not "equal to the original expression", in the same way that the tuples above are equal?

 {{v1, v2}, {v1, v3}, {v2, v3}} is not a tuple, but a set (of sets), and sets are unordered. Therefore, {{v3, v2}, {v3, v1}, {v2, v1}} is the same set as the first one. But note that you cannot even write this set unless you have access to the names of its elements.

What is unique about CHOOSE that it is "the only TLA+ operator that can produce a non-symmetric expression”?

A CHOOSE expression allows you to name an element of the set, distinguishing it from the others.

Suppose we have a constant parameter S, instantiated to the set of model values {v1,v2,v3}, and a definition

  someS == CHOOSE x \in S : TRUE

Then the expression

  IF s = someS THEN 0 ELSE 42

returns 0 for the chosen value but 42 for the others and is therefore not symmetric in S. This shows that S cannot be declared as a symmetry set for a specification that contains these entities.

The other TLA+ operators do not allow you to name elements of your parameter sets, for example you cannot explicitly build the tuple

  << v1, v2, v3 >>

which would not be symmetric in S. In contrast, expressions such as

  { seq \in Seq(S) : Len(seq) = 3 }

i.e., the set of all triples built from S, are symmetric. 

In contrast, replacing the definition of someS with the operator definition

  notS == CHOOSE x : x \notin S

does not destroy symmetry of the specification with respect to S. In particular, the test

  s = notS

returns FALSE for all elements of S.

In summary, symmetry reduction is very helpful for model checking, but deciding if a parameter can be declared as a symmetry set for a given specification can be subtle.

Regards,

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.

[Philip White]

Thanks — the clarification about tuples vs. sets was very helpful.

I sort of understand what you mean about naming an element with CHOOSE. However, in my spec, I use CHOOSE without caring what item I’m choosing. My goal is to select any item so that later I can check that the item is a member of that set. Is it possible to do this and retain symmetry?

—
Philip

[Hillel Wayne]

Hi Philip,

It sounds like there might be an XY problem here. CHOOSE is consistent:
for the same set and predicate, it will choose the same element across
all behaviors. If you're expecting TLC to try all selections, this could
lead to your spec passing when you think it should fail. This is a
common pitfall for beginners, which is why I'm bringing it up now.

If this is an issue in your spec, you can replace

item' = CHOOSE x \in Set: P(x)

with

item' \in {x \in Set: P(x)}

which retains symmetry.

H

[Philip White]

I see… yes, I was expecting TLC to try all selections. Thank you very much for clarifying this newbie mistake.

What I like about CHOOSE is that it will select exactly one item, or give a model error if it couldn’t find one. With the second (symmetric) syntax you suggest, we get a set, and the set may be empty. To make up for CHOOSE’s functionality, is using a type invariant the answer?

Philip

[Jay Parlar]

A TypeOK invariant would work great. And it would have the added benefit of throwing an error at the exact step in which the set is no longer satisfying the invariant, rather than waiting for the CHOOSE to take place.

This will make it much easier to track down _why_ things went awry.

The only reason I see that an invariant wouldn’t be feasible is if the set in question is not one of your variables. If it’s some computer value, then you’d need to use an assert.

Jay P

[Philip White]

An update to my own message. Turns out that I missed the syntax difference between

item \in {x \in Set: P(x)}

vs

item = {x \in Set: P(x)}

The former, which is what you recommended in the first place, gives me exactly one item at a time. I can get rid of CHOOSE! Thank you.

—
Philip