Wie häufig in der Informatik versuchen wir Dinge aus der Realität in Modell abzubilden, die innerhalb eines Computers laufen. Genau das soll auch mit einem endlichen Automaten oder Zustandsautomaten (engl. State Machine) erfolgen. Kennzeichnend für einen Zustandsautomaten sind ein oder mehrere Zustände, Zustandsübergänge zwischen Zuständen und Aktionen, die einen Zustandsübergang auslösen. Der Übergang von einem in einen anderen Zustand ist nur möglich (zulässig), wenn zwischen diesen beiden Zuständen ein Zustandsübergang und die dazugehörige Aktion definiert sind. Daraus folgt, dass Zustandsübergänge immer gerichtet sind, also nur in eine Richtung gehen. Es ist zulässig, dass es von einem Zustand Zustandsübergänge zu verschiedenen Zuständen geben kann.
Betrachten wir beispielsweise eine Lichtzeichenanlage (ugs. Ampel), wie sie in Deutschland üblich sind. Die Zustände einer (sehr) einfachen Anlage wäre hier: Rot, Rot-Gelb, Grün, Gelb, Gelb-Blinken. Ein typischer Zustandsübergang ist der Übergang von Rot nach Rot-Gelb. Einen Zustandsübergang von Rot nach Gelb, oder von Rot unmittelbar nach Grün ist ein unzulässiger Zustandsübergang. Ausgelöst werden die Zustandsübergänge beispielsweise durch einen zeitgesteuerten Taktgeber, oder durch das Drücken eines Tasters bei Fußgängerampeln.
Die folgende Implementierung stellt die Basisklasse für einen einfachen Zustandsautomaten dar. Der Zustandsautomat wird initialisiert mit einem Startzustand und einer Liste von Zuständen und deren Zustandsübergängen. Vor und nach jedem Zustandsübergang kann optional eine individuelle Methode aufgerufen werden. Zusätzlich verfügt der Zustandsautomat über optionale allgemeine Methoden, die vor und nach jedem Zustandsübergang aufgerufen werden, sowie einer optionalen Methode, die bei einem unzulässigen Zustandsübergang aufgerufen wird. Ein unzulässiger Zustandsübergang führt nicht zu einem Zustandswechsel.
Code
# Statemachine.py
from typing import TypeVar, Generic, Callable
TState = TypeVar('TState')
TCommand = TypeVar('TCommand')
class StateMachine(Generic[TState, TCommand]):
class StateTransition:
CurrentState: TState
Command: TCommand
OnBeforeTransition : Callable[[], None] = None
OnAfterTransition : Callable[[], None] = None
def __init__(self, current_state, command):
self.CurrentState = current_state
self.Command = command
def __cmp__(self, other):
if isinstance(other, self.StateTransition):
return self.CurrentState == other.CurrentState and \
self.Command == other.Command
return False
def __hash__(self):
return 17 + 31 * self.CurrentState.__hash__() + \
31 * self.Command.__hash__()
transitions = {}
CurrentState : TState
OnInvalidTransition: Callable[[TState, TCommand], None] = None
OnBeforeTransition: Callable[[TState, TCommand], None] = None
OnAfterTransition: Callable[[TState, TCommand], None] = None
def __init__(self, initial_state : TState):
self.CurrentState = initial_state
def move_next (self, command : TCommand) -> TState:
transition = None
for k in self.transitions.keys():
if k.CurrentState == self.CurrentState and \
k.Command == command:
transition = k
break
if transition is None:
if callable(self.OnInvalidTransition):
self.OnInvalidTransition(self.CurrentState, command)
return self.CurrentState
if callable(transition.OnBeforeTransition):
transition.OnBeforeTransition()
if callable(self.OnBeforeTransition):
self.OnBeforeTransition(self.CurrentState, command)
next_state = self.transitions.get(transition)
self.CurrentState = next_state
if callable(transition.OnAfterTransition):
transition.OnAfterTransition()
if callable(self.OnAfterTransition):
self.OnAfterTransition(self.CurrentState, command)
return self.CurrentState
def add_transition (self, start_state : TState, \
end_state : TState, \
transition : TCommand, \
before_transition: Callable[[], None] = None, \
after_transition: Callable[[], None] = None):
key = self.StateTransition(start_state, transition)
key.OnBeforeTransition = before_transition
key.OnAfterTransition = after_transition
self.transitions.__setitem__(key, end_state)
Verwendung
Die Verwendung dieser Implementierung soll am Beispiel der schon zuvor genannten Lichtzeichenanlage erfolgen. Hierzu zunächst die Modellierung der Entität Ampel:
# Ampel.py
class Ampel:
Rot: bool = False
Gelb: bool = False
Gruen: bool = False
def __init__(self):
self.Rot = True
def __str__(self):
return "Rot: {} | Gelb: {} | Grün: {}".format(self.Rot, self.Gelb, self.Gruen)
Weiter geht es mit den Zuständen und den Aktionen:
# AmpelStatesAndCommands.py
from enum import Enum
class AmpelState(Enum):
AutoRot = 0
AutoRotGelb = 1
AutoGruen = 2
AutoGelb = 3
class AmpelCommand(Enum):
Tick = 0
Die Zustände und Aktionen werden als Auflistung (engl Enumeration) implementiert. Hierzu ist in Python das Modul enum notwendig. Kommen wir nun zum eigentlichen, konkreten Zustandsautomaten:
# AmpelStatemachine.py
import Statemachine
class AmpelStateMachine(Statemachine.StateMachine[AmpelState, AmpelCommand]):
ampel : Ampel = None
def __init__(self, ampel : Ampel):
super(AmpelStateMachine, self).__init__(AmpelState.AutoRot)
self.ampel = ampel
self.OnInvalidTransition = self.Fehler
self.add_transition(AmpelState.AutoRot, \
AmpelState.AutoRotGelb, \
AmpelCommand.Tick, \
None, self.Rot_nach_RotGelb)
self.add_transition(AmpelState.AutoRotGelb, \
AmpelState.AutoGruen, \
AmpelCommand.Tick, \
None, self.RotGelb_nach_Gruen)
self.add_transition(AmpelState.AutoGruen, \
AmpelState.AutoGelb, \
AmpelCommand.Tick, \
None, self.Gruen_nach_Gelb)
self.add_transition(AmpelState.AutoGelb, \
AmpelState.AutoRot, \
AmpelCommand.Tick, \
None, self.Gelb_nach_Rot)
def Rot_nach_RotGelb(self):
self.ampel.Rot = True
self.ampel.Gelb = True
self.ampel.Gruen = False
print(self.ampel)
def RotGelb_nach_Gruen(self):
self.ampel.Rot = False
self.ampel.Gelb = False
self.ampel.Gruen = True
print(self.ampel)
def Gruen_nach_Gelb(self):
self.ampel.Rot = False
self.ampel.Gelb = True
self.ampel.Gruen = False
print(self.ampel)
def Gelb_nach_Rot(self):
self.ampel.Rot = True
self.ampel.Gelb = False
self.ampel.Gruen = False
print(self.ampel)
def Fehler(self, state: AmpelState, command: AmpelCommand):
print("BLINKEN!!")
Die Klasse AmpelStateMachine
wird abgeleitet von der oben gezeigten Basisklasse StateMachine
, wobei die Zustände und Aktionen als generische Parameter der Klasse übergeben werden: Statemachine.StateMachine[AmpelState, AmpelCommand]
.
Die möglichen Zustandsübergänge werden über die Methode add_transition
festgelegt. Der erste Parameter kennzeichnet hier den Ausgangszustand, der zweite Parameter den Zielzustand. Dann folgt als dritter Parameter die auslösende Aktion. die letzten beiden Parameter sind optional. Hier kann auf Methoden verwiesen werden, die vor, bzw. nach einem Zustandsübergang auszuführen sind. In unserem Beispiel gibt es nur Methoden, die nach einem Zustandsübergang ausgeführt werden.
Der Ampelzustandsautomat kann nun im Programm verwendet werden:
# Irgendwo im Quellcode...
ampel = Ampel()
statemachine = AmpelStateMachine(ampel)
print (statemachine.CurrentState)
Ein Zustandsübergang wird ausgelöst durch:
# [...]
statemachine.move_next(AmpelCommand.Tick)
print (statemachine.CurrentState)