STATECHARTS: A VISUAL FORMALISM FOR COMPLEX SYSTEMS
📜 Abstract
We present a broad extension of the conventional formalism of state machines and state diagrams, that is relevant to the specification and design of complex discrete-event systems, such as multi-computer real-time systems, communication protocols and digital control units. Our diagrams, which we call statecharts, extend conventional state-transition diagrams with essentially three elements, dealing, respectively, with the notions of hierarchy, concurrency and communication. These transform the language of state diagrams into a highly structured and economical description language. Statecharts are thus compact and expressive—small diagrams can express complex behavior—as well as compositional and modular. When coupled with the capabilities of computerized graphics, statecharts enable viewing the description at different levels of detail, and make even very large specifications manageable and comprehensible. In fact, we intend to demonstrate here that statecharts counter many of the objections raised against conventional state diagrams, and thus appear to render specification by diagrams an attractive and plausible approach. Statecharts can be used either as a stand-alone behavioral description or as part of a more general design methodology that deals also with the system’s other aspects, such as functional decomposition and data-flow specification. We also discuss some practical experience that was gained over the last three years in applying the statechart formalism to the specification of a particularly complex system.
✨ Summary
Overview
David Harel introduces statecharts as a structured extension of conventional state-transition diagrams for specifying complex reactive and discrete-event systems. The formalism addresses the state-space explosion and poor modularity of flat state machines by combining hierarchical state decomposition, orthogonal components for concurrency, broadcast communication, default and history entries, and transitions that may operate across abstraction levels. The paper develops these ideas through a detailed wristwatch example and discusses actions, activities, timeouts, selection and conditional entrances, parameterized states, overlapping states, temporal-logic integration, recursion, and probabilistic extensions.
The paper also identifies formal-semantic challenges created by simultaneous events, internally generated events, broadcast chain reactions, history, and interactions among hierarchical and concurrent components. It sketches an operational approach based on configurations and successive-event processing, while noting that several advanced features required further formal development. Practical experience applying statecharts to an avionics system is reported, along with the design of graphical tooling for editing, simulation, consistency checking, and verification.
Influence
The paper became a foundational reference for hierarchical and concurrent state-machine modeling. Its most direct industrial influence is the incorporation of a related state-machine formalism into UML: the OMG UML specification explicitly describes UML state machines as an object-based variant of Harel statecharts. (omg.org) UML state-machine concepts subsequently became part of systems-modeling practice, including SysML, whose behavioral diagrams include state-machine diagrams for representing state transitions and actions in response to events. (omg.org) Later research continued to address the formal semantics, verification, tooling, and extensions of statecharts and UML state machines, including work on operational semantics and automated verification. (lics.siglog.org) The article was published in Science of Computer Programming, volume 8, issue 3, pages 231–274, in June 1987. (sciencedirect.com)