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

  1. initial state satisfies
  2. 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 Naturals by using EXTENDS 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 hr declares hr to be a variable
  • The operator .. is defined in Naturals. In general i .. j is the set of integers from i through j, for any integers i and j.
  • The line -------------------- can appear anywhere in the spec, it is purely cosmetic.
  • The THEOREM asserts that the formula follows logically from the definitions in this module, the definition in the Naturals module, and the rules of TLA+.
  • 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.