Appendix C: PlusCal to TLA+
In this book we used TLA+ through the intermediary of PlusCal, an algorithm syntax built on top of TLA+. While PlusCal is simple to learn and useful for a wide range of problems, not everything can be expressed in it. Rather than teach you how to write specs in TLA+, we’re going to provide an overview and intuition for how TLA+ “works.” If you want a more rigorous treatment, please refer to the book
Specifying Systems
, which can be accessed for free in the Toolbox under
Help > Specifying Systems
.
This appendix assumes you’ve read the first six chapters of the book and Appendix A. We’ll start by covering some extensions to logic, follow up with how we express properties in TLA+, and conclude with a brief discussion of when you’d want to use pure TLA+ over PlusCal.
Temporal Logic
With predicate logic, we could
quantify
statements: say whether something is true for
all possible
values, or only true for
at least one
value.
Modal logic
lets us
qualify
statements. □
P
means that P is
necessarily
true. ⋄
P
means that P is
possibly
true. What “necessarily” and “possibly” mean depends on the modal logic system you’re using. Most of them are only interesting to philosophers, but one type of modal logic,
temporal logic
, matters a great deal in software engineering. In a temporal logic, □
P
means that P is
always
true, while ⋄
P
means that P is
sometimes
true.
“Always” is unambiguous here, but there’s two common and exclusive ways people interpret “sometimes”:
- 1.
For every initial state, it is possible to reach a state where P is true.
- 2.
For every initial state, no matter what you do, you will at some point reach a state where P is true.
To see the difference between the two, consider rolling a 6-sided dice. If you roll once, is it true that ⋄(
roll
= 6)? Under the first interpretation
, yes: it is
possible
that you rolled a six. Under the second interpretation, no: you could roll a 5 instead. But under both interpretations, we have ⋄(
roll >
0) and
¬
⋄(
roll
= 7).
TLA+ follows the second interpretation. To make it clearer we say
eventually
instead of
sometimes
. In order for these qualifiers to be useful, we need a way to talk about how our statements change. This is what makes it a
temporal
logic: instead of having fixed, static statements, we allow them to evolve over time.
We do this by adding a concept of a
variable
. You’re already familiar with this: a variable is some value that may be different at different points in time. In the context of a temporal logic, we represent “different points in time” by having a sequence of states, where the values of variables may change between states. For example, if x starts at zero, increases by one until it reaches 2, and then goes back to zero, we could represent “what happens” as the sequence
(x
= 0
, x
= 1
, x
= 2
, x
= 0
)
. Here the statement ⋄(
x
= 2) is true, while the statement □(
x
= 0) is false. We call any such sequence of states a
behavior
.
Now that we have a means of describing behaviors
and properties we want, we need a way of describing which behaviors in our system are
valid
, or actually can happen in our system. For example, one possible behavior is
(x
= 0
, x
= −9,
x
= ” :)”,
x
= 0). We probably don’t want that to be valid!
In order to mark the valid behaviors, we use
next-state relations
, which are built on the “actions” of TLA+.
Actions
An
action
is a predicate between two consecutive states of a behavior. It looks and behaves exactly like any other predicate, except it also contains a
prime
operator (a single quote, or ’). In an action,
x
is the value of
x
in the first state, while
x’
is the value of x in the next state.
This may seem confusing, so let’s give an example. Take the action
Increases == x
’
> x. Increases
is true for a state if, in the
next
state, x is greater than it was before. If the behavior is
(x
= 0
, x
= 1
, x
= 2
, x
= 0
)
,
Increases
is true for the first and second states, but not the third state. In the first state,
x
= 0 and
x’
= 1, so
x’ > x
. In the third,
x
= 2 and
x’
= 0, so
¬
(
x’ > x
).
Another example action is
DecreaseFromAtLeastThree ==
/ x > 2
/ x’ < x
This is only true if x is greater than 2 and then decreases. In our above behavior, it is never true: while at one point x decreased, it didn’t start out greater than 2.
Why are actions important? Combined with our modal operators, actions give us a way to describe the total evolution of a system. Let’s assume our counter is supposed to be modulo-3: x starts at 0, increments by 1 each tick until it reaches 2, and then returns to 0. Every transition can be described as one of two actions:
Increment ==
/ x < 2
/ x’ = x + 1
Reset ==
/ x = 2
/ x’ = 0
Every transition is one of these actions. This means that one of these actions is
always
true. This means we can describe
all possible behaviors
as follows:
Init == (x = 0)
Next == Increment / Reset
Spec == Init / []Next
Init
by itself means the starting state: x must start at zero. □
Next
means that
Next
must be true for the entire behavior, aka either
Increment
is true or
Reset
is true. Since both of them constrain
how x can change between two states, this is enough to give us a specification of our system.
Now, write the following PlusCal algorithm and translate it to TLA+:
EXTENDS Integers
(*--algorithm counter variables x = 0
begin
while TRUE do
either
await x < 2;
x := x + 1;
or
await x = 2;
x := 0;
end either; end while;
end algorithm; *)
Look familiar?
TLA
There are two last things we need to take care of. First of all, we require that the next-state relation must specify the new values of
all
variables. Between any two states, the actions that are true must cover every variable in the spec. If we forget to account for some value, say,
account_total
, we’re saying it doesn’t matter
what
account_total’
is. This means it’s a valid behavior for
account_total = 1
and
account_total’ = "abcdefg"!
This quickly leads to nonsense, so we require that all variables are specified.
Finally, we need all of our specs to be
stutter-invariant
. At any point we should be able to drop in an extra state where nothing happens. Without this property, we eventually run into bizarre problems, and it becomes nearly impossible to cleanly combine two specs together. Permitting stuttering just makes the specs a whole lot cleaner. So instead of writing
[]Next
, we write
[][Next]_x
. That’s equivalent to writing
[](Next / UNCHANGED x)
, or “either Next is true or x is unchanged.” This lets stuttering happen, giving us all the nice properties of stutter-invariance. Obviously, if our spec uses more than one variable, we’d1 have to add them too.
With that, we now have a
T
emporal
L
ogic of
A
ctions, or
TLA
. TLA+ is just TLA with some extra structure on top, such as the module system. There’s still a few small details, such as fairness, but you now have a broad overview.
You might sometimes see specs written as
THEOREM Spec => []TypeInvariant
That’s a note to the reader that
if
the system obeys
Spec
,
then
it will have
TypeInvariant
as an invariant. In practice, this doesn’t change what the model checker does; you still have to make
Spec
the temporal formula and add
TypeInvariant
as a specific invariant.
Limitations
of PlusCal
PlusCal abstracts a lot of this away. For many problems, it’s perfectly adequate. However, there are some limitiations. First of all, it’s not as flexible as writing everything in TLA+. You couldn’t, for example, have an action of form
(A / B) / (A / C)
in PlusCal, or allow two processes to run “simultaneously.” You also can’t compose specifications with variables together in PlusCal, while it’s pretty straightforward in TLA+.
One major limitation of PlusCal is something we touched on in Chapter
: you can’t prove one spec is a
refinement
of another. In TLA+, we could instantiate the high-level spec with
INSTANCE HighLevel
and then check the temporal property
HighLevel!Spec
. That would say that every behavior of the implementation is also a valid behavior
of the high level spec.
PlusCal will serve you well for a very long time. But you should know when you’re pushing against the limits.