In this chapter, we will introduce TLA+ proper and use it to write more powerful specs with complex invariants. We’ve already been using some TLA+. All of our variables were defined in terms of TLA+ expressions. All of our values, sets, sequences, and structures were TLA+ expressions. All of our conditionals were TLA+ expressions. PlusCal was just a framing structure, a simplified assignment rule, and a few extra keywords.
Now that we know this, we can express it more formally and leverage what it actually means.
Operators
An operator is the TLA+ equivalent of a procedure in programming. You write it like this:
Op(arg1, arg2) == Expr
Yes, that’s a double equals. If the expression doesn’t depend on the arguments, you can write Op == Expr. This is commonly used to represent constants. We can use operators to simplify the setup of our recycler:
BinTypes == {"trash", "recycle"}
SetsOfFour(set) == set X set X set X set
Items == [type: BinTypes, size: 1..6]
(* --algorithm recycler
variables
capacity * ...
items in SetsOfFour(Items);
Since the set of possible items we’re feeding in is constant, we define it as an operator instead of a variable. This prevents us from accidentally modifying the set in the algorithm itself. The TLA+ does not use semicolons; only the PlusCal computations need semicolons. TLA+’s syntax is (with the exception of nested conditionals below) not whitespace sensitive, and you could place all three operators on the same line if you really wanted to.
If you want to define an operator using the variables of a PlusCal algorithm, you can place it in a define block:
The PlusCal translator is very simple and everything needs to be in the right order. Definitions must go above macro definitions and below variable definitions.
We can place the definition of the operator on a new line. We could also place both clauses on separate lines, too. Another way we could define our assertion is to combine both NoBinOverflow and CountsMatchUp into a single operator:
define
Invariant ==
/ capacity.trash >= 0
/ capacity.recycle >= 0
/ Len(bins.trash) = count.trash
/ Len(bins.recycle) = count.recycle
end define;
For convenience in formatting, we can place an optional / before the first clause. This is the idiomatic way to write multiple clauses in a single operator. We can also nest clauses: this is the only place in TLA+ where whitespace matters. If the line following a clause is indented, it belongs to the same subclause. In other words, if we write
/ A
/ B
/ C
/ D
We get A / (B / C) / D.
There’s also a few special forms of operators with their own syntax. First, we can have higher-order operators, or ones that take other operators as parameters. You need to specify in advance how many parameters the operator takes, which you do with _:
Add(a, b) == a + b
Apply(op(_, _), x, y) == op(x, y)
>> Apply(Add, 1, 2)
3
You can define anonymous operators with LAMBDA. Anonymous operators can only be used as arguments to other operators, not as stand-alone operators. They’re written as LAMBDA param1, param2, paramN: body.
Apply(LAMBDA x, y: x + y, 1, 2)
>> 3
Finally, things like >= and o are operators, too. There’s a set of “User Definable Operator Symbols” that can be defined as operators. You can see them by going to Help > The TLA+ Cheat Sheet in the Toolbox.
set ++ elem == set union {elem}
set -- elem == set {elem}
>> {1, 2} ++ 3
{1, 2, 3}
>> {1, 2} – 2
{1}
Invariants
We can use operators as invariants. An invariant is a Boolean expression that’s checked at the end of every “step” of the model. If it’s ever false, the model fails. One example of an invariant is the NoOverdrafts operator we saw in Chapter 2. Similarly, we can use NoBinOverflow and CountsMatchUp as our invariants in the recycler, which makes the assert at the end superfluous.
Not all models you write will check all invariants. You have to specify what you actually care about. You can do this by adding the invariants to the “Invariants” section of the model and then checking them (Figure 3-1).
Figure 3-1
An added invariant that checks everything
If we add them and rerun the model, you’ll note two differences with the failure. First of all, the error is much nicer. Second, instead of our spec failing at the very end of the run, it fails as soon as the error appears. This makes it easier to identify what went terribly wrong.
We don’t need to define an operator to add an invariant. We can place any expression we want in the “Invariants” box. However, creating dedicated operators is cleaner and better signals your intent to anybody else who reads your spec.
From now on, we will note the invariants you are checking with INVARIANT NameOfInvariant. In the above case (Figure 3-2), we are running the model with INVARIANT Invariant.
Figure 3-2
An inlined expression
Logical Operators
With invariants, we can express simple properties like “there is some capacity left,” or “the number of items in the bin matches the count.” Often we want to express more complex properties, either for setups, conditionals, or invariants. We can significantly increase our expression power with two sets of two operators, one for Booleans and one for sets.
A and E
A means “all elements in a set.” It’s used in the form A x in set: P(x), which means “for all elements in the set, P(x) is true.” Here’s how we can use this to check that all numbers in a set are less than a given number:
AllLessThan(set, max) == A num in set: num < max
>> AllLessThan({1, 3}, 4)
TRUE
>> AllLessThan({1, 3}, 2)
FALSE
>> AllLessThan({1, 3}, "FOO")
[Error]
E means “there exists some element in the set.” It’s used in the form E x in set: P(x), which means “there is at least one element in the set where P(x) is true.” As an example, here’s how to check that a given sequence has at least one element in a given set:
SeqOverlapsSet(seq, set) == E x in 1..Len(seq): seq[x] in set
>> SeqOverlapsSet(<<1, 3>>, {2, 3, 4})
TRUE
Note
If the set is empty, E will be false and A will be true, regardless of your expression.
We can write both ~E for “there is no element in the set” and ~A for “not all elements in the set.” A and E are called quantifiers.
There’s some additional syntactic sugar for defining quantifiers over multiple values. As an example, a “commutative” operator is one where the order of the arguments doesn’t matter. If we want to check if an operator is commutative over a set, we need to test that for every pair of values in the set, calling that operator gives the same value if you switch the order of the inputs. This means quantifying over two values, not one. There are several different ways we express that:
* We can pull multiple elements from the set
IsCommutativeOver(Op(_, _), S) ==
A x, y in S: Op(x, y) = Op(y, x)
* We can have sequential clauses to the quantifier
IsCommutativeOver(Op(_, _), S) ==
A x in S, y in S: Op(x, y) = Op(y, x)
* We can "unpack" a tuple
IsCommutativeOver(Op(_, _), S) ==
A <<x, y>> in S X S: Op(x, y) = Op(y, x)
>> IsCommutativeOver(LAMBDA x, y: x + y, 1..10)
TRUE
>> IsCommutativeOver(LAMBDA x, y: x - y, 1..10)
FALSE
=> and <=>
P => Q means that if P is true, then Q is true. This does not go both ways. In other words, it’s equivalent to writing ~P / Q. Usually you use it when you only want to check for something being true when the preconditions are satisfied.
P <=> Q means that either P and Q are both true or P and Q are both false. It can be used to check if two Boolean expressions are equivalent.
Xor(A, B) == (~A / B) / (A / ~B)
OtherXor(A, B) == ~A <=> B
>> A A in BOOLEAN, B in BOOLEAN: Xor(A, B) = OtherXor(A, B)
TRUE
Recall here that BOOLEAN = {TRUE, FALSE}.
There’s a bit of a land mine here: both of these operators follow the conjunction rules for significant whitespace. If I write
/ P
/ Q
=> R
TLC will interpret it as (P / Q) => R, while if I write
/ P
/ Q
=> R
TLC will interpret it as P / (Q => R).
Expressions
We’ve been implicitly using a lot of expressions. Let’s make them more powerful. All of these keywords can be used as part of any expression. This means that when assigning a variable in a PlusCal algorithm, you’re free to use a LET statement that’s inside an IF that’s inside another LET.
LET-IN
Any expression can use LET-IN to add local operators and definitions to just that expression alone.
RotateRight(seq) ==
LET
last == seq[Len(seq)]
first == SubSeq(seq, 1, Len(seq) - 1)
IN <<last>> o first
>> RotateRight(<<1, 2, 3>>)
<<3, 1, 2>>
IF-THEN-ELSE
IF Condition THEN Exp1 ELSE Exp2. Unlike most programming languages, all if-statements must include an ELSE.
Max(x, y) == IF x > y THEN x ELSE y
>> <<Max(2, 3), Max(3, 2)>>
<<3, 3>>
IF THEN or if then?
What’s the difference between the TLA+ conditional and the PlusCal conditional? IF THEN is an expression, so we could do x := IF P THEN x + 1 ELSE x - 1. But we couldn’t do IF P THEN x := x + 1 ELSE x := x - 1. The PlusCal version is exclusively for control flow, so it can do the latter (but not the former).
CASE
A case statement. Subsequent cases are marked by a [].
CASE x = 1 -> TRUE
[] x = 2 -> TRUE
[] x = 3 -> 7
[] OTHER -> FALSE
OTHER is the default. If none of the cases match and there is no default, TLC considers that an error. If more than one case statement matches, the behavior is undefined. Under the current implementation of TLC, it will select the first matching statement, but don’t count on it and make sure your statements are mutually exclusive.
CHOOSE
CHOOSE x in S : P(x) is “select an x such that P(x) is true.” If more than one x matches, TLC will select an arbitrary one (implementation-wise, the first such x it found). If no x matches, TLC will raise an error.
IndexOf(seq, elem) ==
CHOOSE i in 1..Len(seq): seq[i] = elem
>> IndexOf(<<8, 3, 1>>, 3)
2
>> IndexOf(<<8, 3, 1>>, 4)
Attempted to compute the value of an expression of form
CHOOSE x in S: P, but no element of S satisfied P.
CHOOSE becomes exceptionally powerful when combined with our logical operators. The canonical way to express Max is this:
Max(set) == CHOOSE x in set: A y in set: x >= y
>> Max(1..10)
10
In most languages we’d have to either use a loop or a recursive function to compute the max (or use a language primitive). In TLA+, we simply say “CHOOSE an element of the set that’s bigger than the rest of them.” That’s it.
A more complicated example: what values for x and y satisfy the two equations 2x + y = − 2 and 3x − 2y = 11? We don’t need to come up with an algorithm to solve algebraic equations, as we can use CHOOSE:
>> CHOOSE <<x, y>> in (-10..10) X (-10..10):
>> / 2*x + y = -2
>> / 3*x - 2*y = 11
<<1, -4>>
Functions
The last complex data type in TLA+ is the function. A function maps a set of inputs (its domain) to a set of outputs. The mapping can either be set manually or via an expression. All functions have the form [x in set |-> P(x)]. A function that maps every element in a set of numbers to its double might be written as [x in numbers |-> x * 2]. You can also use multiple elements in a function: [x, y in set |-> P(x, y)] and [x in set1, y in set2 |-> Q(x,y)] are both valid syntax.
To call a function, you write f[bar], just as you would with tuples or structs. In fact, tuples and structures are actually just special cases of functions. Tuples are functions where the domain is 1..n, and structs are functions where the domain is a set of strings.
>> [x in 1..2 |-> x*2]
<<2, 4>>
>> Head([x in 1..2 |-> x*2])
2
Tip
If f has two values, you can call it with both f[a, b] and f[<<a, b>>].
This goes the other way too: just as we can assign sequences and structures to PlusCal variables, we can also assign functions. This means we can use them to represent data structures like counters, flags, etc.
Flags == {"f1", "f2"}
(*--algorithm flags
variables
flags = [f in Flags |-> FALSE];
begin
with f in Flags do
flags[f] := TRUE;
end with;
end algorithm; *)
This has five states, three of which are distinct. On execution, TLC will set one of the flags to true while leaving the other false.
Functions and Operators
You can make a function as an operator. If the operator doesn’t take any arguments, the following two are valid syntax:
Op == [x in S |-> P(x)]
Op[x in S] == P(x)
If an operator defines a function based on arguments to the operator, though, you need to use the first syntax.
MapToSomeNumber(set, num) == [x in set |-> num]
Operators and functions have some key differences. Operators can work on arbitrary inputs, while functions must have a specified domain. Functions can be created by operators and passed around, and they have no restrictions on recursion or higher-order operators.
SumUpTo(n) ==
LET F[m in 0..n] ==
IF m = 0 THEN 0
ELSE m + F[m-1]
IN F[n]
>> SumUpTo(10)
55
In PT helper library, we also have ReduceSet, which you can use to make an operator recursive over a set. This “hides” the internal use of a function. Look at how it’s implemented, but don’t worry too hard about completely understanding it; after all, that’s why we made a wrapper.
PT == INSTANCE PT
SumUpTo(n) ==
PT!ReduceSet(LAMBDA x, y: x + y, 0..n, 0)
>> SumUpTo(10)
55
Note
If you haven’t imported PT yet, do so now. We’ll be using it regularly from here on out. You can find the instructions at the end of the introduction.
There’s a few special operators we get for manipulating functions.
DOMAIN
DOMAIN is a special prefix operator that gives us the possible inputs to a function. If func == [x in set |-> ...], then DOMAIN func = set. Since sequences and structs are forms of functions, we can use DOMAIN on them, too. DOMAIN seq = 1..Len(seq). DOMAIN struct is the set of keys in the struct.
F[x in BOOLEAN] == x
G == <<6, 0, 9>>
H == [F |-> DOMAIN F, G |-> DOMAIN G]
>> H
[F |-> {FALSE, TRUE}, G |-> 1..3]
>> DOMAIN H
{"F", "G"}
@@
f @@ g merges two function. If some element x is in both domains, then we use f[x]. It’s identical to the following definition:
Merge(f, g) == [
x in (DOMAIN f) union (DOMAIN g) |->
IF x in DOMAIN f THEN f[x] ELSE g[x]
]
To use @@ we need EXTENDS TLC.
EXTENDS TLC
f[x in 1..2] == "a"
g[x in 2..3] == "b"
>> f @@ g
<<"a", "a", "b">>
>> g @@ f
<<"a", "b", "b">>
:>
To use :>, we need EXTENDS TLC. a :> b is the function [x in {a} |-> b].
>> (2 :> 3)[2]
3
>> ("a" :> "b").a
"b"
Sets of Functions
[set1 -> set2] is the set of all functions that map elements of set1 to elements of set2. We write->for this, not|->. |-> is for functions, not sets of functions. You will probably mess this up at least twice.
>> [s in {"a", "b"} |-> {1, 2}]
[a |-> {1, 2}, b |-> {1, 2}]
>> [{"a", "b"} -> {1, 2}]
{ [a |-> 1, b |-> 1],
[a |-> 1, b |-> 2],
[a |-> 2, b |-> 1],
[a |-> 2, b |-> 2] }
Sets of functions will be increasingly useful as we write more complex specs. As an immediate use, we can use it to make sets of sequences. In the recycler, we defined the list of items as item X item X item X item. What if we wanted to try with six items, or all possible lists up to some number? If we’re hand-coding it, it’s clumsy and difficult to change. And the “variable sequence” case is outright impossible. What we really want is some operator of form SeqOf(set, count) that can generate all of these for us.
Here’s where we can use the fact that sequences are just functions with a special domain. In fact, TLC will display functions with a domain 1..N as a sequence! [x in 1..3 |-> P(x)] is just the sequence <<P(1), P(2), P(3)>>. The set of functions [1..3 -> S], then, are all the sequences where the first value is some element in S, the second value is some element of S, and so on with the third. In other words, it’s S X S X S.
We can also use this to expand a spec’s initial state space. In the PlusCal example above, we started with all of the flags as false. What if we also wanted to spec the cases where some flags start out true? Using function sets, it’s a tiny change:
Flags == {"f1", "f2"}
(*--algorithm flags
variables
flags in [Flags -> BOOLEAN]
begin
* . . .
This now has 15 states. As with any set, we can map and filter on function sets. This is how we could restrict the spec to only initial states where at least one flag is true:
flags in {config in [Flags -> BOOLEAN]: E f in Flags: config[f]}
This passes with 12 states.
Let’s move on to a more involved example of functions.
Example
The Knapsack Problem is an optimization problem that’s known to be NP-complete. We can define it as: We have a knapsack of volume N and a set of items. Each item has a value and a size. You can fit any number of each item in the knapsack as long as the sum of them all is less than the capacity of the sack. What’s the most valuable knapsack you can make?
Actually solving this problem is uninteresting to us: that’s an algorithms question, not a specification one. Instead, we will show how we can formally define the most valuable knapsack with TLA+ operators. Instead of having an algorithm find it, we create an operator that simply is the answer.
First, let’s figure out what our inputs will be, first by hard-coding, then by generalizing. We define the possible items as a set of strings and the maximum capacity as a number.
EXTENDS TLC, Integers, Sequences
PT == INSTANCE PT
Capacity == 7
Items == {"a", "b", "c"}
If every item has a size and a value, we could represent that as a struct, say [size: 2..4, value: 0..5]. There are then two ways to represent the inputs to the problem. First, we can have a set of structures, each of which has an item, a value, and a size.
HardcodedItemSet == {
[item |-> "a", size |-> 1, value |-> 1],
[item |-> "b", size |-> 2, value |-> 3],
[item |-> "c", size |-> 3, value |-> 1]
}
This works but has a couple of problems. First of all, it’s hard to find the value for a given item. We’d have to write something like
ValueOf(item) == (CHOOSE struct in HardcodedItemSet: struct.item = item).value
>> ValueOf("a")
1
Worse, there’s nothing stopping us from having invalid data. What if I had two structs with the same item but different values? We’d have an invalid input to our problem, leading to nonsense results. A better idea is to define our input as a mapping of item names to their size and value:
HardcodedItemSet == [
a |-> [size |-> 1, value |-> 1],
b |-> [size |-> 2, value |-> 3],
c |-> [size |-> 3, value |-> 1]
]
Now ValueOf(item) is just HardcodedItemSet[item].value, and we guarantee that all items have distinct names. Much simpler. We can generalize the inputs first by creating a set of structures representing all values an item can have:
The keys are just the elements of the set Items, and the values are just elements of the set ItemParams. This represents all possible configurations of values for the items. But we’re hard-coding a, b, and c, so if we change Items then ItemSets won’t be accurate. We can fix this by using a function set:
ItemSets == [Items -> ItemParams]
Remember, that’s a ->, not a |->. Try evaluating ItemSets as a constant expression to see what it consists of. For any given problem, we’d be working on a single element of that set; call it ItemSet.
That gives us the possible inputs we care about. Next, we need a measure of what counts as a valid knapsack. We can represent a knapsack as a function in [Items -> Count], representing how many of each item the knapsack contains. For example, the knapsack [a |-> 1, b |-> 2, c |-> 0] contains a single a, two b’s, and no c’s.
We’ll arbitrarily cap the maximum number of each item at 4 for the sake of explanation and for model-checking purposes. Then the set of all knapsacks would be [Items -> 0..4].
But not all of these will be valid. Remember, the sum of the sizes of all of the items must be less than the capacity. For a given knapsack, the total size for a given item is ItemSet[item].size * knapsack[item]. We need to sum the sizes for all items in the knapsack, which we can do with PT!ReduceSet.
KnapsackSize(sack, itemset) ==
LET size_for(item) == itemset[item].size * sack[item]
IN PT!ReduceSet(LAMBDA item, acc: size_for(item) + acc, Items, 0)
ValidKnapsacks(itemset) ==
{sack in [Items -> 0..4]: KnapsackSize(sack, itemset) <= Capacity}
With this, we can define the “best” valid knapsack: it’s the one with the highest possible value. We calculate value in the exact same way we calculate size.
* A minor amount of duplicate code
KnapsackValue(sack, itemset) ==
LET value_for(item) == itemset[item].value * sack[item]
IN PT!ReduceSet(LAMBDA item, acc: value_for(item) + acc, Items, 0)
>> KnapsackValue([a |-> 1, b |-> 3, c |-> 0], HardcodedItemSet)
10
Looks good. But we should test that this works for all possible item sets.
>> {BestKnapsack(itemset) : itemset in ItemSets}
Attempted to compute the value of an expression of form
CHOOSE x in S: P, but no element of S satisfied P.
Why does nothing satisfy it? In this case, we don’t have any information on which ItemSet caused the problem. For debugging purposes, let’s make this a PlusCal algorithm, so we get a trace.
(*--algorithm debug
variables itemset in ItemSets
begin
assert BestKnapsack(itemset) in ValidKnapsacks(itemset);
end algorithm; *)
Since we’re adding a PlusCal spec, remember to remove “evaluate constant expression” and set “What is the behavior spec?” to “Temporal formula.” When you run this, you should get something like what is shown in Figure 3-3.
Figure 3-3
The error
If none of the items have any value, then all knapsacks have the same value and there is no knapsack with a value greater than all the others.
We could change our operator to use >=, but that’s not actually what we want! Remember, if multiple elements satisfy a CHOOSE, it picks an arbitrary one. Then we’re saying that two knapsacks have the exact same value, and one is arbitrarily “better” than the other. So that’s wrong. Alternatively, we could add a “tie breaker,” such as the fewest items. But that doesn’t work here (all of the items have the same size and value) and regardless we’re now modifying the core definition to fit our operator. The definition doesn’t have a tie breaker, so we should not add one.
The best path, then, is to just return all the different best knapsacks as opposed to just an arbitrary one. We can do this in two ways:
1.
Choose the subset of valid knapsacks that are higher than everything outside of that set. This most closely matches the defintion of “best knapsacks.”
Pick a best knapsack arbitrarily, calculate its value, and filter for all the other knapsacks that match it. This is more understandable and faster, too.
{k in all: value_of_best = KnapsackValue(k, itemset)}
I’d prefer we use the simpler one, but as a sanity check, let’s make sure it matches the former for all possible itemsets.
Capacity == 4 * To reduce the state space for faster testing
>> A is in ItemSets: BestKnapsacksTwo(is) = BestKnapsacksOne(is)
FALSE
Hm, that’s surprising. Try writing the following to see the difference.
LET is == CHOOSE is in ItemSets:
BestKnapsacksTwo(is) /= BestKnapsacksOne(is)
IN <<is, BestKnapsacksOne(is), BestKnapsacksTwo(is)>>
If you evaluate it, you’ll see that BestKnapsacksOne will set the empty set as all_the_best, and A x in S is trivially true. We need to also qualify that there is at least some element in all_the_best. We do this by changing A good to E good:
Now the two are equivalent. Just to be thorough, I ran both of them individually and confirmed that BestKnapsacksTwo was indeed faster for a capacity of 7. Finally, just as a means of cleaning things up, let’s remove all of the KnapsackValue calls with an inline operator.
BestKnapsacks(itemset) ==
LET
value(sack) == KnapsackValue(sack, itemset)
all == ValidKnapsacks(itemset)
best == CHOOSE best in all:
A worse in all {best}:
value(best) >= value(worse)
IN
{k in all: value(best) = value(k)}
Summary
We learned how to use operators, expressions, and functions to write complex operators. We then used it to take a complex definition – a collection of values maximizing a constraint problem, and solve it solely through the definition.
One problem with our knapsack specification, though, is that we’ve hard-coded all of the integer values. It would be better if, instead of forcing Capacity == 7 and the range of item sizes as 2..4, we could specify them as configurable numbers and ranges and only define them when it’s time for the model checking. We’ve also been using PT == INSTANCE PT often enough that we should finally learn what that actually means. Finally, our specs are beginning to get a little slow, and it would be nice to more easily run and debug them.
In the next chapter, we will cover all of these in model constants and module organization.
