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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Слово о Форте. Попытка формализации сути языка
СообщениеДобавлено: Сб апр 25, 2009 23:25 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Автор: Андрей Черезов
Дата публикации: 1999
оригинал статьи взят: FORTH.TXT
публикуется с разрешения автора.

Слово о Форте. Попытка формализации сути языка

1. Форт-система
Традиционная форт-система состоит из двух частей: исполняющая среда (её
часто назвают VFM - виртуальная форт-машина) и транслятор. Транслятор
занимается поглощением исходных текстов программ (и что-то при этом
производит, о чем позже), VFM занимается выполнением программного кода.

Однако две части могут работать и независимо. VFM без транслятора может
использоваться для выполнения скомпилированной ранее программы. Если эта
программа в процессе выполнения сама ничего не транслирует, то транслятор
ей не нужен и может отсутствовать. Многие прикладные программы на Форте
могут относиться к этому классу - использоваться без транслятора Форта,
только с VFM.

Транслятор без "родной" VFM используется например при целевой компиляции
- создании программы для другой платформы - когда целевая VFM просто не
может работать на инструментальной VFM. В этом случае целевой компилятор
(расширение стандартного транслятора Форта) просто создает код для целевой
платформы, выполнять его будет уже другая VFM на другом компьютере.

2. VFM

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

Абсолютно подавляющее большинство языков программирования используют
стек для передачи параметров и для хранения адресов возвратов из
подпрограмм (функций, процедур). Большинство делают это неявным образом
- программист не оперирует с понятием "стек". Но их исполняющие среды -
практически всегда используют стек. Это очень удобная конструкция для
хранения точек возврата при вызове многократно вложенных подпрограмм,
для передачи параметров и для хранения временных локальных переменных.

Но большинству языков хватает одного стека. Откуда взялись два стека в
Форте? Форт - представитель достаточно малочисленного класса процедурных
языков. Большинство языков оперирует с функциями - видом подпрограмм,
возвращающих одно значение в качестве результата. Вернуть несколько
значений функция может только либо записывая их в переменные, чьи адреса
передаются в качестве параметров, либо возвращая в качестве результата
указатель на структуру, содержащую несколько значений. При выходе из
функции данные на стеке, используемые при работе этой функцией, могут
быть безболезненно сняты со стека. И адрес возврата тоже. На стеке либо
ничего не возвращается (обычно результат функции при возврате хранится
в регистре процессора), либо возвращается известное число элементов -
один элемент. Процедура Форта может использовать аналогичные способы, но
может и вернуть несколько значений на том же стеке, на котором
передавались параметры (это плюс, а не минус, но плюсах позже). И если
при вызове процедуры помещать адрес возврата в стек над параметрами
процедуры (как делается в функциональных языках), то придется принимать
специальные меры, чтобы извлечь этот адрес из под возвращаемых значений
и еще и "сплотить" данные на стеке для ликвидации "дырки" от адреса
возврата. Можно придумать разные способы для решения этой проблемы, но
кто-то когда-то решил эту проблему с перемешиванием данных и адресов
возвратов на одном стеке просто не создавать - и так появились два стека:
один для параметров процедур и возвращаемых значений, другой для адресов
возврата. Это удобно и достаточно эффективно, поэтому широко применяется
в Форте.

Однако Форт мог бы существовать и с одним стеком, и с тремя, это
для языка не принципиально. К сожалению, в Форте утвердилась практика
использования второго стека (стека возвратов) не только по прямому
назначению автоматически при вызовах/возвратах из процедур, но и явных
ручных манипуляций с этим стеком для хранения безымянных локальных и
временных переменных и даже для ручного вмешательства в ход возвратов
из процедур (что нарушает принципы структурного программирования). С
другой стороны, форт не заставляет этим пользоваться, так что и бороться
с этим явлением не нужно. Я просто пытался показать, что наличие двух
стеков не является неотъемлемой частью Форта и его отличительной чертой.

Что же тогда является отличительной чертой виртуальной машины Форта?
По-моему, у неё нет отличительных черт, кроме того факта, что Форт
использует не функции, а процедуры. Внутренние же структуры - стеки,
способы компиляции и выполнения кода, и т.д. - зависят от конкретной
реализации. Других каких-либо особых черт, типа "всеобщей спискофикации"
Лиспа или "всеобщей объектизацией" Смолтолка с автоматическими сборщиками
мусора в Форт-машине нет. Форт-машина очень близка к обычным процессорам
и поэтому предельно проста в реализации.

3. Транслятор

Транслятор языка - носитель языка. Программист пишет на Форте,
транслятор Форта это письмо "понимает" и объясняет машине на её языке,
переводит (транслятор = переводчик). В трансляторе и заключена суть языка.
Транслятор воспринимает программу в соответствии с синтаксическими
правилами языка. В Форте эти правила упрощены до "физического предела"
упрощения. Синтаксис таков - слово1 слово2 слово3 и т.д. Слова (имена
процедур, запускаемых на выполнение) разделены пробелами. Если слово -
не имя процедуры, то оно пытается опознаться в качестве числового
литерала, если не удается - ошибка. Всё, больше никаких правил в Форте
нет. Транслятор не понимает ничего кроме слов, разделенных пробелами.

Все синтаксические конструкции, предлагаемые стандартным Фортом - такие
как определение процедур и переменных, операторы управления и т.п. -
обрабатываются не транслятором Форта, а самими запускаемыми словами,
которые могут временно "отбирать" у транслятора контроль над входным
потоком (текстом транслируемой программы), а также переключать транслятор
между двумя режимами его работы. Режим работы задает, чтО будет делать
транслятор с найденным словом - немедленно его выполнять (режим
интерпретации) или откладывать его выполнение на потом (режим компиляции).

Привычное для традиционных языков понятие "ключевое слово" в Форте
отстутсвует. Все слова равноправны за одним исключением - есть слова
"с признаком немедленного выполнения". Это слова, которые запускаются
на выполнение даже, если текущий режим транслятора - компиляция. Без
таких слов невозможно было бы управлять компиляцией, в том числе
возвращаться в режим интерпретации. В некоторых Фортах даже прекращение
трансляции производится не по факту достижения конца входного потока,
а по факту получения в конце потока слова с нулевой длиной. Это слово
у них есть в словаре, имеет признак немедленного выполнения и при
выполнении это слово прерывает трансляцию.

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

4. Страшилки для начинающих фортеров

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

ПРИМЕРЫ:
1) Если слова-процедуры не имеют входных параметров, то запись программы
на Форте выглядит так:

СЛОВО1 СЛОВО2 СЛОВО3
(линейная последовательность команд)

То же самое на Си выглядело бы так:

ФУНКЦИЯ1(); ФУНКЦИЯ2(); ФУНКЦИЯ3();
(линейная последовательность команд, только с избытком пунктуации)

2) Если СЛОВО3 требует для работы двух параметров, предварительно
вычисленных словами СЛОВО1 и СЛОВО2, каждое из которых параметров не
требует, то запись программы на Форте выглядит так:

СЛОВО1 СЛОВО2 СЛОВО3
(линейная последовательность команд, можно выполнять одну за другой)

То же самое на Си выглядело бы так:

ФУНКЦИЯ3(ФУНКЦИЯ1(),ФУНКЦИЯ2());
(префиксная запись: сначала записывается имя операции, потом её операнды;
перед тем как выполнить операцию ФУНКЦИЯ3, нужно забежать вперед и
выполнить ФУНКЦИЯ1 и ФУНКЦИЯ2.)

3) Возьмем конкретный пример, сложим 2 и 3.
На Форте:
2 3 +
(линейная последовательность команд: взяли 2, взяли 3, сложили)

На Си:
2+3
(инфиксная запись: имя операции между операндами, нужно забегать вперед
за вторым операндом, т.к. на момент получения "+" тройки еще нет).

4) Еще один конкретный пример - увеличим значение переменной N на 1.
На Форте:
N 1+!
(линейная последовательность команд: взяли переменную и инкрементировали,
"1+!" - это одна команда, такая же нелепая в записи как ++ в Си)

На Си:
N++
(точно также как и на Форте)

5) Ещё пример - увеличим значение переменной N на 5.
На Форте:
N @ 5 + N !
(линейная последовательность команд: взяли переменную (N), извлекли её
значение (@), взяли 5, прибавили к значению переменной (+), взяли
переменную (N) и записали туда полученное значение (!))

На Си:
N=N+5;
(взяли переменную, взяли "=", нужно присваивать зачение, какое значение?,
пока не ясно, отложим N и "=", пойдем дальше - опять N, дальше берем "+",
нужно проводить сложение, один операнд у нас уже готов, а где второй? идем
дальше и получаем 5. Предложение кончилось, проходим отложенные операции и
операнды в обратном порядке: прибавляем 5 к N и записываем результат в N).


Вопрос 1: где здесь стеки и обратная запись? Стек это что? Структура, в
которую "последним вошел, первым вышел", т.е. как магазин автомата
Калашникова, устройство для откладывания чего-то на потом и доставания
в обратном порядке. Где мы в наших примерах откладывали операнды и
операции и выполняли их потом в обратном порядке? Правильно, в примере 5
программе на Си. Именно стек используется транслятором Си для
разворачивания записи вида N=N+5 в последовательность машинных команд
"взять адрес N, извлечь значение, взять 5, сложить их, взять адрес N
и записать туда сумму", так как только такую линейную последовательность
команд может выполнить процессор. Т.е. программист, имея в виду эту
последовательность команд, записывает её на Си задом наперед, затем
транслятор Си, разворачивает её в прямую последовательность команд и
в этом виде она может быть выполнена процессором. Стек и обратная запись
налицо. В Форте во всех примерах последовательность одна и та же -
прямая, никакого забегания вперед для вычисления недостающих операндов.
Каждое слово работает уже с вычисленными ранее операндами. И именно как
временное хранилище вычисленных ранее операндов и используется стек в
Форте. В примере 3 на стеке Форта хранилось два операнда - 2 и 3, и слово
"+" брало их оттуда. В том же примере на Си при вычислениях на стеке
оказываются не только отложенные операнды, но и отложенная операция.
Как бы там ни было - результат один - линейный машинный код. При
выполнении этого кода стек может присутствовать, а может и отсутствовать
в обоих языках. Например, если операнды в Си с плавающей точкой, то
они оба при выполнении попадут на стек сопроцессора x87 и операции
над ними произведутся там в точности также, как над операндами Форта
на внутреннем стеке Форт-процессора или программной FVM. Это зависящие
от реализации малосущественные детали. Стеки имеют место во всех
современных языках программирования. Форт может быть "более стековый"
только за счет того, что у него есть много операций для манипуляции
этим стеком в явном виде, тогда как в других языках этот стек для
программиста доступен только как контейнер для параметров и локальных
переменных, с возможностью обращения к ним только по именам. В Форте
тоже можно использовать именованные локальные переменные, но можно
обходиться и без них.

Вопрос 2: какая система записи операций проще - у Си, или Форта? Если
не уверены, посмотрите еще раз примеры. В Си мы имеем смесь префиксной,
инфиксной и постфиксной записи. Кроме того, не обойтись без скобок и
разделителей выражений ";". Скобки группируют операнды и операции - т.е.
говорят транслятору "я не хочу выполнять операции по порядку, а хочу
задом наперед и вперемешку. Точка с запятой говорит транлятору что пора
остановится в забегании вперед и пора пойти по стеку отложенных операций
и операндов назад для разворачивания "обратной американской записи" в
линейную последовательность команд для компьютеров Фон-Неймановской
архитектуры. В Форте во всех примерах один и тот же примитивный порядок
записи - прямая последовательность действий. Скобки там не нужны -
если нужна другая последовательность выполнения команд, то в Форте
это можно записать в виде именно этой другой последовательности. Скобки в
Форте используются для комментирования (как и в этом предложении русского
языка). И ограничитель предложений не нужен, т.к. не нужно возвращаться
назад. На каждый момент времени всё что было "раньше" - уже выполнено и
возвращаться незачем. Точка с запятой используется в Форте только в
конце определения процедуры (кстати, это зря, можно тоже не ограничивать,
но об этом позже).

Система записи Форта может показаться сложной только на первый
поверхностный взгляд. На самом деле синтаксис Форта вы уже изучили -
слова и пробелы, и ничего больше. А вспомните сколько лет вы изучали
алгебраическую форму записи, на которой основан язык Си? Форт -
синтаксически самый простой язык. И если где-то встречаются сложности,
то дело не в Форт-идеологии, а в реализации конкретных слов. Набор
слов стандартного Форта действительно очень необычен и хаотичен. Причина
- хаотическое развитие на протяжении 30 лет. Неоптимальность языковых
конструкций - болезнь большинства языков, особенно таких старых как
Форт. Но Форт гибок, и вы можете не использовать те его средства,
которые вам не понравятся. Более того, вы можете СОЗДАТЬ те средства
языка, которые считаете нужным - примеры будут в этой статье.

Наверное я не снял страхи новичкам, а только усугубил их. Но я и не
обещал избавлять от страхов. Но вот что касается стека и синтаксиса -
надеюсь, расставил точки над i. Стеки есть везде, а синтаксис Форта
прямее всех прямых. Если по-польски это обратная запись, то это проблема
поляков или того, кто придумал это название. А у нас в Форте всё прямо.

5. Возможности языка

Часто можно быть свидетелем спора "в языке А есть возможность сделать
так, а в языке Б так не сделать". Из этого делают вывод что язык "А"
лучше. Более правильный вывод - язык А лучше, когда надо "сделать так".
Если в языке "Б" нет никакой возможности сделать "так" обычными средствами,
и нет возможности расширить язык "Б" "такими" средствами, то язык "А"
однозначно лучше языка "Б" для "таких" применений. Если же "Б" - язык
расширяемый, то "А" лучше настолько, насколько долго расширить "Б"
необходимыми средствами. Хотя "Б" может стать и лучше чем "А" в "таких"
применениях, если после расширения необходимыми средствами эти средства
оказались удобнее. Т.е. вывод может быть однозначным только если один
из сравниваемых языков не расширяем в "таком" направлении.

На деле программирующие программисты находят, что на большинстве языков
можно решать большинство задач, и выбор конкретного языка определяется
многими дополнительными факторами, не только на основании "может-не-может".
Часто особо выдающиеся свойства языка в какой-то конкретной сфере
(например, 100-процентная портируемость) приводит к недостаткам в других
(например, ради портируемости отказываются от эффективности). Языка,
лучше всех подходящих для всех существующих задач, не существует. Однако
расширяемые языки имеют преимущества - можно заполнять имеющиеся пробелы
возможностей.

Расширять возможности языка можно по-разному. Первый способ - написать
библиотеку на самом этом языке для реализации каких-либо новых
возможностей. То есть просто набор дополнительных функций, включаемых
в программу. Второй способ расширения - внешними модулями, которые могут
быть написаны на другом языке. Например, язык PHP расширяется модулями,
написанными на языке Си. Не только из-за того, что такие модули быстрее
работают, но главным образом из-за того, что в PHP отсутствуют прямые
интерфейсы с операционной системой и низкоуровневые средства. Главным
образом для гарантий портируемости. Нужно какое-либо отсутствующее
средство - пишут внешние модули на Си, которые на разных платформах
разные, но языковый интерфейс PHP с ними будет сделан одинаковым везде.
В данном случае язык PHP - расширяемый, а Си - расширитель. Такая схема
расширения принята в подавляющем большинстве современных языков. Так как
Си имеет особые привилегии в современных операционных системах: они сами
написаны на Си и поэтому лучше к нему приспособлены по программным
интерфейсам. Язык Си был разработан для разработки операционных систем,
поэтому имеет достаточно низкоуровневых средств. Всем этим его роль
"всеобщего расширителя" и объясняется. Трансляторы и виртуальные машины
многих языков также написаны на языке Си. Форт почти ровесник языка Си
(старше на 1-2 года) и является таким же низкоуровневым. Вплоть до наличия
встроенного языка ассемблера. Он может расширять сам себя, хотя для
связи с операционной системой вынужден использовать соглашения о связях,
принятые в Си - вызов функций операционной системы как функций языка Си.

Для Форта расширяемость - ключевая возможность. В стандартный Форт входят
в основном только те средства, которые использовались при создании его
транслятора, а поскольку транслятор примитивен, то и имеющиеся средства
того же уровня: арифметические операции, операции с памятью (в том числе
строками), операции управления ходом выполнения и файловый ввод/вывод.
В Си и Паскале набор тот же. В Форте еще есть готовые средства ведения
командного диалога в консоли, так как транслятор может работать в режиме
интерпретатора (как Лисп, Бейсик, Смоллтолк, ПостСкрипт, SQL, Perl и т.п.)
Всё остальное - расширения. Наличием или отсутствием необходимых
программисту расширений определяется ценность для него конкретной
Форт-системы. Но ценность самого Форта - просто в возможности его
расширения. Форт - один из немногих языков, трансляторы которого пишутся
на нем самом. Хотя FVM нередко пишут не только на Форте, но и на
ассемблере или Си. Есть даже реализации FVM на Java.

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

Синтаксические и управляющие конструкции языка - это средства определения
новых процедур, переменных, условные операторы if, операторы циклов while,
do, и т.д. Всё это в Форте доступно для замены или расширения. Заменять
оператор if врядли кому-то нужно в обычном программировании, но при целевой
компиляции на другую платформу в Форте заменяют этот оператор так, чтобы
он компилировал код для целевой платформы, кроме того в встроенных в Форт
ассемблерах тоже нередко делают команды if, которые являются макросами для
ассемблера. И добавлять конструкции не лишне. Например, в Форте изначально
отсутствуют средства объектно-ориентированного программирования, но их
может добавить в Форт любой Форт-программист, а не только разработчик
транслятора. Причем любую объектную модель, какую только сможет придумать.

6. Промежуточные итоги сказанного

Простейший синтаксис и соответствующий простейший транслятор - это
основная идея Форта. Тотальная расширяемость - это основная возможность
Форта. Такая возможность является следствием реализации такой идеи.
Стеки, словари, FVM и другие детали реализации - это следствия такого
подхода.

7. Место Форта в генеалогии языков

У Форта, насколько мне известно, нет прямого предка. Но есть близкий
старший родственник - Лисп. Возможно автор Форта никогда не программировал
на Лиспе, и может быть даже не знал о его существовании, но идеи в основу
языка положены те же - предельная простота. На первый взгляд языки совсем
не похожи. Синтаксически - Лисп-программы содержат больше скобок, чем
программы на любом другом языке, в Форте скобки лишь в комментариях.
Ядро Лиспа - везде списки, у Форта списки лишь в словарях. Но у Лиспа
почти такой же простой транслятор - всего один способ записи. И такая же
расширяемость. Идеи одни и те же, но совсем разные способы реализации.
Списки являются неотъемлемой частью идеологии Лиспа, его математической
и физической основой. Форт, увы, математическим образованием не блещет.

И есть у Форта и прямой потомок - язык ПостСкрипт. Он унаследовал его
лучшие черты - простоту синтаксиса и расширяемость. Это практически Форт,
но с другим набором слов, намного более логично спроектированный. Однако
разработчики сознательно не делали из ПостСкрипта универсальный язык.
Им требовался язык, рисующий образ страницы в принтерах. И, как известно,
они с этой задачей превосходно справились. Низкоуровневых средств в языке
ПостСкрипт нет, поэтому расширяется он только в "высокую" сторону - можно
определять новые графические и вычислительные процедуры на основе
имеющихся.

И относительно недавно появился у Форта и внук - язык PDF (Portable
Document Format), наследник ПостСкрипта. Похоже разработчики PDF о
Форте не слыхали, потому о некоторых полезных свойствах забыли. Язык
получился довольно сложным, лишь частично совместимый с ПостСкриптом
(есть трансляторы ПостСкрипта в PDF, написанные на ПостСкрипте!), но
благодаря маркетинговым усилиям Adobe интерпретатор PDF есть почти на
каждом компьютере в виде программы AcrobatReader.

Есть еще один Форт-подобный язык - это DSSP. Разработан он в России и
активно развивается. Авторы провели серьезный пересмотр форт-идей и
выдвинули свой уникальный принцип для DSSP: одному слову программы
соответствует одно слово кода.

Другие близкие родственники у Форта наверное есть, но мне неизвестны.

8. Зачем я это всё написал
Все эти записки не являются введением в Форт, не являются приманкой или
страшилкой для новичков в Форте, а у старых фортеров могут вызвать
раздражение и алергию. Какова цель изложения?

Я описал имеющееся положение дел вокруг Форта, не вдаваясь в детали.
Рассмотрел наиболее частые заблуждения. И достаточно подробно остановился
на том, что на мой взгляд является основной ценностью Форта - простейший
синтаксис (и всё что из этого следует). Зачем?

Затем чтобы привести в порядок прежде всего свои мысли, и заодно дать
вам обоснование некоторых моих технических решений при создании
трансляторов Форта, и чтобы не шокировать старых фортеров задуманным
мной реформированием Форта при реализации SPF4 (кто не знает, что такое
SPF, тому и необязательно :). Я не собираюсь ничего портить в Форте, я
хочу его еще упростить - убрать "шаманство", присущее программированию
на Форте, убрать мусор из базового словаря, но сохранить совместимость
путем реализации ANS FORTH 94 в виде расширения.

Этим мы сейчас и займемся.

9. План работ

Задача минимум - написать минимальный транслятор Форта, средств которого
будет достаточно для компиляции самого себя. "Просто минимальный
транслятор Форта" - это намного более простая задача, с неё мы и начнем.
А дальше видно будет. Вдруг у меня, как часто бывает, просто не хватит
времени дописать SPF4 до конца, а в следующем заходе появятся другие идеи,
как с SPF4 уже было раз пять... ;)

Писать Форт мы, конечно, будем на Форте.

10. Основной цикл транслятора
: Eval ( -- )
BEGIN
NextWord ?DUP
WHILE
TranslateWord
REPEAT DROP
;

Надеюсь, что даже не-фортерам здесь всё понятно. Цикл "взять слово",
"транслировать слово" продолжается до достижения конца входного потока.
Слова NextWord и TranslateWord в стандартном Форте отсутствуют, но все
фортеры знают, как их можно реализовать стандартными словами. Однако мы
временно об этом знании условно забудем.

Нестандартные слова я буду записывать с использованием строчных букв,
стандартные - только прописными.

Отсутствие параметров в реализации Eval объясняется наличием
понятий "текущий входной поток" и "текущий контекст трансляции".

Слово NextWord возвращает адрес строки и длину строки. Если достигнут
конец входного потока длина строки 0 и цикл WHILE завершится.

Если по ходу возникают ошибки - генерируется исключение (THROW),
прерывающее работу Eval.

11. Выборка слов (парсер)

Было бы легко читать файл с исходным текстом Форт-программы целиком в
память, как делает Си-транслятор, но в Форте есть обстоятельства, которые
заставляют относиться к тексту программы не как к сплошлому потоку, а как
разбитому на чанки. В Форте нет понятия "чанк", но мы его будем
использовать как обозначение порции текста программы, получаемой за одну
операцию чтения входного потока. Форт в отличие от Си, может работать в
режиме диалога с пользователем (программистом). В этом режиме программист
ожидает, что транслятор будет обрабатывать его ввод построчно, и сразу
после ввода строки давать результат, не ожидая окончания входного потока.
Кроме того, традиционно Форт может использовать в качестве входного потока
"блоки" - фрагменты программы размером 1 килобайт. Это используется для
переноса программ между компьютерами разного типа с различными файловыми
системами и вообще без файловой системы и операционной системы.

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

Входным потоком для транслятора Форта может быть текст программы,
поступающий из любого источника - блоков, файлов, клавиатуры, сокетов,
GUI и т.п. Для слова Eval это безразлично, оно имеет дело с уже
прочитанным в память чанком. Атрибуты этого чанка: адрес начала, длина
и указатель текущего слова - смещение относительно начала чанка. В Форте
адрес начала и длину возвращает слово SOURCE, а смещение находится в
переменной >IN.

: NextWord ( -- c-addr u ) SkipDelimiters ParseWord ;

SkipDelimiters пропускает пробелы (или "пробельные символы", к которым
может относиться TAB, CR, LF и т.п.) в текущей позиции >IN, до первого
непробельного символа, и устанавливает >IN на него.
: SkipDelimiters ( -- ) \ пропустить пробельные символы
BEGIN
OnDelimiter
WHILE
>IN 1+!
REPEAT
;

: OnDelimiter ( -- flag )
GetChar SWAP IsDelimiter AND
;

: GetChar ( -- char flag )
EndOfChunk
IF 0 FALSE
ELSE PeekChar TRUE THEN
;

: EndOfChunk ( -- flag )
>IN @ SOURCE NIP < 0= \ >IN не меньше, чем длина чанка
;

: CharAddr ( -- c-addr )
SOURCE DROP >IN @ +
;

: PeekChar ( -- char )
CharAddr C@ \ символ из текущего значения >IN
;

: IsDelimiter ( char -- flag )
BL 1+ <
;

ParseWord выбирает из строки непробельные символы до первого пробельного
и возвращает адрес и длину этой последовательности символов (слова) во
входной строке.
: ParseWord ( -- c-addr u )
CharAddr >IN @
SkipWord
>IN @ SWAP -
;

: SkipWord ( -- ) \ пропустить непробельные символы
BEGIN
OnNotDelimiter
WHILE
>IN 1+!
REPEAT
;

: OnNotDelimiter ( -- flag )
GetChar SWAP IsDelimiter 0= AND
;

Это полная реализация парсера Форта (NextWord) - 11 простейших процедур
общим размером около 50 строк. Её уже можно оттранслировать стандартным
Фортом. См. spf4_parser.f от "parser begin" до "parser end".

Слово
: TEST ( -- )
BEGIN
NextWord ?DUP
WHILE
TYPE SPACE
REPEAT DROP
;

при выполнении

TEST AAA BBB CCC

выдаст результат:

AAA BBB CCC

Тем не менее наша реализация парсера NextWord оказалась громоздкой по
сравнению с традиционной для Форта реализацией слова WORD (стандартное
слово для извлечения слова из чанка). Очень часто WORD реализуют в
Форте в виде одной процедуры на ассемблере. Но принятой здесь
реализацией мы убили много зайцев: во-первых, она намного понятнее, чем
ассемблерная; во-вторых, её можно скомпилировать в любой версии Форта
на любом процессоре; в-третьих, мы получили аж 10 дополнительных слов,
которые нам пригодятся в других программах - целая библиотека для
реализации других парсеров; в-четвертых, наша реализация не использует
дополнительных буферов для хранения слов, что удобнее в многопоточной
форт-системе.

Примечание: для трансляции spf4_parser.f на SwiftForth и Win32for
пришлось сначала определить слово 1+!
: 1+! DUP @ 1+ SWAP ! ;
т.к. это слово в этих фортах отсутствует.

12. Поиск слов (словари)

Для описанного выше цикла транслятора не хватает реализации слова
TranslateWord, которое должно проводить поиск слов в словаре и выполнять
либо компилировать слово. Если поиск завершился неудачей - попытаться
использовать слово как литерал.

Процедуры форта - слова - хранятся в линейных списках - словарях. Слова
при определении добавляются в конец списка, и поиск начинается с конца
списка, чтобы разрешить переопределение слов. Словарей может быть
несколько, и поиск слова транслятором производится в нескольких словарях.
Текущий набор словарей, подлежащих просмотру, и порядок поиска задается
в специальном стеке словарей. Этот стек называют контекстом.

Стандартное слово Форта для поиска в контексте - FIND, однако оно не
совсем удобно, т.к. использует строку со счетчиком в качестве параметра,
и возвращаемых им значений для некоторых применений недостаточно. Слово
SEARCH-WORDLIST ищет только в одном словаре, и тоже возвращает неполный
набор результатов, поэтому мы реализуем свой набор слов для поиска.

Словари Форта (vocabulary) фактически являются связанными списками пар
ключ-значение и являются близкими аналогами ассоциативных массивов,
словарей (dictionary) и т.п. структур, имеющихся во многих других языках
программирования. Точнее почти во всех языках, так как без такой удобной
структуры обойтись сложно. Из широко известных языков словари или их
другие названия есть в Perl, PHP, PostScript, Smalltalk, Lisp и т.д.),
так что распространенное мнение об особой уникальности словарей Форта на
мой взгляд неверно. Хотя есть отличия в реализации. Например, флаги у
элементов словаря встречаются в других языках нечасто (я знаю только в
PostScript), с другой стороны эти флаги можно "эмулировать" и в других
языках.

В соответствии с ANS Forth94, словари официально теперь называются
WORDLIST - список слов.

Словарь можно рассматривать как частный случай более простой структуры -
списка. Каждый элемент списка имеет некое содержимое и указатель на
следующий элемент. В случае словаря содержимым элемента списка будет
пара указателей - на имя и значение элемента словаря. Если элемент словаря
- процедура, то имя - это имя процедуры, а значение - адрес кода процедуры
(не обязательно реальный адрес, а то что в стандарте называется execution
token, т.е. некая ссылка, которую может выполнить слово EXECUTE).

Пусть слово Where ищет элемент списка по его имени в словарях контекста и
возвращает идентификатор словаря wid и указатель на элемент списка item.
По item можно будет получить имя элемента словом Name, значение элемента
словом Value, флаги элемента словом Flags, и "еще что-нибудь хорошее",
если нам когда-нибудь понадобится, будет несложно добавить в такой объект.
( Where и другие зависящие от конкретной реализации словарей слова 
см. spf4_trans_dep.f )

: Where ( addr u -- wid item true | addr u false )
...
;
: IsImmediate ( item -- flag )
ItemFlags &Immediate AND
;
: Interpreting ( -- flag )
STATE @ 0=
;
: AsWord ( item -- ... )
DUP IsImmediate Interpreting OR
IF ExecuteWord ELSE CompileWord THEN
;
: TranslateWord ( addr u -- ... )
Where IF AsWord ELSE AsLiteral THEN
;


12.1. Конкретная реализация словарей

Традиционно в Форт-системах все словари физически хранятся вместе в
одном непрерывном участке памяти. Словарные статьи разных словарей при
этом могут чередоваться. В некоторых Форт-системах возможно отдельное
хранение заголовков словарных статей, тел процедур и области данных.
Мы также реализуем возможность раздельного хранения. Это позволит удобнее
создавать временные словари для локальных переменных, делать подключаемые
двоичные образы словарей и, возможно, реализовать для словарей различные
"протоколы" доступа к спискам слов и телам словарных статей, что позволит
прозрачно работать со словарями в устройствах хранения другого типа,
нежели ОЗУ (сеть, registry, flash и т.п.).

В Форте есть слово для создания неименованных словарей - WORDLIST, которое
создает пустой словарь и возвращает его идентификатор wid. В дальнейшем
поиск в словаре по имени выполняется словом SEARCH-WORDLIST, которое в
случае успеха возвращает выполнимый токен xt и флаг наличия признака
IMMEDIATE. Для создания именованных словарных статей служит слово CREATE,
которое берет имя слова из входного потока и создает словарную статью в
текущем словаре компиляции. В некоторых форт-системах есть слово HEADER,
используемое при реализации слова CREATE, но не создающее никакого кода
в словарной статье. А слово HEADER использует слова, явно модифицирующие
словарь. Эти слова везде разные (+WORD в SPF, "HEADER в Win32for,
WID-HEADER в SwiftForth). Принцип один и тот же - для операции необходимо
имя слова и wid словаря. Тело словарной статьи предполагается строить
уже после создания заголовка. Однако есть стандартное слово :NONAME для
создания неименованного телапроцедуры - возвращается xt.

Введем более "прозрачный" набор более низкоуровневых слов, который
позволит реализовать упомянутые Форт-слова для создания слов в словаре
и для их поиска, и заодно даст набор слов для более удобной работы со
словарем как ассоциативным массивом со строками в качестве ключей.
( коды ошибок не возвращаются, в случае ошибок - THROW )

0
CELL -- iWid \ указатель на словарь, где создается этот элемент
CELL -- iLink \ указатель на предыдущий элемент
\ один из iWid и iLink избыточный, но так быстрее будет
CELL -- iName \ указатель на имя
CELL -- iValue \ указатель на значение
CELL -- iFlags \ флаги элемента (immediate, executable, etc)
CREATE /Item

: NewValue ( -- value )
\ создать новый объект без имени, без типа, во временном хранилище
;
: NewItem ( wid -- item )
\ создать пустой элемент словаря
;
: Value! ( value item -- )
iValue !
;
: Flags! ( flags item -- )
iFlags !
;
: Name! ( name item -- )
iName!
;
: InsertValue ( value wid -- item )
\ прикрепить объект к словарю, вернуть полученный элемент словаря
NewItem SWAP OVER SetItemValue
;
: Def ( item addr u -- )
\ дать имя элементу словаря
S>C SWAP Name!
;
: CreateItem ( addr u value wid -- )
\ сохранить объект value в словаре wid под именем addr u
InsertValue Def
;
: DeleteItem ( item -- )
;
: GetItem ( addr u wid -- item )
;



За это сообщение автора mOleg поблагодарили - 2: Majestio, vikt
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

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


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

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


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

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