CSE503: Software Engineering
Lecture 14 (February 5, 1999)

David Notkin

v The Hoare-style proofs of correctness and the Z specification approach are not appropriate for many classes of software specification

v In many situations, for instance, the key issue is the order in which operations are applied, as opposed to the details of the behavior of any given operation

v These situations generally arise in the context of reactive systems, in which external events (stimuli) occur, causing the system to perform some actions, with the system then (optionally) generating some external events (responses, which might, for instance, cause some behavior external to the software system itself)

Ø Examples include:

§ The software controller for a cruise control system on a car

§ Most avionics systems

§ In other words, essentially all embedded systems software is like this

v In these systems, the crucial questions tend to be different from those in conventional imperative or ADT-based systems (although those may arise, too)

v Therefore, the specification methods (and supporting verification and validation techniques) tend to differ

Ø Consider this room's touch panel

§ There are lots of questions that the specification could/should address

· The obvious are, "What happens when I press button x?"

§ There are many more complicated questions, too (and this isn't an especially complicated system)

· What happens on intentional reinitialization? On unintentional reinitialization (after a power outage, for instance)?

· Can I perform one action (say, sending one screen up) while another action is already being performed (say, sending the other screen down)?

¨ If the answer is "no", does the second action get ignored or does it simply get delayed?

· There are videotape controls on both the physical VCR and on the touch screen: how do they interact?

· Others?

Ø As users of an established system, we can often answer these questions by trying things

§ However, this doesn't support getting the system built to a given specification

v A classic way to capture these kinds of decisions in a specification is to use a state-based description

Ø You've seen state machines in a zillion situations before (the closest to software per se was probably in capturing lexical patterns for a compiler)

Ø Have the group collectively sketch some pieces of the touch panel's state machine

v We notice a few things from this sketch

Ø One, we have to handle concurrency in some way

§ One way to do this is implicitly by expanding the state machine to handle all interleavings; this leads to a state explosion for even quite simple examples

§ Another way is to use variants of state machines that capture the notion of concurrency explicitly

· Petri nets are a classic example of this, as are concurrent finite-state machines, and others (a very simple Petri net is shown at the end of these notes)

Ø A related problem is that we would have to interleave some aspects that are largely independent

§ The clock on the touch panel is essentially independent of all other functions (as far as I can tell)

· But it is not unrelated to startup and shutdown activities

§ In a classic state machine, one might have to relate these independent activities

Ø A final problem, not fully obvious, is that the size of the state machine description can get very, very large, very very quickly.

v David Harel developed statecharts as a notation to reduce these problems

Ø Statecharts is a visual notation, which Harel characterizes as a visual formalism

§ He observes that one needn't write down character-based symbols to have a formal language, and that graphical notations have a number of significant benefits in some domains (like state machine description languages)

Ø Statecharts have been captured in an environment, the original was called STATEMATE

§ A company, i-Logix, http://www.ilogix.com/, has commercialized the environments, etc.

Ø Statecharts is also the underlying basis for the state-based aspects of UML

§ From a UML page: "A statechart diagram shows the sequences of states that an object or an interaction goes through during its life in response to received stimuli, together with its responses and actions."

v The central notion in statecharts is the addition of parallelism and hierarchy to state machine descriptions

Ø For example, for the touch panel, the state machine for the clock could be written as a parallel state machine to (say) the screen handler

§ Shared events, such as "shutdown", could cause exits from both the clock and the screen handler states to another state, "shutdown"

· This retains the independence of the two parallel states

· Statecharts also provides a notation by which the substates for a state can (for example) share an exit event without writing it explicitly for every substate

Ø There are other notational conveniences, such as history states, etc.

Ø Theoretically, there is no difference between what statecharts can represent and what conventional finite state machines can represent

§ But the size of the descriptions are, in general, much smaller using statecharts; this is, of course, crucial for the communication aspects of specifications

Ø One minor but key point is that there are many different possible semantics of statecharts

§ When are external events processed? If one accepts a single external event and then processes all transitions until a stable state is reached, before accepting the next external event, then this assumes the synchrony hypothesis

§ How are multiple pending events handled?

v Transitions in statecharts (and many notations) can be annotated with conditions under which the transition should be taken

v The classic version of this is to directly annotated the arcs representing the transitions

Ø A common example of conditional transition says, "Only consider taking this transition if event E holds. If it does, then only take the transition if the associated condition holds (for instance, if another part of the machine is in a specified (sub)state).

Ø In some cases, the conditions are very large, making this style of annotation quite unwieldy.

v A variant of statecharts, RSML, handles conditions differently, extracting them into a separate and-or table

Ø I'll pass a big example from RSML around (the TCAS-II spec, an earlyish version)

Ø RSML has some other variations on statecharts, for instance bus-style communication

Ø RSML assumes the synchrony hypothesis, while statecharts (STATEMATE version) permits it

v There are basically two ways to validate state-based specifications: simulation and analysis

Ø On Monday, William will talk about one style of analysis, applying model checking to such specifications