Switch-technology
From Wikipedia, the free encyclopedia
Switch-technology is a technology for automata-based programming support. It was proposed by Anatoly Shalyto in 1991. It involves software specification, design, implementation, debugging, documentation and maintenance. The term “automata-based programming” is used not only for finite automata building and implementation, but also the whole process of software design and implementation, when automata are used to describe programs’ behavior.
[edit] Automata-based programming paradigm
The main idea of suggested approach is to construct computer programs the same way the automation of technological processes (and other kinds of processes too) is done.
For all that on the basis of data domain analysis the sources of input events and the automated objects, each containing the control system (the system of interacting finite state automata) and the control objects implementing output actions are singled out. These control objects can also form yet another type of input actions that are transmitted through a feedback from control objects back to the control system.
Automata-based programming paradigm consists in representation of computer programs as systems of automated objects.
[edit] Automata-based programming and Turing machine
Universality of suggested approach is proved by the fact that it is an extension of the Turing machine. Any algorithm can be implemented using the Turing machine.
From the control theory point of view the Turing machine represents an autonomous system of automated objects. In this system the finite state machine that applies output actions to the control objects (cells of the tape) receives input actions from these control objects through a feedback loop.
The complexity of programming of the Turing machine comes from very low level of abstraction used in this model. It uses only the simplest control objects that can perform only the simplest actions (operations) like reading and writing single symbols on the tape.
[edit] From Turing machine to practical programming
When the first computers had appeared switching to a practical programming was made thanks to the rising of abstraction level achieved by complication of the control object. The arithmetic and logic unit was introduced, which made it possible to execute rather complex actions from definite instruction set.
Though the finite state machine was used as a control unit of the computer, states and automatons were not explicitly used in programming, while the program logic still had been being implemented on the low level of abstraction using "flags".
[edit] Rising level of abstraction in higher-level languages
Using imperative higher-level languages for programming caused further rising of abstraction level because of further complication of actions (operations) of the fixed instruction set executed by the "control objects". With all this, however, when the program logic had been being designed, the level of abstraction was not changed compared to the lower-level languages.
[edit] How the automata-based programming allows to fight the program complexity
Automata-based programming allows one to raise the level of abstraction not only for operations being executed, but also for description of the program behavior itself. There is no upper bound on complexity of control objects in automata-based programming. As well control system can hold a group of interrelated automata rather than single automaton. This allows concerned approach to be useful in practice.
This all is provided by the following:
- When designing the program the processes (modes of operation) are singled out, each of which is then described by a finite automaton.
- In general case every process (automaton) can be decomposed into smaller processes (automatons).
- Every process (automaton) is described in terms of states and transitions between states.
- In general case every state can be decomposed into smaller states.
- Interaction of automatons is realized by "binding" automatons to states or transitions of other ones.
- States decompose the set of input actions, which invoke transitions, into the groups, each of which defines transitions from one corresponding state.
- Set of automatons' output actions, which are implemented by control objects, is not fixed and can be defined by the data domain.
- Output actions are not processes and are not considered as processes.
- Output actions are "bound" to the states and/or transitions of automatons.
- When object-oriented and automata-based paradigms are used together, it becomes possible to describe both static and dynamic characteristics of programs in visual form.
- Object decomposition allows one to implement automata-based programs effectively.
- Multi-level decomposition based on finite-state machines, when performed as described above, supports basic principle of decreasing of program complexity, which is named "separate and dominate", and allows one to construct programs with complex behavior visually.
[edit] Programming styles
Programming styles are distinguished by their basic notions, such as “event”, “subroutine”, “function”, “class” (“object”) and etc.
In automata-based programming and supporting Switch-technology “state” is the basic notion (State-Driven Architecture). Events are considered only the means to change state. Thus, “state” is the primary notion against “event”, that is reflected in structure of programs based on switch-technology.
Automata-based programming can be considered not only as an independent programming style, but also as an addition to other programming styles, for example, to an object-oriented paradigm.
Also automata-based programming can be viewed in a different manner, in which programming styles are designated with the mathematical apparatus used in program creation process, as it is done, for example, for genetic programming.
[edit] Computing devices and programming languages
Switch-technology can be used with different computing devices (programmable logic controllers, microcontrollers, microprocessors).
Switch technology can be used in combination with other styles and other languages -- such as procedural languages, object-oriented programming styles languages, ( ladder diagrams languages, functional diagrams languages, and etc.).
[edit] Objections against Switch-technology
Usage of Switch-technology is restrained because many people think that automata’s area of application is well known and quite limited. Usually, the following reasons are put forward:
- automata are used in hardware design (e.g., counters) and in programming hardware implementations based on large-scale integration circuit;
- automata are used in building compilers;
- state diagrams are used in UML as behavior description model for object-oriented software;
- automata are one of the models of discrete mathematics and, like other models, are used when necessary.
All this statements are certainly true. However none of them prevents using automata-based programming in different problem domains.
[edit] Main theses
[edit] Automata and programming
It is stated that: “Control states + input actions = finite (deterministic) automaton without output”.
And also: “Automaton without output + output actions = automaton”.
Automata can be abstract (input and output actions are formed sequentially) and structural (input and output actions are formed concurrently). Switch-technology, in contrast to programming compilers, uses structural automata.
Time is not used in automata explicitly. Delay components are considered as control objects. Delays are started and stopped from automata and time expiration events arrive into automata as input actions.
A programming style based on explicit state detachment and using automata to describe programs behavior is called "automata-based programming” and the corresponding design style – automata-based design.
[edit] States
States are divided into two types: control states (automaton states) and computational states (non-automaton states).
Such division presents, for example, in Turing machine, where a control devices with few states (a finite automaton) is able to control an infinite number of states on the tape (cells of the tape are a control objects in Turing machine). Laboriousness of Turing programming is due to simplicity of tape cell. Complication of operations turns Turing machine into a computer that is programmed simpler but still has a control device with relatively small number of states that controls memory with extremely large number of states. This memory stores the results of performed computations.
The idea of dividing states into control and computational may be expanded on programming. For example, in Hanoi towers problem the number of computational states of control object (which includes three shanks and n disks) grows exponentially with n, while an automaton that provides disks shifting has only two or three control states.
Computational states may be not only discrete, but also continuous, which leads to a notion of “hybrid automaton”.
In the considered technology the main attention is paid to control states, which are detached and listed explicitly, while computational states are usually described inside output actions. That is why by “state” here a control state is meant.
The number of states in automaton is defined by a number of control states in automated object. For example, a valve control object can be in four different states (closed, opening, open and closing). Here it is natural for automaton, which controls a valve, to have four states also, each supporting control object in corresponding state. Input actions transfer automaton from state to state and output actions move valve into corresponding state.
If different states of control object can be supported by the same state of automaton, the number of automaton states can be reduced. For example, a valve can have control objects with memory that hold its open and closed states in absence of control signals. Therefore, the automaton that controls valve can have not four but three states. In general, control device can have fewer states that its control object.
Within software implementation of automata it is unreasonable to minimize the number of states, because it can destroy an “image” of transition graph in developer’s mind, while no essential improvement of automaton is introduced.
Explicit state detachment allows one to provide "stability" of programs.
[edit] State encoding
States are encoded to be distinguishable. It is especially important when there are same output actions generated in different states. There are several kinds of state encoding, but the main is multivalued encoding, when a single variable is used to encode all states. The number of variable’s values coincides with the number of states, a distinct number should be assigned to each state. State encoding allows giving up flags that perform the same function implicitly.
Ability to watch automaton’s state with the help of a single multivalued variable allows introducing a notion of “observability” in programming (by analogy with control theory).
[edit] Communication diagram
Communication diagram is the main document that defines program structure (as in automation of technological and other processes). It contains sources of input actions (events and input variables), control system (a system of interacting automata) and control objects that implement output actions and form specific input actions, which are feedback loops.
Input actions make automata perform transitions between states that are explicitly detached and form output actions in states and/or on transitions, which are implemented in control objects. Such a view on programming is natural for control problems of different levels.
Control objects may be real, including physical models, and virtual, implemented in software. In later case they can be implemented with the help of Switch-technology.
[edit] Transition graphs
Automata behavior is defined with the help of transition graphs (state diagrams), where input and output actions are denoted with symbols for compactness and words are used only to label numerated states. Symbol decoding is reflected in communication diagram. Usage of symbols allows depicting complex transition graphs in a very compact form, so that human in most cases is able to seize each of them at a single glance. This is an essential prerequisite for providing cognitive perception of mentioned graphs.
Transition graphs reflect in a way, obvious for human, transitions between states and "binding" of output actions to the states and/or transitions.
To simplify transition graph picture it is possible to use composite states, which are applied in a case, when several states have similar outgoing transition arcs.
When program behavior is defined with a transition graph, it is possible to check its correctness, e.g., completeness, consistency and absence of generative circuits.
When program is built after such transition graph, symbols should also be used in it instead of semantic identifiers that are used in other programming styles. This is because the source code in suggested technology is built formally and isomorphically after transition graphs and all changes are done not directly to the source code, but to the transition graph and communication diagram. This allows keeping consistency of source code and documentation.
[edit] Automata programs structure
Behavior-related part of automata programs (their schemes) should be built starting with state decoder.
Four-level program scheme (state decoder – output actions – input actions decoder – next state forming) implements Moor automata.
Four-level program scheme (state decoder – input actions decoder– output actions – next state forming) implements Mealy automata.
Five-level program scheme (state decoder – output actions – input actions decoder– output actions – next state forming) implements compound (Moor-Mealy) automata.
Programs with above stated structure are called automata programs.
When building programs in such a way, transition graphs, automata program schemes and switch-statement are isomorphic.
[edit] Automata interaction
Automata can interact by nesting (an automaton is nested in one or several states of another automaton), by invocation (an automaton is invoked with certain event in output action of another automaton), by state numbers (an automaton checks the current state of another automaton).
Nesting can be considered invocation with any event. The number of automata, nested in a state, is not limited. Nesting depth is not limited too.
Automata interaction is reflected on “automata interaction diagram”, which can be combined with communication diagram.
Automata interaction checking can be done with the help of logging their work, which is done in terms of automata.
[edit] Automata, neural networks, genetic algorithms
Automata and neural networks usually have different fields of application. However there are some kind of tasks in which it is expedient to use them both together.
Also there are tasks that can be solved using any of these means. In this case use of automata is more appropriate because they can be easily and transparently changed manually. This possibility can be important, for example, in those cases in which the control law is constructed in two stages: the first stage is forming of this law using genetic algorithms and the second one is more precise definition of control law during the course of experiments.
[edit] Automata and concurrent programming
In traditional programs it is often a difficult problem to allocate fragments that can be implemented concurrently. However, there is a wide class of problems that can be specified with concurrent automata. Such automata can be effectively implemented in different threads and different processors.
[edit] Program checking
A program that is isomorphic with a transition graph can be verified by comparing its code with this graph.
If a logical control program is implemented in suggested way after Moore automaton transition graph, its certification can be done in two phases. Dynamic check can display presence of all transitions in a graph by watching state variable values. Static check can compare output variables values with their values in transition graph vertices.
Such a verification is more correct that tradition “input-output” check.
Automata programs debugging can be done in terms of automata, which simplifies it greatly.
[edit] Program verification
Programs built with Switch-technology can be efficiently verified using Model checking [16], because control states in such programs are explicitly singled out. Number of these states is limited, therefore compact Kripke models can be built even for large scale programs.
Automata programs structure, which has input and output action functions completely separated from program logic, makes them suitable for formal proofs with the help of pre- and postconditions [17, 18].
[edit] Implementation and tools
[edit] Transition graphs implementation
Transition graphs are implemented formally and isomorphically, for example, with the help of switch statement and corresponding patterns. That is why suggested approach was called “Switch-technology”.
For each automaton four documents are created. They are verbal description (declaration of intentions), communication diagram, transition graph and isomorphic implementation.
Implementation is done in such a way that on each invocation of automaton no more than a single transition is performed. It makes current state number of each automaton visible to its environment and allows introducing no additional variables for providing automata interaction.
[edit] Automata-based programming tools
There are many well-known tools for generating code after transition graphs (examples here). Two of these tools were developed within the offered technology.
Visio2Switch tool [1] provides automatic generation of the C program code, isomorphic to the transition graph that was built in certain notation and depicted with the help of Visio editor.
MetaAuto tool [2] allows generating isomorphic program code in any programming language (if only developer has provided a corresponding pattern) after transition graph built in the same notation.
A shortcoming of these tools is that they do not suggest any methodology for designing and implementing software application as a whole.
UniMod tool [3] is intended to support automata-based programming, that is, not only for design and implementation of automata, but also for creating complete applications.
This tool is open-source and can be described with formulation: “UniMod = UML + Switch-technology + Eclipse + Java + Sourceforge”. It uses only two types of UML diagrams: class diagrams (in form of communication diagrams) and statecharts. This tool supports “Executable UML” and “Model Driven Architecture” software development concepts.
An application, developed with the help of UniMod, consists of above states diagrams and single handmade functions that correspond to input and output actions. It can be either interpreted or compiled. This tool in many respects implements the concept of “Visual Program Design”.
[edit] Switch-technology application
The technology is used in four directions:
- Logical control (no events, only binary input and output variables).
- Programming with explicit states detachment.
- Object-oriented programming with explicit states detachment.
- Computational algorithms (discrete mathematics algorithms).
Automata-based programming is supported by web site [4].
The first application of automata-based programming technology to logical control was described in a book “Switch Technology: Algorithmization and Programming of Logical Control Proglems” [5] by Anatoly Shalyto (in Russian).
Programming with explicit states detachment for a reactive systems (with events) was applied for the first time in automation of marine diesel generator [6].
Object-oriented programming with explicit state detachment was first used in Robocode game [7].
Automata-based approach is effective for implementing visualizers [8] of discrete mathematics algorithms and for some of there algorithms themselves (e.g., tree traverse and substring search).
Automata-based programming is used wider and wider within such a subject area as “artificial intelligence” http://is.ifmo.ru/application/.
Automata are a convenient instrument for describing concurrent processes [9].
[edit] “Automata-based programming technology: application and tools” project
In 2005 this project won a competition within Federal special scientific and technical program “Research and development in priority directions of science and engineering evolution” and was supported by Federal Science and Innovation Agency.
The project was included in a list of 15 most perspective and social important projects within the mentioned program http://www.kommersant.ru/application.html?DocID=625381.
Works that were done with the help of Switch-technology lie in course of movement for improving software quality that started in West Europe with inventing synchronous programming [10] and is supported by NASA within developing software for unmanned spacecrafts [11].
[edit] Foundation for Open Project Documentation
There started a “Foundation for Open Project Documentation” that supplements foundations for open and free source codes. Switch-technology improvement is done within this foundation.
