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
Constants can be used anywhere you’d use any other value. As you’d expect from the name, they cannot be modified.
In this text we will specify assignment to constants with C <- val.
Ordinary Assignment
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
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
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
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.
- 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.
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?
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
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
Permutations and SortSeq
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.
- 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.
We can add a universal library path under Preferences > TLA+ Preferences, as we did in the introduction to the book.
- 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
INSTANCE
- 1.
You cannot import multiple modules in the same statement.
- 2.
Like operators, you can prefix an instance with LOCAL to make it private to the module.
- 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.
You can import parameterized modules, or modules with constants defined at import time.
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.