Технологии программирования
О чем мечтают все программисты? Наверное, чтобы компьютер сам писал за них программы. А если это невозможно, то хотя бы чтобы компьютер максимально помогал в этом нелегком занятии. Цель направления "Технологии программирования" Международной научной лаборатории "Компьютерные технологии" – разработка методов, позволяющих автоматизировать процесс проектирования, разработки, тестирования и верификации программного обеспечения.
Построение управляющих программ по спецификации
Управляющие программные системы, как правило, обладают сложным поведением, а именно, могут порождать различные управляющие воздействия в ответ на одни и те же входные воздействия в зависимости от предыстории – для построения и анализа таких систем целесообразно применять модели, основанные на состояниях. Наиболее известной моделью, основанной на состояниях и имеющей детерминированный характер, является конечный автомат. Парадигма программирования, предполагающая описание логики работы программ в виде систем взаимодействующих конечных автоматов, известна как автоматное программирование. Поскольку проектирование управляющих программных систем, в том числе основанных на использовании конечных автоматов, вручную является крайне сложным и трудоемким процессом, активно развиваются методы автоматизированного построения конечно-автоматных моделей.
Задачи автоматизированного построения конечно-автоматных моделей зачастую могут быть сведены к задачам оптимизации. При этом такие задачи, как правило, не могут быть решены с помощью традиционных методов оптимизации, так как пространство поиска – множество возможных конечных автоматов – не является непрерывным.
Кроме того, эти задачи оптимизации зачастую являются, как минимум, NP-трудными, поэтому для их решения применяются всевозможные метаэвристические алгоритмы, а также методы пропозиционального кодирования на таких языках, как SAT и CSP.
На рис. 1 представлена модель автопилота на основе конечного автомата, выполняющая "бочку". Автомат представлен в правой части рисунка. Данный автомат построен с помощью муравьиных алгоритмов на основе траекторий нескольких полетов, выполненных людьми в авиасимуляторе.
Рис. 1. Автопилот на основе конечного автомата
Конечно-автоматные модели широко применяются на практике при реализации систем управления. Например, в промышленном стандарте IEC 61499 управляющие программы реализуются в виде сетей взаимосвязанных функциональных блоков (рис. 2); базисные функциональные блоки реализуются с помощью конечных автоматов (рис. 3). Одно из направлений исследований – автоматизация генерации автоматных моделей функциональных блоков по примерам поведения и темпоральной спецификации.
Рис. 2. Фрагмент сети взаимосвязанных функциональных блоков
Рис. 3. Пример конечного автомата, реализующего базисный функциональный блок
В рамках программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014 - 2020 годы» проводятся исследования по проектированию, верификации и тестированию кибер-физических систем. В частности, разрабатываются методы генерации формальной модели объекта управления по симуляционной модели (рис. 4). Разрабатываемые методы направлены на повышение надежности ответственных кибер-физических систем за счет формальной верификации в замкнутом цикле.
Рис. 4. Генерация моделей объекта управления по симуляционной модели
Генерация тестов с использованием эволюционных алгоритмов
Поисковая инженерия программного обеспечения (Search Based Software Engineering) – способ решения задач, возникающих в процессе производства программного обеспечения, путем сведения их к задачам оптимизации и последующего решения этих задач. В поисковой инженерии программного обеспечения применяются генетические алгоритмы, эволюционные стратегии, муравьиные алгоритмы и другие алгоритмы стохастического поиска.
Тестирование является одним из самых затратных этапов производства программного обеспечения – по оценке экспертов, на него уходит до 50% времени и более 50% стоимости производства ПО.
В рамках исследований по направлению "Технологии программирования" решается одна из задач тестирования – нахождение таких тестовых данных, на которых тестируемая программа работает как можно дольше. Для генерации таких тестов используются генетические алгоритмы.
Помимо производства программного обеспечения, такие тесты нужны в образовании – для проведения олимпиад по программированию. Кроме того, методы построения таких тестов применимы при автоматизации ускорения программ – организуется коэволюция программ и тестов, приводящая к появлению более быстрых версий исходной программы.
Испытание разрабатываемых методов проводится при генерации тестов для олимпиадных задач по программированию. На рис. 5 приводятся графики, иллюстрирующие построение тестов против алгоритмов поиска максимального потока.
Рис. 5 - Графики, иллюстрирующие процесс построения тестов против алгоритма поиска максимального потока