View source for Automata-based programming (Shalyto's approach)


'''Automata-based programming''' is a programming technology.{{sfn|Nepeyvoda|2005}} Its defining characteristic is the use of finite state machines to describe program behavior. The transition [[Graph (discrete mathematics)|graphs]] of state machines are used in all stages of software development (specification, implementation, debugging and documentation). Automata-based programming technology was introduced by Anatoly Shalyto in 1991.{{sfn|Shalyto|1991}} Switch-technology{{sfn|Shalyto|1998}} was developed to support automata-based programming. Automata-based programming is considered to be rather general purpose program development methodology than just another one finite state machine implementation.

== Automata-based programming ==

<!-- Unsourced image removed: [[Image:Fig1-en.png|right]] -->The main idea of suggested approach is to construct computer programs the same way the [[Control theory|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, the control system (the system of interacting finite state machines) 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|feedback]] from control objects back to the finite state machines.

== Main features ==
In recent years great attention has been paid to the development of the technology of programming for embedded systems and real-time systems. These systems have special requirements for the quality of software. One of the best known approaches for this field of tasks is [[Synchronous programming language|synchronous programming]].{{sfn|Benveniste|Caspi|Edwards|Halbwachs|2003}}{{sfn|Shopyrin|Shalyto|2004}}

Simultaneously with the advance of synchronous programming in [[Earth:Europe|Europe]], an approach to software development for crucial systems called ''automata-based programming'' or ''state-based programming''{{sfn|Shalyto|1998}} was being created in {{wipe|Russia}}.

The term [[Event-driven programming|event]] is being used more and more widely in programming; recently it has become one of the most commonly used terms in software development. As opposed to it, the offered approach is based on the term [[State (computer science)|state]] (State-Driven Architecture). After introduction of the term ''input action'', which could denote an input variable or an event, the term ''automaton without outputs'' might be brought in. After adding the term ''output action'', the term “automaton” might be used. It is the finite deterministic automaton.

That is why, the sort of programming, which is based on this term, was called “automata-based programming”. So the process of software creation could be named “automata software design”.{{sfn|Shalyto|2000}}

The feature of this approach is that automata used for development are defined with the help of transition [[Graph (discrete mathematics)|graphs]]. In order to distinguish the nodes of these graphs the term ''state coding'' has been introduced. With ''multivalued state coding'' a single variable can be used to distinguish states of automaton, the number of states is equal to the number of values this variable can take on. This allowed introducing of the term ''program observability'' (that is, the value of the state variable can be checked).

Using the concept of “state” in contrast to the concepts of “events” and “variables”, allows one to understand and to specify the task and its parts (subtasks) more clearly.

It is necessary to note that using automata-based programming implies debugging by drawing up the protocols (logging) in terms of automata.

For this approach there is a formal and [[Isomorphism|isomorphic]] method of transforming from the transition graph to the software source code. So when using [[High-level programming language|high-level programming language]]s, the simplest way is to use a construct which is similar to the ''switch'' construct of the [[C (programming language)|C programming language]]. That is why the first implementation of automata-based programming was called “Switch-Technology”. Additional information about automata-based programming can be found in the “Switch-technology” article.

Nowadays automata-based programming has been developed in several ways, for different types of task to be solved and for various type of computing devices.

Russian registration certificate was issued for the ''Automata-based programming core'' and for the ''Automata-based programming plug-in for Eclipse IDE''.

== Logical control ==

In 1996 Russian Foundation for Basic Research<ref>{{cite web|url=http://www.rfbr.ru/eng/default.asp?section_id%3D0 |title=Archived copy |access-date=2008-03-17 |url-status=dead |archive-url=https://web.archive.org/web/20080314055513/http://www.rfbr.ru/eng/default.asp?section_id=0 |archive-date=2008-03-14 }}</ref> in the context of publishing project #96-01-14066 had supported publishing of a book,{{sfn|Shalyto|1998}} in which the offered technology was described in application to the logical control systems.

In such systems there are no events, but input and output actions are [[Binary data|binary variables]] and [[Operating system|operating system]] is working in the scanning mode. Systems of this class are usually to be implemented on [[Programmable logic controller|programmable logic controller]]s, which have relatively small amount of [[Computer memory|memory]] and programming is to be performed using specialized languages (for example, the language of ladder schemes or functional blocks). Methods of formal source code generation for such languages were developed for the cases in which the specification of the project being developed is represented by a system of transition graphs of interacting automata.{{sfn|Shalyto|1998}}

== State-based programming ==
Henceforth automata approach was spread to the [[Event-driven programming|event-based]] (reactive) systems.{{sfn|Harel|1987}} In such systems all of the limitations mentioned above are taken away. It is obvious from the name of these systems that events are used among the input actions. Output actions could be represented by arbitrary [[Subroutine|function]]s. Any [[Real-time operating system|real-time operating system]] could be used as an environment.

The automata implementation of event-based systems was made with the help of the [[Procedural programming|procedural approach]] to software development,{{sfn|Shalyto|2001}}{{sfn|Shalyto|Tukkel|2001}} hence the name “state-based programming”.

When using this method, output actions are assigned to the [[Glossary of graph theory|arcs]], [[Glossary of graph theory|loops]] or [[Glossary of graph theory|nodes]] of the transition graphs (in general case mixed Moore-Mealy automata are to be used).{{sfn|Shalyto|1998}} This allows representing in a compact form the sequences of actions, which are the reactions to the corresponding input actions.

One of the features of such approach to programming for the reactive systems is that the centralization of program logic is achieved by liquidation of logic in the event handlers and forming of system of interacting automata, which are called from these handlers.{{sfn|Tukkel|Shalyto|2001a}} Automata in such system can interact by nesting, by ability to call each other and with the help of state numbers interchange.

Another important feature of this approach is that automata in it are used thrice: for specification, for implementation (they remain in the source code) and for drawing up the protocol, which is performed, as said above, in terms of automata. The latter allows to verify the propriety of automata system functioning. Logging is performed automatically on the base of created program; it can be used for debugging of programs with complicated behavior.

Also this approach allows effective documenting of the decisions made during design process, especially those related to formalization of program behavior.{{sfn|Tukkel|Shalyto|2002}}

All this allowed to start the Foundation for Open Project Documentation,{{sfn|Shalyto|2003}} in the context of which many projects on perfecting of automata-based programming are being developed.

== State-based object-oriented programming ==
The composite approach, based on both object-oriented and automata-based programming paradigms,{{sfn|Shalyto|Naumov|2004}}{{sfn|Shalyto|Naumov|Korneev|2005}} may be rather useful for solving tasks from a very large spectrum. This approach was called “state-based object-oriented programming”.

The main feature of this approach is that, like in [[Turing machine]]s, controlling (automata) states are explicitly singled out. The number of these states is noticeably fewer than amount of all other objects' states (for example, run-time states).

The term “states space” was introduced in programming. This term means the set of object's controlling states. So this approach provides more understandable behavior in comparison with the case when such space is not singled out explicitly.

The minimal set of documents, which visually and clearly describe structural (static) and behavioral (dynamic) sides of a software project, is described.{{sfn|Tukkel|Shalyto|2003}}

From the experience of adaptation of suggested approach{{sfn|Tukkel|Shalyto|2001b}} one can conclude that application of automata makes programs' behavior clearer as using objects makes programs' structure clearer. Existence of high quality project documentation makes further program refactoring (changing of its structure while retaining its functionality) much easier.{{sfn|Kuznetsuv|Shalyto|2003}}

== Computational algorithms ==

Automata approach can be used for computational algorithms implementation. It was shown{{sfn|Shalyto|Tukkel|2002}} that arbitrary iterative algorithm can be implemented with the help of construction, that is equivalent to the loop operator <code>do ... while</code>, inside which there is single <code>switch</code> operator that implements automaton.

Automata-based approach is very effective for implementation of some algorithms of discrete mathematics, for example, tree parsing algorithm.{{sfn|Korneev|Shamgunov|Shalyto|2004}}

A new state-based approach to creation of algorithms' visualizers was offered. Such visualization software is widely used in the Computer Technologies department of Saint Petersburg State University of Information Technologies, Mechanics and Optics for students teaching in programming and discrete mathematics.{{sfn|Kazakov|Shalyto|2005}}{{sfn|Korneev|Shalyto|2005}} This approach allows representing of visualizer's logic as a system of interacting finite state machines. This system consists of pairs of automata; each of this pairs contains “forward” and “backward” automata, which provides step-by-step forwards and backwards execution of algorithms respectively.

== Instrumentation ==
Various software tools are developed to support automata programming. One of these tools is UniMod.{{sfn|Gurov|Mazin|Narvsky|Shalyto|2004}}{{sfn|Gurov|Mazin|Narvsky|Shalyto|2005}} This tool is based on the following concepts: [[Unified Modeling Language|UML]], Switch-technology, [[Software:Eclipse|Eclipse IDE]], [[Java (programming language)|Java programming language]], [[Open-source software|open source code]] (http://unimod.sourceforge.net/). All this enables one to talk about the UniMod as of the implementation of [[Executable UML|executable UML]].

== Publications==
Collected articles on automata-based programming were published in ITMO University. The bulletin<ref>[http://ntv.ifmo.ru/file/journal/61.pdf Bulletin of St Petersburg State University of Information Technologies, Mechanics and Optics.] 2008. Volume 53. Automata-based programming.</ref> contains 28 articles on different problems of automata-based programming.

In 2009, in St. Petersburg, Russia the first book about automata-based programming was published.{{sfn|Polikarpova|Shalyto|2009}}

==See also==
* [[Communicating sequential processes]]
* [[Executable UML]]

== References ==
{{Reflist}}

==Bibliography==
{{refbegin}}
*{{cite journal |first1=Albert |last1=Benveniste |first2=Paul |last2=Caspi |first3=Stephen A. |last3=Edwards |first4= Nicolas |last4=Halbwachs |first5= Paul |last5=Le Guernic |first6= Robert |last6=De Simone |url=http://www-verimag.imag.fr/~caspi/PAPIERS/iee03.pdf |title=The Synchronous Languages 12 Years Later |journal=Proceedings of the IEEE |volume= 91 |issue= 1 |date= January 2003 |pages=64–83|doi=10.1109/JPROC.2002.805826 }}
*{{cite journal |last1=Gurov |first1=V.S. |last2= Mazin |first2=M.A. |last3= Narvsky |first3=A.S. |last4= Shalyto |first4=A.A. |url=http://is.ifmo.ru/works/uml-switch-eclipse/ |script-title=ru:UML. SWITCH-технология. Eclipse | journal=Информационно-управляющие системы |year=2004 |volume=6 |pages=12–17 |language=ru}}
*{{cite journal |last1=Gurov |first1=V.S. |last2= Mazin |first2=M.A. |last3= Narvsky |first3=A.S. |last4= Shalyto |first4=A.A. |url=http://is.ifmo.ru/articles_en/_unimod.pdf |title= UniMod: Method and Tool for Development of Reactive Object-Oriented Programs with Explicit States Emphasis |journal=Proceedings of St. Petersburg IEEE Chapters. International Conference "110 Anniversary of Radio Invention" |year= 2005 |volume=2 |pages=106–110}}
*{{cite journal |last=Harel |first=David |archive-url=https://web.archive.org/web/20070422105816/http://www.tik.ee.ethz.ch/tik/education/lectures/hswcd/papers/Statecharts.pdf |archive-date= April 22, 2007 |title=Statecharts: A Visual Formalism for Complex Systems] |journal=Science of Computer Programming |year= 1987 |volume=8 |issue=3 |pages=231–274 |doi=10.1016/0167-6423(87)90035-9 |url= http://www.tik.ee.ethz.ch/tik/education/lectures/hswcd/papers/Statecharts.pdf|doi-access=free }}
*{{cite journal |last1=Kazakov |first1=M.A. |last2= Shalyto|first2= A.A. |url=http://is.ifmo.ru/works/heapsort/ |script-title=ru:Автоматный подход к реализации анимации в визуализаторах алгоритмов |trans-title=Automata-based approach to implementation of animation in algorithms' visualizers |journal=Компьютерные инструменты в образовании |year= 2005 |volume=3 |pages=52–76 |language=ru}}
*{{cite journal |last1=Korneev |first1=G.A. |last2= Shamgunov |first2=N.N. |last3= Shalyto |first3=A.A. |url=http://is.ifmo.ru/works/traverse/ |script-title=ru:Обход деревьев на основе автоматного подхода |trans-title=Automata-based tree traversing |journal=Компьютерные инструменты в образовании |year= 2004 |volume=3 |pages=32–37 |language=ru}}
*{{cite journal |last1=Korneev |first1=G.A. |last2= Shalyto |first2=A.A. |url=http://is.ifmo.ru/works/_a_visualizerExample.pdf |script-title=ru:Построение визуализаторов алгортмов дискретной математики |trans-title=Constructing of visualizers of algorithms of discrete mathematics |journal=Научно-технический вестник СПбГУ ИТМО |volume=23 |year= 2005 |pages=118–129 |language=ru}}
*{{cite book |last1=Kuznetsuv |first1=D.V. |last2=Shalyto |first2=A.A. |url=http://is.ifmo.ru/projects/robocode2/ |script-title=ru:Система управления танком для игры "Robocode". Вариант 2 |trans-title= Tank control system for the "Robocode" game. Version 2 |year=2003 |language=ru}}
*{{cite web| last=Nepeyvoda |first=N.N. |url=http://is.ifmo.ru/foundation/moving |script-title=ru:Стили и методы программирования |language=ru |year=2005 |trans-title=Styles and methods of programming |publisher= Internet University of Information Technologies}}
*{{cite book |last1=Polikarpova |first1=N. I. |last2= Shalyto |first2=A. A. |url=http://is.ifmo.ru/books/_book.pdf |script-title=ru:Автоматное программирование |trans-title=Automata-based programming |location=Saint Petersburg |publisher=Piter |year= 2009 |language=ru}}
*{{cite journal |last=Shalyto |first=A.A. |url=http://is.ifmo.ru/works/switch_prr/ |script-title=ru:Программная реализация управляющих автоматов |trans-title=Programmatic implementation of control automata |journal=Журнал «Судостроительная промышленность. Серия «Автоматика и телемеханика» |year= 1991 |volume= 13 |pages=41–42 |language=ru}}
*{{cite book |last=Shalyto |first=A.A. |url=http://is.ifmo.ru/books/switch/1 |script-title=ru:Switch-технология. Алгоритмизация и программирование задач логического управления |trans-title=Switch-technology. Algorithmization and programming of logic control problems |location=Saint Petersburg |publisher= Nauka |year=1998 |language=ru}}
*{{cite journal |last=Shalyto |first=A.A. |url=http://is.ifmo.ru/works/app-aplu/1/ |script-title=ru:Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления |trans-title=Software Automation Design: Algorithmization and Programming of Problems of Logical Control |title=Известия Российской академии наук. Теория и системы управления |date= November–December 2000 |volume=6 |journal=Известия Российской академии наук. Теория и системы управления |language=ru |pages=63–81}}
*{{cite journal |last=Shalyto |first=A.A. |url=http://is.ifmo.ru/articles_en/_logic_control_and_reactive_systems.pdf |title=Logic Control and "Reactive" Systems: Algorithmization and Programming] |journal=Automation and Remote Control |date= 2001 |volume=62 |issue=1 |pages=1–29|doi=10.1023/A:1002837232103 |s2cid=17521847 }} [http://is.ifmo.ru/works/arew/1/ Russian original]
*{{cite journal |last1=Shalyto |first1=A.A. |last2= Tukkel |first2=N.I. |url=http://is.ifmo.ru/works/switch/1/ |script-title=ru:SWITCH-технология — автоматный подход к созданию программного обеспечения «реактивных» систем |trans-title=SWITCH-Technology: An Automated Approach to Developing Software for Reactive Systems] |journal=Программирование |language=ru |year= 2001 |volume=5 |pages=45–62}}
*{{cite journal |last2=Tukkel |first2=N.I. |last1= Shalyto |first1=A.A. |url=http://is.ifmo.ru/works/iter/ |script-title=ru: Преобразование итеративных алгоритмов в автоматные |trans-title=Translating Iterative Algorithms into Automata |journal=Программирование |year=2002 |volume=28 |issue=5 |language=ru }}
*{{cite journal |last=Shalyto |first=A.A. |url=http://is.ifmo.ru/works/open_doc/ |script-title=ru:Новая инициатива в программировании. Движение за открытую проектную документацию |trans-title=A new initiative in programming. Foundation for open project documentation |journal=PC Week/RE |year= 2003 |volume=40 | pages=38,39,42 |language=ru}}
*{{cite journal |last1=Shalyto |first1=A.A. |last2= Naumov |first2=L.A. |url=http://is.ifmo.ru/works/_aut_oop.pdf |script-title=ru:Методы объектно-ориентированной реализации реактивных агентов на основе конечных автоматов |trans-title=Methods of object-oriented implementation of reactive agents on base of finite state machines |journal=Искусственный интеллект |year= 2004 |volume=4 |pages=756–762 |language=ru}}
*{{cite book |last1=Shalyto |first1=A.A. |last2= Naumov |first2=L.A. |last3=Korneev |first3=G.A. |url=http://is.ifmo.ru/articles_en/_kimas05-1.pdf |chapter=Methods of Object-Oriented Reactive Agents Implementation on the Basis of Finite Automata |title=International Conference on "Integration of Knowledge Intensive Multiagent Systems. KIMAS '05: Modeling, Exploration, and Engineering" |publisher= IEEE |year= 2005 |pages=460–465}}
*{{citation | last1=Shopyrin |first1=D.G. |last2= Shalyto |first2=A.A. |url=http://is.ifmo.ru/works/sync_prog/ |script-title=ru:Синхронное программирование |trans-title=Synchronous programming |journal= Информационно-управляющие системы |year= 2004 |volume=3 |pages=35–42 |language=ru}}
*{{cite journal |last1=Tukkel |first1=N.I. |last2= Shalyto |first2=A.A. |url=http://is.ifmo.ru/works/mirk/ |script-title=ru:Программирование с явным выделением состояний |trans-title=State-based programming |journal= PC World |year= 2001a |volume=8–9 |pages=116-121, 132-138 |language=ru}}
*{{cite book |last1=Tukkel |first1=N.I. |last2= Shalyto |first2=A.A. |url=http://is.ifmo.ru/projects/tanks/ |script-title=ru:Система управления танком для игры Robocode. Объектно-ориентированное программирование с явным выделением состояний. Программная документация |trans-title=Tank control system for the game Robocode. Object-oriented programming with explicit state allocation. Program documentation |year=2001b |language=ru}}
*{{cite book |last1=Tukkel |first1=N.I. |last2= Shalyto |first2=A.A. |url=http://is.ifmo.ru/projects/dg/ |script-title=ru:Система управления дизель-генератором (фрагмент). Программирование с явным выделением состояний. Проектная документация |trans-title=Diesel-generator control system (fragment). State-based programming. Project documentation |year= 2002 |language=ru}}
*{{cite journal |last1=Tukkel |first1=N.I. |last2= Shalyto |first2=A.A. |url=http://is.ifmo.ru/works/tanks_new/ |script-title=ru:Автоматы и Танки |trans-title=Automata and tanks |journal=BYTE/Россия |year= 2003 |volume=2 |pages=69–73 |language=ru}}
{{refend}}

==External links==
* Automata programming homepage ([http://is.ifmo.ru in Russian]), ([http://is.ifmo.ru/english/ in English])
* [http://unimod.sourceforge.net/intro.html UniMod]
* Examples of using of UniMod tool ([http://is.ifmo.ru/unimod-projects/ in Russian], [http://is.ifmo.ru/unimod-projects-en/ in English])

[[Category:Programming paradigms]]

{{Sourceattribution|Automata-based programming (Shalyto's approach)}}