Pull to refresh
81.75
Rating
ITMO University
IT's MOre than a University

«Лекарство от болезни»: автоматное программирование

ITMO University corporate blog Website development *Programming *System Analysis and Design *Development of mobile applications *
Новости о различных уязвимостях программного обеспечения появляются регулярно, к этому все привыкли. Однако одно дело — ошибки в мобильном приложении, а другое — возможная остановка ядерного реактора. Сегодня мы поговорим об истоках проблем с программным обеспечением и возможном способе исправления ситуации, в частности — автоматном программировании.

Robson# / Flickr / CC

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

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

Откуда растут ноги


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

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

Автоматное программирование вступает в игру


Автоматное программирование — это парадигма программирования, при использовании которой программа или её фрагмент осмысливается как модель какого-либо формального автомата. Этот термин в 1991 году предложил заведующий кафедрой Технологии программирования Университета ИТМО Анатолий Шалыто.

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

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

В качестве примера использования автоматного подхода при построении алгоритма приведем решение задачи прямого обхода (0–9) двоичного дерева.


Пример двоичного дерева

Будем считать, что каждая вершина содержит свой номер и указатели на дочерние вершины. На языке C++ эта структура может быть представлена следующим образом:

struct Node { 
int id; // Номер узла 
Node* left; // Левый дочерний узел 
Node* right; // Правый дочерний узел 
};

Также введем в систему функцию put (int x), которая выводит номер вершины в выходную последовательность, и класс, реализующий стек со следующим интерфейсом:

template class Stack { 
void push(const T& x); // Поместить значение x в стек 
void pop(); // Удалить из стека верхний элемент 
const T& top() const; // Верхний элемент стека 
}; 

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


Схема связей автомата, реализующего обход дерева


Диаграмма переходов автомата, реализующего обход дерева

Отметим, что теория конечных автоматов была успешно применена компанией Corezoid для построения одноименной облачной платформы для ИТ-решений. Анатолий Шалыто говорит о необходимости внедрения этого метода в современную разработку: «Программисты — они ведь очень умные, и применяют автоматы, как и другие математические абстракции, когда считают нужным. А я говорю: всегда его [автоматное программирование] надо применять для описания программ со сложным поведением, в которых имеет место зависимость их поведения от предыстории».

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

P.S. Из приведенного текста может сложиться впечатление, что помощью автоматного программирования можно решать только «игрушечные» задачи. Однако это не так.

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

Правда, и при обучении вычислительным алгоритмам, автоматное программирование пригодилось: Георгий Корнеев и Матвей Казаков показали, что на его основе можно проектировать визуализаторы и автоматизировать их построение даже для весьма сложных алгоритмов дискретной математики, а не каждый раз писать их вручную, как «Бог на душу положит». Пример проектной документации приведен здесь, а вот пример такой документацией для сложного проекта.

С документацией для еще более сложного проекта можно ознакомиться вот тут. На сайте is.ifmo.ru есть еще много проектов, как студенческих, так и других, изучение которых сможет ответить на многие Ваши вопросы. С книгой Поликарповой Н.И. и Шалыто А.А. Автоматное программирование. СПб.: Питер, 2010 можно ознакомиться здесь.

И не фантазируйте – пишите: shalyto@mail.ifmo.ru.
Tags:
Hubs:
Total votes 26: ↑21 and ↓5 +16
Views 17K
Comments Comments 28

Information

Founded
Location
Россия
Website
en.itmo.ru
Employees
Unknown
Registered
Representative
itmo