Приведенная ниже статья является одной из первых работ автора в
области динамически структурируемых кодов.
В ней описывается следующий прием:
в ситуации, когда необходимую
для порождения кода информацию трудно извлечь во время компиляции,
но легко получить во время исполнения, заключительная фаза
порождения кода откладывается до момента первого исполнения кода.
Данная статья была опубликована на английском языке в трудах конференции euroFORTH'93. Сейчас, в 2000 году, эта статья публикуется в Интернете как пример (1) применения динамических кодов и (2) разбиения процесса на две фазы.
[Gas93] Gassanenko, M.L. Multi-CFA DOES> : Implementation via Self-Modifying Code. Proc. of the euroFORTH'93 conference, 15-18 October 1993, Marianske Lazne (Marienbad), Czech Republic, 9 p.
РЕАЛИЗАЦИЯ ПОРОЖДАЮЩИХ СЛОВ ДЛЯ ФУНКЦИЙ С НЕСКОЛЬКИМИ ПОЛЯМИ КОДА
В ЯЗЫКЕ ФОРТ: ИСПОЛЬЗОВАНИЕ САМОМОДИФИЦИРУЮЩЕГОСЯ КОДА
Гасаненко М.Л.
Описывается синтаксис для слов, порождающих слова с
несколькими полями кода, реализуемый как на односегментных, так и
на многосегментных Форт-системах. В реализации используется
техника самомодифицирующегося кода: порождение кода определяющего
слова завершается при первом его вызове. Это позволило
значительно упростить реализацию, т.к. в противном случае
пришлось бы или использовать неоправданно громоздкий синтаксис,
или применять чересчур сложный анализ шитого кода.
1. Введение
Содержимое поля кода процедуры (фортовского слова)
определяет, какое действие будет выполнено при вызове этой
процедуры. (Обычно в поле кода хранится или адрес подпрограммы,
или команда перехода или вызова ее.) Для константы это действие -
положить число из поля параметра на стек, для двоеточечного
определения - вызов фрагмента шитого кода, который (или указатель
на который) находится в поле параметра, и т.д. Конструкция DOES> ,
используемая в определяющем слове, позволяет задавать это
действие для определяемого слова. Когда определяемое слово будет
вызвано, на стек будет положен адрес поля параметра (parameter
field, этот термин следовало перевести скорее как поле-параметр),
и управление будет передано на код за DOES> . Естественно,
что от слов с несколькими полями кода можно ожидать выполнения
нескольких различных действий со своим полем-параметром.
По умолчанию использование имени процедуры означает обращение
к первому из её полей кода; для обращения к остальным
используются специальные префиксы [7,1]. Напомним также, что
шитый код, используемый в Форте - это исполнимый код, почти
все элементы которого обозначают вызовы процедур (некоторые
процедуры предполагают, что вслед за ними в шитом коде находятся
данные). При компиляции фортовские определения преобразуются
в шитый код за один проход, анализ текста со стороны системы
минимален и сводится в основном к поиску слов в словаре. Следует
заметить, что благодаря предельной простоте кодогенерации
возможно вмешательство программиста в этот процесс, что является
одной из сильнейших сторон Форта.
При реализации определяющих слов для слов с несколькими
полями кода возникает несколько проблем. Первая из них в том, что,
т.к. слово DOES> вызывает выход из фрагмента шитого кода, в
котором используется, заполнить несколько полей кода, разместив
несколько частей DOES> в одном определении, не удаётся. В
различных реализациях эта проблема решается по-разному: возможно
использование вспомогательных меток и порождение полей кода
"вручную", в [1] для заполнения полей кода используются
вспомогательные слова и довольно сложные манипуляции на стеке с
записываемыми в поля кода значениями, а в [8] для создания
слова, определяющего слова с N полями кода, сначала строится N
элементов словаря без заголовков, задающих действия,
соответствующие полям кода; их адреса через стек передаются в
определение порождающего слова, где строится образец совокупности
полей кода.
Следует отметить, что на практике часто отказываются
от создания специального механизма, а поля кода строят "вручную",
смирившись с системной зависимостью.
В [2] описана конструкция "рекурсивный блок". Слова
START и EMERGE обозначают границы блока, DIVE осуществляет его
рекурсивный вызов. Использование этой конструкции в виде
START ... EMERGE (без DIVE ) эквивалентно использованию
вспомогательной процедуры: слово немедленного исполнения EMERGE
компилирует EXIT, внутри блока на стеке возвратов будет лежать
адрес шитого кода, скомпилированного за EMERGE . Используя эту
конструкцию, можно поместить несколько частей DOES> в одно слово.
Вторая проблема - зависимость от системы. В различных
реализaциях Форт-систем возможны следующие варианты размещения
нескольких полей кода и поля параметра:
1) Поля кода и параметра находятся в одном и том же сегменте.
Поля кода располагаются одно за другим; поле параметра
располагается за последним полем кода. ("Классическая",
несегментированная модель.)
2) Поля кода и поле параметра находятся в разных сегментах.
За каждым из полей кода помещен указатель на поле
параметра.
3) Поля кода и поле параметра находятся в разных сегментах.
Указатель на поле параметра помещен за последним из полей
кода.
Целью данной работы является синтаксис, позволяющий
порождать определяющие слова для слов с несколькими полями кода и
пригодный для всех трех моделей.
Для того, чтобы породить код, вычисляющий адрес поля
параметра, в первой и третьей моделях необходимо знать (во время
компиляции) номер поля кода и общее число полей кода в слове.
Явная передача числа полей кода и номера поля кода компилятору
через стек (например, [ 5 ] #DOES> ) вряд ли оправдана: это
приводит к громоздкому коду и совершенно не нужно для второй
модели. Вторая модель выдвигает самые слабые требования: она
требует только, чтобы число и номера полей кода были известны во
время исполнения определяющего слова.
2. Методика реализации
Предлагаемое в этой статье решение довольно просто - в
случае первой и третьей моделей завершение порождения кода
определяющего слова откладывается до момента, когда оно уже
вызвано и все необходимые данные уже известны. Разумеется,
приходится смириться с тем, что один и тот же фрагмент кода с
конструкцией DOES> сможет работать для единственного значения
смещения от адреса поля кода до (указателя) поля параметра. В
принципе, приемлемым было бы даже более строгое ограничение:
использование одного и того же оператора DOES> допускается только
для единственной комбинации числа полей кода и номера поля кода.
В односегментной модели код, компилируемый словом DOES> ,
выглядит следующим образом:
(#DOES>) маш.команда <шитый код, исполняемый порождаемым словом>
|________| |___________|
"Маш.команда" - это команда перехода на подпрограмму DOES,
обеспечивающую наличие на стеке адреса поля кода и вызов шитого
кода, расположенного вслед за "маш.командой". Более подробно
реализация слов CREATE и DOES> описана в [1].
Для реализации слов с несколькими полями кода можно
использовать ту же самую подпрограмму DOES, но тогда необходимо
скорректировать адрес, который кладётся на стек: для всех полей
кода, кроме последнего, это будет адрес следующего поля кода. В
случае односегментной модели это можно сделать двумя способами:
а) включить это действие в начало шитого кода, исполняемого
порождаемым словом;
б) до обращения к подпрограмме DOES прибавить к адресу поля кода
необходимое смещение и получить адрес последнего поля кода
(т.е. вставить машинную команду ADD <регистр>, <смещение> )
В случае третьей модели будет работать только последний вариант.
Ниже описывается реализация варианта а) для первой
(несегментированной) модели. Реализация варианта б) принципиально
ничем не отличается.
Итак, для односегментной модели код, соответствующий слову
#DOES> , должен в итоге выглядеть следующим образом:
(#DOES>) маш.команда LIT+ смещение
|________| |___________| |________| |________|
Слово #DOES> порождает следующий код:
(#DOES?) маш.команда LIT+ 0
|________| |___________| |________| |________|
При порождении первого слова и число полей кода, и номер поля
кода уже известны - число полей кода хранится в переменной #CFAS,
номер поля кода находится на стеке данных.
Слово (#DOES?) ( n -> n ; передача управления) вычисляет
значение смещения от n-ого поля кода до поля параметра и заносит
его в шитый код после LIT+ ; затем оно меняет в шитом коде ссылку
на себя на ссылку на (#DOES>) , после чего передает на неё
управление ( сдвигая указатель возврата на позицию назад). Теперь
с того адреса, где было скомпилировано слово (#DOES?), начинается
фрагмент шитого кода, модифицирующий поле кода последнего
определенного слова должным образом; он и будет теперь выполнен.
Слово (#DOES>) ( n -> ; выход ) заполняет n-oe поле кода
определяемого слова и проверяет, что в шитом коде находится
правильное значение смещения, в противном случае выдается
сообщение об ошибке.
Итак, порождение кода определяющего слова завершается при
первом его вызове, одновременно с построением первого
определяемого слова. Поскольку слово (#DOES?) не влияет на
определяемое слово, все определяемые слова порождаются с
использованием одного и того же фрагмента кода, и мы можем быть
уверены, что первое порожденное слово будет вести себя так же,
как и остальные.
Ниже приводится исходный текст для "классической"
односегментной модели.
-- системно-зависимые определения:
-- ITC означает, что данный фрагмент кода предназначен
-- для систем с косвенным шитым кодом
-- SPEC - это проходит на Форт-системе автора
-- T=C - ссылка на процедуру занимает 1 ячейку (token=cell)
-- NST - используются нестандартные слова
: CFLS CELLS ; -- ITC ( Code Field LengtheS )
: CF! ! ; -- ITC ( Code Field store )
: TOKEN! ! ; -- T=C
: TOKEN+ CELL+ ; -- ITC
: TOKEN- CELL- ; -- ITC
: LIT+ R> DUP CELL+ >R @ + ;
: CMDL+ CELL+ ; -- SPEC -- увеличить число на
-- длину команды перехода
: COMPILE-INSTR DOES-CMD @ , ; -- SPEC -- компиляция машинной
-- команды, используемой в DOES>
: IT ( -> cfa ) LATEST NAME> ; -- NST -- адрес поля кода последнего
-- созданного слова
QUAN #CFAS -- QUAN уже есть в системе
: CFAS DUP 1- CFLS ALLOT TO #CFAS ;
: (#DOES>) ( n -> ; выход)
#CFAS OVER - CFLS R@ >CMDL+ TOKEN+ @
XOR ABORT" НЕДОПУСТИМЫЙ НОМЕР ПОЛЯ КОДА"
1- CFLS IT + R> SWAP CF! ;
: (#DOES?) ( n -> n ; переход )
#CFAS OVER - CFLS R@ CMDL+ TOKEN+ !
R> TOKEN- >R
['] (#DOES>) R@ TOKEN! ;
: #DOES> COMPILE (#DOES?) COMPILE-INSTR COMPILE LIT+ 0 , ; IMMEDIATE
: CFA ?EXEC CREATE IMMEDIATE 3 CFAS ,
START 1 #DOES> @ 1- CFLS ' +
STATE @ IF , ELSE RUSH THEN EMERGE
START 2 #DOES> @ EMERGE
START 3 #DOES> @ 1- CFLS + EMERGE ;
2 CFA IS 2 CFA TO 3 CFA AT 1 CFA DFT
-- TO и IS - синонимы; в различных системах приняты разные имена
Пример:
: QUAN CREATE 3 CFAS 0 ,
START TO DFT #DOES> @ EMERGE
START TO TO #DOES> ! EMERGE
START TO AT #DOES> EMERGE ;
QUAN Q -- описание переменной
5 TO Q -- записать 5 в Q
Q -- положить на стек значение переменной
AT Q -- положить на стек адрес поля параметра переменной
Для второй модели реализация описанного синтаксиса очевидна;
в третьей модели следует реализовывать упомянутый выше вариант б).
3. Обсуждение результата
Слово CFA, порождающее префиксы, само является словом с
несколькими полями кода. При использовании в виде TO <префикс> на
стек будет положен номер префикса, так что его можно использовать
перед словом #DOES> ; при исп в виде ' <слово> AT <префикс> на
стек будет положен адрес поля кода, соответствующий префиксу.
Данная система является, пожалуй, самой маленькой объектноо-
риентированной системой: объекты реализуются в виде слов с
несколькими полями кода, сообщениями будут являться префиксы, а
посылка сообщения будет выглядеть как ' <объект> AT <префикс>
EXECUTE . Возможно даже статическое наследование:
: СУММА QUAN TO TO #DOES> +! ;
Разумеется, чтобы этим можно было пользоваться, следует изменить
CREATE так, чтобы оно могло создавать объекты в куче.
В случае, если мы хотим использовать эту методику в целевом
компиляторе, возникает несколько вопросов, которые тем не менее
оказываются разрешимыми. Происходят они оттого, что целевая
память может и не располагаться в основной памяти; автор считает,
что этого следует просто избегать. Тем не менее, не вдаваясь в
подробности, приведем ряд соображений.
1. Порождающие слова в целевой системе не всегда нужны.
2. Если не предполагается запись в ПЗУ, можно смириться с тем,
что порождение первого слова целевой системой займет чуть
больше времени.
3. Чтобы завершить порождение кода определяющего слова, можно
создать "ненужное" определение и тут же его "забыть" (FORGET).
4. Неплохо, если целевые определения можно сразу же исполнять.
5. Если целевая система доступна только для записи, можно создать
буфер-прослойку, доступный для чтения и записи.
6. Вслед за словом (#DOES?) можно компилировать ещё и адрес(а)
в целевой системе.
4. Обсуждение методики
Конструкция DOES> - один из примеров того, что в Форте один
и тот же объект может рассматриваются то как программа, то как
данные. Фрагмент кода, следующий за (DOES>) , рассматривается
словом (DOES>) как данные, равно как и определяемое слово. Ссылку
на процедуру, предшествующую этим данным, можно рассматривать как
поле тега, определяющее, как надо их обрабатывать. (Обработка
производится адресным интерпретатором.) Так что нет ничего
удивительного в том, что данные и тег подвергаются модификации во
время выполнения. В работах [3,4] описана обработка
списков (а также более сложных структур данных, в т.ч. графов) с
помощью адресного интерпретатора. В [6] аналогичная техника
(данные представлены в виде исполнимого самомодифицирующегося
кода) позволила получить быстродействие, характерное для
дорогостоящих специализированных процессоров редукции
комбинаторных графов. В работе [5] описывается, как
динамическое порождения кода в объектно-ориентированной системе
позволяет повысить быстродействие, сохраняя гибкость, характерную
для позднего связывания. Форт-систему, загружающую программу,
также можно считать самомодифицирующейся - имеет место
динамическое порождение кода. Интересно отметить, что гибкость
языка Форт обуславливается возможностью применения собственных
инструментальных средств, и создаваемых в памяти, и используемых
во время компиляции программы, и именно из-за них Форт-систему
можно считать самомодифицирующейся. Существующий опыт позволяет
предположить, что самомодифицирующиеся и динамически
порождающиеся коды связаны с представлением данных в виде
программ и с обращением с программой как с данными.
ЛИТЕРАТУРА
[1] Баранов С.Н., Ноздрунов Н.Р. Язык Форт и его реализации.
Л.:Машиностроение, 1988.
[2] Гасаненко М.Л. Новые синтаксические конструкции и бэктрекинг
для языка Форт./Вопросы технологии программирования - СПб:
СПИИРАН, 1993. (В публикации)
[3] Тузов В.А. Функциональные методы программирования./
Инструментальные средства программирования - Л:ЛИИАН, 1988.
- с.129-143.
[4] Тузов В.А. Языки представления знаний. Л:ЛГУ, 1990.
[5] Craig Chambers, David Undar, "Customization: Optimizing Compiler
Technology for SELF, a Dynamically-Typed Object-Oriented
programming Language". Proceedings of the SIGPLAN'89 Conference
on Programming Language Design and Implementation, in
SIGPLAN Notices, v.24 n.7, July 1989.
[6] Koopman, Philip. "TIGRE: Combinator Graph Reduction On The
RTX2000", Proc. of the 1990 Rochester Forth Conf.
[7] Rosen, Evan. "High Speed, Low Memory Consumption Structures
( QUAN and VECT )." Proc. of the 1982 FORML Conf., p191-196.
[8] Schleisiek, Klaus. Multiple Code Fields Data Types and
Prefix Operators. The Journal of Forth Application and
Research, Vol.1,No.2, Dec. 1983, pp.55-68.
исходники (Там могли использоваться Бета-Форт, F-PC, и мой Форт для ЕС ЭВМ ряд-2)
eof