1. Алгоритм перетворює алгоритм! George Columbow При програмуванні на Delphi або Паскалі іноді трапляються...
2. усвідомлення

Алгоритм перетворює алгоритм!

George Columbow

При програмуванні на Delphi або Паскалі іноді трапляються завдання, які важко "втиснути" в стандартні конструкції мови. А рішення лежить зовсім поруч - в теорії кінцевих автоматів. Ми не будемо залазити в нетрі, а просто покажемо як це робиться.

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

Міркування про алгоритми - якраз такий особливий випадок.

Ліричний відступ

Одного разу, ще в школі, на уроці алгебри, я в перший раз почув про існування формальних перетворень. Пам'ятається це були (a + b) 2.

Це було щось! Мене вразила сама можливість виконувати ряд простих кроків і гарантовано отримувати правильний результат.

Ну а вже потім були приклади з тригонометрії: чотириповерхові дробу з жахливим кількістю синусів, косинусів і нескінченно довгими аргументами, які шляхом невеликої гри розуму згорталися в боязке 1 + sin (x), а то й просто в непримітну 1.

З тих самих пір я дуже небайдужий до формальних перетворень і намагаюся знайти їм застосування в програмуванні. І, ви знаєте, іноді виходить! :-)

Давним-давно, коли люди ще не придумали об'єктно-орієнтоване програмування, модним напрямком було програмування структурний. Жарти жартами, але в результаті саме структурного підходу ми зараз маємо Pascal і Delphi.

Чому я говорю то Паскаль, то Дельфі? Просто тому, що лінгвістична основа Delphi - це Object Pascal, сильно виріс з дитячих штанців, але все ж впізнаваний. І нові об'єктно-орієнтовані можливості і чудові бібліотеки класів в сукупності з CASE-засобами так і не приховали повністю довгі вуха структурного мови (і це чудово!). Вони вилазять то тут, то там, в окремих процедурах, в обробниках подій ... :-)

Так ось, в ті давні часи виникла наступна ситуація:

• "Твір" алгоритмів вирішення різних завдань - процес творчий, а творчість дуже не любить будь-яких обмежень. Чи стало бути алгоритм може бути будь-яким, як завгодно заплутаним, що створює петлі та інші нелінійності.
  (Особливо цим грішать процедури, що займаються різного роду синтаксичним розбором.)
• Стандартний Паскаль має дуже обмежену кількість структурних інструкцій (if-then-else, while-do і т.д., ви це краще за мене знаєте ...)
• А програму-то написати хочеться! Що робити ?
• А чи не можна як-небудь "втиснути" цей наш премудрий алгоритм в куций набір інструкцій?
• Можна, можливо! Причому використовуючи цілком формальне перетворення .
• Ось цим ми зараз і займемося.

Але на початку - трохи теорії.

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

А ось в цьому якраз може допомогти наша робоча конячка - непотоплюваного конструкція REPEAT-CASE. При вмілому застосуванні ця нехитра пара команд може "переварити" алгоритм будь-якої складності і заплутаності. Головне, щоб ВИ чітко представляли що робите.

Проте чи вистачить нам ходити коло та навколо, чи не час зайнятися справою? А що ви скажете на це:
Виглядає ніби просто, це ми миттю!

Гмм .. да .. пробуємо і так і сяк - в стандартний Паскаль це явно не вкладається. Можна, звичайно, спробувати "розшити" процедурні блоки B1 і B3 або застосувати GOTO або EXIT з циклу. Але все це, погодьтеся, виглядає якось шкода і самодіяльно. Знову ж треба кожен раз думати де розімкнути цикл ...

І ось тут-то з'являємося ми, (на білому коні! -) з нашої універсальної відмичкою на ім'я REPEAT-CASE.

Тепер ми можемо виконати кілька чисто формальних кроків:

• Виділяємо в нашому алгоритмі фрагменти, які добре вкладаються в структурну модель (якщо такі є). У нашому випадку такий фрагмент тільки один: B2 + C2, тобто послідовність з блоку і умови.
  (Якщо ви вважаєте, що фрагмент можна взяти трохи ширше і включити в нього C1 + B2 + C2, я з вами погоджуся, але см. нижче )
• Поза цих фрагментів ставимо жирні точки в наступних місцях:
  • на вході в модуль (позначимо її 1)
  • на виході модуля (позначимо 0)
  • на входах і виходах всіх фрагментів, що ми знайшли
  • у всіх місцях, де є перетин ліній на блок-схемі
  Швидше за все, багато точки просто зіллються - нехай, ми будемо вважати їх за одну. Наприклад, у нас точка 1 на вході модуля збігається з точкою перетину ліній входить і від B3.
• Пронумеруємо залишилися точки довільно. пізніше ми ще поговоримо про те, що можуть насправді означати ці номери. У нашому прикладі виходить 4 точки від 0 до 3.
• Тепер ми готові перейти до моделі кінцевого автомата і написати-таки нашу програму.
• Уявіть, що є якийсь блок, який може знаходитися в одному з 4 станів. І є набір дій, в результаті яких блок переходить з одного стану в інший.
• Для відображення цього самого стану, заведемо в програмі деяку змінну, скажімо, 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 і інших неприємностей.

усвідомлення

А тепер, після того, як ми добилися такого блискучого результату, давайте усвідомимо: що ж ми зробили і що у нас вийшло. Що зробили (або як все це назвати по-справжньому)

• Ми зобразили наш алгоритм як блок-схему або, іншими словами, спрямований граф
• Потім провели інваріантне перетворення цього графа з виділенням декількох стаціонарних станів програми - кінцевого автомата
• В результаті отримали новий граф, який легко укладається в структурні конструкції Паскаля (Delphi)

Проводячи зазначені дії кілька разів для різних алгоритмів, можна помітити, що насправді наші довільно розставлені крапки-стану не такі вже випадкові і довільні. Як правило, при більш глибокому розгляді вашого конкретного алгоритму можна знайти кожному з цих станів свою назву. Ця назва може бути набагато більш виразним, ніж просто 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;

Чудово, що Delphi все ще підтримує цю специфікацію і навіть показує при налагодженні символьне уявлення стану! Це дуже зручно на практиці. Дякуємо, Borland ! інший наслідок

Можливо ви, як і я, зробивши підряд кілька таких перетворень і увійшовши у смак, помітите, що стали мислити при програмуванні трохи інакше. Іноді, особливо коли завдання кілька заплутана, хочеться відразу виділити кілька важливих станів і будувати обробник вже навколо них. Це правильне бажання, йому варто потурати. :-)

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

Невелике дослідження: крайні випадки

Як сказав один мудрий чоловік, "Ідея, доведена до абсурду, часто перетворюється на свою протилежність". Давайте спробуємо довести наш метод до крайнього ступеня.

У нашому випадку це означає додавання ще двох станів - 4 і 5. Тоді програма набуде вигляду:

Добре це чи погано?

Добре, в тому сенсі, що навіть при такому знущанні програма не перестає працювати правильно. З іншого боку, подивіться на вихідний код: де прозорість, де легкість і ясність? Суть алгоритму розчинена в суцільних переходах станів і через це втрачається.
Ні, мабуть цей варіант нам не підходить.

А що, якщо піти в іншу сторону і зменшити число виділених станів? У нашому прикладі реально тільки виключити стан 2.
(Так, я знаю, на блок-схемі двійка є, але давайте поки її не помічати, OK? :)

Після "приведення подібних" програма буде мати наступний вигляд:

(Якщо незрозуміло, то тут формально виходять дві гілки ELSE, провідні обидві до третього стану. Якщо стан винести вгору, до умови, то програма виходить коротше. Втім, це - справа смаку :)

Як вам цей варіант? Мені здається він теж має право на життя, хоча особисто мені варіант з чотирма станами подобається більше. Якось він наочніше показує що куди переходить і за яких умов. А вам?

Передбачаю заперечення такого штибу, що при подібному підході програми матимуть підвищену схильність до зациклення. І так і ні. Цикли взагалі схильні до зациклення :-) особливо якщо написати що-небудь на зразок repeat until false; . Так на то і голова дана, щоб карась не дрімав!

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

І, нарешті, мені потрібно розставити крапки над i.

Я ні в якій мірі не претендую на авторство в даному формальному підході, більш того, всі проблеми і рішення, викладені в цій статті, відомі вже досить давно. Моя мета була просто нагадати вам про один красивому, але, боюся, забутому підході до програмування на Паскалі і Delphi.

Пишіть, якщо надумаєте чим поділитися,
George Columbow