Models & Notation:
System Models - Dynamics in Graph Notation |
| Models & Notation:
|
| |||
| back to: programming language design | paradigms | programming language list | signs | relations |
Remember that a system, in system theory,
is a concrete section of the physical reality
in which interactions take place, ie., processes run [SuB 13].
System theory, software engineering and computer science
developed several ways of modeling computation and other processes,
many of them in the form of directed graphs.
These graph-based models of system(dynamic)s are centered around concepts like
state, quantity, event/action (eg. transition),
operand/data, operator/processor/actor:
[SuB] Norbert Bischof: Struktur und Bedeutung: Eine Einführung in die Systemtheorie; Verlag Hans Huber 1995. |
| Black-Boxes: Input-Output Models | |
|
(Without internal structure or state, the graph is trivial.)
The quantities in this case are n input terminals
and m output terminals.
The dynamics of black boxes is described by the relation
between the values at the input and output terminals.
The ``arrivals'' of value-changes at the input terminals
and at the output terminals are principally concomittant
(cf. arrows in flow charts show temporal order) [SuB 32].
Examples: deterministic discrete memoryless black boxes
(described by a "transfer function" f: Inn -> Outm),
probabilistic transfer,
continuous steams of inputs and outputs
(transfer function is a smooth function of time).
The general equation relating inputs and outputs
for n = m = 1 has the form:
output(t) = |
| Grey/Glas-Box models with (hypothetical/substantial) internal variables | |||||||||||||||||
| |||||||||||||||||
|
|
| |||||||||||||||
| Mason diagrams | Connectionist networks/ graphs/ systems: perceptrons, artificial neural networks, ... | Control Block Diagrams (Blockschaltbild/Wirkungsplan) | |||||||||||||||
Mason diagrams partition the state into quantities
and show which quantity depends on which
(Mason 1953) [SuB]
If we assign the quantities to specific subsystems and then abstract from these quantities, we arrive at dependencies between subsystems, ie., -> couplings/bonds.
|
Connectionist networks partition the system into nodes,
each have one quantity as its state
and one constraint to determine it from other quantities.
Abstractly, dependency between the nodes' activations
becomes dependency between the nodes,
ie., -> couplings/bonds.
|
Control block diagrams partition the system
into transformers implementing the constraints
(Mittelstaedt 1954) [SuB]
| |||||||||||||||
| Taxonomy of Control Blocks (whether shown in control block diagrams or Mason diagrams) | |
|
Explicit control blocks X0 (blocks of complexity 0, or type K(0))
have just one output x, and some inputs z1 ... zn.
They can be described by an explicit equation for output x:
Implicit control blocks have several outputs. | z1 _________ ---->| | : | | x : | X0 |---- ---->| | zn |_________| |
|
Control blocks of complexity 1 (type K(1)) have two outputs x and y.
A K(1) block X with only one input z can be specified
by an implicit equation for outputs x and y: "z=f'(x,y)" [SuB].
There are five structurally different ways of decomposing X into two explicit control blocks F (for output x) and G (for output y) [SuB]: | _________
| | x
z | |----
---->| X |
| |----
|_________| y
|
|
| |||||||||||||
|
|
| ||||||||||||
|
where y-->x = "y controls x", i.e., a different value for y can change the value of x (negation: -|->).
and z==>x = "z controls x directly", i.e., arrows can be cut in a way that all other quantities (here: y) become constant without making x constant (negation: =|=>). | ||||||||||||||
II. State/Event-Order Models |
|
| Black-Boxes: Trace Models | |
|
(Without internal structure or state, the graph is trivial.)
The only way to model the state/event-order without refering to internal states
is by using as states the history of inputs and outputs of the system,
the traces.
... |
| Visualize order of events: Flow charts | |||||||
|
[Goldstine and John von Neumann 1946/47] [PDI]:
-> taxonomy of flow charts
| |||||||
| Events and states: Activity Models | |||||||||||||
They can be translated partially, but not totally, from/to dataflow diagrams. [E.D. Falkenberg, R. van der Pols, and Th. P. van der Weide. Understanding process structure diagrams. Information Systems, 16(4):417-- 428, Sept 1991] Activity diagrams (UML) are a generalization of the basic flow charts model where an activity diagram can model an events (process) in another, etc. | |||||||||||||
UML acitivity diagrams do not express object communication (ie., dataflow, cf. message flow) [3KBM]: «[I]t is a common mistake to assume [object operation] messages are passed between steps ... The method containing the step [in the activity diagram specifying it] coordinates the steps by defining their order and the conditions under which they are invoked, without making the operations in them dependent on each other. An advanced technique to make the behavior model [expressed as activity diagram] object oriented is to associate each step with the changes to objects that the step is intended to cause, and associate those changes with the steps that they initiate.» |
| ||||||||||||
| With multiple state actualizations: Petri Nets | |||||||
(by Petri 1962)
[ref].
Petri-nets are activity graphs whose states can be multiply actualized.
(They are therefore useful in modelling systems with concurrent processes.)
Multiple actualizations of a state (multiple "tokens" in a "place")
is just a compact way of writing parallel sub-diagrams (cf. decompose state below)
- but it places the emphasize not on how the state is decomposed
but on which processes run concurrently.
Also a Petri-net can be expanded to a normal state machine (???),
but it may expand to an infinite state machine
if the total number of actualizations is not limited.
``SLANG is a domain-specific language for software process modeling and enactment, based on ER nets. ER nets are a high-level extensionm of Petri nets, that provide the designer with powerful means to describe concurrent and real-time systems. In ER nets, it is possible to assign values to tokens and relations to transitions, that describe the constraints on tokens consumed and produced by transition firings.'' [Sergio Bandinelli, Alfonso Fuggetta: Computational Reflection in Software Process Modeling: the SLANG Approach; 144-154 in SE'93] | |||||||
| |||||||
|
| highlight states | \/ |
/\ | decompose process | |
| State machines, I/O automata, Statecharts, ... | ||||||
Automata are of greater interest than black box models because, unlike the latter, they take into account not only the behavior but also the internal states of the system. Consequently an automaton model can succeed ... where a black box model must fail ..., namely (a) when a stimulus elicits different responses depending on the state of the system [as far as it is not determined by the input history???], or (b) when the system has spontaneous (uncaused) outputs» [MB4 262].  | ||||||
| With (varying) state dimensions | ||
| ||
|
In some (set of) system states,
certain orthogonal factors (state-dimensions)
may be distinguished, that can change (in part) independently.
Without changing the underlying state machine, this can be exploited
to structure the diagram:
One region of a diagram is split into two (or more) parallel sub-diagrams A and B.
This split can always be expanded to a set of product states x | ||
Statecharts [Harel 1985/87]
are a generalization of the basic state machine model with
| ||
|
Taxonomy of Flow Charts. A prime program is a minimal single entry, single exit flow chart graph which cannot decomposed into smaller minimal single entry, single exit flow chart subgraphs [PDI]. Maddux 1975 developed a theory of prime programs [PDI] based on a normal form of flow charts where function nodes [#] are single entry, single exit; decision nodes <%> are single entry, double exit; and with special joining nodes + which are double entry, single exit. Here is the list of prime programs with one to four nodes [PDI] (my appologies for the crude character graphics): | ||||||||
| 1 | ---> [#]--->basic side-effect (assignment, etc) | |||||||
| 2 | ---> [#]---> [#]--->sequence | .-----v
---> <%> +--->
`-----^ empty if (no effect)
| .------.
v |
---> *---> <%>---> empty loop (no effect)
| |||||
| 3 | ---> [#]---> [#]---> [#]--->triple sequence (superfluous) [why is it prime?] | .-----------v
---> <%> +--->
`---> [#]---^ if-then
| .--------------.
v |
---> *---> [#]---> <%>---> do-while (repeat-until)
| .---[#] <--.
v |
---> *-------> <%>---> while-do
| ||||
| 4 | ---> [#]---> [#]---> [#]---> [#]--->quadruple sequence (superfluous) [why is it prime?] | .---> [#]---v
---> <%> +--->
`---> [#]---^ if-then-else
| .-----[#] <----.
v |
---> +---> [#]---> <%>---> do-while-do [PDI]
| |||||
.-----------v
---> <%> .--> +---> +--->
`---> <%>---------^ useless (no effect)
| .------------.
v |
---> <%>--> +---> +---> <%>--->
`-----------^ conditional jump into empty loop (no effect)
| .--------------.
v |
---> +---> <%>---> <%>---> +--->
`--------------^ empty loop with exit (no effect)
| ||||||
.------------.
v |
---> +---> +---> <%>---> <%>--->
^ |
`--------------'empty overlapping loops (no effect)
| .------+ <-----.
| ^ |
v | |
---> +---> <%>---> <%>---> empty two conditions loops (no effect)
| .----<%> <---.
| | |
v v |
---> +---> +---> <%>---> empty long/short loop (no effect)
| ||||||
| A data element's transformers: Process Models | |||||
are the data view of architectures.
They make explicit the data elements
(look at their state properties, as far as relevant to the processors manipulating them),
and which processor transforms one into the other
(the "processing flow");
less emphasis is put on connectors than in dataflow models.
[D. E. Perry and A. L. Wolf. Foundations for the study of software architecture. ACM SIGSOFT Software Engineering Notes, 17:40--52, October 1992]:
| |||||
| Processors and data elements | |
|
Diagrams showing both processors and data elements
[but how are they called???] - and processor/data hybrids - are popular, eg., in compiler construction:
|
| A processors's data sources & sinks: (Untimed) Dataflow Models | |||||||||||||||||||||||||||
A. Dataflow diagrams (DFD) [ML1] and [P.D. Bruza and Th. P. van der Weide. The semantics of data flow diagrams. In Proceedings of the International Conference on Management of Data, pages 66--78, 1989. Hyderabad, India.]
B. "Henderson" diagrams (shown to Sussman by Peter Henderson)
| |||||||||||||||||||||||||||
| (Timed) Message-passing Models | |||||||||||||
| |||||||||||||
| Event Progress Diagrams | |||||||||||
[ref]
| |||||||||||
| Location: http://www.cs.mun.ca/~ulf/pld/sysmod.html. Written 090602-050903 by Ulf Schünemann. Copyright (C) 2003 Ulf Schünemann. |
