EFORTH для МК-161: Структуры данных

Эта статья — окончание цикла статей про eForth на программируемом калькуляторе. Начало здесь:habr.com/ru/post/452398

Вторую половину занимают таблицы, разработать которые был не меньший труд, чем написать алгоритмическую часть транслятора. Команды входного языка «Электроники МК-161» занимают только половину файла eForth0.mkl. Попробуем разобраться, как эти таблицы используются.
Профессор Вирт учит, что «программирование в малом» состоит из разработки двух одинаково важных составляющих — алгоритмов и структур данных.

Это тело СВУ (слов высокого уровня), расположенное в байтовой памяти. С одной структурой данных eForth мы уже сталкивались. Четыре обработчика по разному интерпретируют поля параметров «своих» СВУ:

DB DOVAR ; поле кода переменной и массива
. . DB … ; поле параметров в свободной форме

DB DOCON ; поле кода константы
. . DW значение_константы ; поле параметров

DB DOCONM ; поле кода отрицательной константы
. . DW значение_константы ; поле параметров

DB DOLST ; поле кода слов двоеточия
. . DW токен1, токен2,… EXITT ; поле параметров

Все сообщения eForth пронумерованы и перенесены в дешёвую память программ. Если слово TYPE выводит единственную литеру, её код может быть номером такого сообщения, от 0 до 7. Следующая относительно простая структура данных связана со «стандартными сообщениями» TYPE.

BASE
tblTYPE: . ; Стандартные сообщения TYPE
. DBB str7,str6, str5, str4, str3, str2, str1, str0

BASE задаёт «базу» для команды . На расширенном языке МК псевдокоманда . относительно метки базы tblTYPE. DBB, которая последовательно размещает в байтах смещения строк str7, str6 и т.д. Прибавив найденное смещение к tblTYPE, получим адрес нужной строки. Прибавляя к адресу таблицы числа от 0 до 7, можно считать из неё это смещение.

eForth широко использует такие «счётные строки». Первый байт строки содержит её длину.

Если слово не примитив, таблица содержит 0. Также мы сталкивались с таблицей tblTokens, в которой перечислены адреса кода всех 208 встроенных слов. Переход по адресу 0 вызовет перезагрузку eForth, причём с писком.

Имена всех 208 слов хранятся в той же «резиновой» памяти программ, как счётные строки. Была упомянута и таблица tblNames, ссылающаяся на имена тех же 208 строк. Во время компиляции eForth.f перенесёт адреса имён в более полезную структуру данных, хранящуюся в десятичной памяти (см. Сама таблица tblNames будет недоступна во время работы eForth, но содержащаяся в ней информация не пропадёт. 2).

Ещё семь таблиц, от tblKeyNum до tblKeyRusF, переводят код кнопки, нажатой в разных режимах клавиатуры, в 8-битный код литеры. Рассказывал я и про tblCHPUT, ассоциативную таблицу управляющих кодов при выводе символа. Адрес подпрограммы, отвечающей за активный режим клавиатуры, содержится в десятичном регистре ptrKbdInt.

Оставим их на десерт (см. Итого в файле eForth0.mkl осталась неразобранной лишь одна структура данных, это таблицы распознавания имени. Сперва вооружимся инструментами для «фаршировки» эти заголовков. 5) после основного блюда — двух таблиц заголовков, хранящихся в десятичной памяти.

1. Работа с заголовками: HEAD! и HEAD@

HEAD! ( xt nfa r -- ) Записать заголовок в регистр r, взяв xt и nfa.
HEAD@ ( r -- xt nfa lex ) Считать заголовок из регистра r, дав xt, nfa и лексикон.


eForth использует такой регистр для хранения трёх небольших чисел, каждое от 0 до 9999. Один десятичный регистр МК-161 может запомнить 12 десятичных знаков. Три «поля» для хранения этих чисел я назвал A, B и C: AAAABBBBCCCC. Знак десятичного числа относится только к полю A.

собирает поля в длинное число и записывает получившегося «монстра» в указанный регистр. Примитив HEAD@ получает номер регистра и разбивает число оттуда на поля, а HEAD! Но есть нюансы.

Если этот адрес отрицательный, имя хранится в памяти программ. «Десятичный заголовок» слова содержит в поле A адрес его имени (nfa). Поле C называется «лексиконом». Поле B содержит токен слова (xt). В нём хранится бит IMMEDIATE и признак, что слово предназначено только для компиляции.

На вершину стека кладётся поле лексикона C, под ним поле имени A. HEAD@ разбивает заголовок на части. Поле B, в котором обычно хранится токен — в самом низу.

обнуляет поле C. HEAD!

2. Заголовки встроенных слов

Заголовки каждого из 208 встроенных слов (от 0 до 207) идут по порядку, начиная с R44. Поле A всегда содержит отрицательное число, так как имена этих слов жёстко прописаны в памяти программ.

Поэтому пользователь может переопределять встроенные слова и делать нужные из них IMMEDIATE (см. Поля B и C доступны для редактирования. 4).

3. Заголовки слов пользователя

Работа только с 208 заранее заданными именами экономит байтовую память, но необычайно скучна. Поэтому я разработал ещё одну структуру данных, где фантазия в выборе имени ограничена только 32 литерами. Эта структура состоит из 32 списков, каждый из которых отвечает за пользовательские слова определённой длины. Каждый из этих 32 списков снабжён личным заголовком. Сами списки «прыгают» по десятичной памяти, но их заголовки всегда хранятся в R301…R332.

Кому нужны хэш-функции, если у каждого имени есть известная длина? Сортировка слов по длине имени — важная «изюминка» 161eForth. Сортировка сильно уменьшает число сравнений, когда ищешь слово по его имени, ускоряя компиляцию.

Назначения этих полей отличаются. Для простоты заголовок списка имеет такую же структуру с полями A, B и C, как заголовок слова. Поле B содержит количество регистров, предоставленных списку. Поле A содержит номер первого регистра списка. Поле C хранит число слов, чьи заголовки уже включены в список.

Поля B равны 2, каждому списку для начала отдано по паре регистров. В начале работы поля C равны нулю, слова во всех списках отсутствуют. Поля A указывают на блоки по 2 регистра, начиная с R333.

Мы уже их разобрали (см. Каждый список содержит заголовки слов. Здесь, разве что, адрес имени (nfa) будет положительным и указывать на счётную строку, традиционно хранящуюся перед телом СВУ. 1). Исключение одно — если слово уже определялось, поле A будет указывать на старое имя. Зачем хранить строку повторно? Также и токен в поле B представляет из себя адрес поля кода (cfa), идущего в двоичной памяти сразу после этого имени. Двоичная память дорога.

Когда все регистры списка заполнятся (B=C), слово PUBLISH предоставляет ещё 5 свободных мест, раздвигая эту структуру данных в нужном месте и корректируя ссылки (A) в заголовках списков.

4. Публикация нового слова: WORK и PUBLISH

LAST ( -- a ) Указатель на последнее имя в словаре.
WORK ( -- a ) Номер регистра заголовка строящегося слова.
PUBLISH ( -- ) Включить в словарь новое слово.
$,n ( nfa -- ) Построить новый заголовок для словаря, используя строку в nfa.
?UNIQUE ( a -- a ) Отобразить предупреждение, если слово уже существует.


Когда CREATE, CONSTANT или : создают новое слово, они обращаются к системному слову $,n для создания заголовка слова с данным именем. Разработанная для МК-161 структура данных для хранения заголовков слов оказалась практичной и лёгкой в использовании. UNIQUE ради проверки — мы создаём новое слово или переопределяем старое? $,n обращается к ?

UNIQUE предупреждает об этом пользователя. Если слово с таким именем уже существует, ? Для нового слова LAST обнуляется. Одновременно адрес переопределяемого заголовка заносится в системную переменную LAST.

Если имя не было найдено, оно включается в словарь перед полем кода, как это происходит в 86eForth и многих других Фортах. В любом случае $,n строит новый заголовок в переменной WORK — это десятичный регистр, способный хранить 12 разрядов заголовка. На МК-161 удалось обойтись без «поля связи», это тоже экономит двоичную память.

Для слов двоеточия PUBLISH вызывается из ;. Примитив PUBLISH завершает определение слова. Если в LAST ноль, новый заголовок создаётся в соответствующем списке (см. Место, куда копируется заголовок из WORK, определяется словом LAST. Нужный список заполнен? 3). Тогда PUBLISH добавит ему ещё 5 регистров, четыре из них на будущее.

Это помогает IMMEDIATE сделать своё дело, изменив поле лексикона. После работы PUBLISH переменная LAST всегда указывает на заголовок слова, определённого последним.

5. (FIND) и таблицы распознавания имени

(FIND) ( a -- r T | a F ) Дать номер регистра r, в котором находится заголовок слова с именем a.
FIND ( a -- a F | xt 1 | xt -1) Поиск строки в словаре. Вернуть 1, если IMMEDIATE.

Поиском слова по его имени заведует примитив (FIND). Сперва он ищет имя среди встроенных слов с заранее известными именами, потом проверяет список слов пользователя с нужной длиной имени (см. 3). Таблицы распознавания имени серьёзно ускоряют это «сперва». Вот, как они устроены.

В этой таблице (FIND) ищет первую литеру имени. В начале (FIND) находит в массиве tblLen адрес главной ассоциативной таблицы, в которой «препарированы» известные имена нужной длины. В большинстве случаях это сразу позволяет узнать номер регистра заголовка искомого слова.

Тогда вместо номера регистра (FIND) натыкается на адрес следующей ассоциативной таблицы (считанное число равно 300 или больше) и поиск продолжается по второй литере. Бывает, что несколько слов имеют одинаковые первые литеры. И так далее, пока слово не будет найдено или установлено, что такого слова нет.

Но таблицы распознавания сделали eForth быстрым. Конечно, после совпадения по первым литерам (FIND) сверяет всё имя целиком. «Ключи» в них даже отсортированы по алфавиту. Этой весной я вложил в них много своего времени, и теперь они экономят время поиска. Жаль, прошивке МК-161 на это начхать.

Уже рассмотренное слово ? Ради совместимости я реализовал слово FIND из Форта ANS [4], которое доверяет «чёрную работу» примитиву (FIND). UNIQUE также ищет свой аргумент через (FIND).

6. Внешний интерпретатор

Книга [1] содержит исчерпывающее описание eForth, в том числе рассказывает про внешний «текстовый» интерпретатор. Отличия от текстовых интерпретаторов других диалектов Форта ([2], [3]) за прошедшие десятилетия появились, но их немного.

Будьте внимательны — у этого «интерпретатора» есть режим компиляции! Ниже я привожу блок-схему текстового интерпретатора, взятую из [1].

Вот её перевод. После блок-схемы автор приводит расшифровку, что какой из блоков делает. Имена блоков обычно соответствуют именам слов eForth.

Обработчик ошибок
QUIT Сбросить стек возвратов и войти в цикл интерпретатора
QUERY Принять ввод текста с терминала
EVAL Вычислить или интерпретировать строку текста
PARSE Выделить слово из введённого текста
$INTERPRET Интерпретировать слово
$COMPILE Скомпилировать слово
NAME? MAIN Настроить виртуальный «движок» Форта
COLD Инициализировать системные переменные
ABORT Сбросить стек данных. Перевести строку текста в целое
EXECUTE Исполнить слово
IMMED? Поискать слово в словаре
NUMBER? Это слово — немедленная команда?
LITERAL Скомпилировать целый литерал
COMPILE Скомпилировать токен

В чём версия для МК-161 отличается, я вам уже рассказал. Также в книге приводится исходный текст каждого слова eForth в варианте для Windows, с краткими пояснениями. 5b.zip Исходный текст моей реализации есть в архиве: the-hacker.ru/2019/161eforth0.

Отладка заняла неделю, зато повысила скорость компиляции в два раза. Напоследок упомяну реализацию слова (PARSE) на языке МК-161. Слово (PARSE) делает всю «чёрную работу» для PARSE по вычленению отдельных слов из входного потока текста.

Слово FILE переводит ввод-вывод на консоль, но считывает строки для интерпретации из порта RS-232. Мои добавления к внешнему интерпретатору это два слова, помимо обычного цикла QUIT: уже упоминавшийся TLOAD и взятый из старых версий FILE. Загружаемый с компьютера файл должен заканчиваться словом QUIT. После успешной обработки каждой строки в порт выводится литера с кодом 11.

Если оно кому-либо нужно, поделитесь впечатлениями. Слово FILE я пока не отлаживал.

Даже когда вы во всём досконально разобрались, кто-нибудь где-нибудь на планете придумает очередной фокус, способный вас удивить. Обзор трудных мест 161eForth закончен, но Форт — невероятно гибкий инструмент, который каждый владелец подстраивает под себя.

Приведу завершающие слова автора eForth из [1]:

В каждом пере-писывании я старался сделать его проще и яснее. За 26 лет я переписывал eForth много, много раз. 2, думаю, я достиг правильности, и поэтому очень счастлив. Теперь в 86eForth v5.

Как сказал Эйнштейн:
Всё должно быть сделано так просто, как возможно, но не проще.

2 ещё проще, возможно, поломает его или не полезно, как инструмент программирования.
Сделать 86eForth v5.

Литература

1. Dr. Chen-Hanson Ting. eForth and Zen — 3rd Edition, 2017. Есть на Amazon Kindle.
2. Баранов С.Н., Ноздрунов Н.Р. Язык Форт и его реализации. — Л.: Машиностроение. Ленингр. отд-ние, 1988.
3. Семёнов Ю.А. Программирование на языке ФОРТ. — М.: Радио и связь, 1991.
4. Стандарт ANS Forth. X3.215-1994. Перевод: oco.org.ua/download/forth/dpans94_ru.html