Switch-technology
From Wikipedia, the free encyclopedia
 |
This article may need to be rewritten entirely to comply with Wikipedia's quality standards. You can help. The discussion page may contain suggestions. (January 2010) |
 |
The neutrality of this article is disputed. Please see the discussion on the talk page. Please do not remove this message until the dispute is resolved. (January 2010) |
Switch-technology is a technology for automata-based programming support. It was proposed by Anatoly Shalyto[1] 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 the suggested approach is to construct computer programs the same way the automation of technological processes (as well as other kinds of processes) is performed. Additionally, 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 other (new) types of input actions that are transmitted through a feedback from control objects back to the control system.
Automata-based programming paradigm consists therefore in representation of computer programs as systems of automated objects.
[edit] Automata-based programming and Turing machine
The universality of the suggested approach is proven by the fact that it is simply an extension of the Turing machine concept (i.e. any algorithm can be implemented using a 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 the very low level of abstraction used in this model. It uses only the simplest control objects that can perform only the simplest actions (operations) such as reading and writing single symbols on the tape.
[edit] From Turing machine to practical programming
When the first computers had appeared, switching to "practical programming" was made thanks to the raising of the abstraction level achieved by complication of the control object. The arithmetic and logic unit (ALU) was introduced, which made it possible to execute rather complex actions from a 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 was still 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 raising of abstraction level because of further complication of actions (operations) of the fixed instruction set executed by the "control objects". Despite 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 automata-based programming helps reduce program complexity
Automata-based programming makes it possible 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. Additionally, control system can hold a group of interrelated automata rather than single automaton. This allows the approach approach to be practical.
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, 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, 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 effective implementation of automata-based programs.
- Multi-level decomposition based on finite-state machines, when performed as described above, supports the basic principle of decreased program complexity, (known as "divide and conquer") and allows one to construct programs with complex behavior visually.
[edit] Programming styles
Programming styles are typically 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 the structure of programs that are based on switch-technology.
Automata-based programming can be considered not only as an independent programming style, but also as an addition (or complement) 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 the program creation process, just as it is, for example, in genetic programming.
[edit] Computing devices and programming languages
Switch-technology can be used with different computer hardware 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 currently restrained because many people think that automata’s area of application is understood and considered 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 therefore used when appropriate.
However, despite these beliefs, 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 a Turing machine, where a control device with few states (a finite automaton) is able to control an infinite number of states on the tape (cells of the tape are control objects in a Turing machine). The laboriousness of Turing programming is due to the simplicity of the tape cell. Complication of operations turns a Turing machine into a computer that is programmed more simplly - but still has a control device with a 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 further expanded in relation to programming. For example, in the "Hanoi towers" problem, the number of computational states of control object (which includes three rods 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 switch-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 we mean "a control state".
The number of states in automaton is defined by a number of control states in an 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 its corresponding state. Input actions transfer automaton from state to state and output actions move the valve into the 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 the 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 the "image" of the transition graph in the 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 - where
- - A distinct number should be assigned to each state.
- - A single variable is used to encode all states.
- - The number of the variable’s values coincides with the number of states,
State encoding allows the elimination flags that perform the same function implicitly.
The ability to watch an automaton’s state - with the help of a single multivalued variable - allows introducing the notion of “observability” in programming (by analogy with control theory).
[edit] Communication diagram
A communication diagram is the main document that defines program structure (as in automation of technological and other processes). It contains the 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 of programming is natural for control problems of different levels.
Control objects may be real, including physical models, and virtual, implemented in software. In the latter case they can be implemented with the help of Switch-technology, using control variables
[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 the communication diagram. Usage of symbols allows depicting complex transition graphs in a very compact form, so that a human in most cases is able to appreciate each of them in a single glance. This is an essential prerequisite for providing cognitive perception of these graphs.
Transition graphs reflect, in a sense, that is obvious for humans, transitions between states and "binding" of output actions to the states and/or transitions.
To simplify the transition graph picture it is possible to use composite states (that are applied in a case where 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 a program is eventually written, after building such a transition graph, symbols should also be used in it - instead of semantic identifiers (that are used in other programming styles). This is because, in this technique, the source code is intended to be built formally and isomorphically - after transition graphs and all changes are made - not directly to the source code, but (first) to the transition graph and communication diagram . This allows consistency of source code and documentation.
[edit] Automata programs structure
The 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 Moore automata[2].
- 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 the above structures 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 also unlimited
Automata interaction is reflected on the "automata interaction diagram", which can be combined with a communication diagram.
Automata interaction checking can be done with the help of logging (tracing) 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 switch-technology after Moore automaton transition graph, its certification can be done in two phases. A dynamic check can display the presence of all transitions in a graph by observing state variable values. A static check can compare the output variables values with their corresponding values in the transition graph vertices.
Such a verification is more accurate that traditional "input-output" checks.
Automata program 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 the switch statement and corresponding patterns (That is why the original suggested name was "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 performed 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 prevents the introduction of 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 Switch-technology framework.
- 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 the 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 their 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[3].
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 the 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] Open Source Projects
- "Foundation for Open Project Documentation" - supplements foundations for open and free source codes. Switch-technology improvement is done within this foundation.
[edit] See also
- Asynchronous cellular automaton
- Automata-based programming
- Comparison of programming paradigms
- Control tables
- Event-driven programming
- Flag byte
- J Strother Moore, co-developer of the Boyer-Moore string search algorithm and the Boyer-Moore automated theorem prover, Nqthm
- State
