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

Эта статья — окончание цикла статей про 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; поле параметров

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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