Интерпретатор

Перейти вниз

Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 12:44 pm

Каждый раз, когда речь заходит о "попробовать новый язык", хочется иметь его интерпретатор. В нашем случае, как говорят бывалые фортеры, первое, что делает новичок, пишет свой FORTH-интерпретатор...
Это не просто, а очень просто - см. "Работу над ошибками" - ТЕМА #30. Но...


Последний раз редактировалось: Gudleifr (Ср Дек 06, 2017 1:00 pm), всего редактировалось 1 раз(а)
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 12:47 pm

НЕОЖИДАННОСТЬ ПЕРВАЯ. ИНТЕРПРЕТАТОР FORTH - САМ FORTH

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

Казалось бы столь простой механизм можно было бы записать раз и навсегда в виде красивой блок-схемы и высечь в камне в назидание потомкам...

Ан нет, эта простейшая связка операций
1. считать еще кусочек ввода (назову процедуру EXCEPT, тут фортеры расходятся);
2. считать из ввода слово (процедура WORD);
3. поискать слово в словаре команд (FIND);
4. если это не команда, то, может, это литерал одного из поддерживаемых типов (NUMBER);

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

Но, ведь, команду мало считать, ее нужно и выполнить... Тут все совсем просто. Т.к. никаких параметров у команд нет, то выполнить ее - значит, просто передать управление по адресу, найденному в словаре.
И все.
Вот вам и весь FORTH...
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 12:49 pm

НЕОЖИДАННОСТЬ ВТОРАЯ. ИНТЕРПРЕТАТОР FORTH - КОМПИЛЯТОР FORTH

Конечно, если бы FORTH умел только сам себе "с пониманием кивать", то он был бы бесполезен. Постулируется возможность создать на его основе практически любой проблемно-ориентированный язык.
Как?
Помните, я писал, что FORTH почти ничего не умеет, кроме самоинтерпретации?
Теперь речь об этом "почти". Оно состоит в возможности создавать на основе старых команд новые. Ввиду простоты языка это выглядит, как считывание целого предложения из нескольких слов и обозначение его одним словом.
***

Тут возникает вопрос: как быть, если исходного набора команд не хватает для определения новой? Допустим, нет изначально команды извлечения квадратного корня, как определить команду решения квадратного уравнения?

Возможны два решения:
1. Заранее заложить в исходный интерпретатор все нужные элементарные команды. Это часто удобно, но иногда невозможно заранее предусмотреть все возможные варианты.
2. Добавить возможность создавать новые команды не только из других, но и непосредственно в машинных кодах. Самое приятное: если вы создавали свой интерпретатор не на языке высокого уровня, реализовывать-то уже почти ничего не надо - все необходимые для этого команды уже входят в вашу программу.
***

Вернемся к тонкой разнице между интерпретацией и компиляцией.
При интерпретации мы просто исполняли команды одну за другой. А при компиляции? Оказывается, достаточно так же одну за другой брать команды, но не исполнять их, а записывать найденные адреса в "код" новой команды. Т.е. все наши EXCEPT, WORD, FIND и NUMBER остаются, где были, а разница только в том, что вместо "исполнить" вписано "сохранить".
FORTH-интерпретатор и FORTH-компилятор, это одна и та же программа с ма-а-аленьким условным оператором где-то внутри.
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 12:55 pm

НЕОЖИДАННОСТЬ ТРЕТЬЯ. ОДНОГО ИНТЕРПРЕТАТОРА МАЛО

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

"Зеркальное" отражение ситуации - компилирование составной команды: т.е. компилируется не один код команды, а код с довеском - какими-то нужными ему данными. Работает так же - управление передается команде, а она сама вытаскивает из кода нужные ей параметры.
Ни интерпретатор, ни "исполнятор" команд не знают, что имеют дело с чем-то необычным, они просто считывают команду/адрес и исполняют ее, а то, что исполняемый код продолжит читать дальше - не их проблема.
***

Составим для примера табличку обычных для FORTH конструкций, не сводящихся к обычной интерпретации-компиляции:

КонструкцияКем читается из потокаКем исполняется из кода
Обычная командаинтерпретаторсама
Ветвление/циклинтерпретаторкоманда (без)условного перехода
Числовой литералинтерпретаторкоманда литерала
Строковый литералоборот-литералкоманда литерала
Имя определяемой командысоздатель командне исполнимо, нужно только для поиска команды
Команда, нуждающаяся в принудительной компиляциипринудительный компиляторсама

Т.е., разрешив обороты и составные команды, мы открыли ящик Пандоры - необычныхе слова начали плодится, как тараканы.
***

Но, если появления новых слов-интерпретаторов неизбежно, то, может, наличие одного главного, это, вообще - лишь частный граничный случай? По крайней мере, поскольку я настаиваю на развитии всякого FORTH от "просто интерпретатора самого себя" до "проблемно-ориентированного языка", что странного в том, что он начнет с одним интерпретатором, а закончит с другим.
Например, мой FOBOS начинает свою работу с определения необходимых команд, считывая их из текстового файла вполне традиционным способом. Затем, когда Windows-пример готов к работе, создается окно и начинается чтение "команд" из совершенно другого источника - очереди сообщений.
***

Так что, сильно подозреваю, что любая уважающая себя FORTH-система должна иметь два интерпретатора - стартовый и рабочий.
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 12:59 pm

ОЖИДАННОСТЬ ПЕРВАЯ. КОМПИЛЯТОР FORTH ВМЕСТО ИНТЕРПРЕТАТОРА

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

Так мы, действительно, придем к "еще одному компилятору", все своеобразие которого будет базироваться на том, что он "транслирует с языка FORTH". Что о нем можно сказать:
1. Он очень прост. Вся сложность программы создается программистом. Вплоть до возможного создания "по FORTH-привычке" промежуточного языка для облегчения записи решения задачи.
2. Результат компиляции все еще будет содержать код стартового интерпретатора, который для программы будет лишним балластом. Как и код тех довесков к интерпретатору, которые нам понадобились для удобства пользованием нетривиальными программными конструкциями. И, заодно, вместе с интерпретатором, становятся избыточными и все имена слов.
3. Компактность и быстродействие. Так считают многие фортеры. И, даже, не обращают внимания на то, что эти требования взаимоисключающие.
Чем они это мотивируют? Тем, что подпрограмма заменяется в коде верхнего уровня одним словом, нет ни полной ассемблерной команды вызова подпрограммы, ни загрузки в стек параметров, ни очистки стека по возвращении. Экономия и места, и времени, не правда ли?
Не совсем, ведь процедуры передачи управления от одной скомпилированной программы к другой никуда не делись: либо они компилируются где-то рядом, в начале и конце каждой команды, либо в отдельное место интерпретатора, и теряется меньше места, но больше времени... И, что еще хуже, т.к. передачи параметров нет, приходится использовать специальные команды для размещения данных там, где другие команды их смогут достать. Это еще потери места и времени.
Да и странно было бы получить язык с рекордными характеристиками, не прикладывая для этого никаких усилий.
С другой строны, если FORTH используется только для компиляции, возможно прицепить к нему оптимизатор...
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 1:00 pm

ОЖИДАННОСТЬ ВТОРАЯ. ВИРТУАЛЬНАЯ МАШИНА

Другая крайность - считать FORTH полноценной виртуальной машиной, сравнивая его с "обычными" интерпретаторами. К сожалению, для превращения FORTH в такой интерпретатор, надо столько всего добавить, что проще сразу решить задачу, для которой предназначался бы интерпретатор.
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 1:02 pm

ОТКУДА И КУДА

Какие источники команд-слов возможны в принципе (потом мы их пересмотрим/отсортируем)?
1. строка, введенная с консоли;
2. блок, строки, считанные из явно указанного файла;
3. строка, считанная из файла, подменяющего стандартный поток ввода;
4. строка, программно сформированная в каком-либо буфере;
5. искусственно сформированное слово.

Из широко применяемых нюансов надо упомянуть разный способ обращения с отдельным словом:
- поиск его в словаре;
- поиск слова в специальных таблицах;
- распознавание слова, как представления числа (или символьного литерала);
- преобразование слова перед его поиском;
- разбиение слова на отдельные фрагменты и обращение с каждым, как с отдельным словом.

Реализовать каждый из вариантов достаточно просто, но "серебряной пули" нет. Более того, попытка унифицировать обработку случаев (1-3) породила избыточное количество переменных, которые приходится проанализировать, чтобы понять, откуда надо брать следующее слово (особенно, если анализируемый поток вдруг иссякает).
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 1:15 pm

ЦИКЛ УПРАВЛЕНИЯ



Чем отличается программа откомпилированная от программы интерпретируемой? Допустим, и та, и другая состоят из процедур a1, a2... aN. В случае откомпилированной программы они все представлены в ее коде. Там же жестко прошита последовательность их вызова. Например, сначала выполняем a1, затем a2-a5, затем - в зависимости от результата вычислений - a6 или a7, затем a8 и т.д.
В случае интерпретируемой программы, код этих процедур представлен в самом интерпретаторе, а в программе содержаться только их имена и параметры. Т.е. некоторая процедура интерпретатора (назовем ее Циклом Управления) выбирает одно за другим имена из программы, ищет в интерпретаторе их код исполняет его. Один прогон Цикла Управления - исполнение одной процедуры.
Таким интерпретатором изначально был и FORTH. Все его отличие состояло в том, что хранилище кодов процедур могло пополнятся в процессе работы. Правда речь шла, в основном, не о пополнении библиотеки исполняемых кодов, а о запоминании некоторых "макросов", каждый из которых создавался как приписывание некому новому имени, допустим, b1, некой последовательности из уже понятных интерпретатору процедур a1... aM.
Цикл Управления по-прежнему при каждом прогоне исполнял одну процедуру, но мог брать ее не только из программы, но и из своей библиотеки "макросов". Рассмотрим, например, условную FORTH-программу:

: ЧАЙНИК НАЛИТЬ ;
: ПЛИТА ПОСТАВИТЬ ВКЛЮЧИТЬ ;
: КИПЯТИТЬ ЖДАТЬ ВЫКЛЮЧИТЬ СНЯТЬ ;
: ЧАЙ ЧАЙНИК ПЛИТА КИПЯТИТЬ ;
ЧАЙ ПИТЬ

Все предложения вида ": ... ;" нужны только для того, чтобы создать "макросы" (далее будем называть их, как принято в FORTH - словами) ЧАЙ, ЧАЙННИК, ПЛИТА, КИПЯТИТЬ. (Мы считаем, что остальные слова FORTH известны). Начнем с исполнения слова ЧАЙ: Цикл Управления считывает его из программы и находит его уже скомпилированное определение. Т.к. оно найдено, то Цикл Управления на время "забывает" о том, что он читал программу и начинает читать "код" слова ЧАЙ. При следующем прогоне он считывает слово ЧАЙНИК (это уже легче, т.к. он читает не имя из символьной строки - текста программы, а из скомпилированного кода, где адреса слов идут одно за другим. На следующем прогоне он углубляется еще на один уровень, читая слово НАЛИТЬ, которое, наконец, может выполнить непосредственно. Выполняет и возвращается назад к определению ЧАЙНИК. Т.к. оно кончилось, "вспоминает", что читал определение ЧАЙ и на следующем прогоне будет читать ПЛИТА. Так, по одному слову за прогон, Цикл Управления дойдет, в конце концов до конца определения ЧАЙ и опять вернется к программе - уже к чтению слова ПИТЬ.
Прежде чем начать разговор о более современных FORTH-системах, попробуем ввести некоторые термины:

- Внешнее управление - наличие какого-то "управлятора" (в нашем случае Цикла Управления), который может, пользуясь некоторыми данными (например, текстом программы), управлять последовательностью исполнения кода, хранящегося в системе, как набор процедур.
- Внутреннее управление - наличие какого-то предварительного связывания исполняемого кода для того, чтобы было заранее ясно какая процедура вслед за какой будет исполняться. Так делают все компиляторы. Поэтому скомпилированные программы исполняются сами, не нуждаясь в добавлении к ним каких-то управляторов-интерпретаторов.
- Шитый код - способ хранения в памяти откомпилированных слов (для избежания поиска уже считанных и распознанных имен слов). Шитый код похож на байт-код некоторых систем программирования основанных на использовании виртуальной машины (например Perl или Java), но не совсем - он обычно проще и может генерироваться "на лету".
- Кодовые слова - слова, которые изначально "понятны" интерпретатору, потому, что написаны в кодах процессора (наши изначальные a1... aN).
- Шитые слова - слова-макросы определенные, как последовательности других слов (b1...).
- Поток - текст программы - последовательность слов, которые нужно прочесть, распознать и выполнить.

Как разные слова "добираются" до кода:
- Обычная откомпилированная программа - внутреннее управление. Поток и шитый код отсутствуют.
- Программа для виртуальной машины - внешнее управление (управлятор - виртуальная машина) на основе байт-кода (по сути, шитого кода) "словами". Потока нет.
- Интерпретатор - внешнее управление на основе потока. Шитого кода нет.
- FORTH по Муру - внешнее управление на основе потока и шитого кода.
- Более современные Forh-системы - внешнее управление на основе потока и внутреннее на основе шитого кода.

Поясним последний вариант. Из нашего рассмотрения Цикла Управления FORTH выходило, что он только и делал, что скакал с уровня на уровень и искал следующее слово. Однако, обычная простота шитого кода делает эти процедуры очень простыми, не на много сложнее процессорных инструкций call и ret, обеспечивающих внутреннее управление откомпилированных программ. И практически все современные FORTH-системы добавляют к своему шитому коду эти маленькие "довески", превращающие его в исполяемый код процессора. Таким образом внешнее управление для шитого кода более не является необходимым.
Вот и получилось, что современные FORTH-системы оказались лишены какого-либо явно выраженного управлятора и Цикл Управления, вокруг которого они раньше лепились, занял свое скромное место в распознавателе входного потока.
Благодаря этому стало возможным еще одно упрощение. Изначально читать поток приходилось по-разному в двух местах FORTH-системы: в Цикле Управления и в словах, желающих прочесть что-то из потока самостоятельно. После того, как Цикл Управления оказался упрятан в обычное слово, он читает из потока на общих основаниях. Другим следствием отказа от внешнего Цикла Управления была потеря "особого значения" процедурами распознавания потока, исполнения и/или компиляции распознанных слов. Теперь они стали "обычными" словами. Конечно, это привело бы к сильному усложнению изготовления минимального FORTH при набивании его в кодах на голом железе, но сейчас, когда мы имеем возможность писать его в текстовом редакторе для ассемблирования/компиляции, это не имеет значения.
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 1:35 pm

Для дальнейших рассуждений нам необходимо как-то классифицировать код:
- q-code - описание кода на псевдокоде или человеческом языке;
- f-code - код записанный на языке программирования. В случае FORTH это язык входного потока;
- l-code - откомпилированный, но пока не привязанный к коду программы ссылками фрагмент. Например, хранящийся в обычном объектном файле. В случае FORTH - хранящийся в словах, создающих другие слова;
- a-code - код, хранящий в себе адрес возврата. Например, обычная откомпилированная программа, завершающаяся вызовом функции exit(), т.к. нас обычно не интересует, как последняя работает. Более простой вариант - код, завершающийся переходом на конкретный адрес;
- n-code - код, возвращающий управление по адресу, хранящемуся "где-то рядом", например в оговоренном заранее регистре или прописанном в следующей ячейке;
- r-code - код, возвращающий управление обычным для процессора способом. Обычно, по адресу в стеке возвратов.

Рассмотрим фрагменты откомпилированного кода для перечисленных выше систем:
- обычная откомпилированная программа - процедуры в r-code;
- программы в байт-коде и программа для FORTH по Муру - a-code т.к. все процедуры/слова возвращают управление в одну и ту же точку Цикла Управления;
- FORTH с подпрограммным шитым кодом - r-code. Шитые слова - просто набор следующих друг за другом команд call c завершающей конструкцию командой ret.
- FORTH с прямым шитым кодом: кодовые слова - n-code (адрес возврата хранится в регистре-курсоре); фрагмент, обеспечивающий переход по курсору обозначается как NEXT; шитые слова (r-code) - начинаются с n-code (CALL), запоминающего курсор в стеке возврата, затем идут адреса слов, последнее слово (EXIT) обеспечивает восстановление курсора;
- FORTH с косвенным шитым кодом: в нем кодовые фрагменты вынесены из шитого кода, в котором остаются только адреса: первый адрес - n-code фрагмента CALL (для кодовых слов - исполняемого r-code слова), последний - n-code EXIT. Существуют многочисленные варианты косвенного (а иногда и прямого) кода, позволяющие хранить не честные адреса слов, а упакованные, свернутые, индексы и т.д., но с точки зрения передачи управления это не важно. Просто пара-другая лишних операций.

Из этой перепутаницы можно сделать следующие выводы:
- Как бы не крутил фортер с видом кода, без r-code (т.е. без стека возвратов) не обойтись. Он необходим для обеспечения вложенных (и рекурсивных вызовов) вызовов процедур.
- Так как вариантов реализации много, значит, нет ни одного удачного. Т.о. начинающий фортер для реализации своего FORTH может свободно выбрать тот вариант шитого кода, который ему приглянулся и/или показался наиболее понятным. Как сказал Дейкстра: "Кроме того, машина, о которой говорится в статье [идеальный FORTH], до такой степени неэффективна, что каждая реализация фактического алгоритмического языка, вероятно, может рассматриваться как ее оптимизация, возможная благодаря некоторым ограничениям языка".
- Косвенный шитый код отличается от других тем, что позволяет хранить весь шитый код в сегменте данных, отдельно от кода. Это делает программирование проще - не надо разбираться в тонкостях организации памяти операционной системы и можно писать даже на языках высокого уровня.
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 1:37 pm

ПРИМЕР. КАК ЭТО РАБОТАЕТ В FOBOS?

И в DOS и в Win32 версиях я использовал прямой шитый код. Почему? Мне показалось, да и по сей день кажется, что избрав "средний" путь, я получаю максимальную гибкость кода, не особенно обрезая возможность отклонения в ту или другую сторону.
Разница DOS и Win32 версий только в двух моментах: использовании стека возвратов и размере ячейки. С ячейкой все понятно, DOS версия была 16-разрядной, а Win32 - 32-разрядная (надо только не забывать, что процессор использует, в зависимости от разрядности, совершенно разные системы адресации операндов в командах).
Как известно, Intel-процессоры 86-й серии имеют один стековый сегмент, но две точки входа в него, что дает возможность организации двух стеков - растущих с разных концов сегмента к середине, и в разной степени поддерживаемых аппаратно.
Обычный стек, на вершину которого указывает регистр SP, поддерживает операции push и pop, используется в командах call и ret... Второй стек беднее - на его вершину указывает регистр BP и... все.
Если писать в подпрограммном шитом коде, то выбирать не из чего, стек возвратов - SP, стек данных - BP (как и положено "обычной" программе). Для DOS FOBOS я принял такое же соглашение (насколько помню, чтобы сэкономить пару команд в процедурах запуска шитого кода и выхода из него), а в Win32 FOBOS - обратное (так удобнее вызывать функции Win API, которые ждут, что их параметры будут расположены в стеке SP).
Получилось вот так (в WIN-версии).
Процедура перехода от одного кодового слова к следующему (NEXT):

LODSD
JMP EAX

(SI - регистр, где хранится курсор шитого кода).
Процедура перехода на шитый код (CALL):

MOV [EBP], ESI
ADD EBP, 4
MOV ESI, START
NEXT

Кодовое слово, завершающее шитый код (EXIT):

SUB EBP, 4
MOV ESI, [EBP]
NEXT

Теперь видно, что r-code фрагменты при прямом шитом коде заключены в n-code оболочки. И слово, по необходимости, само сохраняет курсор шитого кода на стеке возвратов. В принципе, при применении подпрограммного и/или прямого шитого коде, FORTH не может накладывать никаких ограничений на формат слова. Последнее может интерпретировать свое содержимое любым способом, лишь бы при выходе оно ничего не испортило. Например оно может скрывать в себе вызовы какого-либо API с самыми замысловатыми соглашениями о вызовах.
Так, например, смешно выглядят заявления о модных FORTH-системах, поддерживающих, например, OpenGl. А чего его поддерживать-то? Это просто набор функций. Если наш FORTH умеет вызывать функции, он умеет и "поддерживать OpenGl". А заодно и DirесtX, и кучу других библиотек...
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 1:41 pm

Раньше я уже упоминал об основных краеугольнух FORTH-"камнях": EXPECT, WORD, FIND, NUMBER... Их "краеугольность" следует вовсе не из особой FORTH-важности, а из необходимости писания и отладки этих, достаточно больших, кусков в кодах. Написаны они, значит, FORTH уже, по-сути, работает. Дальше можно писать по-FORTH-овски... Недаром Цикл Управления "по Муру" завязан именно на эти куски (см. рисунок в начале).
***

А как связаны эти куски с "общей функциональностью"? Или, если угодно, можно ли, все-таки, формализовать FORTH "сверху"?
Выделим четыре основных класса структур данных: ПОТОК, ЗНАЧЕНИЕ, СТЕК и СЛОВАРЬ. Обратите внимание: это не "экземпляры" - их в FORTH-системе может быть много, разных типов.
ПОТОК - связь FORTH с внешним миром (одним концом - в FORTH-систему, другим - в систему операционную). Причем, я склонен думать, что в общем случае ПОТОК ведет "в обе стороны". Например, FORTH-вывод "по Муру", сводится к механизмам, поддерживающим ПОТОК (способ сообщить пользователю, что в ПОТОК нужно что-то вввести). Назовем процедуру вывода в ПОТОК (точнее - управления ПОТОКОМ) ОК.
Слово EXPECT (с необходимыми управляющими конструкциями) в общем случае занимается поддержанием потока - созданием иллюзии его непрерывности. Сборкой бесконечной текстовой строки общего вида из машинно-зависимых данных.
Все три оставшихся кодовых фрагмента (WORD, FIND и NUMBER) занимаются анализом потока (до получения в итоге одного-единственного ЗНАЧЕНИЯ). Это важно - аморфность в понимании того, как трактовать считанный из ПОТОКА фрагмент, недопустима. Никаких пустопорожних "интерпретируем-компилирем".
WORD выделяет законченный фрагмент - "символ" из потока. FIND ищет символ в СЛОВАРЕ. NUMBER пытается вернуться к распознаванию символа, как некоего регулярного выражения. В принципе, возможны самые разные реализации, с многоуровневым распознаванием, обработкой отказов, переключением ПОТОКОВ и т.д. Назовем все это процедурой СИМВОЛ - получение из потока ЗНАЧЕНИЯ.
На этом, как бы, и наметки Мура, и FORTH-теория заканчивается... и начинается описание манипуляций со стеком.
Рассмотрим СТЕК и мы. Только это будет "не тот" стек. Не статический объект для обмена данными между процедурами, а стек для временного хранения введенных ЗНАЧЕНИЙ (именно так его описывал Дейкстра). Это почти одно и то же, но разница, все-таки, есть. В первую очередь тем, что нас тут совершенно не интересует "обмен данными между словами-процедурами". Можно без труда вообразить проблемно-ориентированный язык без обмена данными через стек (например, Мур описал такой язык для работы с базой данных).
Итак, то ЗНАЧЕНИЕ, которое мы вытащили из ПОТОКА, записывается на СТЕК. В той или иной форме. Например, стандартно ЗНАЧЕНИЕМ может быть число (от NUMBER) или адрес слова (от FIND). В первом случае оно просто помещается на СТЕК, во втором - стек заполняет (или чистит) вызванное слово. В модели Дейкстры на стек нормально помещались адреса слов, чтобы выполниться позднее. Назовем это процедурой ВЫПОЛНИТЬ. Заметим, что в некоторых случаях она может поместить ЗНАЧЕНИЕ не в СТЕК, а напрямую в СЛОВАРЬ, например, стадартно это происходит, когда FORTH-система находиться в состоянии компиляции.
Наконец, нужна процедура КОМПИЛИРОВАТЬ, чтобы переместить то, что накопилось на стеке, в СЛОВАРЬ. Например, так поступают компилирующие слова.
Остаются "только" процедура СЛЕДУЮЩИЙ для переустановки курсора исполнения в СЛОВАРЕ (переходе от исполнения одного слова к исполнению другого) и процедуры "преобразования типов" (используемых при переносе из одной структуры данных/управления в другую)...

avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 1:45 pm

ПРИМЕР. КАК ЭТО РАБОТАЕТ В FOBOS

Имеется две вложенных FORTH-машины (на момент написания этого фрагмента внутренняя - перебора Win-сообщений - еще на машину похожа очень мало). Внешняя:
- ПОТОК - текстовый файл (3 уровень FORTH-системы, FORTH-ассемблер, Win-примеры, в т.ч. внутренняя машина) грузится сразу в память целиком (макс. длина 128К). EXPECT не требуется.
- СИМВОЛ - простой цикл вызова WORD, затем FIND, при неудаче FIND - NUMBER. Ошибка NUMBER вызывает останов машины и выдачу сообщения о ненайденном слове.
- ОК - для сообщения об ошибке (нераспознании слова) требуется MessageBox. Т.е. мы вынуждены аппелировать к механизмам Windows раньше, чем получимся получать к ним "правильный" доступ.
- ЗНАЧЕНИЕ - адрес слова или числовое значение - обрабатывается стандартно: слово исполняется/компилируется, число компилируется в оборот "выдача числа" или помещается на стек.
- ВЫПОЛНИТЬ является частью СИМВОЛ - проверить STATE и IMMEDIATE и выполнить/компилировать.
- СТЕКА два - для целых (в т.ч. адресов) и вещественных чисел.
- КОМПИЛИРОВАТЬ - все, кроме слов : и ; реализовано на 3-м уровне. Тоже все как обычно.
- СЛОВАРЬ - по Баранову и Ноздрунову.
- СЛЕДУЮЩИЙ - см. выше NEXT. Там же стек возвратов.

Т.е. все до предела стандартно, хоть и без консоли.
Внутренняя:
- ПОТОК - очередь Win-сообщений. EXPECT, понятно, заменяется циклом обработки сообщений приложения.
- СИМВОЛ - она же оконная функция. Никаких WORD и NUMBER (за WORD можно считать код, сохраняющий в Win-стеке параметры/регистры оконной функции). FIND заменен вызовом RECEPTING - ищущим обработчик сообщения в дереве.
- ОК - возвращение значения - результата обработки сообщения.
- ЗНАЧЕНИЕ - адрес обработчика.
- ВЫПОЛНИТЬ является частью RECEPTING - исполняет найденный обработчик.
- СТЕК для распознавания ПОТОКА не используется (только использование стеков внешней машины для внутренних нужд).
- Возможности КОМПИЛИРОВАТЬ не используются. Хотя, вероятно, имеет смысл вносить некоторые изменения в дерево обработчиков при изменении вида окна и/или состояния приложения. Впрочем, сам Must Die такими возможностями не пользуется.
- СЛОВАРЬ - дерево обработчиков (RECEPTOR), формируется внешней машиной в ее СЛОВАРЕ. Есть возможность что-то писать в СЛОВАРЬ внешней машины, но не используется (пока?).
- СЛЕДУЮЩИЙ - используется дополнительный стек для хранения параметров/регистров вложенных оконных функций (WIN-STACK). После окончания обработчика управление возвращается внешней машине (точнее, циклу обработки сообщений в ней). Внутри обработчика используется механизм внешей машины.

Сравним, например, с интерпретатором языка Trac:
- ПОТОК - входная строка (цепочка). По умолчанию формируется "программа": "считать/исполнить - напечатать", но ее можно, по ходу дела, заменить на что-то более проблемно-ориентированное.
- СИМВОЛ - от цепочки отрезается очередной "кусок": приказ или параметр. Приказы связываются с началом/концом выражений в скобках, параметры разделяются запятыми.
- ОК - вызов, по необходимости, стандартного перезапука ПОТОКА - "чтение-печать-цепочки".
- ЗНАЧЕНИЕ - цепочка с блоком указателей на нее.
- ВЫПОЛНИТЬ является частью СИМВОЛ - приказы исполняются сразу, параметры грузятся на СТЕК.
- СТЕК - блоки указателей в кадрах стека и строковый накопитель для цепочек параметров.
- КОМПИЛИРОВАТЬ запоминает пару (цепочка-имя, цепочка-значение).
- СЛОВАРЬ - ассоциативный массив этих пар.
- СЛЕДУЮЩИЙ - цепочки являются лишь параметрами для изначально прописанного Цикла Управления (внешнее управление).

В чем отличие Trac от FORTH? В основном, в том, что, подобно LISP, он содержит в себе некоторую виртуальную машину, доступ к которой средствами пользователя запрещен. Хотя, механика LISP-машины записывается на самом LISP замечательно, но пока вы не напишите ее от начала до конца в кодах, LISP не заработает.
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 08, 2017 2:13 pm

Можно "определить" FORTH-систему, как интерпретатор "ОК-ПОТОК-СИМВОЛ-ЗНАЧЕНИЕ-ВЫПОЛНИТЬ-СТЕК-КОМПИЛИРОВАТЬ-СЛОВАРЬ-СЛЕДУЮЩИЙ", который начинает работать, как только определен ПОТОК и написана процедура СИМВОЛ (и, чисто формально - ВЫПОЛНИТЬ).
Но...
1. Т.к. идея этих "составных частей" пришла уже в процессе написания этих заметок, большая часть изложения по-прежнему крутится вокруг устройства процедуры СИМВОЛ...
2. "Схему интерпретатора" нужно урезать до "ОК-СИМВОЛ-ВЫПОЛНИТЬ-КОМПИЛИРОВАТЬ-СЛЕДУЮЩИЙ". В FORTH-традиции данные значения не имеют. Они - лишь техническая подробность реализации действий.
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор _KROL в Пн Сен 11, 2017 8:08 pm

Почитал кое-что отсюда...
Возник вопрос: а правильно ли называть твою внутренню машину фортом?
То что это часть системы и использует ШК это понятно, но разве она контактирует как-то с пользователем своими средствами, или является частью самого языка? Тогда, как мне кажеться, это уже просто что-то типа BIOSа твоей системы.

_KROL

Сообщения : 90
Дата регистрации : 2017-07-28
Возраст : 19
Откуда : Беларусь

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пн Сен 11, 2017 8:27 pm

_KROL пишет:Возник вопрос: а правильно ли называть твою внутреннюю [FOBOS-]машину фортом?
То что это часть системы и использует ШК это понятно, но разве она контактирует как-то с пользователем своими средствами, или является частью самого языка?
Конечно, контактирует. Сообщения пользователя являются частью языка Win-сообщений. По мне, так, визуальное программирование очень близко к FORTH - ТЕМА #14.


Последний раз редактировалось: Gudleifr (Ср Дек 06, 2017 1:01 pm), всего редактировалось 1 раз(а)
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор _KROL в Пн Сен 11, 2017 9:05 pm

Понятно, я согласен. Спасибо, я на это не обратил особого внимания(видимо привык видеть в голове(мечтах что-ли?) форт как единую ОС. А это немного заблуждение(как вроде ты писал) ).

_KROL

Сообщения : 90
Дата регистрации : 2017-07-28
Возраст : 19
Откуда : Беларусь

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 15, 2017 6:37 pm

КАКИЕ МЫ ЗНАЕМ ПРАКТИКИ РЕАЛИЗАЦИИ FORTH-ИНТЕРПРЕТАТОРА?

Первая описана еще Муром - использование Цикла Управления с кучей флагов (и кода) на все случаи жизни.
Учитывая желательность написания отдельного FORTH для каждой отдельной задачи, вполне реально.
Более того, если бы имелся полный (или, хотя бы, официально регулярно пополняемый) список этих переменных-флагов, была бы возможна полная стандартизация FORTH-систем.
В современных FORTH-системах остались только рудименты этой практики - переменные STATE, SRC...

Вторая практика - полное игнорирование наличия каких бы то ни было практик. "Макрофортеры", наверное, даже самому введению этаких "4-х источников и 5-и составных частей FORTH-изма" воспротивятся. Мол, деды так писали и нам велели... Работает, же!

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

Четвертая практика, которая кажется мне наиболее простой (и близкой ко второй) - вторичных FORTH-систем. Т.е. инкапсуляциа вариантов основных процедур внутри отдельных слов первичной системы.
Главный плюс - ничего не нужно делать. Просто по-другому обозвать то, что уже сделано.
Например слово CREATE не просто читает из ПОТОКА имя слова и создает для него новую словарную статью, а
- запускает ограниченный вариант процедуры СИМВОЛ - без FIND и NUMBER;
- выполняет тривиальную (пустую) процедуру ВЫПОЛНИТЬ - на СТЕКЕ обычно и так уже лежит ЗНАЧЕНИЕ;
- выполняет чуть ли не самую сложную процедуру КОМПИЛИРОВАТЬ из возможных - создает словарную статью.
- запускает обычную процедуру СЛЕДУЮЩИЙ.
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 15, 2017 6:40 pm

ИСТОРИЧЕСКИ СЛОЖИВШАЯ ОПТИМИЗАЦИЯ

Универсальный СТЕК. В настоящее время почти никто не воспринимает СТЕК как накопитель введенной, но не обработанной информации. Все уже привыкли к тому, что это "самое удобное средство обмена информацией между процедурами-словами, благодаря которому FORTH так быстр и компактен". Тьфу!

Благодаря такой универсальности СТЕКА, ЗНАЧЕНИЕ (то, что влезает) попадает на его вершину уже в конце процедуры СИМВОЛ (где и обрабатывалось). Процедура ВЫПОЛНИТЬ в этом случае почти ничего не делает и может быть засунута туда же - внутрь СИМВОЛ.

ЗНАЧЕНИЕ обычно представляет из себя вершину СТЕКА и вершину СЛОВАРЯ.

Процедура КОМПИЛИРОВАТЬ используется очень редкими словами-интерпретаторами (см. выше слово CREATE), обычно его функционал ограничивается одним словом "запятая" (или его байтовой версией). Никаких специальных механизмов для переноса со СТЕКА в СЛОВАРЬ никто не разрабатывает (даже при написании, например, ассемблеров удается обойтись почти одной "запятой").

О том, что СЛОВАРЬ тоже своего рода стек, никто уже давно особо не задумывается. Осталось только помещение на его "вершину" остатка ЗНАЧЕНИЯ, распознанного процедурой СИМВОЛ, каковой остаток, если надо, станет началом новой словарной статьи.

Используются флаги для выбора источника ПОТОКА - консоли, блока, файла. В стандарте предусмотрено создание стека источников ввода для облегчения возврата к старому ПОТОКУ после исчерпания текущего (для этого используется тот же универсальный СТЕК). Набор переменных, указывающий, "откуда читаем" отличается жуткой громоздкостью.

Процедура ВЫПОЛНИТЬ исторически базируется на использовании флага STATE и ничего более удобного придумать, кажется, невозможно. Так же исторически различается единственный вид литералов - числовой, все остальное трактуется как слово, ЗНАЧЕНИЕМ которого является его исполняемый адрес.
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 15, 2017 6:43 pm

ОБОРОТЫ...

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

Могут ли понадобиться конструкции, требующие каких-то совсем особых процедур? И каковы пределы их особости?
Изначально "нижним пределом совместимости" является формат поля кода словарной статьи. Исполнить слово - значит передать управление по его адресу. Никаких указаний на то, как передавать параметры, куда возвращать управление, как интерпретировать код... Есть, пожалуй, единственное исключение: СЛОВАРЬ, куда идет компиляция может быть не предназначен для исполнения в текущей FORTH-системе (в случае целевой компиляции).
В других случаях особенность исполнения может касаться, максимум, одного слова, вызванного специальным (например, зависящим от словаря/контекста) способом. Так, слово-обработчик Win-сообщения вынужденно вызывается и возвращает значение не так, как обычные слова. Но если оно будет требовать того же и от слов, которые вызываются из него, то не сможет пользоваться никакими обычными словами. Поэтому "внутри скобок" вызова оконной функции все обычные FORTH-слова должны вызываться как обычно.
Может показаться, что разные способы кодирования слов все-таки нужны: например есть же слова, написанные в кодах процессора, а есть - написанные в шитых кодах... Но FORTH-то этого не знает! Он честно передает управление по адресу, а расположена ли там процедура на языке процессора или интерпретатор шитого кода - FORTH наплевать.
***

Итак, поле кода всех словарных FORTH-системы вынуждено иметь одинаковый формат, за исключением словарей, компилируемых не для себя и слов, не предназначенных для самостоятельного запуска. Например, слов с векторным полем кода, где за вызов нужного кода отвечает "оборот вызывания".
***

Уж точно не имеет смысла считать за постоянную формат ПОТОКА. Здесь за некую "константу" надо принять понятие "символ" (впрочем, иначе не получится той картинки, что я нарисовал в начале).
"Символ" должен стать для FORTH-системы тем, чем являются "файл" или "сообщение" для операционной системы. Точнее, подобно тому, как память блоков позволяла одинаково легко реализовать FORTH в самых различных файловых системах (и без них), чтение "символов" из ПОТОКА и исполнение связанного с ними кода должно примирить FORTH с любыми операционными системами - ориентированными на процедуры и/или сообщения. (Станислав Лем как-то определил литературное произведение, как дефиницию названия. Т.е. вводится "термин" - название романа, а весь остальной роман лишь этот "термин" разъясняет).
***

Чем можно заменить компиляцию?
В самом фантастическом случае - "программировании" человеческого мозга, КОМПИЛИРОВАТЬ означает "сохранить в долговременной памяти" (изменить проводимость связей между нейронами и их ансамблями). СТЕК в этом случае - "кратковременная память" (возбуждение нейронов/ансамблей).
В принципе, все это - "применение статического объекта обмена данными" (например, стека) вместо "объектов динамических" (каналов, кадров стека...).
Выбор конкретного представления СТЕКА целиком определяется свойствами проблемно-ориентированного языка (ПОТОКА), а СЛОВАРЯ... тоже свойствами ПОТОКА, ведь роль СЛОВАРЯ - обеспечить декодирование "символов". Главное, ни в коем случае нельзя зацикливаться на "стандартных для FORTH" стеке и словаре.
Что-либо общее в реализации процедуры КОМПИЛИРОВАТЬ?
К сожалению, только одна большая неприятность: нормальное расположение элементов в СТЕКЕ "задом наперед" (последним зашел - первым вышел), а в СЛОВАРЕ (в пределах одной словарной статьи) - строго последовательное. И если не использовать механизм дополнительных указателей, позволяющий вытаскивать из СТЕКА целыми блоками, то приходиться КОМПИЛИРОВАТЬ очень малыми кусками.
Это подтвердит каждый, кто, например, писал ассемблер чуть более сложный, чем для Intel 8080. В FOBOS я столкнулся с этой же проблемой при заполнении блоков Windows-ресурсов.
(Дополнительные указатели на СТЕК используются, например, в интерпретаторе языка Trac: на начало кадра текущей функции).
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Gudleifr в Пт Сен 15, 2017 6:43 pm

НЕМНОЖКО ПОЛУЧЕННЫХ ПРИ АНАЛИЗЕ ЭТОЙ МОДЕЛИ РЕЗУЛЬТАТОВ:

Имеет смысл рассматривать только процедуры - ОК, СИМВОЛ, ВЫПОЛНИТЬ, КОМПИЛИРОВАТЬ, СЛЕДУЮЩИЙ. Данные - ПОТОК, ЗНАЧЕНИЕ, СТЕК, СЛОВАРЬ - самостоятельного значения не имеют. Просто в силу того, что сама концепция даных чужда FORTH. Поэтому попытки улучшить FORTH путем исключительно совершенствования данных (например, введение типов в СТЕК, дополнительных флагов в ЗНАЧЕНИЕ, синтаксиса в ПОТОК... да, просто, сведение развития языка к расширению СЛОВАРЯ) - полная фигня. Имеют значение только действия!

Наличие дополнительных "петель": процедура ВЫПОЛНИТЬ, вызывающая КОМПИЛИРОВАТЬ, или процедура СИМВОЛ, берущая команду не из ПОТОКА, а из процедуры СЛЕДУЮЩИЙ,- проще осмысливается, если, опять же, отказаться от данных.

Вопреки распространенному мнению, эффективная реализация FORTH-системы требует минимизации общего кода перечисленных процедур. Например, процедура ВЫПОЛНИТЬ должна не сама компилировать ЗНАЧЕНИЕ в СЛОВАРЬ, а вызывать для этого КОМПИЛИРОВАТЬ. А слова для чтения из СЛОВАРЯ (типа "@") - принадлежат процедуре СЛЕДУЮЩИЙ.

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

Реализация процедур оставляет за бортом очень много слов, считающихся FORTH-стандартными. Может, не так уж они и нужны? Особенно, например, слова, порождающие логические значения ("<", "0<", "0="...).
avatar
Gudleifr
Admin

Сообщения : 931
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Интерпретатор

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения