Switch-технологія

Switch-технологія - технологія розробки систем логічного керування на базі кінцевих автоматів, що охоплює процес специфікації, проектування, реалізації, налагодження, верифікації, документування та супроводження. Запропонована А. А. Шалит в 1991 році [1].


1. Підхід до алгоритмізації

В якості мов алгоритмізації та програмування в системах логічного управління в залежності від типів керуючих обчислювальних пристроїв застосовуються: алгоритмічні мови високого рівня ( C, Pascal, Forth, ...), алгоритмічні мови низького рівня ( Асемблери), і спеціалізовані мови (наприклад, на базі сходових і функціональних схем).

Крім того існує два підходи алгоритмізації систем цього класу. У першому з них вважається, що відомий алгоритм функціонування об'єкта управління і потрібно по ньому синтезувати алгоритм логічного керування, що забезпечує заданий поведінка: "Для того щоб клапан відкрився, обчислювач повинен на вхід відкриття виконавчого механізму клапана подавати одиничний сигнал". У другому підході враховується інформація про стан об'єкта управління: "Якщо обчислювач подає на вхід відкриття виконавчого механізму клапана одиничний сигнал, то клапан відкривається". Таким чином, перша стратегія базується на понятті "стан", а друга - на понятті "подія".

Ні та, ні інша різновид управління в загальному випадку не є вичерпною, однак у Switch-технології пропонується зробити поняття "стан" первинним, а в якості мови специфікації для опису алгоритмів застосовувати графи переходів - пропонується представляти програму як систему взаємодіючих кінцевих автоматів, описуваних графами переходів. Іншими словами, спочатку описується поведінка керуючого пристрою, а не його структура, а побудова алгоритмів і програм починається з формування станів.

Об'єкти управління, як і система управління, можуть бути реалізовані за допомогою розглянутої технології, що дозволяє моделювати систему в цілому.


2. Використовувані поняття

2.1. Граф переходів

Поведінка автоматів задається графами переходів ( діаграмами станів), на яких для їх компактності вхідні і вихідні впливу позначаються символами, а слова використовуються тільки для назв пронумерованих станів. Розшифровка символів виконується на схемі зв'язків. Застосування символів дозволяє зображати складні графи переходів вельми компактно - так, що людина може в більшості випадків охопити кожен з них одним поглядом. Це забезпечує когнітивне сприйняття зазначених графів.

Графи переходів у наочній для людини формі відбивають переходи між станами, а також "прив'язку" вихідних впливів і інших автоматів до станів і / або переходах. Для спрощення зображення графів переходів допустиме використання складових станів, які застосовуються в тих випадках, коли кілька вершин мають однаково помічені вихідні дуги.

Завдання поведінки програм за допомогою графів переходів дозволяє перевіряти коректність їх побудови, наприклад, повноту, несуперечність і відсутність генеруючих контурів.

У програмі, побудованій за графами переходів, також, як і в цих графах, використовуються символьні позначення, а не смислові ідентифікатори, як в інших стилях програмування. Це пов'язано з тим, що текст програми в рамках зазначеної технології будується по графу переходів формально і ізоморфно, а зміни вносяться не безпосередньо в текст програми, а тільки після коригування схеми зв'язків і графа переходів. Викладене дозволяє забезпечити синхронність змін програм і їх проектної документації.


2.2. Схема зв'язків

Рис. 1. Система Управління з Об'єктом Управління

В якості основного документа, що визначає структуру програми, як і при автоматизації технологічних (і не тільки) процесів, в Switch-технології використовується схема зв'язків [2], яка являє собою деталізацію схеми на Рис. 1. Вона може поєднуватися зі схемою взаємодії автоматів.

Схема зв'язків визначає інтерфейс автоматів і дозволяє застосовувати в графах переходів і в реалізовують їх програмах символьні позначення. Для об'єктно-орієнтованих програм з явним виділенням станів діаграми класів в рамках розглянутого підходу зображуються у вигляді схем зв'язків.


2.3. Кодування станів

Стану кодуються для того, щоб розрізняти їх. Це особливо важливо, коли в різних станах формуються однакові значення вихідних змінних. Можуть використовуватися різні види кодування станів, але в якості основного використовується багатозначне кодування, що дозволяє кодувати стану будь-якого автомата за допомогою тільки однієї змінної [3]. При цьому її значность повинна бути дорівнює числу станів розглянутого автомата, а кожному стану присвоюється відповідний номер. Кодування станів дозволяє відмовитися від прапорів, які неявно виконують ту ж функцію.

Можливість стеження за станами автомата за значеннями однієї багатозначної змінної дозволяє ввести в програмування (за аналогією з теорією управління) поняття "наблюдаемость" [4].


2.4. Структура програми

При використанні Switch-технології прогамма (їх схеми) повинні будуватися, починаючи з дешифратора станів, а не з дешифратора вхідних впливів, як це робиться при використанні інших стилів програмування [5].

Існують три схеми реалізації автоматів:

  • Чотирирівнева схема програм (дешифратор станів - вихідні впливу - дешифратор вхідних впливів - формування наступних станів) реалізує автомати Мура.
  • Чотирирівнева схема програм (дешифратор станів - дешифратор вхідних впливів - вихідні впливу - формування наступних станів) реалізує автомати Мілі.
  • П'ятирівнева схема програм (дешифратор станів - вихідні впливу - дешифратор вхідних впливів - вихідні впливу - формування наступних станів) реалізує змішані автомати.

Схеми програм із зазначеною структурою названі автоматними. При такій побудові граф переходів, автоматна схема програм і конструкція мови програмування аналогічна конструкції switch мови C, що реалізує дешифратор станів, ізоморфні.


2.5. Взаємодії автоматів

Автомати можуть взаємодіяти по вкладеності (один автомат вкладений в одне або декілька станів іншої автомата), по визиваеми (один автомат викликається з певною подією з вихідної дії, формованого при переході іншого автомата), з обміну повідомленнями (один автомат отримує повідомлення від іншого) і за номерами станів (один автомат перевіряє, в якому стані знаходиться інший автомат). Вкладеність може розглядатися як визиваеми з будь-яким подією. Ні число автоматів, вкладених у стан, ні глибина вкладеності не обмежені.

Взаємодія автоматів відбивається на "схемою взаємодії автоматів" [2], яка може поєднуватися зі "схемою зв'язків". Перевірка взаємодії автоматів може виконуватися протоколюванням їх роботи.


3. Універсальність

Рис. 2. Принципова схема Машини Тюрінга
Рис. 3. Машина Тьюринга, як Кінцевий автомат з вхідними і вихідними впливами, одержуваними і записуваними з і на стрічку відповідно

Як відомо кожен алгоритм можна реалізувати на машині Тьюринга. Розглянута технологія є розширенням цієї моделі для практичного використання. У разі машини Тьюринга вхідний вплив з стрічки подається на кінцевий автомат, а на стрічку записується вихідна вплив. Складність програмування на машині Тьюринга в основному визначається тим, що в ній об'єкт управління (осередок) дуже простий, і в ній автомату доводиться виконувати не лише властиву йому функцію - керування, але, при необхідності, і забезпечувати обчислення. Якщо замінити стрічку кожним більш складним пристроєм, а автомат - системою взаємопов'язаних автоматів, то вийде узагальнення машини Тьюринга, яке може бути використане для практичного програмування. Таким чином, пропонований підхід є універсальним засобом для реалізації алгорітмов.1


4. Стилі програмування

Стилі програмування розрізняються за базовими поняттями [6], в якості яких використовуються такі поняття як "подія", "підпрограма", "функція", "клас" ("об'єкт") і т. д. У Switch-технології таким поняттям є " стан ". При цьому події розглядаються лише як засобу для зміни станів. Стиль програмування, заснований на явному виділення станів і застосуванні автоматів для опису поведінки програм, названий " автоматні програмування " [1], а відповідний стиль проектування програм - "автоматні проектування програм". автоматні програмування можна розглядати не тільки як самостійний стиль програмування, але і як доповнення до інших стилям, наприклад, до об'єктно-орієнтованого.


5. Суміжні технології

5.1. Нейронні мережі та генетичні алгоритми

Області застосування автоматів і нейронних мереж звичайно різні. Однак існують завдання, в яких доцільно їх спільне застосування [7].

Відомі також завдання, які можуть вирішуватися за допомогою будь-якого із зазначених коштів. У цьому випадку застосування автоматів більш доцільно, так як в них легко вручну вносити зміни. Це може бути важливо, наприклад, у випадку, коли закон управління будується в два етапи, перший з яких полягає в генерації автоматів за допомогою генетичних алгоритмів, а другий - в коректуванні автоматів в результаті експериментів.


5.2. Паралельні обчислення

У програмах, побудованих традиційним шляхом, виділення фрагментів, які можуть бути реалізовані паралельно, є досить важким завданням. Існує широкий клас задач, специфікація яких здійснюється за допомогою паралельно працюючих автоматів, які обмінюються повідомленнями. Такі автомати ефективно реалізовувати на основі систем з паралельними обчисленнями [8].

6. Перевірка, налагодження та верифікація автоматних програм

6.1. Перевірка та налагодження

Програма, ізоморфна графу переходів, може бути перевірена звіркою її тексту з цим графом. Сертифікація програми логічного управління, яка реалізована зазначеним чином по графу переходів автомата, що є автоматом Мура, може виконуватися в два етапи: перевірка в динаміці за значеннями багатозначної внутрішньої змінної, що кодує стан автомата, наявності всіх переходів у графі; перевірка в статиці відповідності значень вихідних змінних з їх значеннями, вказаними в вершинах графа переходів [3]. Така перевірка більш коректна, ніж традиційна перевірка "вхід-вихід". Налагодження автоматних програм виконується в автоматних термінах, що різко її спрощує.


6.2. Верифікація

Програми, що створюються на основі Switch-технології, можуть бути ефективно верифіковані методом Model checking [9], так як в таких програмах керуючі стану явно виділені, а їх кількість оглядатися. Це дозволяє будувати компактні моделі Кріпке навіть для програм великої розмірності.

Структура автоматних програм, в яких функції вхідних і вихідних впливів майже повністю відокремлені від логіки програм, робить практичним верифікацію цих функцій на основі формальних доказів з використанням перед-та постусловіем [10] [11].


7. Реалізація та інструментальні засоби

7.1. Реалізація графів переходів

Графи переходів реалізуються формально і ізоморфно, наприклад, за допомогою конструкції switch (наприклад, мови Сі) за відповідними шаблонами (тому пропонований підхід був названий "Switch-технологія").

У конструкції switch використовуються символи вхідних і вихідних впливів, а не функції їх реалізують, які розміщуються окремо. Така декомпозиція спрощує розуміння логіки програми за рахунок компактного її подання та відповідає правилу "відділення логіки перемикання від деталей того, що відбувається" [12].

Для кожного автомата створюється чотири документи: словесний опис алгоритму (декларація про наміри), схема зв'язків, граф переходів, ізоморфна реалізація.

Реалізація виконується так, що в кожному програмному циклі або при кожному запуску автомата в ньому виконується не більше одного переходу. Це робить номер кожного стану автомата доступним для його "оточення" і дозволяє не вводити нових змінних для забезпечення взаємодії автоматів [3].


7.2. Інструментальні засоби

Можливість швидкого, безпомилкового, автоматичного і ізоморфного переходу від набору графів переходів до програми на мові високого рівня дозволяє значно спростити відладку і моделювання керуючих автоматів і робить програму повністю спостережуваної і керованою.

Відомо велика кількість інструментальних засобів для генерації програм, що реалізують графи переходів (en: List of state machine CAD tools). Наведемо список найбільш відомих проектів:

  • Visio2Switch - інструментальний засіб Visio2Switch дозволяє по графу переходів, побудованому в певній нотації і зображеному за допомогою редактора Visio, автоматично реалізувати його у вигляді ізоморфної програми на мові С.
  • MetaAuto - інструментальний засіб MetaAuto дозволяє по графу переходів, побудованому в тій же нотації і зображеному за допомогою того ж редактора, автоматично реалізувати його у вигляді ізоморфної програми на будь-якій мові програмування, для якого попередньо побудований шаблон.
  • UniMod - інструментальний засіб UniMod призначено для підтримки автоматного програмування та побудови та реалізації не тільки автоматів, але й програм в цілому.

Це засіб характеризується формулою: "UniMod = UML + Switch-технологія + Eclipse + Java + SourceForge ". Воно є відкритим і використовує тільки два типи UML-діаграм: діаграми класів у формі схем зв'язків (для опису структури програми) і діаграми станів (для опису її поведінки) [13] [14]. Валідація діаграм станів виконується автоматично. Зазначене інструментальний засіб дозволяє створювати програми, підтримуючи концепції "Виконуваний UML" (en: Executable UML) і "Розробка на базі моделей" (en: Model Driven Architecture).

При використанні інструментального засобу UniMod програма складається з зазначених діаграм і написаних вручну функцій, відповідних вхідним і вихідним впливів. Таким чином, це інструментальний засіб дозволяє поєднувати декларативний і процедурний підходи до написання програм.

Реалізація таких програм може бути виконана як в режимі інтерпретації, так і в режимі компіляції. Це засіб реалізує концепцію "Візуальне конструювання програм" [15].


8. Застосування технології

Описаний підхід використовується в чотирьох напрямках:

  • логічне керування (події відсутні, вхідні і вихідні змінні двійкових);
  • програмування з явним виділенням станів;
  • об'єктно-орієнтоване програмування з явним виділенням станів;
  • обчислювальні алгоритми (алгоритми дискретної математики).

Відомі практичні застосування:

  • Вперше технологія автоматного програмування стосовно до логічного управлінню викладена в книзі [3] стосовно до логічного управлінню.
  • Програмування з явним виділенням станів для систем, що реагують на події, вперше було використано при автоматизації суднових дизель-генераторів [16].
  • Об'єктно-орієнтоване програмування з явним виділенням станів вперше було застосовано в грі Robocode [17].
  • Розробка прикладного програмного забезпечення для мікроконтролерів [18]
  • Проекти, створені з використанням інструментального засобу UniMod [19].

Крім того, автоматний підхід ефективний для реалізації визуализаторов алгоритмів дискретної математики і при реалізації деяких з таких алгоритмів (наприклад, обхід дерева [20]), а також все частіше починає використовуватися в рамках такого наукового напряму, як "штучний інтелект" [35], і при програмуванні мобільних пристроїв [21].


9. Проект "Технологія автоматного програмування: застосування та інструментальні засоби"

У 2005 році за результатами конкурсу, що проводиться в рамках Федеральної цільової науково-технічної програми "Дослідження та розробки з пріоритетних напрямів розвитку науки і техніки" на 2002-2006 роки, проект "Технологія автоматного програмування: застосування та інструментальні засоби" був підтриманий Федеральним агентством з науки та інновацій.

Проект увійшов до списку 15 найбільш перспективних і соціально значущих проектів, які виконуються в рамках зазначеної програми (проект ІТ-13.4/004 [22], а також стаття в додатку до газеті Коммерсант [23]).

Зазначені вище роботи в області Switch-технології знаходяться в руслі робіт по забезпеченню високої якості програмного забезпечення, що проводяться в Західній Європі при створенні синхронного програмування для відповідальних систем [24] і в NASA при створенні програмного забезпечення для безпілотних космічних апаратів [25].


Література

Примітки

  1. 1 2 Шалит А. А. Програмна реалізація керуючих автоматів / / Суднобудівна промисловість. Серія "Автоматика і телемеханіка". 1991. Вип.13, с.41, 42
  2. 1 2 Туккель Н. І., Шалит А. А. SWITCH-технологія - автоматний підхід до створення програмного забезпечення "реактивних" систем / / Програмування. 2001. № 5, c.45-62.
  3. 1 2 3 4 Шалит А. А. Switch-технологія. Алгоритмізація і програмування задач логічного керування. СПб.: Наука. 1998.
  4. Шалит А. А. Алгоритмізація і програмування для систем логічного керування та "реактивних" систем / / Автоматика і телемеханіка, 2001, № 1, с.3-39.
  5. Шалит А. А. Використання граф-схем і графів переходів при програмної реалізації алгоритмів логічного керування. II / / Автоматика і телемеханіка. 1996. № 7. с.144-169.
  6. Непейвода Н. Н. Стилі і методи програмування. М.: Інтернет-Університет Інформаційних технологій. 2005
  7. Кретинин А. В., Солдатов Д. В., Шалит А. А., Шостак А. В. Ракети. Автомати. Нейронні мережі / / Нейрокомп'ютери: розробка і застосування. 2005. № 5, с. 50-59.
  8. FSM - itc.ua/articles/fsm_19921 /. ITC Publishing (20 лютого 2005). Читальний - www.webcitation.org/687RMY65V з першоджерела 2 червня 2012.
  9. Кларк Е., Грамберт О., Паладій Д. Верифікація моделей програм: Model Checking. М.: МЦНМО. 2002.
  10. Дейкстра Е. Нотатки по структурному програмуванню / Дав У., Дейкстра Е., Хоорі К. Структурне програмування. М.: Мир, 1975.
  11. Мейер Б. Об'єктно-орієнтоване конструювання програмних систем. М.: Російська редакція. 2005.
  12. Фаулер М. Рефакторинг. Поліпшення існуючого коду. СПб.: Символ. 2003.
  13. Гуров В. С., Мазін М. А., Нарвський А. С., Шалит А. А. UML. SWITCH-технологія. Eclipse / / Інформаційно-керуючі системи. 2004. № 6, c.12-17.
  14. Gurov VS, Mazin MA, Narvsky AS, Shalyto AA UniMod: Method and Tool for Development of Reactive Object-Oriented Programs with Explicit States Emphasis / Proceedings of St. Petersburg IEEE Chapters. Year 2005. International Conference "110 Anniversary of Radio Invention". SPb ETU "LETI". 2005. V. 2, pp. 106-110.
  15. Новиков Ф. А. Візуальне конструювання програм / / Інформаційно-керуючі системи. 2005. № 6. с.9-22.
  16. Туккель Н. І., Шалит А. А. Система управління дизель-генератором (фрагмент). Програмування з явним виділенням станів. Проектна документація. 2002. c. 51
  17. Туккель Н. І., Шалит А. А. Система управління танком для гри "Robocode". Варіант 1. Об'єктно-орієнтоване програмування з явним виділенням станів. 2001. c. 52
  18. Татарчевскій В. (Єкатеринбург) Застосування SWITCH-технології при розробці прикладного програмного забезпечення для мікроконтролерів. Частини 1-7 / / Компоненти та технології. 2006. № 11 - 2007. № 7.
  19. UniMod-проекти. http://is.ifmo.ru/unimod-projects/ - is.ifmo.ru / unimod-projects /
  20. Корнєєв Г. А., Шамгунов Н. Н., Шалит А. А. Обхід дерев на основі автоматного підходу / / Комп'ютерні інструменти в освіті. 2004. № 3, с.32-37.
  21. Програмування мобільних пристроїв. http://is.ifmo.ru/science/MD-Mobile.pdf - is.ifmo.ru / science / MD-Mobile.pdf
  22. Вибрані кращі інноваційні проекти Росії / / Інформаційна система "Наука та Інновації", http://www.rsci.ru/company/innov/more.html?MessageID=965 - www.rsci.ru / company / innov / more.html ? MessageID = 965
  23. Чарівна скринька Роснауки / / Додаток до газети Коммерсант, 16.11.2005. http://www.kommersant.ru/application.html?DocID=625381 - www.kommersant.ru/application.html?DocID=625381
  24. The Synchronous Languages ​​12 Years Later. http://www-sop.inria.fr/aoste/benveniste2003synchronous.pdf - www-sop.inria.fr/aoste/benveniste2003synchronous.pdf (Англ.)
  25. Ріган П., Хемілтон С. NASA: місія надійна / / Відкриті системи, 2004. № 3. http://www.osp.ru/os/2004/03/184060/ - www.osp.ru/os/2004/03/184060/