При программировании иногда попадаются задачи, которые трудно "втиснуть" в стандартные конструкции языка. А решение лежит совсем рядом - в теории конечных автоматов. Не пугайтесь – это только название страшное, а на самом деле все очень просто.
Из курса школьной алгебры мы знаем о существовании формальных преобразований. Самым простым примером является разложение скобки (a+b)2.
Давным-давно, когда люди еще не придумали объектно-ориентированное программирование, модным направлением было программирование структурное. Шутки шутками, но в результате именно структурного подхода мы сейчас имеем Pascal и Delphi.
Так вот, в те давние времена возникла следующая ситуация:
"Сочинение" алгоритмов решения различных задач - процесс творческий, а творчество очень не любит каких-либо ограничений. Cтало быть алгоритм может быть любым, сколь угодно запутанным, образующим петли и прочие нелинейности.(Особенно этим грешат процедуры, занимающиеся разного рода синтаксическим разбором.)
Стандартный Паскаль имеет очень ограниченное количество структурных инструкций ( if-then-else, while-do и т.д., вы это лучше меня знаете...)
А нельзя ли как-нибудь "втиснуть" этот наш премудрый алгоритм в куцый набор инструкций? Можно! Причем используя вполне формальное преобразование. Вот этим мы сейчас и займемся.
Итак, структурное программирование учит нас, что есть 5 основных конструкций, из которых как из кубиков строится любая процедура:
|
SEQUENCE |
IF-THEN-ELSE |
WHILE-DO |
REPEAT-UNTIL |
CASE |
В нашем запутанном алгоритме наверняка не все так ужасно, как кажется. Скорее всего, там можно найти несколько фрагментов, подходящих под определение чисто структурных конструкций. Вопрос лишь в том, как эти конструкции соединить между собой.
А вот в этом как раз может помочь наша рабочая лошадка - непотопляемая конструкция REPEAT-CASE. При умелом применении эта пара команд может "переварить" алгоритм любой сложности и запутанности.
Предположим, у нас есть алгоритм следующего вида:
Если приглядеться, то он легко разбивается на 3 вложенные стандартные структуры:
Так что мы с легкой душой можем воплотить его в программе вроде такой:
repeat
while C1 do B1;
if C2 then B2
else B3;
until C3;
И все! Очень красиво и компактно.
Как было бы хорошо, если бы в жизни нам попадались только такие алгоритмы.
А что вы скажете на это?
Выглядит вроде просто, но в стандартный Паскаль явно не укладывается. Можно, конечно, попытаться "расшить" процедурные блоки B1 и B3 или применить GOTO или EXIT из цикла. Но все это, согласитесь, выглядит как-то жалко и самодеятельно. Опять же надо каждый раз думать где разомкнуть цикл...
И вот теперь мы можем выполнить несколько чисто формальных шагов:
Выделяем в нашем алгоритме фрагменты, которые хорошо укладываются в структурную модель (если такие есть). В нашем случае такой фрагмент только один: B2 + C2, т.е. последовательность из блока и условия.
Вне этих фрагментов ставим жирные точки в следующих местах:
на входе в модуль (обозначим ее 1)
на выходе модуля (обозначим 0)
на входах и выходах всех фрагментов, что мы нашли
во всех местах, где есть пересечение линий на блок-схеме
Скорее всего, многие точки просто сольются - пусть, мы будем считать их за одну. Например, у нас точка 1 на входе модуля совпадает с точкой пересечения линий входящей и от B3.
Пронумеруем оставшиеся точки произвольно. В нашем примере получается 4 точки от 0 до 3.
Теперь мы готовы перейти к модели конечного автомата и написать-таки нашу программу.
Представьте, что есть некий блок, который может находиться в одном из четырех состояний. И есть набор действий, в результате которых блок переходит из одного состояния в другое.
Для отображения этого самого состояния, заведем в программе некоторую переменную, скажем, State. А внутри веток CASE будем изменять ее состояние.
Пишем нашу программу:
var State:integer;
begin
State:=1; {для любого алгоритма}
repeat
case State of
...
end;
until State=0; {тоже для любого алгоритма}
end;
Теперь пропишем ветки CASE. Не забудьте в конце каждой ветки уточнить состояние:
case State of
1: begin B1; if C1 then State:=2 else State:=3 end;
2: begin B2; if C2 then State:=0 else State:=3 end;
3: begin B3; State:=1 end;
end;
Все! Программа готова. И она работает. И с точки зрения логики Паскаля все безупречно - никаких GOTO и прочих неприятностей.
Что мы сделали?
Мы изобразили наш алгоритм как блок-схему или, другими словами, направленный граф
Затем провели преобразование этого графа с выделением нескольких стационарных состояний программы - конечного автомата
В результате получили новый граф, который легко укладывается в структурные конструкции Паскаля
Проводя указанные действия несколько раз для разных алгоритмов, можно заметить, что на самом деле наши произвольно расставленные точки-состояния не такие уж случайные и произвольные. Как правило, при более глубоком рассмотрении вашего конкретного алгоритма можно найти каждому из этих состояний свое название. Это название может быть гораздо более выразительным, чем просто 1-2-3, поскольку это действительно состояния вашей программы.
Пусть ваш алгоритм занимается, скажем, синтаксическим разбором HTML-файла. Тогда одно из состояний может звучать как "Обнаружен тэг BODY" или "Найден конец документа".
Паскаль предлагает нам замечательное средство для работы с такими обозначениями в символическом виде и об этом средстве сейчас часто забывают. Программа из нашего примера может выглядеть так:
var State:(START, EOF_found, Line_Added, DONE);
begin
State:=START; {для любого алгоритма}
repeat
case State of
START: begin B1; if C1 then State:=EOF_Found else State:=Line_Added end;
EOF_Found: begin B2; if C2 then State:=DONE else State:=Line_Added end;
Line_Added: begin B3; State:=START end;
end;
until State=DONE; {тоже для любого алгоритма}
end;
Возможно, проделав подряд несколько таких преобразований и войдя во вкус, вы заметите, что стали мыслить при программировании чуть-чуть иначе. Иногда, особенно когда задача несколько запутана, хочется сразу выделить несколько важных состояний и строить обработчик уже вокруг них.
Кстати, сейчас тема конечных автоматов вновь стала актуальной и то и дело мелькает на страницах компьютерных журналов.
Крайние случаи
Как сказал один мудрый человек, "Идея, доведенная до абсурда, часто превращается в свою противоположность". Давайте попробуем довести наш метод до крайней степени.
В нашем случае это означает добавление еще двух состояний - 4 и 5. Тогда программа примет вид:
case State of
1: begin B1; State:=4 end;
2: begin B2; State:=5 end;
3: begin B3; State:=1 end;
4: if C1 then State:=2 else State:=3;
5: if C2 then State:=0 else State:=3;
end;
Хорошо это или плохо?
Хорошо, в том смысле, что даже при таком издевательстве программа не перестает работать правильно. С другой стороны, посмотрите на исходный код: где прозрачность, где легкость и ясность? Суть алгоритма растворена в сплошных переходах состояний и из-за этого теряется.
А что, если пойти в другую сторону и уменьшить число выделенных состояний? В нашем примере реально только исключить состояние 2.
После "приведения подобных" программа будет иметь следующий вид:
case State of
1: begin
B1; State:=3;
if C1 then begin
B2; if C2 then State:=0
end
end;
3: begin B3; State:=1 end;
end;
Здесь формально получаются две ветки ELSE, ведущие обе к третьему состоянию. Если состояние вынести вверх, до условия, то программа получается короче.
Предвижу возражения такого толка, что при подобном подходе программы будут иметь повышенную склонность к зацикливанию. И да и нет. Циклы вообще склонны к зацикливанию, особенно если написать что-нибудь вроде repeat until false;. А если серьезно, то устойчивость работы преобразованных таким образом программ прямо и недвусмысленно показывает, насколько удачно вы проработали исходную блок-схему и насколько аккуратно ее преобразовали. Поскольку на то оно и инвариантное преобразование, чтобы ничего не менять в смысле и логике программы, а затрагивать лишь ее внешнее представление.
Я ни в коей мере не претендую на авторство в данном формальном подходе, более того, все проблемы и решения, изложенные в этой статье, известны уже довольно давно.
Цель лекции была просто напомнить вам об одном красивом, но, забытом подходе к программированию на Паскале. А если учесть, что и современный Бейсик поддерживает структуры, то и к программированию вообще.
