© Hillel Wayne 2018
Hillel WaynePractical TLA+https://doi.org/10.1007/978-1-4842-3829-5_4

4. Constants, Models, and Imports

Hillel Wayne1 
(1)
Chicago, Illinois, USA
 

In the past few chapters we covered how to write complex specifications. However, our models are fairly rigid. Our knapsack spec from the last chapter had a set of hard-coded values: total capacity of the knapsack, range of values for the items, etc. In this chapter we will use the TLC configuration to simplify and generalize our model, as well as add modularity and better debugging.

Constants

What if we want to change the parameters of a specification on the fly? For example, we might want to first test our spec over a small state space to weed out the obvious errors, and then test it over a large state space to find the subtle ones. We do this by adding Constants , which are values that are defined in the model instead of the specification. We add a constant as follows:
EXTENDS Integers, TLC
CONSTANTS Capacity, Items, SizeRange, ValueRange
* We could also do CONSTANTS Op(_, _...)

Constants can be used anywhere you’d use any other value. As you’d expect from the name, they cannot be modified.

For any given model, we assign values to the constants in the “Model Overview" Page, in the “What Is the Model?” section. You must have specified it in the spec with CONSTANTS ConstantName before it will show up. For constant operators, our only option is to define the operator. For constant values, we have three options (Figure 4-1).
../images/462201_1_En_4_Chapter/462201_1_En_4_Fig1_HTML.jpg
Figure 4-1

Declared constants. Names will only show up if you’ve defined them as CONSTANT.

In this text we will specify assignment to constants with C <- val.

Ordinary Assignment

We can set the constant to any other TLA+ value: numbers, sets, sequences, functions, etc.
Capacity <- 7
ValueRange <- 0..3
SizeRange <- 1..4
Items <- {"a", "b", "c"}

Try running the model with these values and then exploring different possible values. Do any cause problems for our definition of BestKnapsacks?

Model Values

If you assign a model value to a constant, that constant becomes a new type that’s only equal to itself. If M and N are both model values, M /= N.

We’ll be using them a lot to add “convenience” values, like NULL. That’s because comparing values of different types is considered a spec failure. You cannot have the set {TRUE, FALSE, "null"}, but you can have the set {TRUE, FALSE, NULL} if NULL is a model value.

Sets of Model Values

You can also define a whole set of model values. This has to be added as a “Set of model values,” not an “ordinary assignment.” When using constants, sets of model values are often preferable to sets of strings.
Items <- [ model value ] {i1, i2, i3}
The main advantage is this opens up symmetry sets for us. Let’s add back our debugging algorithm from the last chapter. We need to update it to use BestKnapsacks, as we discovered BestKnapsack is inappropriate to the problem. Since BestKnapsacks is a set, we use subseteq instead of in.
(*--algorithm debug
variables itemset in ItemSets
begin
  assert BestKnapsacks(itemset) subseteq ValidKnapsacks(itemset);
end algorithm; *)
If you translate this and run the model, you should see that TLC checked about 12,000 total states, of which 8,000 were distinct. However, most of those states are just extra work for us. In a given run, we’ll get the same results if we replace all instances of i1 with i2, i2 with i3, and i3 with i1. That means the set is symmetric. We can tell TLC this by checking the “symmetry set” option on the constants popup. TLC can use this information to skip checking redundant states, which leads to a shorter run.
Items <- [ model value ] <symmetrical> {i1, i2, i3}

Rerun the model. You should see that TLC checked only about 6,000 states, with just 1,600 or so distinct. With symmetry sets we only needed to find half of the states and only evaluate a quarter of them. Symmetry sets won’t always be more efficient, and we have to be sure that it’s a safe optimization to make. In general, it is safe. I will be very explicit in the situations here where it’s unsafe.

ASSUME

If we’re assigning constants at the model level, we should have a way of making sure that you’ve got the right type of values. If you’re using Values in your spec as a set of numbers, you don’t want someone assigning it a sequence of strings. ASSUME is an expression about your constants that, if false, prevents the spec from running.
CONSTANTS Capacity, Items, SizeRange, ValueRange
ASSUME SizeRange subseteq 1..Capacity
ASSUME Capacity > 0
ASSUME A v in ValueRange: v >= 0
ItemParams == [size: SizeRange, value: ValueRange]
ItemSets == [Items -> ItemParams]

Try passing in a size that should be impossible, SizeRange <- 0..4. You should see that the spec will immediately error with “Assumption is false.”

ASSUME may use constants and constant operators as part of the expression but may not use operators not defined as CONSTANT.

Infinite Sets

Everything we’ve done so far has been in terms of finite sets. In 99% of the cases you work with, you want finite sets. However, TLA+ also has the capacity to specify certain kinds of infinite sets. It cannot select elements from the set nor assign them as part of variables, but it can test membership . If we EXTEND Integers, we get the infinite set Int. We could also EXTEND Naturals to get the set Nat == {0, 1, 2, ...}. This means we could write our assumptions as:
ASSUME SizeRange subseteq 1..Capacity
ASSUME Capacity in Nat {0}
ASSUME ValueRange subseteq Nat

This makes the types explicit, as opposed to implicit. Which one you do is personal preference.

TLC Runtime

Configuration

We won’t cover everything on each page, because some of it is for niche purposes and some of it is out of scope. You can see what everything does under the “Help > Table of Contents.” Here are the important things (Figure 4-2).

  • What Is the Behavior Spec : We almost always want “Temporal Formula” selected. Sometimes, if PlusCal fails to compile, it automatically changes to “No Behavior Spec.” We use “No Behavior Spec” to test expressions without running anything.

  • What to Check : Deadlock will be relevant in the next chapter, when we learn about concurrency. Invariants are where we place safety invariants – pretty much everything we’ve tested so far. Properties is where we place liveness properties – we’ll cover that in Chapter 6.
    ../images/462201_1_En_4_Chapter/462201_1_En_4_Fig2_HTML.jpg
    Figure 4-2

    Model Overview

  • How to Run: Here’s where we do runtime optimizations to make TLC faster. We will not be using it in this book, but you can learn more about them in the Toolbox help. See Figure 4-3.
    ../images/462201_1_En_4_Chapter/462201_1_En_4_Fig3_HTML.jpg
    Figure 4-3

    Advanced Options

  • Additional Definitions : We can add extra operators here to use with state constraints and defining constants. For example, we could define the operator F(x) == x*2 and then, for some constant C, make the ordinary assignment C <- F(1). It can come in handy if we need to do complex setups for our constants.

  • State Constraint : An expression that will hold true for all states in our model. Unlike invariants, state constraint violations do not fail the model. Rather TLC will drop that state from the search. It will not check any invariants on that state, and it will not determine any future states from it. We can use this to prune the exploration space and finish model checking faster, at the cost of potentially missing invariance violations. We can also use this to turn an unbounded model into a bounded one.

    Action Constraint does something similar but is out of scope for us.

  • Definition Override : This lets you replace any definition with a custom one. For example, you could override +(x, y) <- 3 if you wanted to mess with your friends.

WHY OVERRIDE?

The main use of overrides is for people who want their spec to represent an infinite range of possibilities. If I write
with x in ValueRange do
  skip;
end with;
and then define the constant ValueRange <- 1..10, a reader might not be sure whether my spec is “supposed to” work with arbitrary numbers or a bounded ValueRange. So some people prefer to write
with x in Int do
  skip;
end with;

and then add the override Int <- 1..10. We are not going to follow this practice in this book, though.

  • TLC Options : The interesting ones are the modes. By default we are in Model-checking mode using a breadth-first search. We can change it to depth-first. This can be useful if your specification isn’t finite, such as if it has a constantly incrementing counter. However, even many infinite specs can be model checked by TLC, and often your best choice is to use a state constraint instead. Simulation Mode will replace the methodical search with random traces. This is generally less effective but can sometimes be useful if you’ve validated the specification over a small state space and now want to stress test it with a very large state space.

Error Traces

You’ve seen and learned how to interpret error traces already. Now we’ll cover a new use: the Error-Trace Exploration. You’ll find it collapsed between the error output and the error trace. Here’s where you can inject arbitrary expressions into your trace and evaluate it for debugging. If you add an expression, you should see that evaluated for every step of the error trace. Click “Restore” to remove the expression.

There’s one additional and extremely powerful thing you can do with the error trace. Every expression uses the values it has at the beginning of the step. By adding a ' (single quote), we can instead ask it to evaluate what it is at the end of the step. This is called a primed value. If I write Op(x', y), it will evaluate what Op is after x changes in that step. This also works on operators, too: If I write Op(x, y)', it will evaluate what Op’s output changed to. We cover more on the theory of primed values in Appendix C.

Warning

You can’t nest two primed operators. SumItemsOver(knapsack', "value")' is an error.

The TLC Module

In addition to @@ and :>, TLC provides us with several utility operators. What makes them special is that they have overridden implementations distinct from their formal definitions. They are used for debugging.

Print and PrintT

Print(val, out) prints val and out to User Output and then evaluates to out (Figure 4-4).
../images/462201_1_En_4_Chapter/462201_1_En_4_Fig4_HTML.jpg
Figure 4-4

Print

PrintT(val) is equivalent to writing Print(val, TRUE). To help with logging, TLC also provides JavaTime, which evaluates to the current epoch time.

Assert

Assert(val, out) is TRUE if val is TRUE. If val is false, the spec fails with output out. The PlusCal keyword assert is defined in terms of Assert.
>> Assert(3 < 5, "3 is more than 5")
TRUE
>> Assert(3 > 5, "3 is more than 5")
The first argument of Assert evaluated to FALSE; the second argument was:
"3 is more than 5"
If you want to add detailed information in assertion, a fast way to do that is with a tuple or a struct:
>> LET x == 3 y == 5 IN Assert(x > y, <<x, " is more than ", y>>)
The first argument of Assert evaluated to FALSE; the second argument was:
<<3, " is more than ", 5>>
If you want something more polished, you can use the TLC helper ToString(_):
>> LET x == 3 y == 5 IN Assert(x > y, ToString(x) o " is more than " o ToString(y))
The first argument of Assert evaluated to FALSE; the second argument was:
"3 is more than 5"

Permutations and SortSeq

Permutations(set) is the set of all possible ways to order the set set. SortSeq(seq, Op(_, _)), unsurprisingly, sorts a sequence based on Op.
>> Permutations({1, 2, 3})
{ <<1, 2, 3>>, <<1, 3, 2>>, <<2, 1, 3>>, <<2, 3, 1>>, <<3, 1, 2>>, <<3, 2, 1>> }
>> SortSeq(<<1, 2, 3>>, LAMBDA x, y: x > y)
<<3, 2, 1>
Among other things, we can use this to force an arbitrary ordering on a set.
>> CHOOSE seq in Permutations({1, 2, 3}): TRUE
<<1, 2, 3>>

Imports

A specification can have multiple modules. The first module you create is the main module and the only one that is run. Other modules can provide new operators, values, and data structures to the specification.

You can create a new module in your spec by going to File > Open Module > Add TLA+ Module. You can also include any modules in your spec that are in your library path by default.

The new module should not contain any PlusCal; it is for operators only. It may, however, have constants, which we then define on import.

There are two ways to import modules: EXTENDS and INSTANCE. The former can list multiple modules at once, while the latter only imports one at a time. Neither will import operators or instances prepended with LOCAL.

The Toolbox needs to know about the module before you can import it. It discovers modules in one of three ways:
  1. 1.

    The Toolbox automatically knows about all modules in the same folder as the rest of your spec, and you can import them by default.

     
  2. 2.

    We can add a universal library path under Preferences > TLA+ Preferences, as we did in the introduction to the book.

     
  3. 3.

    We can add an additional library path local to your project by right-clicking on the project in the left-hand Spec Explorer and selecting Preferences.

     

EXTENDS

EXTENDS dumps the module into the same namespace. The module may not have any constants. That’s what we’ve been doing for the standard TLA+ libraries, like TLC and Sequences. You may not have more than one EXTENDS statement in your spec. So this is okay:
EXTENDS TLC, Integers
While this is not:
EXTENDS TLC
EXTENDS Integers

INSTANCE

INSTANCE works like EXTENDS, with four differences:
  1. 1.

    You cannot import multiple modules in the same statement.

     
  2. 2.

    Like operators, you can prefix an instance with LOCAL to make it private to the module.

     
  3. 3.

    You can namespace modules. We do this by assigning to an operator, as we do with PT == INSTANCE PT. Then an operator in PT would be called with PT!Op.

     
  4. 4.

    You can import parameterized modules, or modules with constants defined at import time.

     
It’s best to illustrate parameterization with an example.
---- module Point ----
LOCAL INSTANCE Integers
CONSTANTS X, Y
ASSUME X in Int
ASSUME Y in Int
Point == <<X, Y>>
Add(x, y) == <<X + x, Y + y>>
====
Since Point has constants, we have to define them on import. The syntax for this is INSTANCE Module WITH Constant1 <- Val1, Constant2 <- Val2, etc.
INSTANCE Point WITH X <- 1, Y <- 2
This puts Add and Point in our module namespace , but using the values for X and Y.
>> Point
<<1, 2>>
>> Add(3, 4)
<<4, 6>>
Alternatively, we can assign the instance to an operator, which acts as a namespace. This behaves the same way, but places all of the instantiated operators under said namespace.
P1 == INSTANCE Point WITH X <- 1, Y <- 2
P2 == INSTANCE Point WITH X <- 2, Y <- 1
>> P1!Point
<<1, 2>>
>> P2!Point
<<2, 1>>
Finally, we can do a partial assignment to a namespace. If we do this, we define the remaining constant(s) at the exact point we call the operator.
P1(Y) == INSTANCE Point WITH X <- 1
P2(X) == INSTANCE Point WITH Y <- 1
P3(X, Y) == INSTANCE Point
>> P1(3)!Point
<<1, 3>>
>> P2(3)!Add(1, 1)
<<4, 2>>
>> P3(1, 2)!Add(2, 3)
<<3, 5>>
If you define a constant in an module you later instantiate, and you don’t assign a specific value to the constant, it will default to any other operator or constant with the same name in the instantiating module. In other words, we could also import Point like this:
X == 1
Y == 2
P == INSTANCE Point

We did not define P using WITH, so it defaults in this case to Point WITH X <- X, Y <- Y.

Summary

In this chapter we learned how to use constants to create distinct models for the same spec. We also covered making reusable libraries for our specs and simplifying them with module parameterization. With this we are able to clean up our Knapsack operator and check it over different state spaces.

We can only go so far, though, with just single-process algorithms. For many problems, we’re dealing with multiple processes all acting simultaneously, where the order they run is nondeterministic. In the next chapter, we will learn how to write concurrent specifications and learn just why formal methods are so vital to safe concurrency.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.188.37.136