Машина Поста (мП) есть математическая конструкция (т.е. её можно изучать математическими средствами и методами) блок-схемы, которая в свою очередь является средством написания и осмысления алгоритма процедуры, функции, метода, главного блока...
Блок-схема хороша тем, что оперируя существенными элементами алгоритма (уложенного в граф) ещё абстрагирована от "нюансов" языка программирования, т.е. кодирования.
Обобщённая мП (омП) есть граф узлы которого помечены действиями, а исходящие стрелки помечены однозначно (т.е. метки не повторяются) и не обязательно значениями истинности (true, false).
Идеи
Наше обобщение состоит в том, чтобы распространить на мП подход применённый для определения Тьюрингола:
1. принцип "Пиши точно и всё ("до конца") что нужно делать в узле." В "Turingol" описан подход в котором в узлах синтаксического дерева программы размещаются инструкции исполнителю. Этот подход позволяет Исполнителю перемещаться по графу программы "налегке" без всякой инструкции выполнения инструкций в узлах;-)
Аналогичное описание мП, т.е. точная запись инструкций в узлах мП приводит в основном лишь к добавлению "Перейти по исходящей стрелке." в узлы "ШВпр" (шаг вправо), "ШВл", "ПМ" (печатать метку), "СМ" (стереть метку).
- Кроме того мы ещё присоединили ленту к стартовому узлу стрелкой "tape", которая втыкается в текущую ячейку ленты;
- а также решили, что лента будет конечной, что потребовало самых сложных инструкций - достройки ленты;-)
- и ещё: в формулах и действиях употребляются "указание пути" - специальное цепочечное выражение указывающее как пройти от одного (указанного или текущего) узла по стрелкам к другому, чтобы "взять" его метку...
2. омП фактически является [логической] блок-схемой алгоритма, которую не всегда удобно и "наглядно" записывать "линейно".
С другой стороны писать в узлах омП желательно на каком-то ограниченном естественном языке (ОЕЯ), чтобы его можно было автоматически преобразовывать в код;-)
Сериализация
+!: в мП нет меток узла! т.к. достаточно метить исходящие стрелки. а в сериализации приходится переходить от меток стрелок (которые не уникальны!) к меткам узла!!!
= при этом как ни странно лучше пронумеровать узлы (аля Паскаль) и именно эти уникальные номера использовать как метки сериализации!!!
НО при этом переходы по меткам стрелок должны быть "пересчитаны" в переходы на метку узла! т.е. go_by <метка_стрелки> должен быть заменён на goto <номер_узла>!
БОЛЕЕ ТОГО если в графе есть "линейный участок", то его внутренним узлам номера не нужны, т.к. при укладке в цепь строк подразумеваемый переход к следующей строке даст то что надо.
Аналогично с "ПУ" узлом мП и "if" узлом Тьюрингола: если их стрелки втыкаются в узлы имеющие и другие входящие стрелки, то придётся использовать goto...
Представление графа текстом иногда называют сериализацией.
номера узлов, конструкция if-then-else являются элементами сериализации, т.е. в мП их нет.
Хотя действие может быть "закрыто" условием if-then.
- синтаксис кода для узла мП:
<номер_узла>
(<действие> | if <формула> then <действие>)*
if <формула> then <метка_1> else <метка_2> | stop | return | go_by <метка_стрелки>
return введён чтобы мП можно было вызывать из другой мП.
система меток
вместе с then-else представляет сериализацию графа у которого должен быть только один источник, который и будет точкой входа в мП.
Действия
омП работает с конечной моделью некоторой теории (в интересующем нас случае теория это исчисление предикатов с числами).
Часто (особенно в ЯП) эта модель - помеченный граф.
Действия мП это:
- перемещение по графу (что даёт текущие узел и стрелку);
- изменение меток узлов и стрелок;
- перестройка графа: добавление/удаление стрелок и узлов.
Управление:
- call <идентификатор>
где идентификатор задаёт какую мП вызвать.
Формула
Формула берётся из теории.
+У: формула может содержать дополнительные символы - для текущего узла и текущей стелки?
Имя мП
Каждая мП должна иметь уникальное имя. Первым оператором "программы" мП должен быть:
Post_machine <идентификатор>
+ надо выяснить: в СЯП один из языков "семантики" использует оператор действия "закрытого" условием - "условное действие". этот язык переусложнён(?), но содержит, то что понадобилось и нам при описании Тьюрингола - условное действие!
!Этот подход, возможно, называется "система продукций Ледгарда" см. [СЯП], с.48, введение, где "под каждым словом можно подписаться"!
- Английская версия этой статьи - p191-marcotty.pdf. About "Production systems" see p216(26).
- см. также "Production systems: or can we do better than BNF" в ACM dlib в моём Binder.
p(2)"The motivation for the use of production
systems is not (at this point) to provide a method
for parsing, compiling, or theorem proving. Rather,
the objective is to provide a readable, well-structured
definition for human consumption."
!
++ в этой статье нотация разъясняется - можно разобраться!
!а возможно имелся в виду и другой подход! см. например работу Донаху в конце СЯП.