Структуры управления

ПРОСТОТА, КОТОРАЯ ХУЖЕ ВОРОВСТВА

Многие фортеры подозревают FORTH в избыточной "структурности". Ведь, если "структурный" программист строит свои программы из кирпичиков-блоков "begin ... end", "if ... fi" и "do ... do", отказываясь от возможности передачи управления внутрь блоков (и из них), то в FORTH требуется соблюдать еще более строгую дисциплину - используя неделимые кубики - слова. И даже, если отказаться от использования от структур управления FORTH (представляющих собой вариант тех же структурных блоков), введя какой-то аналог go to (т.е. перехода по метке - передачи управления из любого места программы в любое другое), то, все равно, это будет возможно только внутри одного слова - идеально структурного снаружи кирпичика.

Так стоит ли бороться за какую-то свободу, если за пределы клетки все равно не выскочишь?
***

Для обычных языков программирования очевидно, что при наличии какой-либо адресной арифметики (например, массивов) для написания любой программы достаточно всего трех операторов:
- присваивания;
- if условие then оператор;
- go to метка.
(Примечание: при совсем уж развитой адресной арифметике можно обойтись и одним присваиванием, но такой язык уже "обычным" не назовешь).

Значит, все эти "выборы", циклы "до" и "пока" - только украшательство?
К тому же, мешающее упражняться в финтах, вроде конечных автоматов, сопрограмм и т.п.?

Зачем вообще понадобилось ограничивать программиста только заранее заготовленными структурами управления?
Чтобы он, дурак, не запутался?

ДЕЙКСТРА - ВРАГ GO TO?

Дейкстра, на которого ссылаются как на главного врага go to, действительно приложил руку к структурному программированию, но совершенно не с целью усложнить жизнь любителей передач управления куда попало. Он заметил одну очевидную проблему, которая, как ему показалось, очень сильно ограничивает возможность построения правильных программ.

Проблема заключается в следующем. Если мы имеем программный код, по которому программистом разбросаны go to, то нет никакой возможности определить, какие условия будут выполняться после очередной передачи управления. Данный результат строго следует из того, что мы знаем о машине Тьюринга: ни одна машина не может предсказать поведение другой машины (хотя, может ее моделировать). Т.е. этакая добротная математическая невозможность, а совсем не соображения о читабельности или производительности кода. Т.о. доказать правильность программы, содержащей go to, оказалось просто заведомо невозможно.

Тогда Дейкстра придумал некий алгоритм построения заведомо правильных программ. Правильных по самому способу их построения. (Подробнее см. его книгу "Дисциплина программирования"). И использование блоков-кирпичиков, инкапсулирующих в себе области видимости переменных и структуры управления - лишь одна из составляющих решения Дейкстры. Использование этих структур без применения остального разработанного им аппарата - просто копирование внешней формы без учета внутреннего содержания.
***

Т.о. записывать Дейкстру во враги go to столь же смешно, как и считать его врагом рекурсии, вопрос о которой он в упомянутой книге обошел ввиду сложности.

МОЖНО ЛИ ИСПОЛЬЗОВАТЬ GO TO НА FORTH?
В принципе, для передачи управления внутри слова в распоряжении фортера всего шесть специальных слов: BRANCH , ?BRANCH , >MARK , >RESOLVE , <MARK , <RESOLVE . (Как они работают - см. у Баранова и Ноздрунова ТЕМА #120, АБЗАЦ #2030). Из них можно собрать все, что угодно - и стандартные IF-ы и WHILE-ы, и более сложные LOOP-ы или арифметический FORTRAN-IF, а можно и GOTO... Например, реализация синтаксиса Дейкстровских "if ... fi" и "do ... od" заняла у меня когда-то всего один стандартный 1024-байтный блок.

На этом пути нас поджидают всего две трудности:
1. При компиляции этих конструкций активно используется стек (некоторые авторы предпочитают выделять для этого отдельный стек - управления, но это здесь не важно). В стеке запоминаются все неразрешенные пока ссылки переходов. А что такое стек, мы знаем: последним пришел - первым ушел.
Такая организация предполагает самую что ни на еть структурную организацию переходов - правильную вложенность одного программного блока в другой. Иметь перепутанное "спагетти" GOTO - значит отказаться от стека и выделять в памяти специальное место для хранения меток перехода, как FORTH-ассемблерах (или перетасовывать стек каждый раз вручную).
2. Легко было Дейкстре: мол, одна ячейка - одно слово или литерал, что на стеке, что в шитом коде. В практической реализации Мура получилось хуже (зато, работает) - некоторые слова занимают в шитом коде одну ячейку, а другие - две и больше. К последним относятся (наравне с литералами) и наши BRANCH-и - одна ячейка код, другая - адрес перехода. Большое количество таких слов может привести к тому, что "нормальный" шитый код может превратится в "обычный байт-код", нечитаемый за счет того, что в отличие от последнего набор "байт-команд" и их "формат" не фиксированы. Заводить вспомогательные (локальные) слова-переходы и слова-литералы, хранящие свои параметры где-то в другом месте? Делать большие ячейки, чтобы поместился и параметр? Именно об этом предупреждал Дейкстра, говоря, что упрощения в стеково-шитой модели еще обернуться усложнением в ее реализации.
Еще один минус такой излишней параметризованности слов состоит в том, что во время исполнения таких слов надо где-то размещать текущие значения этих параметров. (Посмотрите, например, на то, во что превращает DO...LOOP стек возвратов).

И, повторю, все это так необходимо, если за пределы слова все равно не выпрыгнешь?

АДРЕСНАЯ АРИФМЕТИКА

Есть ли другие способы организовать нетривиальную передачу управления кроме привычного "IF ... GOTO ..."?
"Ибо сказано Броуди: не возжелай IF-ов, если можно вычислить или посмотреть в таблице..."

Я уже писал (там, где про FOBOS), что страшные видом операторы выбора, рекомендованные Биллом для разбора сообщений Windows, были очень быстро заменены на элегантные таблицы (ассоциативные массивы), содержащие указатели функций-обработчиков. Вообще же, с появлением языка C появилась альтернатива - перейти к нужному фрагменту кода путем сложных логических вычислений (выборов), либо вычислить его адрес арифметически.

Казалось бы, для FORTH с его отсутствием соглашений о вызове, такой метод должен вытеснить сложные ветвления напрочь, но этого не случилось. Даже, невзирая на то, что Мур изначально предлагал вынести процедуру выбора следующего слова за пределы слов. Каждое из слов, по его задумке, возвращало управление в одну и ту же точку - в начало Цикла Управления. А уже процедура, обслуживающая цикл, решала откуда брать следующее слово - с текущей позиции курсора входного потока или с текущей позиции курсора шитого кода. Позднее от единого цикла отказались (см. раздел про Цикл Управления): цикл чтения потока реализуется циклом специального отдельного слова, а цикл чтения шитого кода реализуется включением кода "найди следующее слово" внутрь каждого слова (кроме вырожденных систем с косвенным шитым кодом). Однако, способ вызвать любое слово и вернуться в то же место (слово EXECUTE) с тех пор сохранился.

Это позволяет использовать ЛЮБЫЕ структуры (в том числе многомерные и/или динамические) для организации управления. Размещаем адреса нужных слов в самую что ни на есть заумную структуру, изобретаем еще более заумный алгоритм перебора этой структуры - и получаем программу, запутанную так, что ни одному любителю go to не снилось.

В принципе, это было возможно уже в языке C (чем и пользуются любители эмулировать FORTH на этом языке), и минус этого подхода тот же, что и в программировании на C: для каждого логически обособленного куска надо изобретать осмысленное имя.
***

Зато, мы можем таким путем преодолеть проклятие разработки "сверху-вниз" - определение иерархии программы логикой ее управляющих структур. При таком подходе программа представляется развесистым деревом вложенных блоков, где действие сосредоточено исключительно в листьях, а ветви лишь определяют условия, при которых какой-либо лист получает управление. (А при ООП большая часть листьев "засохшая" и будет обрезана при компиляции).

Методом описания структуры управления в виде структуры данных и процедуры ее перебора (обычно это конечный автомат) мы можем отказаться от размещения управления на верхних этажах программы и разместить ее "где-то сбоку", четко сказав: этот кусок - что-то делает, а этот - управляет его работой...

ВНУТРЕННИЕ РЕЗЕРВЫ СЛОВА

Вернемся к Баранову и Ноздрунову - к стеку возвратов. Вопреки желанию Мура, стремящегося всю логику FORTH втиснуть в Цикл Управления, слова сразу получили возможность повлиять на его работу (иначе было, понятно, никак). В первую очередь - играя значениями на стеке возвратов. Т.о. слово, например, вполне способно иметь два выхода в разные места - по успеху и неуспеху (не путать с ABORT"), это удобно, например, при разборе шаблонов и ближе к логике процессора, который обычно связывает условный переход с результатом последней операции. Можно применять различные структуры шитого кода (ведь, слово само себя исполняет) - создавая if-слова или do-слова по Дейкстре, в которых условия и действия прошиты каким-то заранее определенным способом. Можно создавать слова, имеющие префиксы условного исполнения и/или указателя числа повторений.

Конечно, все слова FORTH-системы делать монстрами не следует, тем более, что "обычные средства" вполне позволяют обеспечить все нужное для задачи управление. А, вот, при создании новых проблемно-ориентированных языков, слова с нестандартным шитым кодом вполне могут пригодится.

НЕКОМПИЛИРУЮЩИЕ УПРАВЛЯЮЩИЕ СЛОВА

Время от времени предпринимаются попытки позволить управляющим словам работать вне каких-либо определений.
Например так:

3 FOR VARIABLE NEXT НАФ-НАФ НУФ-НУФ НИФ-НИФ

Вместо:

: ТРИ-ПОРОСЕНКА 3 0 DO VARIABLE LOOP ;
ТРИ-ПОРОСЕНКА НАФ-НАФ НУФ-НУФ НИФ-НИФ

Если речь идет о конструкции без петель, то очевидно можно обойтись оборотами работающими только в терминах чтения/пропуска текста, как это обычно делается для "препроцессорных" [IF] [ELSE] [THEN] (аналогичных C-шным #if #else #endif).
В случае же циклических конструкций, необходим какой-то род временной компиляции.

Но, пока, простые решения:

HERE ЗАПАС ALLOT : ЗАПИХАТЬ <...> ; ЗАПИХАТЬ FORGET ЗАПИХАТЬ

кажутся здесь предпочтительнее.


НЕПОСЛЕДОВАТЕЛЬНЫЕ СЛОВА

Используя всякого рода "условно-исполняемые" слова, мы можем заметить, что определяемое слово совершенно не обязано выполнять подряд все прописанные в него слова.

Например, игра ("в кораблики") может быть прописана как набор частей:

: ИГРА BEGIN ФЛАГ WHILE КОМПАС МЕРКАТОР СУНДУК ПАРТИЯ КЛАБАУТЕРМАН REPEAT ;

И отсюда совсем не следует, что за МЕРКАТОРОМ обязательно следует СУНДУК. СУНДУК может "пропустить свою очередь". В зависимости от состояния (ФАЗЫ) игры чаще всего на каждом прогоне будет исполняться только одно из слов (плюс КОМПАС, который в данном случае управляет переключением ФАЗ).

Когда-то о чем-то подобном писал Тузов, говоря о неких "скобках", возвращающих нужный тип данных из четырех возможных.

Возвращаясь к Дейкстре (и развитии метода в языке ОККАМ), мы можем видеть варианты прошивки слов в код: seq, par, if, do... Причем, как группируя слова, так и группы слов (используя "скобки", вроде дейскстровских "->" и "[]"). Но суть-то хитрости не в создании новых типов определяющих слов, а в том, что слово может само определять, что оно делает в данной ситуации. И делать это столь успешно, что порядок слов в определении может совершенно не соответствовать порядку их исполнения.

Т.е. возможно не только:

: СЛОЖНОЕ-ДЕЙСТВИЕ ПЕРВОЕ ВТОРОЕ ... ПОСЛЕДНЕЕ ;

но и

: СЛОЖНЫЙ-ОБЪЕКТ ЛЕВАЯ-ЧАСТЬ ПРАВАЯ-ЧАСТЬ ... ЗАДНЯЯ-ЧАСТЬ ;

ЦИКЛЫ

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

Итак, мы имеем две "конструкции":

конец начало DO ... LOOP

и

конец начало DO ... приращение +LOOP

Кажется, что все очевидно. Но тут два нюанса: во-первых, т.к. в FORTH нет синтаксиса, то начальный DO совершенно не в курсе, чем закончится "конструкция" (и закончится ли она вообще), а во-вторых, если в первом случае все понятно, цикл закончится тогда, когда после очередного приращения на 1, значение переменной цикла сравняется со значением "конец", то во втором следует ловить и факт того, что переменная "перепрыгнет конец".

В стандарте писано: "отслеживается пересечение границы "конец" и "конец - 1"". Если в случае LOOP (т.е. +1) это событие автоматически наступает при достижении "конца", что позволяет фортерам гордо шокировать не-фортеров тем, что цикл

0 0 DO ... LOOP

выполнится ровно столько раз, сколько есть целых чисел, то +LOOP очевидно "глючит".

Например, цикл

0 25 DO ... 5 +LOOP

выполнится в точках 0, 5, 10, 15, 20, то цикл

25 0 DO ... -5 +LOOP

выполнится в точках 25, 20, 15, 10, 5, 0, т.е. на один раз больше.

Примирить с этим может тот факт, что обычно обратный цикл применяется для обработки массивов "с конца" и тогда

конец-1 0 DO ... -1 +LOOP

вроде бы значит именно то, чего мы хотели.
***

Программисты обычно выкручиваются следующим образом - DO заменяет два введенных числа-границы одним - размером необработанного промежутка т.о. и LOOP и +LOOP проверяют одно и то же - пресечение границы -1/0. "Отслеживается пересечение границы "конец" и "конец - 1"" - это тоже, на самом деле, жульничество, вызванное наличием у многих процессоров (особенно, конечно, Intel x86) возможности проверки этого условия одной командой (проверкой флага переполнения), а совсем не "тщательно продуманное решение".
***

Но это еще не конец.
Дело в том, что сложение и вычитание выглядят в Intel одинаково и для знаковых, и для беззнаковых чисел, а сравнение знаковых и беззнаковых выполняются разными командами. Т.о. проверки того, что старое и новое значение счетчика цикла лежат по разные стороны границы, описанной в стандарте, можно по-разному.

Например, старое значение счетчика -5, новое 5, граница между -1 и 0. Очевидно, в знаковом варианте пересечение было. А в беззнаковом?

Пусть, для простоты, у нас 8-битовые числа. Тогда, старое 251, новое 5, граница между 255 и 0. Какое, нафиг, пересечение? Более того, в беззнаковом варианте границу 255-0 вообще невозможно пересечь. Все числа лежат по одну ее сторону. Отслеживать флаг переносов? Но, ведь, программист вполне мог считать, что приращение в данном случае -246 (ну, захотелось ему перейти от 251-го элемента к 5-му, кто запретит? ведь, слова -LOOP нет) и никакого пересечения границы и быть не должно!

Так, что тут дело не в математике, а в простой логике. Ситуация с одновременным пересечением границы цикла и границ, разграничивающих знаковые и беззнаковые, неразрешима в принципе...

Один программист подразумевает одно, другой - другое, на всех не угодишь.
***

Еще одна неприятность с DO - активное использование ею стека возвратов (или специального стека циклов), надо там хранить и текущее состояние счетчика, и конечное значение, и адрес конца цикла на случай внезапного желания покинуть цикл при помощи слова LEAVE...

А ведь тот же Intel имеет простые команды для организации цикла "повторить CХ раз". Неудивительно, что фортеры пишут свои упрощенные циклы вместо тяжеловесного DO.

Проще всего, видимо, дописать еще одно слово, парное к BEGIN (подобно WHILE, REPEAT и т.д.) - LOOP, которое будет брать со стека адрес переменной, декрементировать ее и прыгать на начало цикла, если не достигнут 0.
***

Также стоит отметить, что, несмотря на "красоту" конструкции "0 0 DO ... LOOP", программисты постоянно пишут одно и то же: "2DUP - IF DO ... LOOP THEN". Для этого даже придумано специальное слово - ?DO.