WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     || 2 |

«Автоматное программирование для среды языково-ориентированного программирования ...»

-- [ Страница 1 ] --

Санкт-Петербургский государственный университет информационных

технологий, механики и оптики

На правах рукописи

Мазин Максим Александрович

Автоматное программирование для среды

языково-ориентированного программирования

Специальность 05.13.11 – «Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей»

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель – доктор технических наук, профессор А. А. Шалыто Санкт-Петербург 2010

ОГЛАВЛЕНИЕ

Введение

Глава 1. Автоматная и языково-ориентированная парадигмы программирования

1.1. Парадигма автоматного программирования 9  1.2. Особенности поддержки автоматного программирования на различных программных платформах 11  1.3. Языково-ориентированное программирование 20  1.4. Задачи в области автоматного языково-ориентированного программирования, требующие своего решения 30  Выводы по главе 1 34  Глава 2. Текстовый язык автоматного программирования.................. 35  2.1. Текстовые языки автоматного программирования 36  2.2. Создание языков в среде MPS 37  2.3. Язык stateMachine 39  2.4. Структура языка stateMachine 44  2.5. Конкретный синтаксис языка stateMachine 52  2.6. Система типов языка stateMachine 58  2.7. Генератор кода для языка stateMachine 63  2.8. Автоматическое построение диаграммы переходов 68  Выводы по главе 2 70  Глава 3. Валидация автоматных моделей

3.1. Формальная модель автомата 73  3.2. Полнота и непротиворечивость условий на переходах 77  3.3. Достижимость из начального состояния 83  3.4. Достижимость конечного состояния 84  3.5. Реализация в среде MPS 85  Выводы по главе 3 95  Глава 4. Инструментальные средства разработки при многопоточном автоматном программировании

4.1. Акторное расширение языка Java в среде MPS 97  4.2. Обработка сообщений с задержкой 100  4.3. Отложенный результат 101  4.4. Генерация кода для языка actors 102  4.5. Совместное использование языков stateMachine и actors 104  Выводы по главе 4 112  Глава 5. Применение текстового языка для автоматного программирования в проекте YouTrack

5.1. Автоматы с состояниями, хранимыми в базе данных 114  5.2. Реализация подсистемы в проекте YouTrack 115  5.3. Совместное использование языков stateMachine и DNQ 121  Выводы по главе 5 123  Заключение

Литература

ВВЕДЕНИЕ

Актуальность проблемы. С момента рождения программирования одной из основных проблем является написания программных систем со сложным поведением. В последнее время для создания таких систем все чаще используется автоматное программирование. Существует несколько подходов адаптации автоматного программирования к различным техникам и парадигмам программирования, среди которых доминирующей является объектно-ориентрованное программирование. Однако эта парадигма существует в практически неизменном виде уже более тридцати лет и требует дальнейшего развития, что может быть выполнено на основе языково-ориентированного программирования. Это должно повысить уровень абстракции программного кода, упростить его реализацию и сопровождение. Поэтому адаптация автоматного программирования применительно к языково-ориентированной парадигме является актуальной.

программирования для среды языково-ориентированного программирования.

Основные задачи исследования. Для достижения указанной цели диссертации решены следующие задачи, решения которых выносятся на защиту:

1. Разработка текстового языка автоматного программирования (абстрактный и конкретный синтаксисы, операционная семантика, системы типов, кодогенератор и т. д.).

2. Разработка средств валидации автоматов в среде языковоориентированного программирования.

3. Создание языка для многопоточного автоматного программирования, основанного на акторах.

4. Внедрение результатов работы в практику программирования в среде языково-ориентированного программирования MPS (Metaprogramming Научная новизна. Научная новизна предлагаемых подходов состоит в том, что автоматное программирование адаптировано для языкоориентированного программирования в части обеспечения языковой поддержки, валидации и многопоточности.

Методы исследования. В работе использованы методы объектноориентированного проектирования, метапрограммирования, теории алгоритмов, исчисление секвенций, теории акторных моделей.

Достоверность научных положений и практических рекомендаций, полученных в диссертации, подтверждается корректным обоснованием постановок задач, точной формулировкой критериев, компьютерным технологии.

Практическое значение полученных результатов состоит в том, что они успешно используются и будут использоваться в дальнейшем при разработке промышленных и учебных программных проектов на основе автоматного подхода и языково-ориентированной парадигмы.

использованы на практике в компании JetBrains (Санкт-Петербург) при разработке коммерческой системы учета ошибок YouTrack, сданной в инструментального средства с открытым кодом для поддержки автоматного sourceforge.net и скачано более 60 тысяч раз.



Полученные результаты используются также в учебном процессе на кафедре «Компьютерные технологии» СПбГУ ИТМО при выполнении программировании».

Апробация диссертации. Основные положения диссертационной работы докладывались на конференциях и семинарах: II конференции молодых ученых СПбГУ ИТМО (2005 г.); XXXV, XXXVI научных учебнометодических конференциях СПбГУ ИТМО «Достижения ученых, аспирантов и студентов СПбГУ ИТМО в науке и образовании» (2006, 2007 гг.); «Телематика-2003», «Телематика-2004», «Телематика-2005», «Телематика-2006», «Телематика-2007» (СПбГУ ИТМО); на семинаре «Автоматное программирование» в рамках международной конференции «International Computer Symposium in Russia (CSR-2006)» (ПОМИ им.

В. А. Стеклова, 2006 г.); Второй Всероссийской научной конференции «Методы и средства обработки информации» (МГУ, 2005 г.); Четвертой Всероссийской межвузовской конференция молодых ученых (СПбГУ ИТМО, 2009 г.); международной конференции «Software Engineering Conference (Russia)» (М., 2005 г.); форуме по открытому программному коду «Open Source Forum» (М., 2005 г.); второй международной научной конференции «Компьютерные науки и информационные технологии» (Саратов, 2007 г.);

(СПбГЭТУ «ЛЭТИ», 2005 г.).

Публикации. По теме диссертации опубликовано 31 научных работ, из которых 24 печатные. Результаты диссертации опубликованы в «Информационно-управляющие системы», «Научно-технический вестник СПбГУ ИТМО» и «Компьютерные инструменты в образовании».

Свидетельства об официальной регистрации программ для ЭВМ.

программирования, разработанное в рамках диссертации, получены следующие свидетельства: «Ядро автоматного программирования»

№2006 613249 от 14.09.2006, «Встраиваемый модуль автоматного программирования для среды разработки Eclipse» №2006 613817 от 7.11.2006.

результаты по теме диссертации получены в ходе научно-исследовательских и опытно-конструкторской работ, проводимых на кафедре «Компьютерных технологий» СПбГУ ИТМО в:

программирования» (грант Российского фонда фундаментальных исследований по проекту 02–07–90114);

2002 – 2004 гг. по теме «Разработка технологии создания программного обеспечения систем управления на основе автоматного подхода»

(Министерство образования и науки РФ);

2005, 2006 гг. по теме «Автоматное программирование» (Федеральная целевая научно-техническая программа «Исследования и разработки по приоритетным направлениям науки и техники» на 2002 – 2006 гг.);

программных систем управления со сложным поведением на основе объектно-ориентированного и автоматного подходов» (Министерство образования и науки РФ);

2009 г. по теме «Методы повышения качества при разработке автоматных программ с использованием функциональных и объектноориентированных языков программирования» (Федеральная целевая программа «Научные и научно-педагогические кадры инновационной России» на 2009 – 2013 гг.).

Структура диссертации. Диссертация изложена на 136 страницах и состоит из введения, пяти глав и заключения. Список литературы содержит 119 наименований.

Работа иллюстрирована 65 рисунками.

программирования в зависимости от использования различных парадигм метапрограммирование и обоснована целесообразность исследования в области автоматного программирования для среды языковоориентированного программирования. Сформулированы особенности среды языково-ориентированного программирования, приводящие к необходимости создания новых подходов к автоматному программированию.

Вторая глава посвящена созданию языка и инструментального средства для автоматного программирования в среде MPS. Описан подход к автоматной разработке, при котором код автомата пишется в виде текста, а диаграмма переходов восстанавливается из кода автоматически.

В третьей главе описан метод валидации автоматов, в условиях на переходах которых, существуют булевы формулы с предикатами сравнения входных переменных с константой и входных переменных друг с другом.

В четвертой главе описаны акторный язык и инструментальное средство для многопоточного автоматного программирования в среде MPS.

Язык actors позволяет в привычной для Java-программистов манере использовать автоматически распараллеливающиеся функциональные конструкции. Описан способ применения языка actors совместно с языком автоматного программирования для многопоточного автоматного программирования.

Пятая глава содержит описание результатов внедрения разработанных средств автоматного программирования в промышленную разработку программного обеспечения.

ГЛАВА 1. АВТОМАТНАЯ И ЯЗЫКОВООРИЕНТИРОВАННАЯ ПАРАДИГМЫ ПРОГРАММИРОВАНИЯ

1.1. Парадигма автоматного программирования «программирование от состояний» или «программирование с явным выделением состояний» – это подход к разработке программного обеспечения (ПО), основанный на расширенной модели конечных автоматов и ориентированный на создание широкого класса приложений. При этом речь идет не только и не столько об использовании конечных автоматов в программировании, сколько о методе создания программ в целом, поведение которых описывается автоматами. При этом программы предлагается представлять, как совокупность автоматизированных объектов управления. Автоматное программирование относится к такому направлению создания ПО, как программная кибернетика [1], так как оно базируется на идеях теории управления и теории автоматов.

Программирование с использованием автоматов имеет достаточно богатую историю развития. Различные аспекты и понятия, связанные с этой идеей, рассматривались в работах многих авторов с самых разных точек зрения и применительно к различным конкретным вопросам [2, 3]. Однако систематически автоматы использовались только при разработке компиляторов и протоколов. В настоящее время программирование от состояний рассматривается как один из стилей программирования [4].

Как парадигма разработки ПО, автоматное программирование сформировалось, в основном, благодаря усилиям А. А. Шалыто, который в программирования [5]. В его работах нашли отражение различные аспекты этого подхода к программированию, а краткое описание предлагаемой парадигмы программирования содержится, например, в работе [6]. Более полное и исчерпывающее изложение сути автоматного программирования, как парадигмы и метода разработки программных систем, дано в работе [7].

Термин автоматное программирование родился в 1997 г. и был впервые использован во введении к работе [8]. На английский язык этот термин переводится как Automata-based Programming. Англоязычное название было предложено в работе [9]. Также этот подход известен под названием SWITCH-технология.

Парадигма автоматного программирования состоит в представлении сущностей со сложным поведением в виде автоматизированных объектов управления. Для этого сущность со сложным поведением разделяется на две части:

управляющую часть, ответственную за поведение – выбор выполняемых действий, зависящий от текущего состояния и входного воздействия, а также за переход в новое состояние;

управляемую часть, ответственную за выполнение действий, выбранных управляющей частью, и, возможно, за формирование некоторых компонентов входных воздействий для управляющей части – обратных В соответствии с теорией управления, управляемая часть называется объектом управления, а управляющая часть – системой управления. В рамках рассматриваемой парадигмы для реализации управляющей части используется система взаимосвязанных автоматов, каждый из которых называется управляющим автоматом или просто автоматом.

После разделения сущности со сложным поведением на объекты управления и автоматы реализовать ее уже несложно, а главное, ее реализация становится понятной и удобной для модификации. Вся логика поведения сущности сосредоточена в управляющих автоматах. Объекты управления, в свою очередь, обычно обладают простым поведением – независящим от состояний. Поэтому объекты управления могут быть легко реализованы традиционными «неавтоматными» методами.

Таким образом, в соответствии с автоматным подходом, сущности со сложным поведением следует представлять в виде автоматизированных объектов управления – так в теории управления называют объект управления, интегрированный с системой управления в одно «устройство».

1.2. Особенности поддержки автоматного программирования на различных программных платформах поддерживалось следующими программными платформами:

контроллеров, например, лестничные схемы, функциональные блоки процедурные языки программирования, например, язык C [12];

объектно-ориентированные языки программирования, например, языки C++ [13] и Java [14];

функциональные языки программирования, например, языки Erlang [15] и Haskel [16];

динамические языки программирования, например, язык Ruby [17].

1.2.1. Cпециализированные языки программируемых логических контроллеров Программирование не сводится к программированию на языках общего назначения. Существует также специализированные языки программирования логических контроллеров и языки для программирования, например, аппаратуры VHDL [18].

рассмотрим язык функциональных блоков (Function Block Diagram). В работе [19] приведено несколько примеров преобразования автоматов в использование цифровых мультиплексоров. Реализация функционального блока цифровым мультиплексором может быть осуществлена с помощью конструкции switch какого-нибудь алгоритмического языка. Поэтому реализация графов переходов автоматов на цифровых мультиплексорах осуществляется практически также как и на конструкции switch в алгоритмических языках.

Для логических систем автоматное программирование напрямую не поддерживается, поэтому предлагается рисовать диаграммы состояний вручную, проводить формальный перевод в лестничные схемы или в функциональные блоки, а по построенной схеме генерировать программу.

1.2.2. Процедурное программирование При применении автоматного программирования для процедурного проектирование от объектов управления и событий. Ниже эти подходы рассматриваются для одного автомата.

В случае проектирования сверху вниз:

управляющих состояний.

2. Строится управляющий автомат программной системы: управляющие состояния связываются между собой переходами, добавляются входные и выходные переменные, необходимые для реализации заданного в словесном описании поведения. Если система является событийной, то определяется набор событий, обрабатываемых автоматом. Они включаются в условия переходов наряду с входными переменными.

3. Входным переменным автомата сопоставляются запросы: булевы функции или (реже) двоичные переменные. Выходным переменным – команды: процедуры. Если упомянутые подпрограммы являются недостаточно простыми для непосредственной реализации, для каждой из них производится цикл традиционного проектирования сверху вниз.

4. Вводятся переменные, необходимые для корректной реализации переменных определяет множество вычислительных состояний Автоматное проектирование сверху вниз целесообразно применять при проектировании всей системы с нуля.

При применении автоматного программирования в случае, когда объекты управления реализованы аппаратно или в виде готовых программных компонент, чаще используется проектировании от объектов управления и событий:

1. Исходными данными задачи считается не только словесное описание целевого поведения системы, но и (более или менее) точная спецификация набора событий, поступающих в систему из внешней среды, и множеств запросов и команд всех объектов управления.

2. Строится набор управляющих состояний.

3. Каждому запросу объектов управления ставится в соответствие входная переменная автомата, каждой команде – выходная. На основе управляющих состояний, событий, входных и выходных переменных строится автомат, обеспечивающий заданное поведение системы.

программировании используются диаграммы двух видов:

диаграмма переходов, описывающая состояния управляющего автомата, правила переходов между состояниями, действия в состояниях и на переходах, вложения автоматов в состояния и вызов автоматов;

схема связей, оп множест входн и вых прог граммиро пере еходов в код [8]. При этом каждому автомат соответ swit (или аналогичная), вет пере еменной состоян конс струкция case, внутри которой происхо возд действий, выполне сост тояния. Н языке C вы авто оматного програм прив ведена система StateFlo прог граммный авто оматное п Visio2Sw созданно в пакете Micros Visio [23];

MetaAuto [24] для генерации тела автоматной программы на различных Visio2Auto [25] для преобразования диаграмм Microsoft Visio в код на 1.2.3. Объектно-ориентированное программирование Для создания объектно-ориентированных автоматных программ в работе [26] предложен метод их разработки. При использовании этого метода при построении диаграмм в рамках SWITCH-технологии сохраняется автоматный подход, но применяется стандартная UML-нотации. При этом предлагается, используя нотацию UML-диаграмм классов, строить схемы связей автоматов, а графы переходов – используя нотацию UML-диаграмм состояний. При наличии нескольких автоматов их схема взаимодействия не строится, а они все изображаются на диаграмме классов. Диаграммы классов (как схема связей) и диаграммы состояний образуют предлагаемый графический язык для описания структуры и поведения программ.

Для проектирования программ с использованием этого языка предлагается следующий метод:

1. На основе анализа предметной области в виде UML-диаграммы классов разрабатывается концептуальная модель системы, определяющая сущности и отношения между ними.

2. В отличие от традиционных для объектно-ориентированного программирования подходов [27], из числа сущностей выделяются источники событий, объекты управления и автоматы. Источники событий активны – они по собственной инициативе воздействуют на автоматы. Объекты управления пассивны – они выполняют действия, которые вызываются автоматами. Объекты управления также могут формировать значения входных переменных для автоматов. Автоматы активируются источниками событий и на основании значений входных переменных и текущих состояний воздействуют на объекты управления, переходя в новые состояния.

3. Используя нотацию диаграммы классов, строится схема связей автоматов, которая задает интерфейс каждого их них. На этой схеме слева изображаются источники событий, в центре – автоматы, а справа – объекты управления. Источники событий с помощью UML-ассоциаций связываются с автоматами, которым они поставляют события. Автоматы связываются с объектами, которыми они управляют, а также с другими автоматами, которые они вызывают или которые вложены в их состояния.

4. Схема связей, кроме задания интерфейсов автоматов, выполняет функцию, характерную для диаграммы классов – задает объектноориентированную структуру программы.

5. Каждый объект управления содержит два типа методов, реализующих входные переменные (xj) и выходные воздействия (zk). При этом отметим, что объект управления инкапсулирует вычислительные состояния системы, которые обычно явно не выделяются из-за большого их числа.

6. Для каждого автомата с помощью нотации диаграммы состояний строится граф переходов типа Мура-Мили, в котором дуги могут быть помечены событием (ei), логической формулой из входных переменных и формируемыми на переходах выходными воздействиями.

7. В каждом состоянии могут указываться выходные воздействия, выполняемые при входе и имена вложенных автоматов, которые активны, пока активно состояние, в которое они вложены.

8. Кроме вложенности, автоматы могут взаимодействовать по вызываемости. При этом вызывающий автомат передает вызываемому событие, что указывается на переходе или в состоянии в виде выходного воздействия. Во втором случае посылка события вызываемому автомату происходит при входе в состояние.

9. Каждый автомат имеет одно начальное и произвольное число конечных состояний.

10. Состояния на графе переходов могут быть простыми и сложными. Если в состояние вложено другое состояние, то оно называется сложным. В противном случае состояние простое. Основной особенностью сложных состояний является то, что дуга, исходящая из такого состояния, заменяет однотипные дуги, исходящие из каждого вложенного состояния.

11. Все сложные состояния неустойчивы, а все простые, за исключением начального – устойчивы. При наличии сложных состояний в автомате, появление события может привести к выполнению более одного перехода. Это происходит в связи с тем, что, как отмечено выше, сложное состояние является неустойчивым, и автомат выполняет переходы до тех пор, пока не достигнет первого из простых (устойчивых) состояний. Отметим, что если в графе переходов сложные состояния отсутствуют, то, как и в SWITCH-технологии, при каждом запуске автомата выполняется не более одного перехода.

12. Каждая входная переменная и каждое выходное воздействие являются методами соответствующего объекта управления, которые реализуются вручную на целевом языке программирования. Источники событий также реализуются вручную.

13. Использование символьных обозначений в графах переходов позволяет весьма компактно описывать сложное поведение проектируемых систем.

Смысл таких символов задает схема связей. При наведении курсора на соответствующий символ на графе переходов во всплывающей подсказке отображается его текстовое описание.

Для поддержки этого метода автором и В. Гуровым было создано инструментальное средство UniMod, на основе которого В. Гуров защитил диссертацию на тему «Технология проектирования и разработки объектноориентированных программ с явным выделением состояний (метод, инструментальное средство, верификация)» [28]. Средство UniMod подробно описано в ряде работ [26, 29 – 40], опубликованных, в том числе и в журнале «Программирование» [41]. Это инструментальное средство обеспечивает валидацию автоматов и поддержку автозавершения пользовательского ввода.

Для программ, построенных с помощью средства UniMod, обеспечивается их автоматическая верификация [42 – 44].

В качестве еще одного инструментальных средства, которое базируется на использовании автоматов можно привести IBM Rhapsody, развившееся из системы Statemate [45], разработанной еще в 1983 году. За эту систему в 2007 году коллектив разработчиков, возглавляемый Д.

Харелом, получил премию ACM Software System Award.

1.2.4. Функциональные языки программирования Основное отличие функциональных программ от императивных состоит в том, что функциональная программа представляет собой некоторое выражение (в математическом смысле), а выполнение программы означает вычисление значения этого выражения.

При сравнении «чистого» функционального и императивного подходов к программированию можно отметить следующие свойства функциональных программ:

в чистых функциональных программах отсутствуют побочные эффекты, поэтому в них не существует прямого аналога глобальным переменным и объектам императивных языков программирования;

в функциональных программах не используется оператор присваивания;

в функциональных программах нет циклов, а вместо них применяются рекурсивные функции;

выполнение последовательности команд в функциональной программе бессмысленно, поскольку одна команда не может повлиять на выполнение следующей.

Отсюда следует, что при использовании чистых функциональных языков программирования (например, языка Haskell) не удается непосредственно применять методы, используемые при реализации конечных автоматов на императивных языках программирования. Это объясняется тем, что состояние автомата, по сути, является глобальной переменной, а обработка последовательностей событий в императивных языках производится при помощи циклов.

В работе [46] предложен метод реализации структурных автоматов на функциональных языках программирования на примере языка Haskell, при котором автомат представляется функцией переходов от состояния и события;

события задаются при помощи алгебраических типов данных;

цикл обработки событий реализуется в виде левой свертки списка событий по функции переходов.

императивными языками программирования является строгая типизация составных частей конечного автомата.

1.2.5. Динамические языки Реализация автоматов в коде с помощью описанных выше методов обладает следующими недостатками: в случае ручной реализации – трудоемкость изоморфного перехода от диаграммы к коду, в случае автоматической генерации кода – ухудшение читаемости кода. В работах [47, 48] предлагается использовать динамические возможности языка Ruby для создания проблемно-ориентированного языка для наиболее точной и изоморфной реализации автоматов в коде.

Для преобразования диаграммы переходов в код на этом языке предлагается использовать следующий метод:

1. Для каждой диаграммы создается новый класс с именем, совпадающим с названием автомата.

2. Внутри класса с помощью конструкций предлагаемого проблемноориентированного языка, описывается диаграмма переходов:

состояниям присваиваются идентификаторы, соответствующие их в описаниях переходов ссылки на состояния производятся по 3. Класс автомата связывается с неавтоматной частью программы через подписку на выходные воздействия автомата.

Ключевыми моментами использования языка Ruby являются полностью декларативное описание поведения системы и автоматическое порождение специальных методов, позволяющих переносить диаграмму переходов с незначительными изменениями.

1.3. Языково-ориентированное программирование В последние годы популярен подход к программированию, у которого много названий: модельно-ориентированный поход (model driven architecutre) [49], порождающее программирование (генеративное программирование) [50], метапрограммирование [51], ментальное программирование или программирование намерений (intentional programming) [52], языково-ориентированное программирование [53]. Все эти названия отражают различные аспекты общего подхода к разработке ПО, и, так или иначе, связаны с разработкой проблемно-ориентированных или предметно-ориентированных языков (domain specific language) [54].

1.3.1. Модельно-ориентированный подход Модельно-ориентированный подход к разработке программных систем состоит в описании функциональности систем в виде платформонезависимых моделей (platform-independent model) с помощью специальных проблемно-ориентированных языков программирования. Далее, имея модели описания платформы (platform definition model), такие как CORBA [55],.NET [56], WEB и т. п., платформо-независимые модели транслируются в платформо-зависимые модели (platform-specific model), которые могут быть запущены на компьютерах. Подобная трансляция требует задания правил отображения, которые также предлагается моделировать.

Платформо-зависимые модели могут быть описаны с помощью различных проблемно-ориентированных языков или языков общего назначения (например, Java, C#, PHP, Python). Как правило, для трансляции моделей используются автоматизированные средства.

Принципы модельно-ориентированного подхода применимы и в других областях, например, для моделирования бизнес-процессов [57], где платформо-независимые модели «транслируются» в автоматизированные или ручные процессы.

1.3.2. Порождающее программирование Порождающее программирование рассматривает другой аспект программирования. В работе [50] авторы сравнивают традиционное программирование с самостоятельной сборкой автомобиля конечным пользователем. Имеется в виду сборка программных систем из готовых компонент, в процессе которой программисту приходится дополнительно писать низкоуровневый код для интеграции компонент друг с другом.

При применении порождающего программирования предлагается настраивать и связывать компоненты с помощью высокоуровневых средств, а низкоуровневый код порождать автоматически. В качестве таких высокоуровневых средств могут быть использованы, например, проблемноориентированные языки программирования.

1.3.3. Метапрограммирование Метапрограммированием называется написание программ (например, кодогенераторов), которые используют код других программ или свой метапрограммированием понимается выполнение во время компиляции части работы, которую в противном случае пришлось бы выполнять во время исполнения. Во многих случаях применение метапрограммирования позволяет решать задачи более гибко и эффективно, чем при написании кода вручную.

Языки написания метапрограмм называются метаязыками. Языки, код на которых используется в качестве данных, называются объектными языками. Способность языков быть метаязыками для самих себя называется рефлексией (reflection) [58].

возможности метапрограммирования одним из трех способов. Первый из них состоит в предоставлении программному коду доступа к внутренностям среды исполнения в виде программных интерфейсов приложений (application programming interface). Второй – динамическое выполнение строковых выражений, содержащих программный код. В этом случае «программы могут писать программы». Несмотря на то, что оба подхода могут совмещаться в одном языке, большинство языков ориентированы на один из них.

Третий способ состоит в том, чтобы выйти за рамки языка и использовать средства трансформации программ, которые принимают на вход описания языков и могут применять различные правила трансформации к коду на этих языках. Эти средства метапрограммирования общего назначения могут применяться к любым целевым языкам вне зависимости от метапрограммирования.

1.3.4. Ментальное программирование программирования состоит в приведении программного кода к виду как можно более точно отражающему ход мысли программиста. Точное воспроизведение уровня абстракции, на котором программист мыслит, упрощает навигацию и сопровождение программ.

Ч. Симони предлагает строить программные системы следующим образом. Программист сначала создает инструментальные средства разработки, специфичные для заданной предметной области. Затем эксперты в этой предметной области, применяя созданные средства разработки, автоматизированная среда разработки порождает по описанному поведению целевой код программы. Компания Intentional Software [52], основанная Ч. Симони, занимается разработкой подобной среды программирования, которая называется Intentional Programming (IP).

Ключевой особенностью среды IP является то, что исходные коды хранятся не в текстовых файлах, а в бинарных. Такой формат хранения подобен языку XML [59] в том, что так же как и язык XML не требует специального синтаксического анализатора для каждой конструкции языка.

Это упрощает создание инструментов для работы с таким кодом.

Тесная интеграция редактора кода с бинарным форматом хранения позволяет привнести в код полезные свойства нормализации баз данных.

Избыточность устраняется присваиванием каждому объявлению уникального идентификатора, что позволяет хранить имена всех переменных и операторов в единственном экземпляре. Многие задачи рефакторинга кода [60] и навигации при этом существенно упрощаются. Также в бинарном представлении не сохраняется информация о пробелах и символах разделителях, и таким образом каждый программист, работающий с проектом, может выбрать размер отступов при отображении кода в редакторе.

порождающем программировании. Поскольку предлагаемый ими подход позволяет создавать проблемно-ориентированные языки без вложений в написание компилятора и среды разработки.

1.3.5. Языково-ориентированное программирование При рассмотрении подходов, требующих разработки проблемноориентированных языков, часто основным достоинством считается то, что, создав однажды проблемно-ориентированный язык для некоторой предметной области, можно в дальнейшем использовать его многократно для более выразительного и компактного написания программ в данной предметной области. Предложенное Мартином Вардом [53] и развитое Сергеем Дмитриевым [61] языково-ориентированное программирование допускает создание проблемно-ориентированных языков даже для однократного применения.

М. Вард предлагает вместо традиционной «водопадной» модели разработки ПО [62] использовать модель «изнутри-наружу». В этой модели разработка программной системы начинается с создания проблемноориентированного языка программирования, затем одна группа программистов реализует отображение конструкций этого языка в конечный код, а другая – описывает требуемое поведение системы на этом языке.

Таким образом, устраняются риски свойственные моделям «сверху-вниз» и «снизу-вверх».

В модели «сверху-вниз» система изначально проектируется в самом общем виде, а затем последовательно уточняется. При этом существующие спецификации часто неформальны и допускают разночтения. Это приводит к тому, что на ранних стадиях разработки возникают ошибки, которые в дальнейшем крайне трудно устранить, так как они проникают во все уровни системы. При программировании «изнутри-наружу» такой проблемы нет, так как проблемно-ориентированный язык подходит для формальной спецификации поведения программы. Более того, изменения спецификации в процессе разработки не требуют изменений в реализации проблемноориентированного языка.

низкоуровневые утилиты и процедуры, которые используются для создания более высокоуровневых процедур и типов данных и так далее до тех пор, пока не будет реализован самый верхний уровень системы. Такой подход позволяет последовательно создавать и тестировать компоненты системы, но на ранних стадиях такой разработки не вполне ясно, какие именно утилиты и процедуры потребуются, что приводит к созданию большого числа лишнего кода.

1.3.6. Среда языково-ориентированного программирования Проблемно-ориентированными языками являются языки, специально предназначенные для решения задач из некоторой предметной области.

Например, такими языками являются язык структурных запросов (SQL) [63] для работы с базами данных, язык задания регулярных выражений (regular expressions) [64] для поиска подстрок по шаблону, язык запросов к элементам XML-документа (XPath) [65] для манипуляций с XML-документами. Сильная связь проблемно-ориентированных языков с предметной областью позволяет с их помощью описывать и решать задачи из данной предметной области очень компактно и выразительно. В теории применение проблемноориентированных языков выглядит достаточно просто: выделить для некоторой предметной области набор абстракций; создать язык, поддерживающий эти абстракции; решить программистскую задачу на этом программировании проблемно-ориентированные языки создаются редко.

В работе [66] М. Фаулер предполагает, что главным образом препятствует этому две причины. Во-первых, на практике, вместо расширений к существующим языкам общего назначения, прежде всего, рассматривается разработка замкнутых [67] проблемно-ориентированных языков. Это, возможно, связано с потенциальной неоднозначностью в текстовых языках программирования конструкций из разных языковых расширений. Во-вторых, создание развитой интегрированной среды разработки, поддерживающей созданный язык, является крайне трудоемкой задачей, а современная промышленная разработка ПО без использования такой среды невозможна в силу малой эффективности [68]. Далее эти причины будут рассмотрены подробнее, и будет показано, как они устраняются при применении среды метапрограммирования MPS.

Несмотря на то, что значительная часть усилий разработчиков самостоятельных языков, большей ценностью могут обладать языковые расширения, добавляющие новые проблемно-ориентированные конструкции в языки общего назначения, например, в язык Java. Языковые расширения, которые можно создавать и использовать также легко, как сейчас создаются и используются библиотеки и каркасы, значительно ценнее для разработчика, чем самостоятельный проблемно-ориентированный язык, используемый лишь для части программы. Подобный подход позволяет разработчику одновременно пользоваться высоким уровнем абстракции проблемноориентированных языков программирования и мощью языков общего назначения.

Создаваемые расширения к языкам общего назначения должны быть совместимы друг с другом. Без совместимости переиспользование языковых расширений крайне затруднено. Совместимость означает, что если существует пара языковых расширений, например, одно, добавляющее в язык работу с денежными значениями, и другое, расширяющее математическую нотацию языка общего назначения новыми операциями, то должна существовать возможность использовать эти расширения совместно, несмотря на то, что они могут быть созданы независимо разными разработчиками.

Для решения задач расширяемости языков общего назначения и совместимости расширений, необходимо решить проблему неоднозначности конструкций в текстовых языках программирования. Большинство существующих языков реализовано с помощью текстовых грамматик, но такие грамматики могут быть неоднозначны – могут допускать различные интерпретации одинаковых программ. Более того, если удается по отдельности устранить неоднозначность для языка общего назначения с расширением A и для того же языка общего назначения с расширением B, то это еще не означает отсутствия неоднозначности в грамматике этого языка общего назначения с расширениями A и B одновременно. Это в результате приводит к возможной несовместимости таких языковых расширений.

Для продуктивной работы разработчикам необходимы «умные»

средства разработки. С тех пор как получили распространение такие редакторы кода, как IntelliJ IDEA [69] и Eclipse [70], в промышленной разработке обычные текстовые редакторы практически перестали использоваться. В обычных редакторах, например, нет подсветки ошибок, контекстной справки, функций автодополнения ввода. Существуют программные каркасы для «умных» редакторов, позволяющие добавлять поддержку для произвольных языков программирования, например, IntelliJ IDEA Language API, XText [71] и Oslo [72]. Однако эти каркасы не поддерживают совместимые языковые расширения. Кроме того, даже промышленного качества занимает много времени и требует высокой квалификации в области теории построения компиляторов.

Для устранения перечисленных препятствий к языковоориентированной разработке в компании JetBrains была разработана среда метапрограммирования MPS, позволяющая быстро создавать языки программирования. Исторически термин «языково-ориентированное программирование» получил распространение позже начала работы над средой MPS, поэтому в названии использован близкий по смыслу термин «метапрограммирование». Тем не менее, среда, прежде всего, предназначена именно для языково-ориентированного программирования.

Неоднозначность текстовых грамматик устраняется в среде MPS отказом от хранения кода программ в текстовом виде. Отсутствие текстового кода избавляет от необходимости в текстовых грамматиках и, как следствие, анализаторах. Вместо этого код хранится и редактируется его в виде абстрактного синтаксического дерева (АСД) [73]. Из этого, однако, не следует, что у языков среды MPS нет грамматик, но это не текстовые, а абстрактные грамматики. Абстрактная грамматика непосредственно описывает абстрактный синтаксис языка. Подобным образом язык XML Schema описывает грамматику XML-документов.

Отсутствие грамматической неоднозначности позволяет легко комбинировать языки друг с другом. Среда MPS позволяет добавлять новые конструкции в существующие языки (языковые расширения) и внедрять языки общего назначения в проблемно-ориентированные языки программирования. Поэтому языки в среде MPS совместимы. Например, для среды MPS создано множество совместимых расширений языка Java:

язык для работы с коллекциями в функциональном стиле (collections);

язык для поддержки дат и операций над ними (dates);

язык, позволяющий использовать различные математические операции в привычной нотации, например, суммы и интервалы и т.д.

Так как языки в среде MPS не хранятся в текстовом виде, для редактирования кода невозможно использовать обычные текстовые редакторы. Для непосредственного редактирования АСД в среде MPS применяются проекционные редакторы [52]. При этом для каждого узла синтаксического дерева создается проекция – элемент графического пользовательского интерфейса. Взаимодействуя с проекциями узлов синтаксического дерева, пользователь редактирует его. Проекционные редакторы в среде MPS реализованы таким образом, что использование их практически не отличается от редактирования обычного текста. Например, если пользователь символ за символом вводит выражение «1 + 2 + 3», то среда MPS построит правильное АСД для этого выражения. Не все особенности ввода текстового кода удается воспроизвести для проекционных редакторов. Однако опыт промышленного применения среды MPS показал [66], что для адаптации нового разработчика к среде MPS требуется около двух недель, после которых разработчик редактирует код в среде MPS не менее эффективно, чем делал это ранее при помощи «умных» редакторов кода.

Хранение кода в виде АСД упрощает разработку возможностей «умного» редактирования кода. Многие из таких возможностей среда MPS предоставляет для всех новых языков автоматически, например, автодополнение кода, поиск использований, рефакторинги переименования и безопасного удаления, поддержка систем контроля версий. Ранее в компании JetBrains была создана интегрированная среда разработки IntelliJ IDEA, для которой была добавлена поддержка большого числа текстовых языков и технологий программирования. В работе [66] указывается, что поддержка одного языка или технологии для среды IntelliJ IDEA занимает несколько человеко-месяцев, а реализация такой же функциональности в среде MPS занимает всего несколько дней. Такая эффективность достигается наличием в указанной среде готовой инфраструктуры и проблемно-ориентированных языков для конфигурирования этой инфраструктуры под разрабатываемый язык. Таким образом, в среде MPS по принципу раскрутки (bootstrapping) созданы проблемно-ориентированные языки для предметной области «разработка языков».

Кроме создания «умного» редактора среда MPS позволяет задавать и другие аспекты языков: системы типов, генераторы кода, потоки данных и т. д.

1.4. Задачи в области автоматного языково-ориентированного программирования, требующие своего решения В настоящее время среда MPS успешно применяется в промышленной разработке. При участии автора в процессе создания в указанной среде системы учета программных ошибок YouTrack, было разработано около несколько проблемно-ориентированных языков программирования различных классов. В силу специфики и новизны подхода, реализация каждого из языков требует дополнительных исследований, так как простота создания языков в среде MPS открывает множество качественно новых возможностей. В ходе разработки указанной системы выявилась необходимость создания инструментальных средств для поддержки автоматного программирования, так как оно наилучшим образом подходит для описания сущностей со сложным поведением.

диссертации связан с тем, что автор в течение последних восьми лет проводил исследования в этой области, используя и создавая различные средства автоматного программирования, начиная от применения автоматного программирования в разработке на Macromedia Flash [74] интерактивных обучающих программ [75 – 79], и кончая соавторством в разработке инструментального средства UniMod, которое опубликовано на сайте sourceforge.net, и скачано более 60 000 раз.

1.4.1. Валидация автоматных моделей Для уменьшения числа ошибок при разработке автоматных программ необходимо проводить валидацию разрабатываемых автоматных моделей.

Валидацией таких моделей называется проверка свойств автоматов, которые не зависят от пользовательской спецификации. Такими свойствами являются:

достижимость любого состояния из начального состояния;

достижимость из любого состояния конечного состояния;

полнота и непротиворечивость [8] условий на переходах.

одноместными предикатами сравнения в условиях на переходах была решена автором ранее [80]. Для дальнейшего увеличения выразительной мощности автоматных моделей необходимо расширить класс формул для выражений условий на переходах двуместными предикатами сравнения входных переменных.

1.4.2. Автоматы в многопоточных средах В связи с тем, что дальнейшее повышение производительности вычислительных систем более не может достигаться увеличением тактовой частоты процессоров, и главной тенденцией становится рост числа ядер в них [81], растет актуальность разработки параллельных программ [82].

Однако для того, чтобы программа выполнялась эффективно на нескольких ядрах, она должна быть написана с применением техник параллельного программирования [83].

наиболее распространенные на сегодняшний день, хорошо подходят для реализации последовательных алгоритмов, но плохо приспособлены для написания алгоритмов параллельных. Это связано с тем, что программа, написанная на императивном языке, представляет собой последовательность инструкций процессору, изменяющих состояние памяти [85]. В виду того, что порядок этих команд зафиксирован, выполнение программы не может быть распределено между несколькими процессорами. Поэтому программисты вынуждены самостоятельно разбивать свою программу на параллельно выполняющиеся потоки [86].

Автоматическому распараллеливанию хорошо поддаются программы, написанные на функциональных языках программирования [4, 87]. Но функциональные языки, в отличие от императивных, значительно менее распространены. Тем не менее, некоторые функциональные конструкции в последнее время стали активно проникать в универсальные императивные языки программирования. Например, становится популярным использование в императивных языках замыканий [88] для обработки списков, так как в некоторых случаях [89] это позволяет выполнять автоматическое распараллеливание по данным [90].

параллельных функциональных программ для императивных языков программирования и, в частности, для автоматного программирования.

1.4.3. Задачи, решаемые в диссертации Среда MPS обладает следующими особенностями, которые приводят к необходимости новых разработок в рамках автоматного программирования:

1. Специфика создания языков, без разработки компиляторов.

2. Возможность встраивать сообщения об ошибках на лету в процессе программирования позволяет сообщать об ошибках валидации. В известных системах программирования автоматов, например, Rational Rose (IBM) отсутствовала автоматическая проверка полноты и реализованные исходно таким образом автоматы функционировали некорректно. В инструментальном средстве UniMod валидация выполнялась, но увеличение выразительной мощности выражений условий на переходах, приводит к необходимости разработки новых методов валидации автоматов.

3. Возможность интеграции в среде MPS языков друг с другом. Поэтому открылась возможность построения языковых средств многопоточного использование общей памяти, что приводит к необходимости синхронизации потоков непосредственно в программном коде.

исследования, которые легли в основу данной диссертации. При этом задачи, решаемые в диссертационной работе, состоят в следующем:

1. Разработка текстового языка автоматного программирования (абстрактного и конкретного синтаксиса, операционной семантики, системы типов, генераторов).

2. Разработка средства валидации автоматов в среде MPS.

3. Создание языка для многопоточного программирования и интеграция его с автоматным языком, позволяющих отказаться от использования программировании.

4. Внедрение результатов работы в учебный процесс и в практику проектирования языков и программных систем в среде MPS.

Выводы по главе 1. Выполнен обзор особенностей автоматного программирования в программирования.

2. Выполнен обзор различных взглядов на метапрограммирование и обоснована целесообразность исследования в области автоматного программирования для среды языково-ориентированного программирования.

3. Сформулированы особенности среды языково-ориентированного программирования, приводящие к необходимости создания новых подходов к автоматному программированию.

4. Сформулированы задачи, решаемые в диссертации.

ГЛАВА 2. ТЕКСТОВЫЙ ЯЗЫК АВТОМАТНОГО

ПРОГРАММИРОВАНИЯ

В рамках проекта UniMod [32] предложены метод и средство для моделирования и реализации объектно-ориентированных программ со сложным поведением на основе автоматного подхода. Модель системы в рамках указанного проекта предлагается строить с помощью двух типов UML-диаграмм: диаграмм классов и диаграмм состояний [30]. При этом на диаграмме классов, которая представляется в виде схемы связей и взаимодействия автоматов, изображаются источники событий, автоматы и объекты управления, которые реализуют функции входных и выходных воздействий. Код для источников событий и объектов управления пишется на языке Java. Поведение автоматов описывается с помощью диаграмм состояний.

С использованием инструментального средства UniMod выполнен ряд проектов, который доступны по адресу http://is.ifmo.ru/unimod-projects/.

Данные проекты показали эффективность применения автоматного программирования и средства UniMod при реализации систем со сложным поведением, но также выявили и ряд недостатков:

трудоемок;

представлением программы, несмотря на то, что диаграммы позволяют представлять информацию более обозримо;

невозможно в одном Java-классе совместить автомат и объект управления, что не позволяет прозрачно использовать автоматное программирование совместно с объектно-ориентированным, так как в настоящее время код, генерируемый из автоматной модели, не является в полной мере объектно-ориентированным.

2.1. Текстовые языки автоматного программирования В настоящее время существует несколько текстовых языков, поддерживающих программирование автоматов, как в рамках автоматной парадигмы (UniMod FSML [91], State Machine [92]), так и вне ее (SMC [93], программирования обладает некоторыми недостатками и ограничениями.

Язык State Machine, представляет собой расширение языка Java, основанное на паттерне проектирования State Machine [97]. Этот паттерн позволяет в объектно-ориентированном стиле описывать структуру автомата, однако такое описание оказывается громоздким, что препятствует использованию языка State Machine в реальной разработке.

Язык SMC – универсальный компилятор автоматов. Этот язык позволяет описывать в автоматы в едином формате и генерировать целевой код на различных языках общего назначения. Однако интеграция этого языка с целевыми языками требует от разработчиков дополнительных усилий – необходимо существенно модифицировать код класса для того, чтобы связать его с автоматом, описывающим его поведение.

В универсальном языке программирования ТАВР предусмотрены встроенные конструкции, облегчающие написание автоматов. Однако синтаксис этого языка вынуждает разработчика оперировать понятиями более низкоуровневыми, чем «состояние». Кроме того, универсальность языка ТАВР доставляет дополнительные трудности разработчику, связанные с необходимостью изучать конструкции нового языка даже для тех задач, для которых подходят более распространенные универсальные языки.

Язык Ragel предназначен для описания конечных автоматы с помощью регулярных выражений. Такой подход ограничивает область применимости этого языка задачами лексического анализа и спецификации протоколов, автоматов Харела [2]. Использовать этот язык непосредственно для написания кода автоматов на нем крайне затруднительно, скорее он подходит для переноса автоматов Харела из одного приложения в другое.

использовать автоматы при программировании. Это доказывает популярность автоматного подхода для решения различных задач программирования. Однако перечисленные недостатки затрудняют его применение. Кроме того для перечисленных языков не существует развитых программистов отдает предпочтение языкам общего назначения, такие средства существуют.

2.2. Создание языков в среде MPS Для устранения указанных недостатков при участии автора был предложен новый подход к разработке автоматных программ и применению автоматов в объектно-ориентированных системах [98, 99]. В рамках этого подхода предлагается использовать среду языково-ориентированного программирования MPS [61], которая позволяет создавать проблемноориентированные языки.

Для задания языка в среде MPS требуется разработать:

структуру абстрактного синтаксического дерева (АСД) [73] для разрабатываемого языка. Узлам АСД могут соответствовать такие понятия как «объявление класса», «вызов метода», «операция сложения»

модель проекционного редактора для каждого типа узла АСД. Задание редактора для узла АСД равноценно заданию конкретного синтаксиса для этого узла. При этом если для традиционных текстовых языков программирования создание удобного редактора – отдельная сложная задача, то для языков, созданных с помощью среды MPS, редакторы являются частью языка. Эти редакторы поддерживают автоматическое завершение ввода текста, навигацию по коду, выделение цветом ошибок в коде программы и т. д.;

модель системы типов [100] для языка;

модель трансформации программы на задаваемом языке в исполняемый Таким образом, создание языка в среде MPS сопровождается созданием инструментального средства разработки программ на этом языке.

Отметим, что среда MPS позволяет, как создавать новые языки, так и расширять языки уже созданные с помощью этой системы.

В отличие от традиционных языков, языки, созданные с помощью среды MPS, не являются текстовыми в традиционном понимании, так как при программировании на них пользователь пишет не текст программы, а вводит ее в виде АСД с помощью специальных проекционных редакторов.

Структура и внешний вид этих редакторов таковы, что работа с моделью программы для пользователя выглядит, как традиционная работа с текстом программы. Отказ от традиционного текстового ввода программ значительно упрощает создание новых языков [52] – исчезает необходимость в разработке лексических и синтаксических анализаторов, и, как следствие, перестают действовать ограничения на класс грамматик языков. Недостатком такого подхода является зависимость языков от среды MPS – невозможно разрабатывать программы без этой среды. Однако подобное ограничение присуще и традиционным, чисто текстовым языкам, которые зависят от компиляторов. Впрочем, после трансляции программы, написанной на языке, созданном в среде MPS, исполняемый код перестает зависеть от этой среды.

Ядро среды MPS написано на кросс-платформенном языке Java. В связи с этим в среде MPS существуют развитые средства для взаимодействия с Java-платформой. Среда MPS позволяет писать код только на тех языках, которые созданы в этой среде, поэтому для написания Java-кода в среде MPS разработан язык baseLanguage. Этот язык является почти полной реализацией спецификации Java 5 [101]. В нем определены такие конструкции, как «класс», «интерфейс», «метод», «предложение», «выражение» и т. д.

2.3. Язык stateMachine Разработанный автором язык автоматного программирования в среде MPS назван stateMachine. Он представляет собой автоматное расширение языка baseLanguage. Основная цель, которая преследовалась при разработке языка stateMachine, – создание языка, позволяющего описывать поведение классов в виде автоматов, не накладывая на сами классы никаких дополнительных ограничений. Более того, автоматное описание поведения класса должно быть инкапсулировано – код, использующий класс не должен «знать» о том, каким образом задано поведение класса. Этот подход отличается от предложенного в работе [32] тем, что позволяет использовать автоматы не только в программах, написанных в соответствии со SWITCHтехнологией, но и в традиционных объектно-ориентированных программах.

В качестве примера использования языка stateMachine рассмотрим систему управления лифтом [102]. При этом отметим, что функциональность этой системы меньше по сравнению с системой, описанной в работе [103].

Поэтому логика управления всеми подсистемами лифта реализована в одном автомате.

Каждый автомат в языке stateMachine связан с некоторым классом и описывает его поведение. Для того чтобы задать поведение класса с помощью автомата необходимо в этом классе определить события, на которые будет реагировать автомат. Особенностью языка stateMachine является то, что события в нем – это методы специального вида. В языке Java декларации методов различаются по способу реализации:

обычные методы, реализация которых следует сразу за объявлением нативные методы, реализованные на платформо-зависимых языках программирования;

абстрактные методы, которые вообще не имеют реализации, непосредственно связанной с декларацией.

В диссертации предлагается еще один способ реализации – декларация метода, реализация которого находится в автомате и зависит от текущего его состояния. Для этого язык stateMachine расширяет язык baseLanguage конструкцией событие (EventMethodDeclaration), соответствующего указанной декларации метода. Например, в классе Elevator объявлены следующие события (рис. 1):

«doorsOpened», «doorsClosed» – события, которые посылает объект управления DoorsEngine, когда двери оказываются в максимально открытом и полностью закрытом положении соответственно;

«floorReached» – событие, которое посылает объект управления ElevatorEngine, когда лифт достигает очередного этажа;

«call» – событие, которое получает автомат, когда пассажир нажимает кнопку вызова лифта на этаже или в кабине лифта;

«openDoors» – событие, которое получает автомат, когда пассажир нажимает кнопку экстренного открытия дверей в кабине лифта;

«loadingTimeout» – событие, которое посылает объект управления LoadingTimer, когда истекает время ожидания погрузки пассажиров;

«fire» – событие, которое автомат получает в случае обнаружения возгорания.

испо ользовать в качес умен ньшить число зависим прое ектирован «Обо ния озреватель [97]. Например в рассм объе управления ElevatorEn клас Elevat инте ерфейс E изве ещает о событиях экземпля этого интерфей Клас Elevato реализу инте ерфейс E объе екта упра Реакц автомата на соб нахо одится. В каждом состояни для каж набо перех ор ходов. Дл перехо дейс ствие на переходе и целев состо для текущего состояния перебираются все переходы, помеченные данным событием, до тех пор, пока не будет найден первый переход, условие на котором выполняется. Если такой переход найден, то выполняется действие на переходе и осуществляется переход в целевое состояние. Отсутствие условия на переходе интерпретируется, как тождественно истинное условие.

События в языке stateMachine могут иметь параметры. На переходе с каждым параметром события может быть связано фильтрующее значение.

Если такое значение задано, то переход выполняется только, если значение параметра обрабатываемого события совпадает с фильтрующим значением.

Состояния автомата бывают двух типов: обычные и конечные.

Конечные состояния отличаются тем, что не могут иметь исходящих переходов. Следовательно, когда автомат оказывается в конечном состоянии, он перестает обрабатывать события.

Для состояния могут быть определены действия при входе в состояние и действия при выходе из состояния.

Первое по порядку состояние, объявленное в автомате, считается начальным. При создании экземпляра класса, для которого определен автомат, после выполнения конструктора осуществляется переход в начальное состояние.

Обычные состояния могут быть вложены друг в друга. При этом если состояние содержит другие состояния, то оно называется составным. При переходе в составное состояние выполняется переход в первое по порядку вложенное в него состояние. Поэтому автомат после обработки события не может оказаться в составном состоянии. Каждый исходящий из составного состояния переход работает так, как если бы такой переход был добавлен к каждому вложенному состоянию.

Каждый автомат в языке stateMachine связан с некоторым классом, имеет доступ к его полям и может вызывать методы этого класса. Поэтому в языке stateMachine нет необходимости в специальных конструкциях для взаимодействия между автоматами, так как вместо вложения одного автомата в другой можно использовать агрегацию одного автоматного класса другим автоматным классом, а посылка события из одного автомата в другой не что иное, как вызов метода.

С каждым автоматом может быть связано несколько объектовслушателей (listener), которые оповещаются о стадиях обработки события.

Например, таким слушателем может быть объект, выводящий сообщения о действиях автомата в специальный файл протокола работы автомата.

Слушатели оповещаются о следующих стадиях работы автомата:

начало и завершение обработки события;

переход в состояние и переход из состояния;

проверка условия на переходе;

обнаружение для текущего состояния и данного события переход, условие на котором выполняется;

игнорирование события, для которого не обнаружено перехода из текущего состояния;

начало и завершение выполнения действия на переходе;

начало и завершение выполнения действия при входе в состояние;

начало и завершение выполнения действия при выходе из состояния.

После написания программы на языке stateMachine, она сначала транслируется в Java-код, а затем компилируется стандартным Javaкомпилятором. Достоинством этого языка является простота его использования в объектно-ориентированных приложениях, написанных на языке Java. При применении этого языка проверка корректности программы выполняется на стадии ее написания, а не в процессе компиляции.

2.4. Струк 2.4.1 Метаязык опис рактный синтакси языка задается в среде MPS пр помощ проб блемно-о опис сывать ти меж жду ними в объе прим мера при язык stateM вление концепта определя (узл АСД) – какие свойства узел мо ссыл латься, и какие узлы он может содержать в качес определении концепта также задаются метасвойства (concept property) и метасвязи (concept links), описывающие структуру самого концепта, а не его узлов.

2.4.2. Иерархия концептов Существует два типа концептов: собственно концепты и интерфейсы концепта. Интерфейсы концепта применяются для описания особенностей, которые могут быть реализованы несколькими разными концептами.

Например, если некоторый концепт имеет имя, по которому на него можно ссылаться, то он может реализовывать интерфейс концепта INamedConcept.

Используются интерфейсы концептов так же, как интерфейсы в объектноориентированных языках программирования.

Любой концепт может наследоваться от другого концепта и реализовывать несколько интерфейсов концепта. Эта система похожа на иерархию классов в языке Java, где класс может наследоваться от другого класса и реализовывать несколько интерфейсов, а интерфейсы могут наследоваться от других интерфейсов. Когда концепт наследуется от другого концепта или реализует интерфейс, он транзитивно наследует все члены родительских концептов и реализованных интерфейсов.

2.4.3. Свойства Для каждого концепта и интерфейса концепта может быть определен набор свойств (properties). Значения свойств хранятся внутри экземпляров концепта. Каждое свойство имеет один из следующих типов:

примитивный тип, например, логический, строковый и целочисленный;

перечислимый тип, имеющий значение из предопределенного набора значений;

ограниченный тип – строковый тип, множество значений которого ограничено регулярным выражением.

конц цепта INa 2.4.4 Ссылк Узлы АСД мог иметь ссылки (reference на дру ссыл объяв иметь экземп (наз звания), т типа и мощности Тип ссылки накладыва конц цепт узл на который ве ссыл данно типа может им мощ щностей: « конц цепта мо ожет иметь, а мож и не иметь соответст мощ щность «1 означа что у един нственном экземпляре. Н соот тветствую ссыл even ntParamet 2.4.5 Дочерн узлы опре еделяется какие узлы могут быт агреги конц цепта. К (наз звания), т концепты узлов, ко конц цепта. До очерним может бы узел концепта, указанн ого в кач или любого унаследо данн групп дочер доче ерних узл данно группы может содержать внутри одного узла. Все сущ ществует ч 0..1 – но или од дочер 2.4.6 Метасв конц цепта, а не для его узлов приме Мет тасвойст и мет для всех узл конце мет тасвойств и мет ва тасвязи отличаются от статическ объе ектно-ори сред MPS использу общ конце щем епте BaseConcept и имеет ло концепты в среде MPS прямо или косвен конц цепта Ba aseConcep так же как в языке Java все классы прямо и косв венно нас сред MPS м Истинные зн упом минанием метасв Abst tractState в язык stateM мета асвойства (concep propert abst tract (рис. 6).

асвойства

Abstract

для концеп AbstractState

2.4.7 Шабло метапр мета асвязи. Н испо ользуется шаблон метапро Этот шаблон применя опци иональны опци иональны дочерн узлов задаются в виде метасвязи Базовым концептом дл всех элементов (опций) автомат являет инте ерфейс концепта элем ментов а (рис 7).

пере еходы, де реал лизовыват интерфейс кон элем реал лизовыват интер пом мощью ме етасвязи applicable каче естве эле объя явление концепта Abstrac конц цептом-эл элем ментов ав 2.4.8 Диагра язык в ср ка реде MP позвол пред дставлени струк пред дставлена диаграм классо для ко Концепты, помеченные стереотипом «baseLanguage», принадлежат языку baseLanguage. Для упрощения диаграммы на ней не упомянуты интерфейсы концептов IStateElement и IStateElementHolder.

2.5. Конкретный синтаксис языка stateMachine Для задания конкретного синтаксиса языка в среде MPS применяется проблемно-ориентированный метаязык editor. Этот метаязык позволяет для каждого концепта указать правила отображения экземпляров этого концепта в набор ячеек проекционного редактора.

Проекционный редактор среды MPS состоит из ячеек, которые могут содержать другие ячейки, некоторый текст или компонент графического пользовательского интерфейса. Проекционный редактор для узла является его отображением и контроллером. Проекционный редактор отображает узел и позволяет редактировать его свойства, добавлять и удалять его дочерние узлы.

проекционного редактора называется редактором концепта. С каждым неабстрактным концептом связан редактор. Если редактор не задан для концепта явно, то используется редактор его базового концепта.

2.5.1. Типы ячеек в языке editor Для задания редакторов концептов метаязык editor позволяет использовать ячейки следующих типов:

константная ячейка. Ячейки этого типа могут содержать только фиксированный, предопределенный при объявлении текст. Константные ячейки, как правило, используются для отображения ключевых слов языка, операторных скобок и т. п.;

коллекция ячеек – ячейка, в которую вложены другие ячейки. Коллекция ячеек может быть:

ячейка с Изменен польз значения свойств ячейка с ссылки состоит из двух частей: левая час указы ссылки, правая определяе внешн концепт EventPa соответс отображ концепт EventP использо ования параметра событи в проекционно редак представ ячейка д концепт в кото ячейка к коллекции дочерни узлов – ячейка, содержащ неско дочерни узлов одной роли. На переходе (конце дочерни узлов с ролью ev с. ользовани е ячейки коллекции дочерних узлов в редакторе размеще поддерж автомати ячейка м условная ячейка позволя некоторое услов сокрыти необход димости показыват скобки вокруг списка па ячейка компоне редактор (рис. 12), а в ре 2.5.2 Стили ячеек пред дставлени Например, цв выд делять в р ячей йки. Табл лица стил может быть ли встроенной (оп ячей йкой в редакторе концепт испо ользована в нескол разл личных ц стил лей для ключевых слов – примен реда акторах я языка baseLanguag которы соотве язык Java; с ке статическ полей – приме поле и ссыл на ст ей лок татически поля; полей объ стро оковых ли base eLanguage поэтом в язык stateMa объя явленные в языке baseLang един нообразие в коде, написанн на смеси этих языков.

ицы стилей ячеек задаютс в виде подобн стил в язы CSS [104]. На рис. 14 представл фрагм стил языка baseLang 2.5.3 Редакт реда акторов (р 15 – рис. 19).

Рис. 17. Редактор конечног состоян (конце FinalSt Рис. 1 Редактор действи по вход в состо 2.6. Систе типо язык stateM мета аязык typ pesystem [105]. Это метаязы позвол типо для к прив водимост типов. Среда MPS, исп выводит тип для ко оши ибки прив лету – в про ема типов языка stateMachine явля типо языка baseLang сред MPS проверял напри дост таточно з к ти boolea языка baseLangu Среда MPS позволяет использовать в качестве типов экземпляр люб бых концептов. В языке ba конц цептов, б базовым концепто которо являет конце АСД для кон Д, нцептов которых о узел типа, ко роцессе ге 2.6.1. Правила вывода типов Основной конструкцией языка typesystem является правило вывода (Inference Rule), которое состоит из условия, определяющего применимость правила к конкретному узлу, и тела, представляющего собой набор операторов, выполняемых в момент применения правила к узлу АСД.

Условие может быть задано одним из двух способов: либо в виде ссылки на концепт, тогда правило применимо ко всем узлам этого концепта и его наследников, либо в виде шаблона, тогда правило применимо ко всем узлам, соответствующим шаблону. Узел соответствует шаблону, если имеет такие же свойства и ссылки, как у шаблона, а дочерние узлы соответствуют дочерним узлам шаблона. Шаблон также в качестве свойств, ссылок и дочерних узлов может иметь переменные, которые соответствуют любому значению.

2.6.2. Типовые уравнения и неравенства Для задания отношений между типами конструкций языка в теле правила вывода применяются операторы типовых уравнений и типовых неравенств. Подсистема вывода типов среды MPS на основе типовых уравнений и неравенств, заданных разработчиком языка, строит для АСД программы систему типовых уравнений с граничным условиями [105]. Решая эту систему уравнений, указанная подсистема выводит тип для узлов АСД.

Неразрешимости системы типовых уравнений свидетельствует о наличии в программе ошибки приведения типов. Среда MPS обнаруживает такие ошибки и сообщает о них пользователю. Например, на рис. целочисленная константа использована в качестве условия на переходе.

Однако семантика языка stateMachine допускает в качестве условий на переходах лишь выражения логического типа.

иметь логиче Это правило вывода является ч цело очисленн пред дставленн на рис. 22.

конс струкции языка typ «a : this.tasks state{OpeningDoors} { this.doorsEngine.open();

on call(toFloor, from) do { this.tasks.addTask(toFloor, from);

on doorsOpened do {} transit to {LoadingPeople} state{LoadingPeople} { this.tasks.removeTasks(this.floor);

this.loadingTimer.start();

on call(toFloor, from)[toFloor != this.floor] do { this.tasks.addTask(toFloor, from);

on loadingTimeout[!(this.tasks.hasTasks())] do { } transit to {Stopped} on loadingTimeout[this.tasks.hasTasks()] do { } transit to {ClosingDoors} state{MovingUp} { this.elevatorEngine.turnUp();

on reached(floor)[this.tasks.shouldStopAscending(floor)] do { this.elevatorEngine.stop();

this.floor = floor;

} transit to {OpeningDoors} on call(toFloor, from) do { this.tasks.addTask(toFloor, from);

state{MovingDown} { this.elevatorEngine.turnDown();

пере еходов, пр прог граммиро пере еходов, а код, реализую гене ерируется автоматически.

1. Описаны средст 2. Описан разработанный автором язык автоматного программирования в среде MPS.

3. Описан шаблон метапрограммирования OptionList.

4. Предложен и реализован подход к автоматной разработке, при котором код автомата пишется в виде текста, а диаграмма переходов восстанавливается из кода автоматически.

ГЛАВА 3. ВАЛИДАЦИЯ АВТОМАТНЫХ МОДЕЛЕЙ

Для уменьшения числа ошибок при разработке автоматных программ необходимо проводить валидацию разрабатываемых автоматных моделей.

Валидацией автоматных моделей называется проверка свойств автоматов, не зависящих от пользовательской спецификации. В этой главе рассматриваются методы валидации автоматов в нотации, предложенной в работе [106], с двухместными предикатами в условиях на переходах, и реализация этих методов в среде языково-ориентированного программирования.

В настоящей работе рассматривается валидация следующих свойств автоматных моделей:

полнота условий на переходах;

непротиворечивость условий на переходах;

достижимость любого состояния из начального состояния;

достижимость из любого состояния конечного состояния.

одноместными предикатами в условиях на переходах была решена автором ранее [80]. Для дальнейшего увеличения выразительной мощности автоматных моделей необходимо расширить класс формул для выражения условий на переходах двуместными предикатами сравнения входных переменных. Практическая ценность такого расширения состоит в том, что оно позволяет проверять корректность автоматных моделей, содержащих в условиях на переходах сравнения переменных друг с другом. Предыдущий результат в этой области, описанный автором в работе [41], позволял проверять условия на переходах, содержащие лишь одноместные предикаты, что с практической точки зрения позволяло сравнивать переменную лишь с константой.

Достижимость любого состояния из начального и достижимость модификацией алгоритма поиска в глубину [107].

3.1. Формальная модель автомата зафиксировать формальную модель автомата [108].

– множество состояний;

– множество событий;

– начальное состояние, – функция переходов;

– набор входных переменных с множеством значений.

переходе в любое из которых работа автомата завершается. Подобное понимание конечного состояния, характерное для структурных автоматов, отличает рассматриваемую модель от принятой в теории формальных грамматик, где понятие конечное состояние – синоним допускающего состояния.

3.1.1. Функция переходов Функция переходов автомата определяется как данного состояния, пришедшего события и набора значений переменных однозначно определяет новое состояние, в которое перейдет автомат. Это означает, что рассматриваются только детерминированные автоматы. На конечных состояниях функция перехода не определена. При переходе автомата в конечное состояние его выполнение завершается, и дальнейшие переходы не осуществляются.

Переменная может соответствовать переменной в программе, быть вещественным или перечислимым. В рамках теоретической части работы определена операция сравнения.

Для формального описания валидируемых свойств удобно ввести возникновении события :

работе рассматриваются лишь такие функции, которые состоят из набора пар где – булева функция, соответствующая условию на переходе из функции допускаются произвольные одноместные предикаты и предикаты условия:

Первое условие соответствует свойству полноты и означает существование перехода для любого набора значений входных переменных. Второе условие соответствует свойству непротиворечивости и означает единственность перехода для любого набора входных переменных.

3.1.2. Достижимость состояний переходах фактически игнорируются.

переходы 3.1.3. Граф изоморфный автомату Для применения результатов теории графов для валидации автоматов будут соединять одно состояние с другим, если определен переход из первого во второе. При этом на ребрах графа записываются событие, при для одной пары состояний может быть определено несколько переходов между ними, построенная конструкция будет гиперграфом.

реберными путями в графе путями из переходов в автомате. Таким образом, 3.1.4. Валидируемые свойства Валидация автомата с учетом данных выше определений состоит из проверки следующих свойств:

3. Достижимость любого состояния из начального состояния 4. Достижимость конечного состояния из любого состояния автомата Не все перечисленные свойства являются обязательными для корректной работы автомата. Свойства 1 и 2 вытекают из данного программирования, описанного в главе 2, частично снимает необходимость выполнения свойства 1 в силу того, что отсутствие явного перехода по некоторому событию и некоторому набору входных переменных трактуется как наличие петли без выходных воздействий. Необходимость свойства умаляется существованием фиксированного порядка, в котором происходит перебор переходов при обработке события. Таким образом, данная операционная семантика для функции переходов на переходах непротиворечивости явных условий на переходах позволяет выявлять ошибки программирования в процессе разработки.

Невыполнение свойства 3 на практике, как правило, указывает на основанной на нем. Нарушение этого свойства означает, что в программе существует код, который не будет выполнен ни при каких условиях.

Невыполнение утверждения 4 для автомата означает, что в нем существуют состояния, при попадании в которые программа никогда не завершится. Такой автомат может быть создан и иметь практическое применение. Более того, для описания системы, работа которой не предполагает явного завершения, может быть создан автомат, не имеющий конечных состояний вообще. Если же автоматная программа реализует конечный по времени процесс, то наличие в нем состояния, из которого программа не достигает конечного, явным образом указывает на ошибку.

Таким образом, проверка перечисленных выше свойств весьма желательна и имеет большую практическую ценность.

3.2. Полнота и непротиворечивость условий на переходах Проверка свойств полноты и непротиворечивости условий на определения, состоит в проверке истинности двух утверждений:

, для свойства полноты;

для функции, для свойства непротиворечивости.

тавтологичности, либо свойства выполнимости набора выражений.

3.2.1. Булевы формулы Ранее в настоящей работе указывалось, что условия на переходах определены, как булевы формулы, в качестве аргументов которых выступают произвольные одноместные предикаты и предикаты сравнения входных переменных автомата. В работе [41] определение булевой формулы вводится следующим образом:

высказывание, которое принимает значение из множества 0, 1.

Пропозициональной формулой является:

всякая пропозициональная переменная;

если – пропозициональная формула, то – пропозициональная – пропозициональные формулы.

Пропозициональная формула – это высказывание, которое может быть истинным или ложным. Пусть пропозициональная формула содержит (пропозициональных) переменных, тогда подстановка на их место конкретных значений 0 или 1 («истина» или «ложь»), выдаст истинное или ложное значение для формулы. Таким образом, задает отображение :

0, 1 0,1, которое называется булевой функцией.

Итак, булева функция задается пропозициональной формулой, значение которой определяется значениями пропозициональных переменных, содержащихся в формуле, и операторами, связывающими эти переменные. В настоящей работе в качестве пропозициональных переменных выступают одноместные предикаты и предикаты сравнения входных переменных автомата.

3.2.2. Предикаты Входные переменные автомата в рассматриваемой модели могут иметь логический, целочисленный, вещественный или перечислимый тип. В качестве пропозициональных переменных, допустимых в функциях условий на переходах, рассматриваются логические переменные и операторы сравнения переменных с константой (одноместные предикаты) и друг с другом (двухместные предикаты): операторы строгого и нестрогого неравенства (,,, ), оператор равенства ( ) и оператор неравенства ( ).

Последние два оператора сводятся к четырем предыдущим следующим образом:

Таким образом, в дальнейшем достаточно рассмотреть только предикаты с первыми четырьмя операторами.

3.2.3. Проверка тавтологичности формулы тавтологичности булевой формулы, поэтому для проверки свойств предложить метод проверки тавтологичности булевой формулы указанного класса. Такую проверку предлагается проводить следующим образом:

представляется в виде секвенции [109].

2. При помощи исчисления секвенций формула сводится к набору элементарных секвенций (аксиом исчисления секвенций) – таких секвенций, у которых и в левой, и в правой части существуют только пропозициональные переменные: логические входные переменные и операции сравнения входных переменных.

3. Если ни одна из полученных элементарных секвенций не является контрпримером, то, в соответствии с теорией исчисления секвенций, исходная формула является тавтологией. Контрпримером называется такая секвенция, для которой существует набор значений входных переменных, при котором все пропозициональные переменные в левой части истинны, а все пропозициональные переменные в правой части Если в некоторую элементарную секвенцию некоторая логическая входная переменная входит и слева, и справа, то такая секвенция не является контрпримером, так как никакая логическая переменная не может принимать и истинное, и ложное значение одновременно.

Значения операций сравнения могут быть связаны друг с другом через сравниваемые входные переменные, поэтому для того, чтобы элементарная секвенция являлась контрпримером, недостаточно того, чтобы ни одна операция сравнения не входила в обе части секвенции одновременно. Для секвенций с операциями сравнения необходимо искать набор значений входных переменных, при которых все неравенства слева истинны, а все неравенства справа ложны.

Все операции сравнения в элементарной секвенции могут быть перенесены в левую часть по правилам:

которые вытекают из правила вывода для секвенций: и свойств операторов сравнения:

Таким образом, задача поиска контрпримера может быть сведена к неравенства может быть пара входных переменных (двухместные предикаты) или входная переменная и константа (одноместные предикаты).

3.2.4. Выполнимость системы неравенств неравенства, то полученная система неравенств будет задавать на множестве своих аргументов отношение частичного нестрогого порядка корректен, а система неравенств невыполнима.

Для этого целесообразно ввести понятие графа отношений – неравенствах. Множество ребер строится следующим образом:

помеченное оператором сравнения ребро естественных неравенств для констант.

нестрогим неравенством в системе, то множество ребер будет содержать ребро только для строго неравенства.

Для того чтобы проверить, что задаваемое системой неравенств Уоршолла [107]. Граф отношений может быть представлен в виде матрицы вершина графа. В ячейках матрицы смежности хранятся числа соответствующие операторам отношения, которыми помечены ребра:

Приведем алгоритм Флойда-Уоршалла, модифицированный для построения транзитивного замыкания графа отношений:

1. Для всех k от 1 до | | В терминах графа, значения операторов на ребрах являются весовой функцией. Предложенный алгоритм находит пути наибольшего веса между всеми вершинами. При этом вес пути определяется как вес ребра с наибольшим весом в данном пути. С точки зрения отношений для всех пар вершин ищется наиболее строгое отношение, определенное для них. Таким 3.2.5. Полнота условий на переходах Проверка свойства полноты условий на переходах для автомата,,,,, состоит в проверке истинности утверждения:

В предыдущих разделах был описан метод сведения проверки свойства тавтологичности булевой формулы указанного класса к поиску контрпримера для секвенции и предложен алгоритм такого поиска. Таким образом, проверка полноты условий на переходах сведена к поиску 3.2.6. Непротиворечивость условий на переходах,,,,, состоит в проверке истинности утверждения:

представить его в виде секвенции предыдущих разделах, свойство непротиворечивости условий на переходах выполняется тогда и только тогда, когда для такой секвенции с помощью предложенного выше алгоритма невозможно найти контрпример.

3.3. Достижимость из начального состояния Проверка свойства достижимости любого состояния из начального использовать следующий алгоритм:

1. Множество состояний, пройденных при обходе графа из начального состояния на нулевом шаге обход вершин в глубину [107]. На каждом шаге обхода строится множество состояний, пройденных при обходе графа из начального i-ом шаге обхода.

недостижимых состояний.

Доказательство корректности решения.

вершину и все вершины, достижимые из нее. Из этого следует верность множество состояний, достижимых из начального, а все остальные состояния все состояния в автомате достижимы из начального состояния.

3.4. Достижимость конечного состояния Проверка свойства достижимости конечного состояния из любого :, для проверки которого предлагается использовать модифицированный алгоритм обратного обхода в глубину графа:

1. В стек, используемый для обратного обхода графа, помещаются все состояния из множества. Множество состояний, посещенных при обходе графа на нулевой итерации, полагается пустым Множество помеченных вершин также полагается пустым.

2. Если стек пуст, то алгоритм заканчивает свою работу.

3. Если стек не пуст на i-ой итерации, то a) из вершины стека извлекается состояние ;

b) множество состояний, пройденных при обходе графа на i-ой c) складываются в стек и помечаются все вершины, которые не были помечены на предыдущих шагах, и из которых существует 4. Выполняется переход к шагу 2.

5. Если после итераций множество совпадает с множеством, то конечные состояния достижимы из всех вершин автомата, иначе Конечность алгоритма [102] вытекает из того, что конечные состояния помещаются в стек один раз на шаге 1, и не могут быть заново помещены в стек на шаге 3, так как в автомате не существует переходов из конечных состояний;

неконечные состояния не могут несколько раз попадать в стек на шаге 3, так как после помещения в стек состояния помечаются, а помеченные ранее состояния заново в стек не складываются;

на каждой итерации из стека извлекается по одному состоянию. При этом каждое состояние может побывать в стеке не более одного раза.

Поэтому алгоритм закончит свою работу за число итераций, не превышающее число состояний в автомате.

Корректность алгоритма доказывается аналогично доказательству корректности обратного алгоритма обхода в глубину.

3.5. Реализация в среде MPS От системы валидации автоматов в среде MPS требовалось предоставить пользователю простой и удобный способ проверки автоматов, а такж предложить ем инстру вали идации.

врем мени по мере нап оши ибках вал лидации выводятся пользов цвет том или подчерки при проверке достижимости к кото орых кон курс сооб бщения об ошибке Рис. ообщение о недости Название состояния выделен цветом. Рядом с названием состояния текст с Для реализации подо проб блемно-о опис сывать не только систему т аспе екты его семанти корр ректности Код проверки записыв type esystem р сооб бщений о ошибк ошибке, у авто оматическ выделя в ред акторе уз оши ибка, и в выводит текст со общения об ошибке при наведени курсо мыш коне ечных со сооб бщения об ошиб недо остижимо ни одно конечно е состоян дейс ствия для автомат испо ользуется для создания средств автомат оши исхо одящими перехода курс испр равления ошибок. При вы испр равление кода.

3.5.1 Реализ матный язык в сре MPS определя услов на пер узел концеп выр ражений, существу условие на переходе не обязательно является булевой формулой из класса, для которого предложен метод валидации.

В реализации метода валидации выполняется разбор условий на переходах и проверка принадлежности этих условий к описанному классу булевых формул. Поддерживаются следующие выражения языка baseLanguage:

AndExpression – конъюнкция;

OrExpression – дизъюнкция;

NotExpression – логическое отрицание;

ParenthesizedExpression – выражение в скобках;

BooleanConstant – булева константа;

LessThanExpression – оператор «меньше»;

LessThanOrEqualsExpression – оператор «меньше или равно»;

GreaterThanExpression – оператор «больше»;

GreaterThanOrEqualsExpression – оператор «больше или равно»;

EqualsExpression – оператор «равно»;

NotEqualsExpression – оператор «неравно»;

StaticFieldReference – ссылка на статическое поле класса, если поле финальное, интерпретируется как константа, иначе – как переменная;

StringLiteral – строковая константа;

IntegerConstant, LongLiteral, HexIntegerLiteral, CharConstant, FloatingPointConstant, FloatingPointFloatConstant – числовые константы;

EventParameterReference – параметр события, который при валидации интерпретируется как входная переменная;

FieldReferenceOperation – поле класса, которое интерпретируется как входная переменная;

InstanceMethodCallOperation – метод, который интерпретируется как входная переменная.

Если поддерево выражения для условия на переходе содержит конструкции, отличные от перечисленных выше, то пользователю будет выдано сообщение о том, что такое выражение не может быть валидировано.

Несмотря на то, что для разработки надежных систем необходимо явно проверять полноту и непротиворечивость, описанная во второй главе операционная семантика для автоматного языка программирования, позволяет корректно исполнять автоматы даже в тех случаях, когда для них не выполняются свойства полноты и непротиворечивости переходов. В случае если в некотором состоянии не определен переход для некоторой комбинации события и значений входных переменных, то событие игнорируется. Таким образом, обеспечивается полнота переходов для любых автоматов. Перебор переходов при обработке события выполняется в порядке определения этих переходов в коде автомата. Поэтому если для некоторой комбинации входных переменных выполняются условия сразу на двух переходах, то будет выбран переход, определенный в коде раньше. Это обеспечивает непротиворечивость переходов для любых автоматов. Средства автоматической валидации автоматов в среде MPS позволяют по желанию пользователя отключать проверку полноты и непротиворечивости переходов для автомата.

Проверка полноты и непротиворечивости переходов реализована для каждого стабильного состояния следующим образом:

1. Исходящие переходы из состояния и состояний, в которые состояние обрабатываемого в состоянии, определяется набор связанных с ним 2. Для каждого перехода определяется, принадлежит ли формула условия на переходе классу, для которого предложен метод проверки свойств принадл ошибке и валидац прекр 3. Для каж условий на перех 4. Для фо осущест метода. Наличие хотя бы одного контрпр свойство пользова переходов из состояния по соб выражен для ав 5. Для каж секвенци предлож женного метода. Наличи хотя бы одн указывает на то, что с выполня ошибке, связанн выражен для ав 3.5.2 Исправ 2. вление неполноты перехо Набор контрпримеров для секв мно ожества з пере еход. Ес конт трпример пере еменных, выполня набо орами зна Таки образо если любое из условий по событию пере еходов на рис. 35 показан пример диалога исправл сост тояния с неполн посл ледствие применен автом Рис. 36. К автома после п 3.5.3 Исправ 3. вление противоре Набор контрпр знач чений вхо одно овременн Если набор сек конт трпример пере еменных, выполня набо орами зн начений входных переменных, для которых услови вып полняются одновре усло На р 37 показан пример диалога исправл сост тояния с противор прив прот тиворечивости пер Рис. 38. К автома после п 3.5.4 Реализ дост тижимост конеч описанные выше, не учитывают наличие вложенных состояний. Однако составные состояния, имеющие исходящие переходы и содержащие вложенные состояния, являются лишь краткой записью для общих исходящих переходов у вложенных состояний. Наличие исходящего перехода из составного состояния эквивалентно наличию такого же исходящего перехода из каждого вложенного состояния.

Поэтому обход в глубину для поиска всех состояний, достижимых из начального, реализован следующим образом:

1. Обход начинается с загрузки начального состояния автомата в стек.



Pages:     || 2 |


Похожие работы:

«СВЕШНИКОВ Александр Сергеевич ФОРМИРОВАНИЕ КОМПОЗИЦИОННОГО МАТЕРИАЛА НА ОСНОВЕ ШПОНА И ДРЕВЕСНО-КЛЕЕВОЙ КОМПОЗИЦИИ 05.21.05 – Древесиноведение, технология и оборудование деревопереработки Диссертация на соискание ученой степени кандидата технических наук Научный руководитель : доктор технических наук, Угрюмов Сергей...»

«МУХАМЕТОВ ИЛЬЯС НИАЗОВИЧ Палтусы прикурильских вод: биология, состояние запасов, перспективы промысла 03.02.06 – ихтиология Диссертация на соискание ученой степени кандидата биологических наук Научный руководитель : д.б.н. А.М. Орлов Южно-Сахалинск – 2014 г. 2 СОДЕРЖАНИЕ ВВЕДЕНИЕ МАТЕРИАЛ И МЕТОДИКА 1. ЛИТЕРАТУРНЫЙ ОБЗОР 2. ХАРАКТЕРИСТИКА ОКЕАНОГРАФИЧЕСКИХ УСЛОВИЙ РАЙОНА 3. ИССЛЕДОВАНИЙ ОСОБЕННОСТИ...»

«БЛИНОВ Александр Георгиевич УЧЕНИЕ ОБ УГОЛОВНО-ПРАВОВОЙ ОХРАНЕ ПРАВ И СВОБОД ПАЦИЕНТА 12.00.08 – уголовное право и криминология; уголовно-исполнительное право ДИССЕРТАЦИЯ на соискание ученой степени доктора юридических наук Научный консультант : доктор юридических наук, профессор, заслуженный деятель науки России Разгильдиев...»

«ИГНАТЬЕВА ЛЮДМИЛА ЮЛЬЯНОВНА ГЛАВНЕЙШИЕ НАСЕКОМЫЕ – ВРЕДИТЕЛИ СМОРОДИНЫ В УСЛОВИЯХ СЕВЕРО-ЗАПАДА РОССИИ И БИОЭКОЛОГИЧЕСКОЕ ОБОСНОВАНИЕ МЕР БОРЬБЫ С НИМИ 06.01.07 защита растений ДИССЕРТАЦИЯ на соискание ученой степени кандидата биологических наук Научный руководитель : НИКОЛАЕВА Зоя Викторовна, доктор биологических наук, профессор Москва – ОГЛАВЛЕНИЕ ВВЕДЕНИЕ.. ГЛАВА I НАСЕКОМЫЕ ВРЕДИТЕЛИ СМОРОДИНЫ И СПОСОБЫ...»

«ВОРОБЬЕВА Ольга Вадимовна СРАВНИТЕЛЬНЫЙ И ИСТОРИЧЕСКИЙ АНАЛИЗ МЕТОДИЧЕСКОГО ПРОГРЕССА В АЛЛЕРГОЛОГИИ: АЛЛЕРГЕН-СПЕЦИФИЧЕСКАЯ ИММУНОТЕРАПИЯ 14.03.09 – клиническая иммунология, аллергология Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : доктор медицинских наук, профессор, член-корреспондент...»

«ШКАРУПА ЕЛЕНА ВАСИЛЬЕВНА УДК 332.142.6:502.131.1 (043.3) ЭКОЛОГО-ЭКОНОМИЧЕСКАЯ ОЦЕНКА СОСТОЯНИЯ РЕГИОНА В КОНТЕКСТЕ ЭКОЛОГИЧЕСКИ УСТОЙЧИВОГО РАЗВИТИЯ Специальность 08.00.06 – экономика природопользования и охраны окружающей среды ДИССЕРТАЦИЯ на соискание ученой степени кандидата экономических наук Научный руководитель Каринцева Александра Ивановна, кандидат экономических наук, доцент Сумы - СОДЕРЖАНИЕ ВВЕДЕНИЕ.. РАЗДЕЛ 1 ТЕОРЕТИЧЕСКИЕ...»

«Самсонов Дмитрий Сергеевич Электроимпульсная технология получения ультрадисперсных материалов 05.09.10 – Электротехнология ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук Научный руководитель д. т. н., профессор Гончаров В. Д. Санкт-Петербург – 2014 2 Содержание Введение.................................... Глава 1 Методы...»

«Богачева Ольга Юрьевна Эмпатия как профессионально важное качество врача (на примере врачей терапевтов и врачей хирургов) Специальность 19.00.03 Психология труда, инженерная психология, эргономика по психологическим наук ам ДИССЕРТАЦИЯ на соискание ученой степени кандидата психологических наук Научный...»

«Лютов Александр Александрович Государственная политика США в области занятости и безработицы на рубеже XX – XXI веков. Специальность 07.00.03. Всеобщая история Диссертация на соискание ученой степени кандидата исторических наук Научный руководитель доктор исторических наук, профессор Попов А.А. Москва – Оглавление Введение Глава 1. Американская модель государственного вмешательства в сферу труда и ее эволюция (1920 – 1990-е гг.)...»

«Фадеева Елена Ивановна КОЛЛЕГИАЛЬНОСТЬ СОСТАВА СУДА В ХОДЕ СУДЕБНОГО ПРОИЗВОДСТВА ПО УГОЛОВНЫМ ДЕЛАМ Специальность 12.00.09 – уголовный процесс Диссертация на соискание ученой степени кандидата юридических наук Научный руководитель : кандидат юридических наук,...»

«УДК 535.529:541.64 Третьяков Илья Викторович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССА ФОРМОВАНИЯ ПОЛИМЕРНЫХ ПЛЕНОК В УСЛОВИЯХ ДВУХОСНОГО РАСТЯЖЕНИЯ С УЧЕТОМ ТЕПЛОПЕРЕНОСА Специальность 01.04.14 — теплофизика и теоретическая теплотехника Диссертация на...»

«Обущенко Сергей Владимирович АГРОЭКОЛОГИЧЕСКОЕ ОБОСНОВАНИЕ СИСТЕМ ВОСПРОИЗВОДСТВА ПОЧВЕННОГО ПЛОДОРОДИЯ В ПОЛЕВЫХ СЕВООБОРОТАХ СРЕДНЕГО ЗАВОЛЖЬЯ 06.01.01 – общее земледелие Диссертация на соискание ученой степени доктора сельскохозяйственных наук Научный консультант д. с.-х. н., профессор, академик РАСХН...»

«ТЮРНИН Владимир Алексеевич ОБОСНОВАНИЕ ПАРАМЕТРОВ ТЕХНОЛОГИЧЕСКИХ СХЕМ ОТРАБОТКИ СВИТ ПОЛОГИХ УГОЛЬНЫХ ПЛАСТОВ, СКЛОННЫХ К САМОВОЗГОРАНИЮ Специальность 25.00.22 - Геотехнология (подземная, открытая и строительная) Диссертация на соискание ученой степени кандидата...»

«УДК 539.172.17+539.173.7 Тищенко Владимир Геннадьевич ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК МНОГОТЕЛЬНЫХ РАСПАДОВ ТЯЖЕЛЫХ ЯДЕР Специальность: 01.04.16 – физика атомного ядра и элементарных частиц Диссертация на соискание ученой степени кандидата физико-математических наук Научные руководители: доктор физико-математических наук, профессор Ю.Э. Пенионжкевич, доктор физико-математических наук, В.В....»

«Стойлов Сергей Валентинович Уретральные стенты в терапии доброкачественной гиперплазии и рака предстательной железы (14. 00. 40 - урология) Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : доктор медицинских наук, профессор Л.М. Рапопорт Москва, 2004 г Оглавление. Введение: Актуальность темы, цель, задачи, научная новизна, практическая ценность исследования Глава 1. Место...»

«Науменко Сергей Анатольевич ДИНАМИКА ОДНОЛОКУСНОГО МУЛЬТИАЛЛЕЛЬНОГО АДАПТИВНОГО ЛАНДШАФТА В МОЛЕКУЛЯРНОЙ ЭВОЛЮЦИИ БЕЛОККОДИРУЮЩИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДНК 03.01.09 — математическая биология, биоинформатика Диссертация на соискание учёной степени кандидата биологических наук Научный руководитель : кандидат биологических наук Г.А. Базыкин Москва — 201 Оглавление Введение Объект...»

«Достовалов Дмитрий Николаевич СПЕЦИФИКАЦИЯ И ИНТЕРПРЕТАЦИЯ МОДЕЛЕЙ ПЕРЕХОДНЫХ ПРОЦЕССОВ В СИСТЕМАХ ЭЛЕКТРОЭНЕРГЕТИКИ 05.13.11 – Математическое и программное...»

«ТЕРНАВЩЕНКО Кристина Олеговна СОВЕРШЕНСТВОВАНИЕ СИСТЕМЫ ВНУТРИФИРМЕННОГО ПЛАНИРОВАНИЯ В МОЛОЧНОМ СКОТОВОДСТВЕ (по материалам Краснодарского края) Специальность 08.00.05 – Экономика и управление народным хозяйством: экономика, организация и управление организациями, отраслями и комплексами (АПК и сельское хозяйство) ДИССЕРТАЦИЯ на соискание учной степени кандидата экономических наук Научный...»

«Иванов Данил Сергеевич ОПРЕДЕЛЕНИЕ УГЛОВОГО ДВИЖЕНИЯ МИКРОСПУТНИКА НА ЛАБОРАТОРНОМ СТЕНДЕ И В ОРБИТАЛЬНОМ ПОЛЕТЕ Специальность 01.02.01 – теоретическая механика Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель : профессор, д.ф.-м.н. М.Ю.Овчинников Москва – 2013 ОГЛАВЛЕНИЕ ВВЕДЕНИЕ 1. МЕТОД ИССЛЕДОВАНИЯ ТОЧНОСТИ ОЦЕНОК АЛГОРИТМА ОПРЕДЕЛЕНИЯ ДВИЖЕНИЯ 1.1. Задача фильтрации 1.2....»

«БЛИНЧИКОВА МАРИНА СЕРГЕЕВНА КЛИНИКО-ИММУНОЛОГИЧЕСКИЕ И МИКРОБИОЛОГИЧЕСКИЕ АСПЕКТЫ БРОНХИАЛЬНОЙ АСТМЫ У ВЗРОСЛЫХ 14.03.09 – клиническая иммунология, аллергология Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : Доктор медицинских наук, профессор А.В. Жестков САМАРА, ОГЛАВЛЕНИЕ СПИСОК СОКРАЩЕНИЙ И ОБОЗНАЧЕНИЙ, ВСТРЕЧАЮЩИХСЯ В...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.