Behaviours
A behaviour is formally defined as a sequence of states, where a state is an assignment of values to variables.
We specify a system by specifying a set of possible behaviours — the ones representing the correct execution of the system.
An Hour Clock
We’ll start with a very trivial system — a digital clock that displays only the hour. Thus, it is a number that cycles from 1 through 12. Let the variable represent the clock’s display.
A typical behaviour of the clock is the sequence of states.
A pair of successive states, such as is called a step.
To specify the hour clock, we describe all its possible behaviours:
- an initial predicate that specifies the possible initial values of
- next-state relation that specifies how the value of can change in any step
The intial predicate can be written informally as The next-state relation as An action is a formula that contains primed as well as unprimed variables. E.g. . Unprimed variables respresent value in the old state and primed variables represent value in the new state.
We want our specification to be a single formula, not a pair of formulas. The formula must assert about a behaviour that
- initial state satisfies
- each of its step satisifed
To specify the second condition, we use temporal-logic operator (pronounced box). The formula asserts that the formula is always true.
So, seems to be the specification we’re looking for. However, it doesn’t make sense when we try to relate the clock to another system. Consider combining the variable with a variable which describes temperature at a particular time. For the same we could have an action where changes. This could an hour clock in a weather station.
The step where remains the same are not allowed by . So our spec doesn’t define the hour clock in weather station.
This suggests we adopt as the specification. In TLA, we let stand for , so we can write the formula more compactly as . The formula does allow stuttering steps.
Now, we use this as our specification (liveness of the system covered later)
The Specification in TLA
------------------------MODULE HourClock-----------------------------
EXTENDS Naturals
VARIABLE hr
HCini == hr \in (1 .. 12)
HCnxt == hr' = IF hr # 12 THEN hr + 1 ELSE 1
HC == HCinit /\ [][HCnxt]_hr
---------------------------------------------------------------------
THEOREM HC => []HCini
=====================================================================
Some points about the spec:
- Begins a module named
HourClock- TLA+ specs are partitioned into modules; the hour clock’s spec consists of this one module
- Arithmetic operators like are not built into TLA+, but are themselves defined in modules (might want to use matrix instead of numbers). The definitions are incorporated from the module
Naturalsby usingEXTENDS Naturals - Every symbol that appears in a formula must either be a built-in operator of TLA+, or else it must be defined or declared
VARIABLE hrdeclareshrto be a variable
- The operator
..is defined inNaturals. In generali .. jis the set of integers fromithroughj, for any integersiandj. - The line
--------------------can appear anywhere in the spec, it is purely cosmetic. - The
THEOREMasserts that the formula follows logically from the definitions in this module, the definition in theNaturalsmodule, and the rules ofTLA+. - Module is terminated by
===========================.
To specify that HC is the specification, we’ll need another file for the configuration. TLA+ is a language for writing mathematical definitions and does not consider that to be in its scope.