1. Преамбула
40 лет тому назад я разработал геометрический язык и написал транслятор чертежей, но бросил разработку на произвол судьбы, т.к. отчетливо понимал, что по-хорошему, чтобы транслятор "взлетел", в него нужно встроить интерпретатор простого алгоритмического языка. Честно говоря, я был не готов к этому, и было лень этим заниматься, да и в тот момент я поменял место работы. Все один к одному...
А на днях я закончил разработку интерпретатора Forth (пока без API обёртки), исполнив свой 40-летний долг, после того как мне понадобились числовые движки в узлах ориентированного графа процессов на базе GenServer OTP в Elixir.
Для развития технологии мне требовалось реализовать Forth в объеме, описанном в известном начальном учебнике [1]. Разработанный интерпретатор Forth на языке Elixir получил рабочее название Forth-ibE, в котором суффикс произносится [айби] и составлен из двух слов: in-built и Elixir.
На разработку ушло 5 месяцев вместе с первоочередным патентным поиском. Именно с него начались неожиданные интересные эпизоды разработки. Поэтому я решил рассказать не о технических деталях реализации, а о нечто большем: о психологическом квесте в ходе разработке.
С техническими деталями реализации Forth-ibE можно познакомится на сайте GitHub https://github.com/VAK-53/Forth-ibE. Прикладные аспекты Forth-ibE заключены в приложении «ТУ на интерпретатор Forth-ibE» в конце данной статьи.
2. Патентный поиск. По теме интерпретатор на языке Elixir в Интернете было найдено достаточно много примеров, но они поставили передо мной одну задачу, которую я потом решал 3 месяца.
Здесь я хотел бы выделить две, на мой взгляд, самые заслуживающие внимание реализации [2,3].
Разработка [2] являлась самой интересной, но мне было не понятен мотив высокопрофессиональная работа с целью созданию многопоточной виртуальной машины интерпретатора Forth. Не скрою, что мне было полезно изучать работу [2], но сам автор называет свою продукцию игрушкой (toy).
Еще я выявил следующий неожиданный факт:
все реализации Forth на Elixir строят AST (дерево!) на этапе синтаксического анализатора, пренебрегая готовой входной постфиксной нотацией.
Получалось как в известной логической задаче — чтобы вскипятить чайник нужно сначала вылить из него воду, т.к. первой сакральной операцией согласно принятой теории является заполнение чайника водой и только потом он ставится на огонь.
Еще раз сформулирую возникшую загадку в виде вопроса:
Почему разработчики интерпретатора Forth сплошь и рядом строят синтаксическим анализатором AST, а не оставляют готовую входную постфиксную нотацию для дальнейшей интерпретации? Почему выходные обработанные данные лексического сканера не используются прямо в стеке?
Я адресовал этот вопрос автору работы [3]. На что получил довольно быстрый ответ. Перевод Google оставлен без исправления:
«Привет!
Интерпретатор Forth для Elixir звучит как очень интересный проект!
Что касается архитектуры: я ориентировался на реализацию на Golang , которая работает с лексером, парсером и оценщиком, поэтому я также выбрал этот подход.
Боюсь, я мало чем смогу помочь с вашим вопросом: я не могу сказать, что вам нужно сделать, чтобы пропустить AST, и я также не являюсь экспертом в области Forth.
Думаю, вам просто нужно попробовать! :)
Кристиан!»
Такой была стартовая точка работы над интерпретатором Forth.
3. Драматическая сторона реализации интерпретатора
Я 3 месяца потратил на то, чтобы попытаться найти ответ на возникший теоретический вопрос. Просмотрел кучу книг и статей. Конечно, смотрел и хвалёную книгу с драконами. Пытался проконсультироваться у профессионального разработчика транслятора. От него я получил замечательный ответ:
«Вячеслав!
(1) Я программированию никогда не учился и никаких технологий парсеров никогда не использовал.
(2) Все парсеры и использующие их программы я "разрабатывал" и писал их сам по своему недоразумению.»
Этот ответ меня вдохновил на отчаянный шаг отложить в сторону все книги и начать делать всё так, как я представлял и понимал самостоятельно.
Разработка шла снизу вверх. Вначале были эксперименты со стеком, т.е. с примитивным калькулятором. Естественно, параллельно был написан лексер. Затем было п��инято решение о выходной структуре синтаксического анализатора. Дела пошли, проектная папка lib стала заполняться файлами модулей, началась помодульная отладка.
Тут начались мучения по поводу архитектуры приложения. Чтобы было понятнее сошлюсь на частное честное мнение Д.Томаса [4]:
«Впервые начав использовать Elixir, я долго мучился над тем, как организовать свои приложения. Когда следует использовать серверы? Какова роль супервизоров? Даже такие базовые вопросы, как «Сколько приложений мне нужно написать?», вызывали у меня нервозность.
Честно говоря, я все еще размышляю над этими вопросами, даже спустя три года...»
Далее у Д.Томаса идут советы, какие задавать себе вопросы при разработке архитектуры. Честно говоря, я не воспользовался этими вопросами, т.к. я понял одну важную вещь, что в приложении присутствуют два независимых бесконечных цикла со своими точками входа:
1. модуль REPL ручного взаимодействия с интерпретатором,
2. модуль GenServer-а OTP для межпроцессного взаимодействия с интерпретатором.
После этого модули размежевались сами собой.
На конечной фазе разработки необходимо было решить проблему обеспечения отказоустойчивости интерпретатора. На это ушли последние 3 недели разработки. Я понимал, что это стенка на финишной прямой, которую надо было если не преодолеть, то обязательно прогрызть.
Неудобно признаться, но я был по гипнозом традиционного способы решения этой задачи в Elixir при помощи надзора за процессами супервизорами в рамках стратегии "Let it crash". С привычным надзором за GenServer-ами проблем не было, а вот о надзоре за одиночны�� процессом Task – молчок!
Я перерыл кучу статей, перечитал учебники, но ответа не находил. И тут одна случайная статья подтолкнула меня к спасительной мысли: "А что, если отказаться от новомодного надзора множества процессов посредством супервизоров и вернуться к старому проверенному защитному программированию в пределах одного процесса."
Быстро смастерил бесконечную зацикленную программу с рекурсивным вызовом в хвосте, имитирующую арифметический калькулятор деления. Деление на 0 должно было вызывать сбой. Затем вложил простенький алгоритм в оператор перехвата ошибок try do ... catch ... end и ... результат меня полностью удовлетворил.
И последний штрих к разработке Forth-ibE. В блоке операторов внутри try do ... catch ... end надо было поставить функцию выхода из бесконечного цикла и вообще из приложения при получении слова bye. Начал искать такую функцию. Я спешил, ведь финишная ленточка маячила перед моим носом.
Таких функций оказалось несколько. Честно говоря, я её угадал методом перебора, а потом нашёл соответствующее указание самого Хосе Валима:
«это (выбор) зависит от того, какое приложение вы запускаете. Если вы создаёте скрипт, вы можете вызвать метод System.halt(0). Если у вас приложение, не вызывайте метод System.halt(0), так как это приведёт к завершению работы всей системы без учёта всех остальных приложений. Вместо этого используйте метод System.stop(0).
В качестве альтернативы вы можете вызвать функцию exit(:shutdown) для завершения текущего процесса. :shutdown -это распространенная причина завершения работы в OTP, и если вы находитесь внутри .exs файлов, это тоже будет работать нормально.»
Вот моё прочтение приведенной выше цитаты: программирование становится все более похожим на заклинания шаманов с бубном вокруг котла с зельем. А глубинный истинный смысл слов заклинания изначально знает только несколько человек из команды богов, сотворивших планету с названием Elixir или Java, или JavaScript, или Python, или С++, или C#. В "солнечной" системе планет много. Поймите меня правильно, на самом деле я очень хорошо отношусь к Х.Валиму и другим разработчикам.
Но мне всё еще продолжает нравиться своей подкупающей брутальной простотой Erlang. А ещё я влюбился в Forth.
4. Тестирование и отладка
Тестирование / отладка интерпретатора Forth-ibE проводились на примерах учебника [1] до темы массивов. Ответы перепроверялись в интерпретаторе gforth [5]. Результаты тестирования / отладки были скомпилированы и оформлены в техническое условие (ТУ) на интерпретатор.
ТУ в моём понимании — это нормативный документ, который устанавливает требования к продукции, её производству, контролю, действует при отсутствии или в дополнение к обязательным стандартам.
5. Следующий этап
Для продолжения разработки планируется выполнить следующие манипуляции:
· обернуть интерпретатор в оболочку GenServer и добавить API доступа к интерпретатору через сообщения;
· создать рабочий релиз Forth-ibE.
Этого будет достаточно для опробования числовых движков Forth в среде связанных процессов GenServer.
6. Благодарность
Хочу высказать глубокое чувство благодарности R. Nystrom, автору честной книги «Crafting Interpreters» [7 ]за его непредвзятой и смелое отношение к сложной теме построения интерпретаторов.
Литература
1. Л.Броуди, Начальный курс программирования на языке Форт: Пер. с англ.; – М.: Финансы и статистика, 1990.
2. https://github.com/alexiob/forthvm
3. https://github.com/fabrik42/writing_an_interpreter_in_elixir
4. D. Thomas, Proramming Elixir > 1.6, The Pragmatic Bookshelf, 2018
6. Forth, Американский Национальный Стандарт, 1994.
7. R. Nystrom, «Crafting Interpreters», https://craftinginterpreters.com/.
ТУ на интерпретатор Forth-ibE.
1. В цикле REPL используется драйвер клавиатуры, построенный на стандартных средствах ввода/вывода языка Elixir, а не на драйвере клавиатуры как у оболочки команд ОС. Поэтому есть два отличия от gforth при вводе команд в режиме клавиатуры:
1) Окончание цепочки командных слов клавишей Enter реально переводит вывод на терминал на другую строку.
Например в Forth-ibE:
Words: > 2 2
ok
Words: > * .
4 ok
В gforth:
2 2 ok
* . 4 ok
В gforth получается компактнее.
2) Нельзя перемещаться по набранной строке командных слов при помощи клавиш < и > для коррекции текста. Нельзя использовать клавишу ^ для повторного использования команды.
3. В gforth можно делить длинное определение на нескольких строках терминала, что составляет большое удобство при наборе большого определения.
В Forth-ibE это не реализовано по указанной выше причине. С другой стороны акцент работы в Forth-ibE делается не на терминал, а через API посылки сообщения.
4. Ввод слова с терминала в транслятор безразличен к регистру.
Можно ввести слово EMIT или emit, результат будет одинаков, т.к. в лексере текстовые токены приводятся к нижнему регистру.
По этой же причине имена переменных сохраняются в словаре строчными буквами.
5. Реализованы пакеты встроенных функций выполнения слов:
io_words - слова ввода/вывода,
math_words - слова математических действий,
logic_words - слова логических операций,
flow_words - слова управления ветвлением программы
stack_words - слова действий со стеками,
interpret_words - слова действий в интерпретаторе.
Массивы не реализованы.
Описания пакетов кодируются во вспомогательных доступных файлах в формате Json.
6. Реализация ввода/вывода и обработки лексических конструкций выполнена в минимальном объеме учебника Броуди, т.к. интерпретатор планируется использовать в режиме обработки математических вычисления в рамках узлов связанных процессов. В режиме калькулятора имеющихся средств ввода/вывода достаточно для отладки кода.
7. В стандарте ANSI 94 отсутствует представление об унарном плюсе, поэтому в синтаксическом анализаторе интерпретатора Forth-ibE допускается только у��арный минус, как и в интерпретаторе gforth.
Математические операции на стеке выполняются с числами, в том числе с плавающей точкой, поддерживаемыми компилятором Elixir. Целочисленные арифметические операции масштабирования forth над числами с плавающей точкой "заменены" арифметическими операциями с плавающей точкой Elixir.
8. По стандарту ANSI 94 реализованы логические слова поразрядных операций and, or, xor и not .
Добавлены функции более высокого уровня &and, &or и ¬, которые являются кальками логических функций and, or и not над атомами true и false Elixir . Непротиворечива нотация &and, &or и ¬ взята из HTML.
Логические константы true и false во внутреннем представлении Forth-ibE переводятся во флаги Forth 0 и -1. Любое число, отличное от 0, также трактуется как true.
9. В книге Броуди сказано, что "оператор IF ... THEN должен содержаться только внутри определения (через двоеточие), так что вы не можете использовать его в режиме калькулятора."
В Forth-ibE в режиме калькулятора можно выполнять оператор IF ... THEN одного уровня. Для работы со сложными конструкциями IF ... THEN предлагается разбивать его определение на подопределения вложенных конструкций слов ветвления.
Например в gforth можно записать длинное определение так:
( вложенные конструкции IF ...THEN )
: КУПЮРЫ DUP 10 < IF ." Это уже долги " ELSE
DUP 200 <= IF ." МЕЛКИЕ " ELSE
DUP 1000 <= IF ." СРЕДНИЕ " ELSE
DUP 5000 <= IF ." Крупные " ELSE
." мы таких не видели "
THEN THEN THEN THEN DROP ;
В Forth-ibE этот же результат достигается следующим образом:
( разложение конструкции вложенных IF ...THEN на определения )
: КРУПНЫЕ DUP 5000 <= IF ." Крупные " ELSE ." мы таких не видели " THEN ;
: СРЕДНИЕ DUP 1000 <= IF ." СРЕДНИЕ " ELSE КРУПНЫЕ THEN ;
: МЕЛКИЕ DUP 200 <= IF ." МЕЛКИЕ " ELSE СРЕДНИЕ THEN ;
: КУПЮРЫ DUP 10 < IF ." Это уже долги " ELSE МЕЛКИЕ THEN DROP ;
10. Реализации слова ?DO...LOOP цикла с начальной проверкой совпадения границы и индекса не потребовалось: работает простой цикл DO...LOOP.
Цикл BEGIN...WHILE...REPEAT и выход из цикла LEAVE в настоящей версии ib-Forth не реализованы. Готов цикл с условием BEGIN...UNTIL.
11. Есть два сходных слова. Слово QUIT вызывает прекращение работы программы, но не очищает стек. Слово ABORT выполняет те же действия, что и QUIT, но очищает стек.
12. Характеристика возможных программирования ошибок в ib-Forth, их выявление и диагностика.
Ошибки синтаксиса.
Ошибки лексического анализа кода forth возможны, т.к. базовые слова, имхо, сочинялись без какой-либо систематизации и правил. Единственное правило - это разделение слов пробельными символами. Поэтому теоретически трудно описать конечный автомат разбора синтаксиса, учитывающего множество вариантов комбинаций символов.
Примеры неоднозначности трактования символов лексером:
ABORT" означает слово, которое по определению выполняет ABORT и вывод заданного за ним текста, т.е. " можно считать открывающей кавычкой.
STAR" может быть последним словом, например, во фрагменте
." Follow your STAR"
В этом случае " считается закрывающей кавычкой, ограничивающей текст.
Чтобы избежать такой неоднозначности и не усложнять синтаксический анализатор в ib-Forth следует строго придерживаться правила разделения слов пробельными символами, т.е. рассмотренную команду следует записать так:
." Follow your star "
Согласно духа учебника Броуди закрывающая кавычка не является словом, так же как закрывающая скобка ) комментария. Мы же предлагаем для однообразия считать их словами, не нарушая семантики языка.
Ошибки преобразования токенов в код.
При синтаксическом анализе в интерпретаторе токены получают семантику. Оценивать правильность принятых семантических решений будет уже движок.
Ошибки времени выполнения движка.
Лексические и синтаксические ошибки сказываются на последнем этапе выполнения virt-coda.
(Примечание. virt-code отличается от byte-code, т.к. построен на списке, содержащего более сложные конструкции, чем простой байт. Приставка virt можно понимать как сокращение слово virtual, а можно считать знаком уважения к Никлаусу Вирту.)
В движке Forth-ibE встроены очевидные блокировки выполнения недопустимых арифметических операций: деление на нуль, извлечение квадратного корня из отрицательного числа и ещё обращение к пустому стеку данных.
После вывода диагностики REPL возвращается к приёму слов.
13. В режиме интерпретатора ib-forth считывает во время сеанса ввод с клавиатуры в реальном времени и в цикле REPL обрабатывает введенные слова. Этот режим идеально подходит для отладки данных или команд. Режим REPL снисходителен к ошибкам, позволяя восстанавливаться интерпретатор и предоставляя информацию о состоянии стека программы в случае ошибки.
Написание кода на Forth чрезвычайно сопряжено с возможностью совершения ошибок. Главная точка в интерпретаторе проявления ошибки располагается в стеке. Например, по невнимательности можно подать в стек неполное количество данных. Приведем элементарный пример:
2 * .
Для защиты от грубых ошибок в приложении ib-Forth применяется приём защитного программирования на базе оператора Elixir
try do ... catch ... end
Этого оказалось достаточно.
Предупреждение об ошибке выводится в следующем виде:
Words $ 2 * .
Ошибка:
Код: [2, :mult, :dot]
Стек: [ ]
Стек возврата: [ ]
Words $
После вывода предупреждения интерпретатор снова переходит к приёму слов.
В дальнейшем в API ib-forth защита от грубых ошибок будет построена на основе супервизора Elixir, реализующего стандартную стратегии OPT "Let it crash!".
14. Исходный код интерпретатора ib-Forth является открытым и будет выложен на GitHub. Промышленный релиз пока не был подготовлен по причине продолжения разработки.
Интерпретатор ib-Forth запускается в режиме разработчика командой:
mix run —no-halt
А завершение работы интерпретатора производится стандартным словом:
bye
15. Чтобы завершить рассмотрение ТУ разберем важную тему переменных и констант ib-forth.
Cвойства переменных и констант соответствуют стандартным, но их таблица реализована на базе словаря Map в Elixir. Это накладывает определенные ограничения на реализацию, например, невозможно в ячейке словаря сохранить переменную, константу или слово под одним именем.
Поведение константы и переменной отличаются друг от друга: переменная по имени в стеке "вытаскивается" из памяти словом @, а имя константы всегда в стеке подменяется интерпретатором её значением.
Допустим, переменная СЧЁТЧИК и константа ПРЕДЕЛ имеют значение 220. Тогда
СЧЁТЧИК @ .
220 ok
ПРЕДЕЛ .
220 ok
16. Дополнение К ТУ.
В ib-forth не предусмотрена смена основания системы счисления и постоянно равно 10.
Еще не реализованы массивы переменных по причине сложности осуществления векторизации ячеек словаря Map Elixir.
Слово RECURSE, которое осуществляет компиляцию адреса текущего определяемого слова, не реализовано по причине отсутствия указателей в языке Elixir. Но рекурсия работает!
В учебнике Броуди есть следующий пример на рекурсию
VARIABLE СЧЕТЧИК
: ПРЕДЛОЖЕНИЕ CR ." Спрашивайте, пожалуйста! " -1 СЧЕТЧИК +! СЧЕТЧИК @ IF RECURSE THEN ;
3 СЧЕТЧИК !
Заменяем вторую фразу без лишних ухищрений на
: ПРЕДЛОЖЕНИЕ CR ." Спрашивайте, пожалуйста! " -1 СЧЕТЧИК +! СЧЕТЧИК @ IF ПОЧЕМУ THEN ;
и вуаля:
Words $ ПРЕДЛОЖЕНИЕ
Спрашивайте, пожалуйста!
Спрашивайте, пожалуйста!
Спрашивайте, пожалуйста! ok