На рис. 1 приведена блок-схема алгоритма нахождения наибольшего общего делителя двух натуральных чисел из книги Н. Вирта[1]. С таких алгоритмов, да и с подобных книг, начинается или должно начинаться знакомство с программированием. И, кстати, книга Н.Вирта была одной из первых, с которой в свое время познакомился и я. Так что здесь присутствует и некий личный мотив.
Рис.2. Блок-схема программы вычисления НОД 2-х натуральных чиселВ немного измененном виде данная блок-схема приведена на рис.2. В такой форме она, во-первых, ближе к существующей практике документирование программ. Во-вторых, изменены имена переменных, что будет удобнее для дальнейших ее преобразований. Например, если на структурном уровне представить программу в форме "черного ящика"/блока, имеющего входы, обозначаемые обычно символами x1, ..., xm, и выходы - y1, ..., yn. В-третьих, в целях последующего перехода к эквивалентному блок-схеме автомату она размечена символами предикатов - x1, ..., действий - y1, ... и состояний - S0, S1, END.
Но прежде чем мы перейдем к автоматной модели рассмотрим реализацию на языке программирования в среде SimInTech. Такой код приведен на рис. 3, а на рис. 4 - ее структурный вариант. Сам выбор среды обусловлен не только особыми предпочтениями автора, а ее доступностью, а также идентичностью ее внутреннего языка программирования языку, который используется, да и собственно придуман, автором книги - Николаусом Виртом. Также немаловажно, что визуальных возможностей SimInTech вполне достаточно для наглядной демонстрации тех идей, о которых нам еще предстоит поговорить. Не думаю, что выбор того же MATLAB-а привел бы к другим результатам (хотя убедиться в этом было бы интересно).
Автоматная модель алгоритма НОД
Выше представлен наиболее типовой подход к реализации любого алгоритма. В его основе понятие блок-схемной модели программ. Эта же модель лежит в основе самых известных языков программирования.
Придуманы блок-схемы были достаточно давно фон Нейманом, но до сих пор на них базируется и программирование, и архитектура процессоров. Такой связкой объясняется и достаточно высокая эффективность реализации подобной модели. Однако на блок-схемах "свет клином не сошелся", т.к. хорошо известны другие модели, одну из которых мы далее рассмотрим. Это модель алгоритмов на базе модели конечного автомата (КА).
От размеченной на рис. 2 блок-схемы несложно перейти к модели КА. Соответствующая модель приведена на рис. 5, а рис. 6 демонстрирует ее реализацию в рамках возможностей визуального программирования среды ВКПа.
Так что нам дает модель КА, кроме хлопот по ее освоению? И, безусловно, речь не идет о ситуации, когда сначала рисуется блок-схема, а затем по ней создается автомат. Новая модель подразумевает и такое мышление, когда автоматный алгоритм создается напрямую.
Выше это демонстрация, скажем так, не только соответствующего алгоритмического мышления, но и доказательство того, что состояния, которые в явном виде фиксируются в автомате, присущи, хотим мы того или нет, но и блок-схемам.
Однако было бы крайне опрометчиво только ради некоего эфемерного преимущества "ломать" уже сложившееся годами мышление: графическое представление, возможно, у автомата и компактнее, но код реализации у модели блок-схемы будет явно короче (по крайней мере, для рассматриваемого примера). И связано это отнюдь не только с "заточенностью" существующих языков программирования под модель блок-схем.
Параллелизм процессов
Модель блок-схем формировалась во времена, когда интерес к параллелизму был не столь повальным, как в нынешние времена. Это нашло даже свое отражение в теории. Так, например, на формальном уровне к алгоритму предъявляются требования по результативности и конечности исполнения. Но процессы достаточно часто не предполагают конечности исполнения, а понятие результативности процесса может быть достаточно размытым. И, несмотря на то, что наш алгоритм НОД явно соответствует требованиям конечности и результативности, при реализации его, как процесса, эти требования должны быть явно пересмотрены. Этим мы далее и займемся.
Превратить любую функцию в процесс достаточно просто. Для этого достаточно включить ее вызов (или ее тело) в бесконечный цикл. Для нашего алгоритма это может выглядеть так (ср. также с рис. 3):
Но такой цикл сразу "рушит" проект, исключая его, видимо, в отместку даже из списка "История" среды, с чем можно даже согласиться. Следовательно, любые подобные - бесконечные процессы в SimInTech недопустимы.
С другой стороны среда SimInTech организует запуск функций/блоков на каждом дискретном шаге исполнения проекта и тем самым поневоле моделирует процессы, но только в пределах заданного в настройках конечного времени расчета. Имитации реального времени служит и режим синхронизации с реальным временем. Но режим "бесконечного" времени, похоже, не предусмотрен.
В ВКПа ситуация с реализацией процессов иная. Любой автомат, как процесс, не ограничен во времени. Запущенный однажды, если не предусмотрено его завершение "насильно", он будет работать "бесконечно", т.е. пока среда не завершит работу. Для этого достаточно зациклить автомат, т.е., например, в нашем случае изменить состояние END на S0.
Имея условные, как в SimInTech, или реальные, как в ВКПа, процессы, можно собирать из них более сложные схемы. Соберем схему из трех НОД. Ее вид вместе с результатами ее работы в SimInTech представлен на рис. 8.
И, вроде, все правильно, по конечному результату, но смущает вид графиков - не отражена динамика процессов, т.к. время нахожнения ими конечного результата явно у них разное. По крайней мере у двух: процесс, имеющий на входах значения 1005 и 5, потратит на нахождение НОД явно дискретных шагов, чем процесс, имеющий на входах значения 10 и 2.
Соберем для проверки ровно такую же схему в ВКПа и ... мы даже не получим результаты, показанные на рис. 8! В чем же дело?
Ошибка Вирта?
Проблема была выявлена достаточно быстро: выходной процесс завис в состоянии S1 (вот вам и преимущество КА). А причина в том, что один из входных параметров процесса остался в нулевом значении, когда второй изменил свое значение. В такой ситуации автомат попадает в состояние S1 и уже из него не выйдет, т.к. сколько не вычитай 0 к равенству значений a и b (условие нахождения НОД) не прийти никак. Ну, а далее все уже просто: переход из начального состояния S0 должен происходить только при ненулевых значениях входных параметров.
Но почему нет зависания в SimInTech, ведь, алгоритм один и тот же? Делаем проверку: обнуляем любой из входных параметров и ... проект "ломается"! До этого же это не случилось только потому, что блоки в среде запускаются по очереди и исполняются до завершения их работы, а потому на входы выходного блока перед его запуском попадали уже вычисленные значения, среди которых не было нулевого. А, исходя из этого, уже становится понятен и вид полученной диаграммы. Таким образом, ожидаемого параллелизма работы блоков не получилось.
А теперь несколько слов собственно по поводу ошибки... Действительно, может показаться что блок-схема алгоритма не верна, т.к. в ней отсутствует проверка входных параметров на нулевые значения. Но, если внимательно вчитаться в условие задачи, то там идет речь об натуральных числах. А к ним относятся только положительные числа не равные нулю. В языке же программирования нет понятия типа натурального числа, что породило ошибку. Входная проверка параметров эту проблему решает.
Но, если с проблемами контроля чисел мы разобрались, то как все же отразить динамику работы блоков?
Автоматы в SimInTech
Обратимся к автоматам. Их реализацию в SimInTech мы уже рассматривали ранее (см. [2]). Таким образом, реализация алгоритма НОД в автоматной форме, но на внутреннем языке программирования и с учетом решения обнаруженных проблем, будет следующей:
На рис. 10 приведена схема и результаты работы автоматного алгоритма НОД в SimInTech. Сама схема из блоков осталась неизменной, но графики теперь уже отражают динамику работы процессов (для наглядности дискретный шаг проекта был увеличен на порядок).
Выводы
Анализируя результаты работы, можно убедиться в том, что даже такая простая задача:
обратила внимание на проблему работы с типами данных,
подчеркнула необходимость контроля за состоянием программы,
выявила "вредность" оператора while,
позволила разобраться с алгоритмами реализации блоков в SimInTech,
показала решение, позволяющее исключить использование оператора while,
обнаружила проблемы с реализацией параллелизма в SimInTech.
Типы данных. Провоцирует скрытые и, порой, сложно обнаруживаемые ошибки. Автор, если честно, просто не обратил внимание на слово "натуральные". И проявилось это уже на этапе тестирования. Надо быть внимательнее, оперируя типами данных.
Контроль состояния программы. Если бы этого не было, то, уверен, ошибку так просто идентифицировать было бы гораздо сложнее. А так, понятно, что "висит" и ясно где. Дальше - дело техники.
Оператор while. Когда-то было заявлено о вреде оператора "go to" и было придумано структурное программирование, доказывающее, что можно обойтись без него. И все это в целом повысило качество программирования. Автоматное программирование демонстрирует, как можно совсем исключить не только операторы цикла, но и условные операторы из программ. И это тоже принесет только пользу делу. Но здесь не надо впадать в крайности: в рамках действий автоматной программы их применение вполне оправдано, т.к. легко поддается контролю.
Реализация процессов. Параллелизм в программировании это не только и не столько "распихивание" процессов по ядрам или потокам. Это и его реализация в рамках одного потока. На практике это осуществляется простым переключением между процессами, прерывая одни и запуская другие. Здесь главное, чтобы процесс, захвативший поток, не держал его очень долго, блокируя работу остальных. В нашем случае анализ работы компонент/блоков проекта склоняет именно к такому предположению. Хочется надеяться, что мы не ошиблись.
Параллелизм процессов. Ответ на предыдущий вопрос тесно связан с проблемами реализации параллелизма в программах. Автоматное программирование предлагает модель реализации параллелизма, когда он (параллелизм) абсолютно не завит от его реализации. Здесь, хотя один поток, хотя множестве ядер или множестве потоков, результат должен быть один. Таково должно быть качество правильной модели параллельных вычислений, когда ни по результату работы, ни по коду программы нельзя будет определить, как реализован параллелизм. Хотя последнее сделать немного сложнее, но тоже вполне возможно.
Предложенный прием реализации автоматов в SimInTech, а ранее и для ПЛК, позволяет пусть не в полном объеме, но все же реализовать базовые принципы автоматного программирования. Так можно познакомиться с ними, накопить необходимый опыт. При этом вам не понадобиться даже ВКПа. Ну, а когда такой опыт появится, то и возникнет и вкус к автоматному программированию. Вот тогда можно будет вести разговор о полноценной модели автоматного программирования.
Конечно, Н.Вирт не ошибся, но ... слукавил, использовав понятие натурального числа. При этом явно указал, что переменные алгоритма - целые числа (см. рис. 1). Хотя явно результат НОД для двух натуральных чисел тоже должен быть натуральным числом. Что тут скажешь, - запутал. Тем более, что этот тип данных в созданный им язык он так и не ввел.
Литература
1. Вирт Н. Систематическое программирование. Введение: Пер с англ. – М.:Мир, 1977. – 184 с.
2. C++, параллелизм и введение в автоматное программирование в SimInTech. [Электронный ресурс], Режим доступа: https://habr.com/ru/articles/719592/ свободный.
Яз. рус. (дата обращения 07.07.2023).
