Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 16:31

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Открытый адресный интерпретатор
СообщениеДобавлено: Пн авг 24, 2009 21:57 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Автор:М.Л.Гасаненко
Дата публикации: 1998
оригинал статьи взят: Open Interpreter: Portability of Return Stack Manipulations
Перевел: mOleg

Открытый интерпретатор: переносимость манипуляций на стеке возвратов.

Преамбула
Для того чтобы сделать операции со стеком возвратов переносимыми, предлагается вариант стековой машины с открытым интерпретатором. Программистские техники, подобные реализации новых структур управления через манипуляции на стеке возвратов, бэктрекинг, и реализации техник подобных хранению литералов в шитом коде будут переносимы среди Фортов с открытым интерпретатором. Подход открытого интерпретатора может использоваться для распределенных ИИ на различных архитектурах.

Аббревиатуры
AI – искусственный интеллект (ИИ)
OI – открытый интерпретатор
RA – адрес возврата
IP – указатель интерпретации
R-stack – стек возвратов
TC – шитый код
TCE – элемент шитого кода
TCF – фрагмент шитого кода

Введение
На протяжении последней декады появилось большое количество статей, показывающих, как манипуляции адресом возвратов могут быть использованы для реализации бэктрекинга эффективно по времени, что позволяет решать проблемы искусственного интеллекта и проблемы, похожие на разбор BNF выражений [Rod90a] и поиск по образцу[Cha91]. В дополнение бэктрекинг мощный выразительный метод программирования, с момента появления модулей-итераторов, отвечающих за просмотр наборов значений (1). Когда потребуются изменения в просматривающем алгоритме будет затронут только один модуль. Современная проблема с бэктрекингом заключается в том, что манипуляции стеком возвратов не переносимы между разными ANS Форт-системами. Другая впечатляющая техника, получающая выигрыш от манипуляций стеком возвратов – это исполнение данных (решение управляемое данными) [Tuz88][Tuz90][Koo90]. Доступ к стеку возвратов предоставляет значительно больший уровень доступа к данным во время исполнения и контроля над процессом исполнения данных, чем можно ожидать в Лиспе, без необходимости традиционного интерпретатора данных. Аналогично бэктрекингу исполнение данных используется в ИИ, и конструкциях компилятора, и может быть полезно в других областях. Фундаментальное отличие между манипуляцией данными и адресами возвратов может заключаться в методах передачи управления. Передача управления производится согласно манипуляциям на стеке возвратов и радикально изменяет поведение исполняемого кода.

Тем не менее, формальное описание такой передачи управления существует [Gas95][Gas96].

В Форте стек возвратов может быть использован для:
- хранения временных данных,
- передачи параметров, сохраненных в шитом коде процедурам,
- создания новых структур управления (классических или нетрадиционных),
- реализации новых методов исполнения программ (таких как бэктрекинг [Cha91] [Cha92] [Gas94] [Rod89] [Rod90a] [Rod90b])
- реализация исполнимых самообрабатывающихся данных [Tuz88] [Tuz90] [Koo90] [Rod90a] [Rod90b],
Текущий стандарт [ANS94] позволяет только первое. Другие методы, использующие стек возвратов важны и как техника программирования, и как техника реализации.

Давайте рассмотрим следующее определение:
: LIT R@ @ R> CELL+ >R ;
Это пример получения данных, сохраненных в шитом коде, являющийся важной техникой реализации, и его формальное описание было наиболее значимой находкой в [Gas95]. Слово LIT в большинстве значений отражает работу слова LITERAL во время исполнения.

: LITERAL COMPILE LIT , ; IMMEDIATE
С точки зрения этого слова следующие определения эквивалентны:
: t1 [ 5 ] LITERAL . ;
: t2 LIT [ 5 , ] . ;
: t3 5 . ;
Хотя в определении LIT всего шесть слов (не забывайте завершающий EXIT), существует проблема: это работает на 16-битной односегментной Форт-системе под ДОС (к примеру, Beta-Forth, Info-Forth, MPE) и некоторых 32 битных Фортах, но, к примеру, в F-PC слово должно выглядеть так:
: LIT 2R@ @L 2R> 2+ 2>R ;
на Win32Forth:
: LIT R@ ABS>REL @ R> CELL+ >R ;
и в 8-битном i8051 Форте:
: LIT 2R@ @C 2R> 1. D+ 2>R ;
(последнее походит на F-PC).
Для того чтобы сделать манипуляции управляющие потоком управления на стеке возвратов переносимыми, предлагается описание стековой машины с открытым интерпретатором.
В терминах этой машины, все приведенные выше определения слов имеют одинаковую функциональность.
Эти определения различаются только потому, что они используют слова, отражающие специфику различных архитектур. Если переписать приведенные выше определения с использованием машины с открытым интерпретатором, их исходный текст будет идентичным. Машина открытого интерпретатора предоставляет семантику в которой определения, использующие манипуляции на стеке возвратов, могут быть написаны в переносимой форме. Это дает путь создания переносимых приложений, использующих бэктрекинг и методики исполнение данных. Открытый интерпретатор так же может быть использован в распределенных системах, теперь, в принципе, возможно исполнять один и тот же код используя вышеупомянутые ИИ техники на различных архитектурах.

Четыре типа Фортов с открытым интерпретатором
Мы рассмотрим 4 типа Фортов с открытым интерпретатором:
Первый тип. Адреса возвратов имеют такой же формат, как адреса данных, система использует
шитый код, который разделяет память данных (2). Упомянутые 16-битные Форты, и 32-битные MPE относятся к этому типу.
Второй тип. Адреса возвратов имеют размер в одну ячейку, но их представление отличается от представления адресов данных. Шитый код находится в пространстве данных. Win32Forth принадлежит к этому типу.
Третий тип. Адреса возвратов имеют размер в одну ячейку, их представление может отличаться от адресов данных. Шитый код может находиться в отдельной памяти, и специальные слова могут требоваться для доступа к этой памяти ( к этому классу принадлежит Гарвардская архитектура).
Четвертый тип. Адреса возвратом могут быть более длинными, чем 1 ячейка, и специальные слова могут требоваться для доступа к шитому коду. К этому типу принадлежат F-PC и Harvard 8-bit i8051 Forth.
Каждый тип – это подтип следующего типа (конец определения).
Как можно сделать манипуляции адресами возвратов переносимым между этими системами образом?
Для систем первого типа проблем нет: мы может использовать слова R> , R@ , и подобные для манипуляций с адресами возвратов, и слова @ , C@ и подобные для получения данных в шитом коде. Для систем второго типа мы вводим слова RR> , RR@ и подобнее для работы с адресами возвратов. Эти слова выполняют преобразование формата адресов возврата к формату адресов данных, и/или обратно. (Такая нотация имеет преимущества: мнемоника недвусмысленно отражает что мы хотим работать с адресами возвратов, а не с обычными данными) Для систем третьего типа мы предлагаем слова /@ , /C@ и подобные слова, позволяющие обращаться к памяти исполнимого кода. Для систем четвертого типа слова >RR , RR@ и подобные манипулируют со значениями двойной (тройной, и т.п.) длины, конвертируя их в вид адресов возврата и обратно, если необходимо. Слова /@ , /C@ и подобные получают адреса в виде, позволяющем использовать представление адресов возврата на стеке данных. Стоит отметить, что возможно манипулировать адресами возвратов и работать с элементами шитого кода переносимым даже на системах четвертого типа. Что же касается компиляторов в естественный код, мы требуем, чтобы они эмулировали систему одного из перечисленных типов, если оно (компиляторы) претендуют на поддержку возможностей открытого интерпретатора. (Возможный подход к реализации – использовать вариант шитого кода, как переходного кода из которого в последствии будет компилироваться целевой код, естественный для используемой процессорной системы).
Давайте детально разберем архитектуру систем четвертого типа. Слова DUP , SWAP и им подобные не могут использоваться для управления адресами возвратов переносимым образом. Мы должны использовать фразы: >RR RR@ RR> взамен DUP или 2DUP для получения копии адреса возвратов на стеке данных, и >RR >RR< RR> вместо SWAP или 2SWAP ; фразу: R> R> SWAP >R >R или 2R> 2R> 2SWAP 2>R 2>R становится: RR> >RR< >RR . Стандартные арифметические операторы не могут использоваться с адресами возвратов.
Как в случае системы третьего типа, стандартные слова @ , C@ и им подобные не могут быть использованы для доступа к литералам и шитому коду. Тип 1 наиболее подходит для научных исследований (формализм [Gas95] [Gas96] разработан для систем первого типа, хотя не будет сложно переписать доказательства для систем второго и третьего типов; для четвертого типа формализм станет очень неуклюжим, потому что формализм требует манипулировать и адресами возвратов и данными на стеке данных, даже если код не должен.)
Четвертый тип наиболее распространен, и код четвертого типа наиболее переносим, пока остается опрятным.
Проблема с написанием кода для систем четвертого типа в том, что он мешает использовать стековые примитивы типа DUP для манипуляции адресами возврата. Если ваш код никогда не будет запущен на системах четвертого типа, это ограничение может выглядеть серьезным. Из практических соображений может быть рекомендовано писать приложения для систем третьего, или, минимум, второго типа в основном потому что слова типа RR> четко показывают что вы намереваетесь манипулировать адресом возвратов, а не данными(различие аналогичное таковому между словами 4+ и CELL+).
Переносимое (тип 4) определение для LIT : LIT RR@ /@ RR> /CELL+ >RR ;
Определение : LIT R@ @ R> CELL+ >R ; переносимо на системах первого типа.

Определение стековой машины с открытым интерпретатором
Исполнимый код открытого форт интерпретатора будет называться шитым кодом (4).
Шитый код может быть рассмотрен как последовательность скомпилированных адресов процедур (в простейшем случае это только адреса процедур ) (5).
Точнее, шитый код может содержать следующие типы элементов шитого кода:
- скомпилированные токены процедур
- ссылки на шитый код (адреса ветвлений представлены в этом формате)
- вшитые данные
только скомпилированные токены процедур обрабатываются интерпретатором.
Существует два типа процедур: примитивы (процедуры реализованные в железе, машинный код языка, отличного от Форта) и высокоуровневые процедуры (тела высокоуровневых процедур – это фрагменты шитого кода, и исполнение таких процедур приводит к вызову этих фрагментов кода).
Интерпретатор шитого кода (внутренний интерпретатор форта) имеет:
- регистр (IP – указатель интерпретации), указывающий на следующий адрес токена в шитом коде, который должен быть исполнен, и
- стек (стек возвратов), куда интерпретатор сохраняет IP во время вызовов фрагментов шитого кода, и с которого загружает IP, покидая фрагмент шитого кода.
Указатель интерпретации и стек возвратов вместе формируют стек интерпретации.
Указатель кода – это адрес элемента шитого кода (или, что тоже самое, адрес фрагмента шитого кода, начинающегося с этого элемента шитого кода).
Есть два типа информации на стеке интерпретации.
Стек возвратов может содержать:
- указатели данных
- другие данные.
Указатели кода отражают незавершенные вызовы.
IP (верхний элемент стека интерпретации) всегда содержит указатель на код.
Только указатели кода могут быть обработаны интерпретатором самостоятельно. Определения хранящие «другие данные» на стеке возвратов написаны так, что данные не пересекаются с интерпретатором. Логика процедурных вызовов такая же как в других языках программирования, лишь с той разницей, что параметры процедуры и локальные переменные не находятся в одном стеке с адресами возвратов. Мы описываем вызовы процедур в терминах фрагментов шитого кода, потому, что вызов высокоуровневых процедур это частный случай вызова фрагмента шитого кода (называемый вызовом тела процедуры).
- Когда фрагмент шитого кода вызывается, новый указатель кода (адрес фрагмента шитого кода) кладется на вершину стека интерпретации.
- Когда фрагмент шитого кода покидается, его указатель кода удаляется со стека интерпретации.
Замечу, что мы представляем двойной вид на стек интерпретации, потому что это ключ к пониманию манипуляций на стеке возвратов. Интерпретатор шитого кода рассматривает стек возвратов и указатель интерпретации (IP) как единственный стек. Программист манипулирует только стеком возвратов, потому что IP изменяется в процессе исполнения кода, и запись в IP приведет к моментальной передаче управления.
С другой стороны, это не ограничение: когда мы вызываем вспомогательную процедуру стек возвратов становится чем был стек интерпретации. Любые изменения, которые должны быть произведены со стеком интерпретации, эта процедура выполнит со стеком возвратов. Когда процедура завершается, стек интерпретации становится тем, чем был стек возвратов. Таким образом, стоит следовать правилу: пишите код, который делает со стеком возвратов то же, что должен делать со стеком интерпретации; определяйте этот код во вспомогательную процедуру. Эта процедура будет делать требуемые изменения со стеком интерпретации.
Скомпилированные токены процедур обрабатываются интерпретатором следующим образом: интерпретатор извлекает скомпилированный токе, на который указывает IP, смещает IP на следующий скомпилированный токен, и исполняет процедуру, определенную извлеченную скомпилированным токеном.
Мы не делаем предположений, как исполняются примитивы, мы знаем только результат их исполнения. В случае высокоуровневой процедуры у нас есть выбор: мы можем рассматривать их как черный ящик с некоторым эффектом, или мы можем выбрать знание того, что новый указатель кода расположен на вершине стека интерпретации и исполнение продолжается с использованием этого указателя кода. Слово EXIT убирает верхний элемент стека интерпретации. Обычно, это слово используется для возврата в вызывающее определение.

Стековая нотация
Стековая нотация следует [ANS94] нотации:
Стековые параметры входящие в и выходящие из определения представляются с использованием нотации:
( состояние стека до исполнения слова -- состояние стека после исполнения )
где stack-id определяет какой стек описывается, before представляет параметры на стеке данных перед исполнением определения, и after отражает состояние после исполнения... Идентификатор стека потока управления "C:", идентификатор стека данных: "S:", и стека возвратов: "R:". В случае, если стековая диаграмма не может быть прочитана неправильно, идентификатор стека данных stack-id может быть опущен.
В случае возможных альтернативных представлений after они будут представлены следующим образом "after1 | after2". Вершина стека располагается справа. Только те элементы стека отражаются на диаграмме, которые поглощаются или используются во время исполнения.
В дополнение к процитированному выше, когда есть альтернативные представления до и после, они описываются как:
( stack-id11 before11 -- after11 ) ( stack-id12 before12 -- after12 ) ...
( stack-id21 before21 -- after21 ) ( stack-id22 before22 -- after22 ) ...
....
Где описания стековых эффектов расположенные в разных линиях соотносятся с различными альтернативами.
Идентификатор стека интерпретации "R&IP:".
Используемые символы в стековых диаграммах те же, что определены в ANS94, а так же следующие:
ra – адрес возвратов (выровненный адрес элемента шитого кода)
tca – адрес элемента шитого кода (то же, что и ra)
ra[ <data> ] – адрес возврата, по которому сохранен <data>
ra+ -- увеличить (на размер данных, сохраненных по адресу ra) адрес возврата ra
addr[ <data> ] – адрес данных <data>
u-tca – не выровненный адрес элемента шитого кода.
Представление адресов возвратов в стеках данных и возвратов может различаться. Реализация может требовать, чтобы адреса возвратов были выровнены определенным образом, но добавление размера ячейки к правильно расположенному адресу токена должно давать выровненный адрес. Скомпилированные токены и ссылки в шитом коде могут навязывать идентичные требования к выравниванию значений, добавление размера ссылки шитого кода к правильно выровненному TCA должен дать выровненный адрес. Только внутренние элементы данных могут располагаться по не выровненным адресам.
Описание сохраненных данных:
ref – ссылка в шитом коде
"abc" – символьная строка содержащая текст "abc"
c"abc" – строка со счетчиком: текст "abc" предваряется байтом счетчика
ct – скомпилированный токен
Пара разделенная точкой format.datа описывает формат в котором сохранены данные data.
Описатели формата:
размер символа в памяти описывается x.

1 cell one cell stored "as is" ref.
1 reference a threaded code reference
c. 1 chars one character
ct. may vary compiled token

Примеры:
ref.a-addr – выровненный на размер ячейки адрес, сохраненный как ссылка в шитом коде
ref.tca – адрес элемента шитого кода, сохраненный как ссылка шитого кода
x.a-addr – выровненный на размер ячейки адрес сохраненный «как есть»
x.xt1 – исполнимый токен, сохраненный «как есть»
ct.xt1 – представление шитого кода (которую может интерпретировать интерпретатор ШК) исполнимой семантики идентифицируемой xt1
Типичный стековый эффект слова ( R&IP: ra -- ra ), это интерпретатор, который увеличивает указатель интерпретации. (Интерпретатор шитого кода увеличивает указатель интерпретации, то есть IP, перед вызовом процедуры; по крайней мере, система должна поддерживать эту иллюзию)
Примеры:
NOOP ( R&IP: ra -- ra )
>R ( x -- ) ( R&IP: ra -- x ra )
(S") ( -- ra ) ( ra[ c"abc" ] -- ra+ ) \ семантика времени исполнения S"
BRANCH ( R&IP: ra1[ ref.ra2 ] -- ra2 ) \ семантика времени исполнения AHEAD
?BRANCH ( false -- ) ( R&IP: ra1[ ref.ra2 ] -- ra2 ) \ семантика времени исполнения IF
( true -- ) ( R&IP: ra1[ ref.ra2 ] -- ra1+ )
LIT ( -- n ) ( R&IP: ra[ n ] -- ra+ )
COUNT ( c-addr[ c.len "abc" ] -- c-addr["abc"] len )
@ ( a-addr[ x ] -- x )

Число в скобках за стековым эффектом слова показывает номер типа системы, начиная с которой это слово необходимо. К примеру, запись >RR ( ra -- ) ( R: -- ra ) [2] означает что это слово может быть использовано если мы пишем код для системы 2-4 типов (для систем первого тип можно использовать классический >R).

Набор слов открытого интерпретатора
EXIT ( R&IP: ra1 ra2 -- ra1 ) [1] Передать управление на адрес, лежащий на вершине стека возвратов.
В терминах стековой интерпретации, его верхний элемент ra2 убирается.
В терминах стека возвратов, IP загружается адресом ra1 взятым со стека возвратов.
>RR ( ra -- ) ( R: -- ra ) [2] Переместить ra со стека данных на стек возвратов.
RR> ( -- ra ) ( R: ra -- ) [2]Переместить ra со стека возвратов на стек данных.
RR@ ( -- ra ) ( R: ra -- ra ) [2] копировать ra со стека возвратов на вершину стека данных.
RRDROP ( -- ) ( R: ra -- ) [2] удалить ra с вершины стека возвратов.
COPY>RR ( ra -- ra ) ( R: -- ra ) [2] копировать ra со стека данных на стек возвратов (6).
>RR< ( ra1 -- ra2 ) ( R: ra2 -- ra1 ) [2] Обменять ra1 на стеке данных с ra2 на стеке возвратов. (6).
Для систем четвертого типа, в которых адреса возвратов могут занимать любое количество элементов стека, это означает только поменять порядок адресов возвратов.
/ALIGNED ( u-tca1 -- tca2 ) [1] tca2 это ближайший адрес больший или равный u-tcal по которому могут быть размещены скомпилированный токен или адресная ссылка.
/@ ( tca[ x ] -- x ) [3] Извлечь литеральные данные из ячейки по адресу tca.
/C@ ( u-tca[ c ] -- x ) [3] Извлечь символьные литеральные данные, находящиеся в tca.
/CELL+ ( u-tca1 -- u-tca2 ) [3] Увеличить tca1 на размер одной ячейки. Для систем 1-3 типов это слово эквивалентно CELL+.
/+ ( n u-tca1 -- u-tca2 ) [3] прибавить n к tca1. Результат tca2 может быть не выровненным.
/C, ( char -- ) [3] Резервировать пространство для одного символа в пространстве шитого кода, и сохранить туда символ.
/, ( x -- ) [3] Зарезервировать одну ячейку в пространстве шитого кода, и сохранить х в нее.
Если указатель пространства шитого кода выровнен на границу TCE когда /, начинает исполняться, он (указатель) будет выровнен на границу ТСЕ к моменту завершения /, .
Примечание. Начиная со второго типа, исчезают гарантии того, что последовательность >RR RR> эквивалентна команде NOOP, если стек данных на вершине не содержит правильный адрес возврата.

Расширенный набор слов открытого интерпретатора
TOKEN, ( xt -- ) [1] добавить скомпилированный токен процедуры, идентифицируемой xt в текущий фрагмент шитого кода(тот, куда ведется компиляция) Аналогично слову COMPILE, .
TOKEN@ ( tca[ ct ] -- xt ) [1] Декодировать скомпилированный токен по адресу tca, вернуть исполнимый адрес процедуры, семантика которой хранится в tca.
TOKEN+ ( tca1-- tca2 ) [1] Декодировать скомпилированный токен по адресу tca, вернуть адрес следующего элемента шитого кода.
TOKEN> ( tca1[ ct ] -- tca2 xt ) [1] Декодировать скомпилированный токен по адресу tca, вернуть адрес следующего элемента шитого кода и адрес процедуры, хранимой по указанному tca. Эквивалент кода:
>RR RR@ TOKEN+ RR> TOKEN@ .
REF@ ( tca1[ ref.tca2 ] -- tca2 ) [1] Вернуть адрес tca2 , на который хранится ссылка в tca1.
REF+ ( tca1[ ref.tca2 ] -- tca3 ) [1] Увеличить адрес tca1 на величину адресной ссылки.
REF- ( tca3 -- tca1[ ref.tca2 ] ) [1] Уменьшить tca3 на размер ссылки, сохраненной перед указанным адресом.
Выражение REF- REF+ эквивалентно NOOP .
REF! ( tca-dest tca-orig -- ) [1] Сохранить ссылку на адрес tca-dest в поле указанном tca-orig. После исполнения этого слова ссылка в tca-orig указывает на tca-dest.
>TCODE ( xt -- tca ) [1] Вернуть адрес tca фрагмента шитого кода, который вызывается, когда высокоуровневое определение, идентифицируемое xt исполняется.
>MARK ( -- orig ) [1] Отметить начало конструкции ссылки вперед: добавить ссылку на текущий фрагмент шитого кода, вернуть адрес, по которому хранится ссылка. Адрес назначения полученной ссылки не определен до тех пор, пока конструкция не будет завершена. См. >RESOLVE .
>RESOLVE ( orig -- ) [1] Завершить конструкцию прямой ссылки, когда новый элемент будет добавлен в текущий фрагмент шитого кода, ссылка по адресу orig будет на него указывать.
<MARK ( -- dest ) [1] начать конструкцию обратной ссылки. Адрес назначения dest идентифицирует следующий элемент шитого кода, который будет добавлен в текущий фрагмент.
<RESOLVE ( dest -- ) [1] завершить конструкцию обратной ссылки. Добавить ссылку на текущий фрагмент шитого кода, dest определяет адрес назначения.
/MOVE ( addr u u-tca -- ) [3] Переместить u адресных ссылок начиная с адреса tca в память, указываемую адресом addr.
Исходный адрес tca на вершине стека, поэтому есть проблемы с манипуляциями на системах четвертого типа.

/XSWAP ( u-tca x -- x ra ) [4] Поменять местами u-tca и x на вершине стека данных.
X/SWAP ( x ra -- ra x ) [4] Поменять местами x и u-tca на вершине стека данных.

>RX< ( ra -- x ) ( R: x -- ra ) [2] Обменять ra (на вершине стека данных) и x (на вершине стека возвратов). Мнемоническое правило: ra уходит, x возвращается.
>XR< ( x -- ra ) ( R: ra -- x ) [2] Обменять x (на вершине стека данных) и ra (на вершине стека возвратов).

Примечание 1. С помощью слов TOKEN> и >.NAME ( xt -- ; отобразить имя слова, определяемое своим xt) можно написать переносимый декомпилятор.
Примечание 2. На системах четвертого типа существуют специфичные проблемы. В случае использования слова + мы можем получить неверный (то есть неверно выровненный) адрес возврата. Мы не можем положить его на стек возвратов с помощью >RR , потому что преобразование внутреннего формата адреса возвратов может привести к непредсказуемым результатам. Так же мы не можем использовать стековые примитивы, подобные SWAP, для изменения порядка следования данных на стеке, потому что размер адресной ссылки не известен. Не смотря на перечисленное, возможно писать переносимый код для систем четвертого типа (использовать /XSWAP и X/SWAP), либо серьезно рассмотреть возможность использовать систему третьего типа вместо четвертого.
Примечание 3. Если вы пишете код для системы четвертого типа, вам необходимо тестировать свой код как минимум на двух системах с различными размерами адресов для уверенности, что вы не использовали системных особенностей неосознанно (случайно). Конечно, всегда остается возможность того, что особенности присутствуют в обоих ваших системах, и вы используете одну из них. Аналогичная проблема существует с переносимым кодом для чисел с плавающей точкой (стандартная система позволяет хранить FP числа на стеке данных, либо на отдельном FP стеке), и даже с размером символов: если вы не имеете системы, где CHARS синоним NOOP, вы не можете быть уверены, что не упустили CHARS формирующий аргумент для MOVE.
Примечание 4. Если код написан с использованием слов из набора открытого интерпретатора легче найти места зависимые от архитектуры интерпретатора в нем. Таким образом, даже если вы будете использовать особенности интерпретатора шитого кода, места где эти особенности важны будут явно отмечены.

Вспомогательные слова открытого интерпретатора
RP@ ( -- x ) [1] Вернуть системно-зависимое значение, идентифицирующее текущую глубину стека возвратов.
Это значение может использоваться совместно с RP!
RP! ( x1 -- ) ( R: i*x -- j*x ) [1] Установить глубину стека возвратов на значение определенное xl.
Если новая глубина стека больше, чем старая, содержимое новых элементов стека возвратов не определено.
Непредвиденное состояние: x1 не соответствует ни одному действительному значению глубины стека возвратов.
Назначение этих слов обеспечивать нелокальные выходы (которые требуются, к примеру, для Пролого-подобных конструкций отсечения).
Эти слова предложены в осознании факта, что они присутствуют в большинстве (если не во всех) Форт-систем.
Слова RDEPTH ( --n ) и RDEPTH! ( n -- ) ( получить и установить глубину стека возвратов соответственно ) так же будут использоваться для нелокальных выходов; их неудобство заключается в том, что они не используются в текущей практике.
RADDR@ ( a-addr -- ra ) [4] Извлечь адрес возврата, сохраненный в a-addr.
RADDR! ( ra a-addr -- ) [4] Сохранить адрес возврата ra в a-addr.
RADDR+ ( a-addr1 -- a-addr2 ) [4] Увеличить адрес a-addr-1 на размер адресной ссылки, вернуть полученный адрес a-addr2.
RADDR- ( a-addr1 -- a-addr2 ) [4] Уменьшить адрес a-addr-1 на размер адресной ссылки, вернуть полученный адрес a-addr2.
Эти слова позволят нам сделать переносимые реализации дополнительных стеков, хранящих адреса возвратов.

Пример 1: литералы в шитом коде.

Первый пример определения слова LIT рассматривался выше.
Второй пример – переносимый (класс 4) код стандартного слова .” .

: /TYPE ( tca[ c"text" ] -- )
>RR
1 RR@ /C@ ( i imax )
BEGIN
2DUP U> 0=
WHILE
OVER RR@ /+ /C@ EMIT
SWAP 1+ SWAP
REPEAT
2DROP RRDROP
;

: (.") ( tca[ c"text" ] -- tca+ )
RR@ \ addr of the string
RR@ /C@ CHAR+ RR> /+ /ALIGNED >RR \ просматривает строку
/TYPE
;

: ." ( Compilation: "text<">" -- )
COMPILE (.")
[CHAR] " WORD
DUP C@ 1+ 0
?DO
DUP I + C@ /C,
LOOP
DROP
/ALIGN
; IMMEDIATE

Мы не можем определить слова C” и S” таким образом, потому что они возвращают адрес в пространстве данных. Их переносимые определения не имеют отношения к манипуляциям с адресом возвратов.

: C"
POSTPONE AHEAD
HERE >R
[CHAR] " PARSE TUCK HERE PLACE 1+ ALLOT /ALIGN
POSTPONE THEN
R> POSTPONE LITERAL
; IMMEDIATE
\ : PLACE ( from len to -- ) 2DUP C! 1+ SWAP CHARS MOVE ;
В этом определении только одно слово требуется из набора открытого интерпретатора: /ALIGN .

Пример 2: реализация структур управления.

Это переносимое (тип 4) определения рекурсивной структуры управления. Слова STAT и EMERGE отмечают границы блока, слово DIVE отмечает рекурсивный вызов блока.

: (CALL) RR@ REF+ >RR< REF@ >RR ;
: (START) RR@ REF@ >RR< REF+ >RR ;
: START ?COMP COMPILE (START) >MARK <MARK 201 ; IMMEDIATE
: EMERGE ?COMP 201 ?PAIRS DROP COMPILE EXIT >RESOLVE ; IMMEDIATE
: (DIVE#) ( an .. a2 # --> )
DEPTH 1 ( n 1 )
DO ( an .. a1 # )
I PICK 201 =
IF
I 2 + PICK 201 =
I 2 + PICK 201 = AND
IF
1- DUP 0=
IF
DROP
COMPILE (CALL) I 2 + PICK <RESOLVE
UNLOOP EXIT
THEN THEN THEN
LOOP
1 ABORT" слишком большой уровень вложенности"
;

: DIVE \ call the enclosing START-EMERGE block
?COMP 1 (DIVE#) ; IMMEDIATE

: DIVE# ( "n" -- ) \ вызвать n-тый закрывающий START-EMERGE блок
\ DIVE# 1 эквивалентно DIVE
?COMP BL WORD NUMBER DROP (DIVE#) ; IMMEDIATE

: .FACT ( n -- )
DUP .
START
DUP 0>
IF DUP 1- DIVE *
ELSE DROP 1
THEN
EMERGE
." ! = " .
;
Слово .FACT простейший пример этой структуры управления. Если мы исполним 5 .FACT получим "5 ! = 120".
Непереносимая версия слова (DIZE#) анализирует скомпилированный код для проверки является ли элемент под номером 201 ссылкой за скомпилированный токен (START). В переносимой версии на стеке данных будет лежать три числа 201. Строго говоря, никто не может гарантировать, что START единственное слово в системе, оставляющее 201 на стеке данных в трех экземплярах, но это совсем невероятно. Другое возможное приближение для проверки корректности, например, сохранять глубину стека соответствующего слову START в переменной, сохраняя старое значение переменной в слове START и восстанавливая его словом EMERGE.

Пример 3: бэктрекинг

Тут мы дадим простейший пример бэктрекинга. Слово TTT печатает числа от 1 до 10.

: ENTER ( tca -- ) ( R&IP: -- tca ) \ вызвать фрагмент кода в tca
>RR ;
: SUCC POSTPONE RR@ POSTPONE ENTER ; IMMEDIATE
: FAIL POSTPONE RRDROP POSTPONE EXIT ; IMMEDIATE
: 1-10
1
BEGIN
SUCC
1+
DUP 11 =
UNTIL
DROP FAIL
;

: TTT
1-10 DUP .
;

Почему эта техника важна. Если мы напишем новый интерпретатор на любом языке программирования, новый интерпретатор будет, в лучшем случае, медленнее на порядок. Если мы расширим существующий интерпретатор новыми операциями, только эти новые операции замедлят исполнение.
В случае использования расширений интерпретатора в 10% случаев, и каждый вызывает 10 Форт примитивов, общая скорость исполнения уменьшится в два раза. Если расширения интерпретатора написаны на Ассемблере, потеря скорости незначительна. В дополнение, расширение интерпретатора предоставляет более простой и менее подвержено ошибкам.

Похожие работы
C Жакман в [Jak96] предложил небольшой набор слов (всего шесть) позволивший ему сделать пакет FOSM для разбора строк [Cha91][Cha92] на ANS Форте с требованиями окружения. Жакман отметил, что для реализации бэктрекинга необходимо манипулировать небольшим количеством элементов стека возвратов (это абсолютно верно). Для реорганизации адресов возвратов Жакман сохраняет их временно на стек данных и во вспомогательную глобальную переменную (невозможно использовать стековые примитивы, потому что размер адресов возврата может варьироваться для различных систем). Шесть слов перемещают адреса возвратов между стеками, дублируют и удаляют их, читают адрес из вспомогательной переменной и сохраняют его туда. Доступ к элементам шитого кода не продуман.

Заключение
Дано строгое определение стековой машины с открытым интерпретатором. Для форта с открытым интерпретатором механизм исполнения кода определен, и предоставлен набор операций для доступа к шитому коду и стеку интерпретатора. Техники со стеком возвратов, подобные бэктрекингу, структуры управления реализованы с помощью манипуляций на стеке возвратов, хранение литералов в шитом коде, становятся переносимыми между Фортами с открытым интерпретатором.

Сноски
(1) Слово "1-10" в "Примеры III: Переносимый бэктрекинг" секции могут использоваться как пример такого модуля.
(2) "Память данных" – ANS Форт термин, это память, доступная словам @ C@ и подобным.
(3) Гарвардские системы с одноячеечными адресами возвратов и без преобразования адресов из формата возврата в формат данные-в-пространстве-кода на уровне систем второго типа. Подобный тип (тип 2б) не представлен, потому что классификация станет менее понятной; в дополнение, Win32Forth можно отнести либо к системе типа 2а, либо к системе типа 2б, но нельзя отнести к обоим, потому что преобразования адресов возвратов могут производиться и с помощью слов RR> и с помощью слов типа /@ . В такой ситуации могут появиться несовместимые приложения для одинаковых систем. Наконец, выбор делается в пользу системы второго типа, потому что такие системы иногда используются для научных целей (в случае недоступности систем первого типа), в то время как системы на основе Гарвардской архитектуры чаще используются в индустриальных приложениях, где поощряются явные обозначения манипуляций адресов возвратов.
(4) На протяжении длительного времени термин «шитый код» использовался для отметки того, что код имеет природу, отличную от естественного процессорного кода. В настоящее время исполнимые коды могут одновременно быть и шитыми и нативными (то есть коды стековых процессоров, подпрограммные шитые коды с вставками нативного кода) и, что значительнее, различия между нативными и интерпретируемыми кодами не сильно значимы с точки зрения программиста. Выражение «шитый код» будет использоваться для обозначения того факта, что исполнимый код имеет определенную структуру и обрабатывается с использованием некой определенной дисциплины.
(5) Скомпилированный токен – это элемент шитого кода, который отмечает процедуру (когда код исполняется, исполняется процедура).
В случае с косвенным и прямым шитыми кодами скомпилированный токен имеет фиксированную длину, обычно одна ссылка занимает одну ячейку (1 CELL) и содержит прямой адрес процедуры. В случае подпрограммного шитого кода, скомпилированный токен – это инструкция CALL на процедуру. В случае подпрограммного шитого кода с инлайн вставками, скомпилированный токен может быть как инструкцией вызова процедуры, либо цепочкой ассемблерных инструкций, выполняющих семантику процедуры (то есть функциональный эквивалент вызова процедуры). Так же могут существовать другие варианты шитого кода.
(6) Аналоги слов >RR< и COPY>RR для первого типа должны называться >R< и COPY>R . Для 2-4 типов >R< и COPY>R могут оперировать только на значениях не являющихся адресами возвратов.

Литература:


[ANS94] ANSI, 1994. American National Standard for Information Systems - Programming Languages - Forth. ANSI X3.215-
1994 - American National Standard Institute, Inc. - 212 p.
[Cha91] Charlton G., 1991. FOSM, A FOrth String Matcher.//1991 FORML Conference Proceedings, euroFORML'91
Conference, Oct 11-13, 1991, Marianske Lazne, Czechoslovakia, Forth Interest Group, Inc., Oakland, USA, 1992. -
P.313-329.
[Cha92] Charlton G., 1992. FOSM, A FOrth String Matcher, continued.//euroForth'92 Conference Proceedings, MPE Ltd.,
Southampton, UK. - P.113-122.
[Gas94] Gassanenko M.L., 1994. BacFORTH: An Approach to New Control Structures. //Proc. of the EuroForth'94
conference, 4-6 November 1994, Royal Hotel, Winchester, UK p.39-41.
[Gas95] Gassanenko M.L., 1995. Formalization of Return Addresses Manipulations and Control Transfers. //Proc. of the
euroFORTH'95 conference, 27-29 October 1995, International Centre for Informatics, Dagstuhl Castle, Germany, 18
p.
[Gas96] Gassanenko M.L., 1996. Formalization of Backtracking in Forth. //Proc. of the euroFORTH'96 Conf., 4-6 October
1996, Hotel Rus, St.Petersburg, Russia, 26 p.
[Jak96] Jakeman, C.M., 1996. Portable Backtracking in ANS Forth. //Proc. of the FORML'96 conf.
[Koo90] Koopman P., 1990. TIGRE: Combinator Graph Reduction On The RTX2000.//Proc. of the 1990 Rochester Forth
Conf., p.82-86.
[Rod89] Rodriguez B., 1989. Pattern matching in Forth.//Proc. of the 1989 FORML Conf.
[Rod90a] Rodriguez B., 1990. A BNF Parser in Forth.//ACM SIGForth Newsletter, vol.2, no.2, December 1990, p.13-18.
[Rod90b] Rodriguez B., 1990. Rules Evaluation through Program Execution.//Proc. of the 1990 Rochester Forth Conf., p.123-
125.
[Tuz88] Tuzov V.A., 1988. Funktsional'nye metody programmirovanija./ Instrumentalnye sredstva programmirovanija -
L:LIIAN. - p.129-143. (The Functional Methods of Programmming [data execution is a powerful programming
technique], in Russian)
[Tuz90] Tuzov V.A., 1990. Jazyki predstavlenija znanij. - L:LGU. (The Languages of Knowledge Representation [what an
ideal language of knowledge representation should be], in Russian.)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 31, 2009 03:20 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
итак, в перечисленном наборе примитивов мне однозначно нравятся следуюшие вещи:
TOKEN@ TOKEN! TOKEN+
REF@ REF! REF+ и возможно REF- хотя я сомневаюсь в их полезности, и уж по крайней мере обязательности
RR> и подобные им мне больше нравятся в иной форме:
A>R AR> (то есть Address) в добавок к словам работающим с адресами A@ A! A, и подобным
а вот различные обмены мне таки не нравятся, кстати, очень напрашивается завести отдельный адресный стек, для чего уже есть достаточно предпосылок (вспомнить регистр адреса в Чаковских SEA). Собственно временный адресный регистр в любом случае не помешал бы, но это как бы уже не минимально достаточный набор.

Кстати, можно представить экстремальный вариант, когда, к примеру разрядность данных = 256 бит, а разрядность адреса = 32 бита (чего вполне достаточно может быть). Тогда разрядности стека данных и стека возвратов будут 1:16 и перенос >R будет увеличивать глубину стека возвратов на 16 ячеек. И тогда возникает идея создания лексикона, позволяющего выполнять адресные операции непосредственно на стеке возвратов!!!

Вот такие у меня мысли.

Впрочем, очень хотелось бы увидеть современные мысли автора работы по ее содержимому...

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB