r2 - 17 Mar 2006 - 23:47:22 - OrloVYou are here: TWiki >  Refaldevel Web > RefalPlus > RefalPlusBook > RefalPlusBookChapII

Глава II. Синтаксис и семантика Рефала Плюс

1. Нотация для записи синтаксиса

Для описания синтаксиса используется расширенная форма Бекуса-Наура (РБНФ).

Синтаксические понятия (нетерминалы) обозначаются словами, выражающими их интуитивный смысл. Цепочки терминальных символов заключаются в двойные кавычки либо апострофы, с тем, чтобы их можно было отличить от нетерминалов.

Если конструкция A представляет собой конкатенацию конструкций B и C, т.е. состоит из конструкции B и следующей вслед за ней конструкции C, мы будем называть B и C синтаксическими множителями и описывать A следующей синтаксической формулой:

     A = B C.

Если конструкция A является либо конструкцией B, либо конструкцией C, мы будем называть B и C синтаксическими слагаемыми и описывать A следующей синтаксической формулой:

     A = B | C.

Для группировки синтаксических слагаемых и множителей можно использовать круглые скобки.

Если конструкция A представляет собой либо конструкцию B, либо является пустой цепочкой, это выражается в виде

     A = [B].

Если же A представляет собой произвольную (может быть пустую) последовательность из конструкций B, это выражается в виде

     A = {B}.

Приведем несколько примеров того, как множества предложений описываются формулами в РБНФ.

     (A|B)(C|D)     A C, A D, B C, B D
     A[B]C          A B C, A C
     A {B A}        A, A B A, A B A B A, A B A B A B A, ...
     {A|B} C        C, A C, B C, A A C, A B C, B B C, B A C, ...

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

Поскольку сама РБНФ представляет собой некоторый язык, ее синтаксис также может быть описан с помощью РБНФ следующим образом:

$    Синтаксис      = { СинтФормула }.
$    СинтФормула    = Идентификатор "=" СинтВыражение ".".
$    СинтВыражение  = СинтСлагаемое { "|" СинтСлагаемое }.
$    СинтСлагаемое  = СинтМножитель { СинтМножитель }.
$    СинтМножитель  = Идентификатор | Цепочка |
$         "(" СинтВыражение ")" | "[" СинтВыражение "]" |
$         "{" СинтВыражение "}".

2. Естественный метод описания семантики

Для описания процесса выполнения программ на Рефале Плюс будет использован метод, известный под названием "естественная семантика" или "структурная операционная семантика" [Плоткин 1983], [Апт 1983].

Название "естественная семантика" объясняется сходством этого метода описания с генценовским естественным выводом в математической логике. При таком способе описания, семантикой языка является неупорядоченное множество утверждений о программах и фрагментах программ.

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

          Env,St' |- E => X,St"

где E - выражение языка, Env - среда, которая связывает переменные с их значениями в том контексте, в котором находится E, St' и St" - глобальное состояние до начала вычисления E и после вычисления E, а X - результат вычисления E. Глобальное состояние может включать состояние памяти, состояние файлов и т.п.

Смысл таких утверждений неформально может быть истолкован следующим образом: если вычисление выражения E начинается в среде Env и глобальном состоянии St', оно может завершиться получением значения X в глобальном состоянии St".

Знак "|-" (который можно читать как "влечет" или "вызывает") служит напоминанием о том, что результат вычисления выражения E зависит от среды Env, в которой вычисляется выражение, ибо это выражение может содержать переменные.

Таким образом, задача описания семантики языка при таком подходе сводится к задаче описания множества истинных утверждений о программах и их фрагментах.

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

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

Кроме того, для каждого правила могут иметься дополнительные условия, которые накладывают какие-то ограничения на вид посылок и заключения. Эти ограничения мы будем записывать справа от правила или непосредственно под ним.

Например, предположим, что в описываемом языке имеется конструкция if E then E' else E", смысл которой неформально может быть описан следующим образом.

Вычислить E. Если получится true, то вычислить E' и полученный результат считать результатом вычисления всей конструкции. Если же в результате вычисления E получилось false, то вычислить E" и полученный результат считать результатом вычисления всей конструкции.

Недостатком такого описания является то, что мы забыли указать, в какой среде происходит вычисление каждого из выражений E, E' и E". Поэтому переформулируем описание более точно.

Если результатом вычисления выражения E в среде Env является true, а результатом вычисления выражения E' в среде Env является X, то X является результатом вычисления конструкции if E then E' else E" в среде Env.

Если результатом вычисления выражения E в среде Env является false, а результатом вычисления выражения E" в среде Env является X, то X является результатом вычисления конструкции if E then E' else E" в среде Env.

Это многословное определение можно записать в более краткой и наглядной форме в виде двух правил вывода:

     Env,St |- E => true,St'
     Env,St'|- E' => X,St"
     ---------------------------------------
     Env,St |- if E then E' else E" => X,St"

     Env,St |- E => false,St'
     Env,St'|- E" => X,St"
     ---------------------------------------
     Env,St |- if E then E' else E" => X,St"

Обратите внимание, что формализованное описание семантики, в отличие от словесного, точно определяет как изменяется глобальное состояние в процессе вычисления.

3. Лексическая структура программы

Программа на языке Рефал Плюс представляет собой конечную последовательность литер. Анализ программы проводится в два этапа. Сначала производится сканирование программы, в результате чего поток литер разбивается на лексемы. Затем результат сканирования подвергается синтаксическому анализу, результатом которого является дерево синтаксического анализа. В связи с этим описание синтаксиса состоит из двух частей: сначала описывается лексическая структура программы, т.е. правила изображения лексем с помощью цепочек литер, а затем - синтаксическая структура, т.е. правила, по которым программы составляются из лексем.

$    Программа = { Межа Лексема } Межа.

$    Межа = РазделительЛексем | Комментарий.

$    РазделительЛексем = Пробел | Табуляция | КонецСтроки.

Программа представляет собой конечную последовательность лексем. В качестве разделителей лексем используются следующие литеры: пробел, табуляция и конец строки. Избыточные разделители лексем могут появляться как до, так и после лексемы, но не внутри лексем.

Если две соседние лексемы могут быть однозначно отделены одна от другой, разделители лексем между ними могут отсутствовать.

3.1. Комментарии

$    Комментарий = "*" ОкончаниеКомментария КонецСтроки
$         | "/*" ТелоКомментария "*/".
$    ОкончаниеКомментария =
$         любая цепочка литер, не содержащая КонецСтроки.
$    ТелоКомментария =
$         любая цепочка литер, не содержащая "*/".

Существует два способа вставлять комментарии между лексемами. Первый способ - поставить литеру *. При этом весь остаток строки игнорируется. Второй способ - заключить комментарий в пару "комментарных скобок" /* и */. Например:

* Это - комментарий.
          * И это - комментарий.
     /* И это - тоже! */

3.2. Лексемы

$    Лексема =
$         Скобка | КлючевоеСлово |
$         ИзображениеЦепочкиЛитер |
$         ИзображениеСлова | ИзображениеЧисла |
$         Переменная.

$    Скобка = "(" | ")" | "{" | "\{" | "}" | "<" | ">".

Лексемы представляют собой скобки, ключевые слова, изображения цепочек символов-литер, изображения символов-слов, изображения символов-чисел, и переменные.

3.3. Ключевые слова

$    КлючевоеСлово =
$         "$box" | "$channel | "$const" | "$error" | "$fail" |
$         "$func" | "$func?" | "$iter" | "$l" | "$r" |
$         "$string" | "$table" | "$trace | | "$traceall" |
$          "$trap" | "$use" | "$vector" | "$with" |
$         "#" | "&" | "," | ":" | "::" | ";" | "=" |
$         "\?" | "\!".

Если ключевое слово начинается с литеры $, не делается различия между прописными и строчными буквами. Например, ниже одно и то же ключевое слово записано тремя разными способами:

$func $Func $FUNC

3.4. Символы-литеры

$    ИзображениеЦепочкиЛитер =
$         "'" { ИзображениеЛитеры | ПереходНаНовуюСтроку } "'".

$    ИзображениеЛитеры =
$         ИзображениеОбычнойЛитеры | ИзображениеОсобойЛитеры.
$    ИзображениеОбычнойЛитеры =
$         любая литера ASCII кроме апострофа ('), кавычки ("),
$         обратной косой (\) и конца строки.
$    ИзображениеОсобойЛитеры =
$         "\n" | "\t" | "\v" | "\b" | "\r" | "\f" |
$         "\\" | "\'" | '\"' .
$    ПереходНаНовуюСтроку =
$         "\" КонецСтроки .

Символ-литера соответствует одной литере кода ASCII и записывается в виде изображения этой литеры ASCII, заключенного в апострофы. Например:

     'A' 'a' '7' '$'

Как правило, изображением литеры ASCII является сама эта литера, за исключением следующих литер ASCII, для которых предусмотрены особые обозначения:

     Новая строка (перевод строки) HL (LF)   '\n'
     Горизонтальная табуляция      HT        '\t'
     Вертикальная табуляция        VT        '\v'
     Возврат на шаг                BS        '\b'
     Возврат каретки               CR        '\r'
     Перевод формата               FF        '\f'
     Обратная косая                \         '\\'
     Апостроф                      '         '\''
     Двойная кавычка               "         '\"'

Последовательность из нескольких символов-литер может быть записана в виде одной последовательности изображений литер ASCII, заключенной в апострофы. Например:

     'ABC'
     '123'
     '\"I don\'t like swimming!\" - said a little girl.'

Таким образом, последовательность из трех символов-литер 'A', 'B' и 'C' может быть записана любым из перечисленных ниже способов:

     'A' 'B' 'C'
     'A''B''C'
     'ABC'

Внутри изображения цепочки символов-литер литера \ и следующая за ней литера перевода строки (LF) игнорируются, что дает возможность переносить цепочки с одной строки на другую. Например:

     'A\
     BC'

3.5. Символы-слова

$    ИзображениеСлова =
$         Идентификатор |
$         '"' { ИзображениеЛитеры | ПереходНаНовуюСтроку } '"'.

$    Идентификатор = НачалоИдентификатора ХвостИдентификатора.
$    НачалоИдентификатора = ПрописнаяБуква | "!" | "?".
$    ХвостИдентификатора = { Буква | Цифра | "!" | "?" | "-" }.

$    Буква = ПрописнаяБуква | СтрочнаяБуква.

$    ПрописнаяБуква = 
$         "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" |
$         "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" |
$         "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z".

$    СтрочнаяБуква = 
$         "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" |
$         "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" |
$         "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z".

$    Цифра = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7"
$         | "8" | "9".

Символ-слово соответствует цепочке литер кода ASCII и записывается в виде цепочки изображений этих литер ASCII, заключенной в двойные кавычки. Изображения литер ASCII такие же, как и при записи символов-литер. Например:

     "ABC"
     "123"
     "\"I don\'t like swimming!\" - said a little girl."

Следует обратить внимание, что "ABC" является изображением одного символа-слова, в то время как 'ABC' - это изображение цепочки из трех символов-литер. Кроме того, считается, что все символы-слова, состоящие из одной литеры, не совпадают с соответствующими символами-литерами. Например символ-литера 'A' и символ-слово "A" - разные символы.

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

Во-первых, этот символ-слово может содержать только следующие литеры ASCII: прописные буквы, строчные буквы, цифры, восклицательный знак, вопросителный знак, знак минус.

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

Если символ-слово записан без окружающих двойных кавычек, то все строчные буквы считаются изображениями соответствующих прописных букв, т.е. "поднимаются в верхний регистр".

Например, ниже приведено три изображения одного и того же символа-слова:

     I-do-not-like-swimming!
     I-DO-NOT-LIKE-SWIMMING!
     "I-DO-NOT-LIKE-SWIMMING!"

3.6. Символы-числа

$    ИзображениеЧисла = [ "+" | "-" ] Цифра { Цифра }.

Символы-числа соответствуют целым числам со знаком. Они могут быть неограниченного размера. Например:

123 +121 -123 -123456789012345678901234567890

3.7. Переменные

$    Переменная =
$         s-переменная | t-переменная | e-переменная |
$         v-переменная.
$    s-переменная = "s" [ "." ] ИндексПеременной.
$    t-переменная = "t" [ "." ] ИндексПеременной.
$    v-переменная = "v" [ "." ] ИндексПеременной.
$    e-переменная = "e" [ "." ] ИндексПеременной.

$    УказательТипаПеременной = "s" | "t" | "v" | "e".
$    ИндексПеременной = ХвостИдентификатора.

Переменная состоит из указателя типа переменной, необязательной точки и индекса переменой. Например:

     tHead  eTail e.1 e1  tX s t e

Различие между прописными и строчными буквами в записи переменных несущественно. Например, eI, e.I, ei и e.i - различные изображения одной и той же переменн ой.

Если две переменные стоят рядом, они должны быть разделены межой. Например, sAeB является одной переменной, в то время как sA eB - две переменные.

Если индекс переменной отсутствует, это означает, что подразумевается, что эта переменная имеет уникальный индекс и отличается от всех прочих переменных в программе. Таким образом, например, если в программе не используются переменные e1000 и e2000, то запись e e может быть заменена на e1000 e2000.

Переменные делятся на четыре класса: s-переменные, t-переменные, v-переменные и e-переменные, в соответствии с их указателями типа.

3.8. Нормализация потока лексем

В процессе ввода программы сканер разбивает входной поток литер на лексемы. Многие лексемы имеют один и тот же смысл. Так, например, все три лексемы

125 000125 +125

обозначают одно и то же число 125.

Именно поэтому при описании лексической структуры программы мы употребляли такие термины как "изображение числа" и "изображение слова" вместо "число" и "слово".

Кроме того, такая лексема как "изображение цепочки литер" является изображением не одного синтаксического объекта, а конечной последовательности литер.

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

Соответствие между исходными лексемами и нормализованными лексемами следующее:

     ИзображениеЦепочкиЛитер  ==>  Литера1 Литера2 ... ЛитераN
     ИзображениеСлова         ==>  Слово
     ИзображениеЧисла         ==>  Число

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

4. Объекты и значения

Под объектами обычно понимают некоторые сущности, которые существуют во времени, могут изменяться, но при этом остаются сами собой.

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

Конечно, значение можно считать частным, вырожденным случаем объекта (а именно, застывшим объектом, не способным к развитию), но мы все же обычно будем называть "объектами" только такие объекты, которые не являются значениями.

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

Программы на Рефале Плюс имеют дело как с объектами, так и со значениями.

Все значения, с которыми работают Рефал-программы, являются объектными выражениями, которые представляют собой конечные последовательности символов и скобок, правильно построенные относительно скобок. Скобки служат для придания объектным выражениям древовидной структуры, в то время как символы представляют собой элементарные данные (литеры, числа, слова и ссылки на объекты).

Объекты, с которыми работают Рефал-программы, могут содержать внутри себя объектные выражения (в частности - ссылки на объекты). Содержимое объектов может изменяться в процессе работы Рефал-программы. Доступ к объектам осуществляется через их имена, в качестве которых служат символы-с сылки.

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

5. Объектные выражения

5.1. Синтаксис объектных выражений

$    ОбъектноеВыражение = { ОбъектныйТерм }.
$    ОбъектныйТерм = Символ | "(" ОбъектноеВыражение ")".

В дальнейшем мы будем обозначать объектные выражения через Oe, объектные термы - через Ot, а символы - через Os.

5.2. Статические и динамические символы

$    Символ = СтатическийСимвол | ДинамическийСимвол.
$    СтатическийСимвол = Литера | Слово | Число.
$    ДинамическийСимвол = СсылкаНаФункцию | СсылкаНаТаблицу |
$         СсылкаНаЯщик | СсылкаНаВектор |
$         СсылкаНаСтроку | СсылкаНаКанал.

Символы делятся, на две категории: статические и динамические.

К статическим символам относятся символы-литеры, символы-слова и символы-числа.

Статические символы существуют "объективно": статический символ может быть выведен в канал ввода-вывода, а затем введен обратно. При этом мы получим опять тот же символ. В этом смысле статические символы сушествуют еще до начала исполнению программы и продолжают существовать после зав ершения исполнения программы.

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

Динамические символы, в противоположность статическим, "субъективны". Они создаются в момент загрузки программы и в процессе ее исполнения. Хотя их можно вывести в канал ввода-вывода, их нельзя ввести обратно. Когда выполнение программы завершается, все динамические символы, созданные в процессе ее выполнения теряют всякий смысл.

К динамическим символам относятся ссылки на функции, ссылки на ящики, ссылки на векторы, ссылки на строки, ссылки на таблицы и ссылки на каналы.

5.3. Символические имена выражений

$    ИмяВыражения = "&" Слово.

Объектным выражениям в программе на Рефале Плюс могут присваиваться символические имена, в качестве которых используются символы-слова. Если символ-слово Os обозначает объектное выражение Oe, то конструкция вида & Os означает, что в этом месте должно быть подставлено объектное выражение Oe.

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

5.4. Устранение символических имен выражений

Если слово Os является символическим именем объектного выражения Oe, то все использования этого имени в программе можно устранить, заменив каждую конструкцию &Os на Oe.

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

6. Значения переменных и среды

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

А именно, пусть Env - среда с областью определения {V1, ..., Vn}. Тогда Env(Vj) = Oej является значением переменной Vj. Такую среду мы будем обозначать через {V1 = Oe1, ..., Vn = Oen}. В частности, пустая среда будет обозначаться через {}.

Область определения среды Env мы будем обозначать через dom[Env]. Таким образом, dom[ {V1 = Oe1, ..., Vn = Oen} ] = {V1, ..., Vn}.

При этом, без дальнейших оговорок, мы всегда будем предполагать, что переменные обязательно имеют значения, соответствующие их типам. Т.е. значениями s-переменных могут быть только символы, значениями t-переменных - только объектные термы, значениями e-переменных - произвольные объ ектные выражения, а значениями v-переменных - непустые объектные выражения.

В дальнейшем Env+Env' будет означать пополнение среды Env значениями переменных из среды Env', которое строится следующим образом.

dom[Env+Env'] содержит все переменные из dom[Env'], а также все переменные из dom[Env], индексы которых отличаются от индексов переменных из dom[Env'].

Для любой переменной V из dom[Env+Env'], если Env'(V) определено, то (Env+Env')(V) = Env'(V), а если Env'(V) не определено, то (Env+Env')(V) = Env(V).

Например

{sX = 1, sY = 2} + {sY = 200, sZ = 300}
     = {sX = 1, sY = 200, sZ = 300}

{sX = 1, sY = 2} + {eY = 200, sZ = 300}
     = {sX = 1, eY = 200, sZ = 300}

7. Результатные выражения

7.1. Синтаксис

$    РезультатноеВыражение =
$         { РезультатныйТерм | ИмяВыражения }.
$    РезультатныйТерм =
$         СтатическийСимвол | Переменная |
$         "(" РезультатноеВыражение ")" |
$         ВызовФункции.
$    ВызовФункции =
$         "<" ИмяФункции АргументВызова ">".
$    АргументВызова =
$         РезультатноеВыражение.

В дальнейшем мы будем обозначать результатные выражения через Re, результатные термы - через Rt, переменные - через V, e-переменные - через Ve, а имена функций - через Fname.

7.2. Вычисление результатных выражений

Результатные выражения служат для порождения объектных выражений.

Результатное выражение Re может быть вычислено в любой среде Env, при условии, что Env дает значения для всех переменных входящих в Re.

Если вычисление результатного выражения Re заканчивается, то результатом этого вычисления является либо объектное выражение Oe, либо неуспех $fail(0), либо ошибка $error(Oe), где Oe - сообщение об ошибке.

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

Запись Env,St |- Re => X,St' означает, что результатом вычисления результатного выражения Re в среде Env является X. При этом, если вычисление началось в глобальном состоянии St, оно закончится в глобальном состоянии St'.

Результатное выражение Re вычисляется слева направо. При этом вместо переменных подставляются их значения и выполняются вызовы функций.

Вычисление вызовов функций выполняется следующим образом. Если вызов имеет вид <Fname Re>, то вычисляется результатное выражение Re. Если в результате получится объектное выражение Oe, то функция Fname применяется к Oe.

Запись St |- <Fname Oe> => X,St' означает, что результатом применения функции Fname к объектному выражению Oe является X, причем, если вычисление началось в глобальном состоянии St, оно закончится в глобальном состоянии St'.

     Env,St |-  =>  ,St

     Env,St |- Re => Oe',St'
     Env,St'|- Rt => Oe",St"
     ------------------------------
     Env,St |- Re Rt => Oe' Oe",St"

     Env,St |- Re => Oe',St'
     Env,St'|- Rt => $fail(0),St"
     -------------------------------
     Env,St |- Re Rt => $fail(0),St"

     Env,St |- Re => Oe',St'
     Env,St'|- Rt => $error(Oe"),St"
     ----------------------------------
     Env,St |- Re Rt => $error(Oe"),St"

     Env,St |- Re => $fail(0),St'
     -------------------------------
     Env,St |- Re Rt => $fail(0),St'

     Env,St |- Re => $error(Oe'),St'
     ----------------------------------
     Env,St |- Re Rt => $error(Oe'),St'

     Env,St |- Os => Os,St

     Env,St |- V => Oe,St
          где Oe=Env(V).

     Env,St |- Re => Oe,St'
     --------------------------
     Env,St |- (Re) => (Oe),St'

     Env,St |- Re => $fail(0),St'
     ------------------------------
     Env,St |- (Re) => $fail(0),St'

     Env,St |- Re => $error(Oe),St'
     --------------------------------
     Env,St |- (Re) => $error(Oe),St'

     Env,St |- Re => Oe,St'
     St' |- <Fname Oe> => X,St"
     -----------------------------
     Env,St |- <Fname Re> => X,St"

     Env,St |- Re => $fail(0),St'
     ------------------------------------
     Env,St |- <Fname Re> => $fail(0),St'

     Env,St |- Re => $error(Oe),St'
     --------------------------------------
     Env,St |- <Fname Re> => $error(Oe),St'

7.3. Примеры

Ниже приведены примеры результатных выражений:

          (A B) C D
          t.Head e.Tail
          While t.Condition Do t.Statement
          <"*" sN <Factorial <"-" sN 1>>

Следующие результатные выражения являются результатными термами:

          (A B)
          t.Head
          <"*" sN <Factorial <"-" sN 1>>

Пусть Env1 = {sM = 2, sN = 3, eA = A B C, tB = (D E F)}, и пусть "+" - имя функции, выполняющей сложение целых чисел, а "*" - имя функции, выполняющей умножение целых чисел, т.е. в частности имеет место

     St |- <"+" 3 100> => 103, St
     St |- <"*" 2 103> => 206, St

для любого глобального состояния St, ибо функции "+" и "*" не изменяют глобальное состояние.

Тогда имеем

     Env1,St |- eA (eA tB) tB =>
                         A B C (A B C (D E F)) (D E F), St
     Env1,St |- <"*" sM <"+" sN 100>> => 206, St

8. Образцы

8.1. Синтаксис

$    Образец = УказательНаправления ОбразцовоеВыражение.
$    УказательНаправления = [ "$l" | "$r" ].

$    ОбразцовоеВыражение =
$         { ОбразцовыйТерм | ИмяВыражения }.
$    ОбразцовыйТерм =
$         СтатическийСимвол | Переменная |
$         "(" ОбразцовоеВыражение ")".

Образец представляет собой образцовое выражение, перед которым может стоять указатель направления "$l" или "$r". Указатель направления "$l" означает что сопоставление с образцом должно выполняться слева направо. Указатель "$r" - что справа налево. Если указатель направления отсутствует, подразумевается указатель "$l".

В дальнейшем мы будем обозначать образцы через P, образцовые выражения - через Pe, образцовые термы - через Pt, а указатели направления сопоставления - через D.

8.2. Сопоставление с образцом

Мы говорим, что среда Env является результатом сопоставления объектного выражения Oe с образцом P в начальной среде Env0, если выполнены следующие условия.

(1) Среда Env является расширением среды Env0, т.е. область определения среды Env является расширением области определения среды Env0, и для любой переменной V из области определения среды Env0 имеет место Env(V)=Env0(V).

(2) Если все переменные, входящие в P, заменить на их значения в соответствии с Env, а указатель направления отбросить, получится объектное выражение Oe.

В этом случае среду Env мы будем также называть вариантом сопоставления Oe с P в среде Env0, a множество таких вариантов сопоставления будем обозначать че рез Match(Env0,Oe,P).

На множестве Match(Env0,Oe,P) вводится отношение порядка следующим образом.

Пусть Match(Env0,Oe,P) содержит два различных варианта сопоставления Env1 и Env2. Рассматриваются все вхождения переменных в P.

Если P имеет указатель направления $l, то отыскивается самое первое слева вхождение, которое принимает для двух вариантов сопоставления Env1 и Env2 различные значения.

Если P имеет указатель направления $r, то отыскивается самое первое справа вхождение, которое принимает для двух вариантов сопоставления Env1 и Env2 различн ые значения.

Пусть найденное вхождение является вхождением переменной V. Тогда если Env1(V) короче чем Env2(V), считается, что Env1 предшествует Env2. В противном случае считается, что Env2 предшествует Env1.

Конечную последовательность сред Env1, Env2, ..., Envn будем записывать в виде [Env1, Env2, ... , Envn], пустую последовательность - в виде [].

Запись [Env0]^[Env1,...,Envn] будет обозначать [Env0, Env1,..., Envn].

Запись Env0 |- Oe : P => [Env1,...Envn] будет означать, что Match(Env0,Oe,P) = {Env1,...,Envn} и при этом Envi предшествует Envj для всех i<j.

8.3. Примеры

Ниже приведены примеры образцов:

          t.Head e.Tail
          eX (eY)
          eA '+' eB
          $l eA '+' eB
          $r eA '+' eB

Далее приведены примеры сопоставления с образцом:

{} |- A () C D E : $l sX tY tZ e1
     =>  [ {sX = A, tY = (), tZ = C, e1 = D E} ]

{} |- 1 2 3 : $l eA eB =>  [
                     {eA = ,         eB = 1 2 3},
                     {eA = 1,        eB = 2 3},
                     {eA = 1 2,      eB = 3},
                     {eA = 1 2 3,    eB = }  ]

{} |- 1 2 3 : $r eA eB => [
                     {eA = 1 2 3,    eB =       },
                     {eA = 1 2,      eB = 3     },
                     {eA = 1,        eB = 2 3   },
                     {eA = ,         eB = 1 2 3 }  ]

{eA = 1 2} |- $l 1 2 3 4 5 : eA eB
     =>  [ {eA = 1 2, eB = 3 4 5} ]

9. Жесткие выражения

9.1. Синтаксис

$    ЖесткоеВыражение =
$         { ЖесткийКрай } |
$         { ЖесткийКрай } e-переменная { ЖесткийКрай } |
$         { ЖесткийКрай } v-переменная { ЖесткийКрай }.
$    ЖесткийКрай = { ЖесткийТерм | ИмяВыражения }.
$    ЖесткийТерм =
$         СтатическийСимвол | s-переменная | t-переменная |
$         "(" ЖесткоеВыражение ")".

Таким образом жесткое выражение на каждом уровне скобок содержит не более чем одну e-переменную или v-переменную.

Индексы всех переменных, входящих в одно и то же жесткое выражение, должны быть попарно различны.

В дальнейшем мы будем обозначать жесткие выражения через He, а жесткие термы - через Ht.

9.2. Сопоставление с жестким выражением

Любое жесткое выражение He представляет собой частный случай образцового выражения. Его особенностью является то, что для любого объектного выражения Oe либо сопоставление Oe с He невозможно, либо может быть сделано только одним способом. Таким образом, имеет место либо {} |- Oe : He => [ ], либо {} |- Oe : He => [Env].

Запись Env |- Oe :: He => Env' будет означать, что {} |- Oe : He => Env" и Env' = Env+Env", т.е. что Env' получается из Env следующим образом. Сначала Ое сопоставляется с He в пустой среде. Т.е. прежние значения переменных игнорируются. В результате получается среда Env", которая содержит значения для переменных из He. После этого исходная среда Env корректируется в соответствии с новыми значениями переменных из He, в результате чего получается новая среда Env'.

9.3. Примеры

Ниже приведены примеры жестких выражений:

          t.Head e.Tail
          sX (eY) eZ (A eA)

Далее приведены примеры сопоставления с жесткими выражениями:

{sX = XXX, eA = A B C}  |-  X Y Z :: sY eA
     =>  {sX = XXX, eA = Y Z, sY = X}

{sX = XXX, eA = A B C}  |-  X Y Z :: eA sY
     =>  {sX = XXX, eA = X Y, sY = Z}

10. Тропы

10.1. Синтаксис

$    Тропа =
$         Условие | Присваивание | Поиск | Перестройка |
$         Хвост | Источник.

$    Условие =
$         Источник Хвост.
$    Присваивание =
$         Источник "::" ЖесткоеВыражение [ Хвост ].
$    Поиск =
$         Источник "$iter" Источник
$              [ "::" ЖесткоеВыражение ] [ Хвост ].
$    Перестройка =
$         Источник ":" Образец [ Хвост ].

$    Хвост =
$         ОгражденнаяТропа | ОтрицаниеУсловия |
$         Забор | Отсечение |
$         Тупик | ПраваяЧасть | Авария |
$         ПерехватАварий.

$    ОгражденнаяТропа =
$         "," Тропа.
$    ОтрицаниеУсловия =
$         "#" Источник [ Хвост ].
$    Забор =
$         "\?" Тропа.
$    Отсечение =
$         "\!" Тропа.
$    Тупик =
$         "$fail".
$    ПраваяЧасть =
$         "=" Тропа.
$    Авария =
$         "$error" Тропа.
$    ПерехватАварий =
$         "$trap" Тропа "$with" ОбразцовоеРаспутье.

$    Источник =
$         Распутье | Выбор | РезультатноеВыражение.

$    Распутье =
$         "\{" ПослТроп "}" |
$          "{" ПослТроп "}".

$    Выбор =
$         Источник ":" ОбразцовоеРаспутье.

$    ОбразцовоеРаспутье =
$         "\{" ПослПредложений "}" |
$         " {" ПослПредложений "}" |

$    ПослТроп = { Тропа ";" }.

$    ПослПредложений =
$         { Предложение ";" }.

$    Предложение = Образец [ Хвост ].

В дальнейшем мы будем обозначать тропы через Q, хвосты - через R, источники - через S, образцовые распутья - через Palt, а предложения - через Snt.

Синтаксис троп выглядит несколько запутанным. Это вызвано стремлением избавить пользователя от необходимости писать лишние разделители в тех случаях, когда в этом нет реальной необходимости.

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

10.2. Вычисление троп

Вычисление тропы Q производится при условии, что задана среда Env и целое неотрицательное число m. Среда Env содержит значения переменных, которые могут потребоваться в процессе вычисления тропы. Число m, именуемое уровнем тропы, характеризует степень вложенности тропы в заборы, т.е. количество заборов "\?", окружающих Q, еще не закрытых отсечениями "\!".

Если вычисление тропы заканчивается, то результатом вычисления является либо объектное выражение Oe, либо неуспех $fail(k), где целое неотрицательное k характеризует "степень серьезности" неуспеха, либо ошибка $error(Oe), где Oe - сообщение об ошибке.

Если тропа находится на уровне m, а результатом ее вычисления является неуспех $fail(k), "серьезность неуспеха" всегда удовлетворяет условию 0 <= k <= m+1. В частности, если тропа находится на уровне 0, всегда либо k=0, либо k=1.

В дальнейшем запись Env,m,St |- Q => X,St' означает, что если тропа Q находится на уровне m, то результатом ее вычисления в среде Env является X, причем если вычисление тропы Q началось в глобальном состоянии St, то оно завершится в глобальном состоянии St'.

Хвосты и источники являются частными случаями троп, поэтому это же обозначение используется и применительно к вычислению хвостов и троп.

Во многих случаях смысл тропы Q может быть объяснен через смысл другой тропы Q'. А именно, чтобы вычислить тропу Q, следует вычислить тропу Q', и то, что получится, следует считать результатом вычисления тропы Q. Формально это можно выразить с помощью следующего правила вывода:

     Env,m,St |- Q' => X,St'
     -----------------------
     Env,m,St |- Q => X,St'

Поскольку такие правила встречаются довольно часто, мы будем в дальнейшем записывать их в сокращенном виде следующим образом:

     Q =>=> Q'

10.3. Условия

Тропа S R означает, что следует вычислить источник S, а затем, в случае успеха, вычислять хвост R.

     Env,0,St |- S => ,St'
     Env,m,St'|- R => X,St"
     ------------------------
     Env,m,St |- S R => X,St"

     Env,0,St |- S => $fail(k),St'
     -------------------------------
     Env,m,St |- S R => $fail(0),St'

     Env,0,St |- S => $error(Oe),St'
     ---------------------------------
     Env,m,St |- S R => $error(Oe),St'

10.4. Присваивания

Тропа S :: He R позволяет вычислить источник S и связать полученные результаты с переменными в He. В результате получается новая среда, в которой и вычисляется хвост R.

Считается, что источник S находится на нулевом уровне.

Если хвост R является огражденной пустой тропой (всегда вырабатывающей пустое выражение), он может быть опущен.

     S :: He  =>=>  S :: He ,

     Env,0,St |- S => Oe,St'
     Env |- Oe :: He => Env'
     Env',m,St' |- R => X,St"
     ------------------------------
     Env,m,St |- S :: He R => X,St"

     Env,0,St |- S => $fail(k),St'
     -------------------------------------
     Env,m,St |- S :: He R => $fail(0),St'

     Env,0,St |- S => $error(Oe),St'
     ---------------------------------------
     Env,m,St |- S :: He R => $error(Oe),St'

Например, результатом выполнения тропы

     100 :: sN, <"+" sN 1> :: sN = sN

является число 101.

10.5. Поиски

Тропа

          S" $iter S' :: He R

означает, что для переменных из He следует подобрать такие значения, что попытка вычислить R успешно завершится. При этом полученный результат и будет результатом всей конструкции.

Если жесткое выражение He - пустое, оно может быть опущено вместе с ключевым словом "::". Если хвост R является огражденной пустой тропой (всегда вырабатывающей пустое выражение), он может быть опущен.

     S" $iter S'  =>=>  S" $iter S' :: ,

     S" $iter S' R  =>=>  S" $iter S' :: R

     S" $iter S' :: He  =>=>  S" $iter S' :: He ,

Источник S" служит для вычисления начальных значений переменных из He, а источник S' служит для вычисления новых значений переменных из He на основе их предыдущих значений.

Считается, что источники S" и S' находятся на нулевом уровне.

Подбор значений переменных делается следующим образом. Сначала для переменных вычисляются начальные значения. Для этого вычисляется значение источника S" и полученное объектное выражение Oe сопоставляется с образцом He. Затем делается попытка вычислить R в новой среде. Если эта попытка заканчивается неуспехом $fail(0), то вычисляется S' и полученное объектное выражение вновь сопоставляется с He, после чего опять делается попытка вычислить R и.т.д.

     S" $iter S' :: He R  =>=>
               S" :: He, \{ R; S' $iter S' :: He R; }

Например, если значения переменных eA и eB еще не определены, перестройка

eX : $l eA eB,
  <Writeln eA>, <Writeln eB> $fail

эквивалентна поиску

()(eX)
  $iter \{ eB : t1 e2 = (eA t1)(e2); }
    :: (eA)(eB),
  <Writeln eA>, <Writeln eB> $fail

10.6. Перестройки

Тропа S : P R имеет следующий смысл. Следует вычислить источник S и сопоставить полученное объектное выражение Oe с образцом P. В результате получится, вообще говоря, несколько вариантов сопоставления. Затем следует попытаться найти самый первый из вариантов сопоставления, для которого вычисление хвоста R завершается успешно.

Если хвост R является огражденной пустой тропой (всегда вырабатывающей пустое выражение), он может быть опущен.

Для описания семантики перестройки нам понадобится следующее обозначение. Запись EnvList,m,St ||- Q => X,St' означает, что если тропа Q находится на уровне m, то результатом ее вычисления для списка сред EnvList является X.

     Env,m,St |- Q => Oe,St'
     ----------------------------------
     [Env]^EnvList,m,St ||- Q => Oe,St'

     Env,m,St |- Q => $fail(0),St'
     EnvList,m,St' ||- Q => X,St"
     ---------------------------------
     [Env]^EnvList,m,St ||- Q => X,St"

     Env,m,St |- Q => $fail(k+1),St'
     ------------------------------------------
     [Env]^EnvList,m,St ||- Q => $fail(k+1),St'

     Env,m,St |- Q => $error(Oe),St'
     ------------------------------------------
     [Env]^EnvList,m,St ||- Q => $error(Oe),St'

     [],m,St ||- Q => $fail(0),St.

Теперь мы можем описать семантику перестройки.

     S : P  =>=>  S : P ,

     Env,0,St |- S => Oe,St'
     Env |- Oe : P => EnvList
     EnvList,m,St' ||- R => X,St"
     ----------------------------
     Env,m,St |- S : P R => X,St"

     Env,0,St |- S => $fail(k),St'
     -----------------------------------
     Env,m,St |- S : P R => $fail(0),St'

     Env,0,St |- S => $error(Oe),St'
     -------------------------------------
     Env,m,St |- S : P R => $error(Oe),St'

Например, вычисление приведенной ниже тропы заканчивается неуспехом. При этом печатается цепочка литер 'CBA':

'ABC' : $r e sX e, <Print sX> $fail

10.7. Огражденные тропы

Вычисление хвоста

          , Q

всегда дает тот же результат, что и вычисление тропы Q.

     , Q  =>=>  Q

10.8. Отрицания условий

Хвост # S R означает, что следует вычислить S, а затем взять "логическое отрицание" полученного результата.

Если хвост R является огражденной пустой тропой (всегда вырабатывающей пустое выражение), он может быть опущен.

     # S  =>=>  # S ,

     Env,0,St |- S => ,St'
     ---------------------------------
     Env,m,St |- # S R => $fail(0),St'

     Env,0,St |- S => $fail(k),St'
     Env,m,St' |- R => X,St"
     -----------------------------
     Env,m,St |- # S R => X,St"

     Env,0,St |- S => $error(Oe),St'
     -----------------------------------
     Env,m,St |- # S R => $error(Oe),St'

10.9. Заборы

Хвост \? Q означает, что если при вычислении тропы Q возникнет неуспех с ненулевой "серьезностью", следует уменьшить "серьезность" на единицу. При этом считается, что уровень тропы Q на единицу больше, чем уровень всей конструкции.

     Env,m+1,St |- Q => Oe,St'
     --------------------------
     Env,m,St |- \? Q => Oe,St'

     Env,m+1,St |- Q => $fail(0),St'
     --------------------------------
     Env,m,St |- \? Q => $fail(0),St'

     Env,m+1,St |- Q => $fail(k+1),St'
     ---------------------------------
     Env,m,St |- \? Q => $fail(k),St'

     Env,m+1,St |- Q => $error(Oe),St'
     ----------------------------------
     Env,m,St |- \? Q => $error(Oe),St'

10.10. Отсечения

Хвост \! Q означает, что если при вычислении тропы Q возникнет неуспех, нужно увеличить "серьезность" неуспеха на единицу. При этом считается, что уровень тропы Q на единицу меньше, чем уровень всей конструкции.

     Env,m,St |- Q => Oe,St'
     ----------------------------
     Env,m+1,St |- \! Q => Oe,St'

     Env,m,St |- Q => $fail(k),St'
     ------------------------------------
     Env,m+1,St |- \! Q => $fail(k+1),St'

     Env,m,St |- Q => $error(Oe),St'
     ------------------------------------
     Env,m+1,St |- \! Q => $error(Oe),St'

Например, в результате вычисления тропы, приведенной ниже, будет напечатана цепочка литер 'ABD' и выдан результат '2'.

{
  \? {
    <Print 'A'> $fail;
    <Print 'B'> \! $fail;
    <Print 'C'> = '1';
    };
  <Print 'D'> = '2';
  }

10.11. Тупики

Вычисление хвоста $fail всегда дает $fail(0), т.е. неуспех серьезности 0.

     Env,m,St |- $fail => $fail(0),St

10.12. Правые части

Хвост = Q означает, что перед вычислением тропы Q следует начать "новую жизнь", т.е. считать, что Q находится на нулевом уровне. Если в результате вычисления Q получится неуспех $fail(k), то результатом хвоста = Q является $fail(m+1), где m - уровень, на котором находится хвост = Q. Таким образом, вырабатывается неуспех, силы которого достаточно, чтобы пробить все заборы, которые еще не отменены с помощью отсечений.

     Env,0,St |- Q => Oe,St'
     -------------------------
     Env,m,St |- = Q => Oe,St'

     Env,0,St |- Q => $fail(k),St'
     ---------------------------------
     Env,m,St |- = Q => $fail(m+1),St'

     Env,0,St |- Q => $error(Oe),St'
     ---------------------------------
     Env,m,St |- = Q => $error(Oe),St'

10.13. Аварии

Хвост $error Q позволяет породить ошибку $error(Oe), где объектное выражение Oe является результатом вычисления тропы Q.

     Env,0,St |- Q => Oe,St'
     --------------------------------------
     Env,m,St |- $error Q => $error(Oe),St'

     Env,0,St |- Q => $fail(0),St'
     -----------------------------------------------------------
     Env,m,St |- $error Q => $error(Fname "Unexpected fail"),St'
          Fname - имя функции, в которой находится конструкция.

     Env,0,St |- Q => $error(Oe),St'
     --------------------------------------
     Env,m,St |- $error Q => $error(Oe),St'

10.14. Перехваты аварий

Хвост

          $trap Q $with Palt

означает, что следует попытаться вычислить Q. Если результатом этого вычисления является $error(Oe), то дальше вычисляется выбор

          Oe : Palt

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

Считается, что тропа Q находится на нулевом уровне.

     Env,0,St |- Q => Oe,St'
     ----------------------------------------
     Env,m,St |- $trap Q $with Palt => Oe,St'

     Env,0,St |- Q => $fail(k),St'
     Env,m,St' |- Fname "Unexpected fail" : Palt => X,St"
     ----------------------------------------------------
     Env,m,St |- $trap Q $with Palt => X,St"
          Fname - имя функции, в которой находится конструкция.

     Env,0,St |- Q => $error(Oe),St'
     Env,m,St' |- Oe : Palt => X,St"
     ---------------------------------------
     Env,m,St |- $trap Q $with Palt => X,St"

10.15. Распутья

Источник \{Q1; Q2; ... Qn;} означает, что следует вычислять тропы Q1, Q2, ..., Qn слева направо, пока не удастся найти тропу, вычисление которой завершится успешно.

А именно, рассмотрим результат вычисления очередной тропы Qj.

Если результат - объектное выражение Oe, то Oe считается результатом всего распутья. Если результат - $error(Oe), то $error(Oe) является результатом всего распутья. Если результат - $fail(k+1), то результатом вычисления всего распутья является $fail(k+1). И, наконец, если результат - $fail(0), то этот неуспех "перехватывается", т.е. делается попытка вычислить следующую тропу. Если же следующей тропы не существует (т.е. j=n), то результатом вычисления всей тропы является неуспех $fail(0).

Распутье вида {Q1; Q2; ... Qn;} эквивалентно распутью \{Q1; Q2; ... Qn; $error(Fname "Unexpected fail");}. Fname - имя функции, в которой находится конструкция.

     {Q1; Q2; ... Qn;}  =>=>
               \{Q1; Q2; ... Qn;
                    $error(Fname "Unexpected fail");}
          Fname - имя функции, в которой находится конструкция.

     Env,m,St |- \{} => $fail(0),St

     Env,m,St |- Q1 => Oe,St'
     ----------------------------------------
     Env,m,St |- \{Q1; Q2; ... Qn;} => Oe,St'

     Env,m,St |- Q1 => $fail(0),St'
     Env,m,St'|- \{Q2; ... Qn;} => X,St"
     ---------------------------------------
     Env,m,St |- \{Q1; Q2; ... Qn;} => X,St"

     Env,m,St |- Q1 => $fail(k+1),St'
     ------------------------------------------------
     Env,m,St |- \{Q1; Q2; ... Qn;} => $fail(k+1),St'

     Env,m,St |- Q1 => $error(Oe),St'
     ------------------------------------------------
     Env,m,St |- \{Q1; Q2; ... Qn;} => $error(Oe),St'

10.16. Выборы

Вычисление источника S : \{Snt1; ... Sntn;} всегда дает тот же результат, что и вычисление тропы S : Ve, \{Ve : Snt1; ... Ve : Sntn;}, при условии, что Ve - некоторая e-переменная, которая больше нигде не используется в программе.

Источник S : {Snt1; ... Sntn;} эквивалентен источнику S : \{Snt1; ... Sntn; e $error(Fname "Unexpected fail");}, где Fname - имя функции, в которой находится данная конструкция.

     S : {Snt1; ... Sntn;}  =>=>
               S : \{Snt1; ... Sntn;
                         e $error(Fname "Unexpected fail");}
          Fname - имя функции, в которой находится конструкция.

     Env,0,St |- S => Oe,St'
     Env,m,St'|- \{Oe : Snt1; ... Oe : Sntn;} => X,St"
     -------------------------------------------------
     Env,m,St |- S : \{Snt1; ... Sntn;} => X,St"

     Env,0,St |- S => $fail(k),St'
     --------------------------------------------------
     Env,m,St |- S : \{Snt1; ... Sntn;} => $fail(0),St'

     Env,0,St |- S => $error(Oe),St'
     ----------------------------------------------------
     Env,m,St |- S : \{Snt1; ... Sntn;} => $error(Oe),St'

10.17. Результатные выражения как источники

Источник вида Re означает, что следует попытаться вычислить Re, и то, что получится, считать результатом вычисления источника.

     Env,St |- Re => X,St'
     -----------------------
     Env,m,St |- Re => X,St'

11. Определения функций

$    ОпределениеФункции =
$         ИмяФункции ТелоФункции ";".
$    ТелоФункции =
$         ОбразцовоеРаспутье | Предложение.

Определение функции связывает имя функции с ее телом, т.е. конструкцией, описывающей способ ее вычисления.

Если определение функции имеет вид Fname Snt; , оно эквивалентно определению Fname \{ Snt; }; .

Пусть определение функции Fname имеет вид

          Fname Palt

Тогда вычисление вызова этой функции, имеющего вид <Fname Oe> сводится к вычислению источника Oe : Palt. Если при этом получается объектное выражение Oe' или ошибка $error(Oe'), они и считаются результатом вычисления вызова. Если же получается неуспех $fail(k), то дальнейшие действия зависят от того, была ли функция Fname объявлена как откатная или безоткатная. Для откатной функции в качестве результата выдается $fail(0), а для безоткатной - $error(Fname "Unexpected fail").

     {},0,St |- Oe : Palt => Oe',St'
     -------------------------------
     St |- <Fname Oe> => Oe',St'

     {},0,St |- Oe : Palt => $fail(k),St'
     ------------------------------------
     St |- <Fname Oe> => $fail(0),St'
          где функция Fname - откатная, т.е. объявлена как
          $func? Fname Farg = Fres;.

     {},0,St |- Oe : Palt => $fail(k),St'
     -------------------------------------------------------
     St |- <Fname Oe> => $error(Fname "Unexpected fail"),St'
          где функция Fname - безоткатная, т.е. объявлена как
          $func Fname Farg = Fres;.

     {},0,St |- Oe : Palt => $error(Oe'),St'
     ---------------------------------------
     St |- <Fname Oe> => $error(Oe'),St'

В вышеприведенных правилах вывода предполагается, что функция Fname имеет определение Fname Palt.

12. Объявления

12.1. Объявления констант

$    ОбъявлениеКонстант =
$         "$const" [ ОбъКонст { "," ОбъКонст } ] ";".
$    ОбъКонст = ИмяВыражения "=" КонстантноеВыражение.
$    КонстантноеВыражение =
$         { КонстантныйТерм | ИмяВыражения }.
$    КонстантныйТерм =
$         СтатическийСимвол | "(" КонстантноеВыражение ")".

Объявления констант позволяют вводить для объектных выражений символические имена, с тем чтобы в дальнейшем использовать их вместо самих выражений. В качестве имен используются слова. Если некоторому объектному выражению Oe присвоено имя N, то в дальнейшем конструкция &N является изображением этого выражения. Например, следующее объявление вводит три имени объектных выражений:

$const LF = 10, CR = 13, "***" = A B C;

после чего &LF обозначает 10, &CR обозначает 13, а &"***" обозначает A B C.

Объявление константы само может ссылаться на предшествующие объявления констант, ящиков, таблиц, каналов и функций. Например, после объявления

$const "CR-LF-***" = &CR &LF &"***";

&"CR-LF-***" начинает обозначать выражение  13 10 A B C.

12.2. Объявления ящиков, векторов, строк, таблиц и каналов

$    ОбъявлениеЯщиков   = "$box"     { ИмяСсылки } ";".
$    ОбъявлениеВекторов = "$vector"  { ИмяСсылки } ";".
$    ОбъявлениеСтрок    = "$string"  { ИмяСсылки } ";".
$    ОбъявлениеТаблиц   = "$table"   { ИмяСсылки } ";".
$    ОбъявлениеКаналов  = "$channel" { ИмяСсылки } ";".

$    ИмяСсылки = Слово.

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

Например, после объявления $box X; конструкция &X обозначает символ-ссылку на ящик. Ниже приведены примеры объявлений:

$box B1 B2 B3;
$vector V1 V2;
$table T1 T2;
$channel Input Output;

12.3. Объявления функций

$    ОбъявлениеФункции =
$         "$func"   ИмяФункции
$              ВходнойФормат "=" ВыходнойФормат ";" |
$         "$func?"  ИмяФункции
$              ВходнойФормат "=" ВыходнойФормат ";".
$    ИмяФункции = Слово.
$    ВходнойФормат = ФорматноеВыражение.
$    ВыходнойФормат = ФорматноеВыражение.

$    ФорматноеВыражение = ЖесткоеВыражение.

Объявление функции вводит символическое имя для функции и должно предшествовать как определению функции, так и всем использованиям ее имени.

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

Входной и выходной форматы должны быть жесткими, т.е. на каждом уровне скобок может находиться максимум одна e-переменная или v-переменная.

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

Если в объявлении функции использовано ключевое слово $func, это означает, что функция - безоткатная, т.е. ее вычисление может завершиться либо успешной выдачей результата, либо выдачей ошибки.

Если в объявлении функции использовано ключевое слово $func?, это означает, что функция - откатная, т.е. ее вычисление может завершиться либо успешной выдачей результата, либо выдачей неуспеха, либо выдачей ошибки.

Например:

$func  Interpreter (e.Program) (e.Input) = e.Result;
$func? Attempt t.Arg = s.Result1 t.Result2 (e.Result3);

12.4. Директивы отладки

$    ДирективаОтладки =
$         "$trace" { ИмяФункции } ";" |
$         "$traceall" ";".

Директива отладки "$trace" означает, что в процессе выполнения программы для функций, имена которых перечислены в директиве, следует печатать отладочную информацию: имя функции и ее аргументы в момент обращения к ней, а также ее результаты в момент выхода из нее. Директива "$traceall" означает, что следует печатать отладочную информацию для всех последующих функций.

13. Контекстные ограничения

13.1. Устранение избыточных конструкций

В этом разделе мы описываем различные контекстные синтаксические ограничения, которым должна удовлетворять любая программа не Рефале Плюс.

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

Хвосты и жесткие образцы, опущенные в присваиваниях, поисках и перестройках, заменены на пустые образцы и пустые огражденные тропы следующим образом:

     S :: He             =>        S :: He ,
     S' $iter S"         =>        S' $iter S" ::  ,
     S' $iter S" :: He   =>        S' $iter S" :: He ,
     S' $iter S" R       =>        S' $iter S" ::  R
     S : P               =>        S : P ,
     # S                 =>        # S ,

Хвосты, опущенные в предложениях, заменены на пустые огражденные тропы следующим образом:

     P                   =>        P ,

"Непрозрачные" фигурные скобки "{" заменены на прозрачные фигурные скобки "\{" в распутьях и выборах следующим образом:

     {Snt1; ... Sntn;}   =>
          \{Snt1; ... Sntn;
                    $error(Fname "Unexpected fail");}

     S : {Snt1; ... Sntn;}   =>
          S : \{Snt1; ... Sntn;
                    e $error(Fname "Unexpected fail");}

где Fname - имя функции, в которой находится конструкция.

"Непрозрачные" фигурные скобки "{" заменены на прозрачные фигурные скобки "\{" в определениях функций следующим образом:

     Fname {Snt1; ... Sntn;}  =>
          Fname \{Snt1; ... Sntn;
                    Farg $error(Fname "Unexpected fail");}

где Farg - входной формат функции из объявления функции Fname (в котором опущены индексы переменных).

Тела функций, являющиеся предложениями, заменены на соответствующие образцовые распутья:

     Fname Snt;     =>   Fname \{ Snt; };

13.2. Ограничения налагаемые объявлениями функций

Объявления функций имеют вид

$func  Farg = Fres;
$func? Farg = Fres;

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

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

Пусть F1 и F2 два формата. Запись F2>>F1 будет означать, что формат F1 является (частным) случаем формата F2. Отношение >> определяется следующими правилами.

     (0)  F >> F.
     (1)  Если F1' >> F1 и F2' >> F2, то F1' F2' >> F1 F2.
     (2)  Если F1 >> F2, то (F1) >> (F2).
     (3)  e >> F.
     (4)  Если F не имеет вида e e ... e, то v >> F.
     (5)  t >> Os, для любого символа Os.
     (6)  t >> s.
     (7)  t >> (F).
     (8)  s >> Os, для любого символа Os.

Если в программе имеется результатное выражение Re, то его форматом считается форматное выражение F, которое получается из Re следующим образом.

(1) У всех переменных, входящих в Re, отбрасываются индексы.

(2) Вызовы всех функций, появляющиеся в Re, заменяются на выходные форматы этих функций. А именно, если в Re имеется вызов функции вида <Fname Re'>, a объявление функции Fname имеет вид $func Fname Farg = Fres; либо $func? Fname Farg = Fres;, то <Fname Re'> заменяется на Fres.

Если в программе имеется образец P, то его форматом считается форматное выражение F, которое получается из P следующим образом.

(1) У всех переменных, входящих в P отбрасываются индексы.

(2) Если P имеет указатель направления сопоставления, то этот указатель отбрасывается.

Если в программе имеется жесткое выражение He, то его форматом считается форматное выражение F, которое получается из He в результате отбрасывания индексов у всех переменных, входящих в He.

В дальнейшем form[Re] будет обозначать формат результатного выражения Re, form[P] - формат образца P, а form[He] - формат жесткого выражения He.

Следует подчеркнуть, что формат результатного выражения Re зависит не только от внешнего вида выражения Re, но и от выходных форматов тех функций, вызовы которых содержатся в Re. Тем не менее, для каждой конкретной программы form[Re] определен однозначно.

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

Пусть объявление функции Fname имеет входной формат Farg, выходной формат Fres, а в ее определении

          Fname Palt

образцовое распутье Palt имеет вид \{P1 R1; ... Pn Rn;}.

Тогда должны быть выполнены следующие условия.

Входные образцы функции P1, ..., Pn должны удовлетворять следующему ограничению: Farg >> form[Pj].

Все вызовы функции Fname во всех определениях функций должны удовлетворять следующему ограничению.

Пусть вызов этой функции имеет вид <Fname Re>. Тогда должно выполнятся условие Farg >> form[Re].

Чтобы описать ограничения, налагаемые на результаты, вырабатываемые тропами, введем следующие обознач ения.

Тот факт, что результаты, вырабатываемые тропой Q, удовлетворяют формату F мы будем записывать в виде F |- Q. Поскольку хвосты, источники и результатные выражения являются частными случаями троп, то же самое обозначение используется и для них.

Точно так же, тот факт, что результаты, вырабатываемые образцовым распутьем Palt, удовлетворяют формату F мы будем записывать в виде F |- Palt.

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

Если функция Fname имеет определение Fname Palt и выходной формат Fres, то должно быть выполнено Fres |- Palt.

Отношения F |- Q и F |- Palt определяются с помощью следующих правил.

     form[] |- S              form[He] |- S
     F |- R                   F |- R
     ------------             ---------------
     F |- S R                 F |- S :: He R

     form[He] |- S"
     form[He] |- S'
     F |- R
     -------------------------
     F |- S" $iter S' :: He R

                                        form[] |- S
     F |- R              F |- Q         F |- R
     -------------       ---------      ------------
     F |- S : P R        F |- , Q       F |- # S R

     F |- Q              F |- Q
     ----------          ----------     F |- $fail
     F |- \? Q           F |- \! Q

     F |- Q
     ---------           F |- $error Q
     F |- = Q

     F |- Q
     F |- Palt
     ------------------------
     F |- $trap Q $with Palt

     F |- Qj  для всех j=1,...,n
     ----------------------------
     F |- \{Q1; ... Qn;}

     F |- Palt           F >> form[Re]
     --------------      --------------
     F |- S : Palt       F |- Re

     F |- Rj  для всех j=1,...,n
     ----------------------------
     F |- \{P1 R1; ... Pn Rn;}

13.3. Ограничения на использование ссылок на функции

Если в образцовом или результатном выражении появляется ссылка на функцию Fname вида &Fname, то эта функция должна быть объявлена как $func Fname e = e или $func? Fname e = e.

13.4. Ограничения на использование переменных

Переменные, появляющиеся в определении функции, должны удовлетворять определенным ограничениям.

А именно, если переменная используется в результатном выражении, она должна быть к этому моменту определена. Определением переменной является ее появление в образце, если к этому моменту она еще не была определена.

Если в каком то месте являются определенными несколько различных переменных, их индексы должны быть попарно различны.

Сформулируем эти требования более точно. Для этого введем следующие обозначения.

vars[X] обозначает множество переменных, входящих в конструкцию X.

{} обозначает пустое множество.

v1+v2 обозначает объединение множеств v1 и v2.

v1++v2 обозначает пополнение множества переменных v1 переменными из v2. А именно, v1++v2 содержит все переменные из v2, а также все переменные из v1, индексы которых отличаются от индексов всех переменных из v2. Например, {sX, sY} ++ {eY, eZ} = {sX, eY, eZ}.

Запись v |- Q означает, что все переменные из v имеют разные индексы, и все переменные, значения которых могут понадобиться для вычисления тропы Q, входят в v. Поскольку хвосты, источники и результатные выражения являются частными случаями троп, то же самое обозначение используется и для них.

Аналогично, запись v |- Palt означает, что все переменные из v имеют разные индексы, и все переменные, значения которых могут понадобиться для вычисления образцового распутья Palt, входят в v.

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

Пусть функция Fname имеет определение Fname Palt. Тогда должно выполняться {} |- Palt.

Отношения v |- Q и v |- Palt определяются с помощью следующих правил.

     v |- S              v |- S
     v |- R              v++vars[He] |- R
     ----------          -----------------
     v |- S R            v |- S :: He R

     v |- S"
     v++vars[He] |- S'             v |- S
     v++vars[He] |- R              v+vars[P] |- R
     -------------------------     ---------------
     v |- S" $iter S' :: He R      v |- S : P R

                         v |- S
     v |- Q              v |- R              v |- Q
     ---------           -----------         ----------
     v |- , Q            v |- # S R          v |- \? Q

     v |- Q                                  v |- Q
     ----------          v |- $fail          ---------
     v |- \! Q                               v |- = Q

                         v |- Q
     v |- Q              v |- Palt
     --------------      ------------------------
     v |- $error Q       v |- $trap Q $with Palt

     v |- Qj  для всех j=1,...,n
     ----------------------------
     v |- \{Q1; ... Qn;}

     v |- S
     v |- Palt
     --------------
     v |- S : Palt

     все переменные из v имеют разные индексы
     все переменные из vars[Re] входят в v
     -----------------------------------------
     v |- Re

     v+vars[Pj] |- Rj  для всех j=1,...,n
     -------------------------------------
     v |- \{P1 R1; ... Pn Rn;}

13.5. Ограничения на использование отсечений

Каждой тропе, входящей в определение функции, может быть поставлено в соответствие целое неотрицательное число k, именуемое ее уровнем. Если двигаться вдоль тропы, то прохождение через "\?" увеличивает текущий уровень на 1, а прохождение через "\!" уменьшает уровень на 1. Таким образом, каждому отсечению "\!" должен однозначно соответствовать некоторый "парный" забор "\?".

Сформулируем это требование более точно. Для этого введем следующие обозначения.

Пусть k - целое неотрицательное число, а Q - тропа. Запись k |- Q означает, что тропе Q может быть приписан уровень k. Поскольку хвосты, источники и результатные выражения являются частными случаями троп, то же самое обозначение используется и для них.

Аналогично, если Palt - образцовое распутье, то запись k |- Palt означает, что образцовому распутью Palt может быть приписан уровень k.

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

Пусть функция Fname имеет определение Fname Palt. Тогда должно выполняться 0 |- Palt.

Отношения k |- Q и k |- Palt определяются с помощью следующих правил.

     0 |- S              0 |- S
     k |- R              k |- R
     ---------           ---------------
     k |- S R            k |- S :: He R

     0 |- S"
     0 |- S'                       0 |- S
     k |- R                        k |- R
     -------------------------     -------------
     k |- S" $iter S' :: He R      k |- S : P R

                         0 |- S
     k |- Q              k |- R              k+1 |- Q
     ---------           -----------         ----------
     k |- , Q            k |- # S R          k |- \? Q

     k |- Q                                  0 |- Q
     ------------        k |- $fail          ---------
     k+1 |- \! Q                             k |- = Q

                         0 |- Q
     0 |- Q              k |- Palt
     --------------      ------------------------
     k |- $error Q       k |- $trap Q $with Palt

     k |- Qj  для всех j=1,...,n
     ----------------------------
     k |- \{Q1; ... Qn;}

     0 |- S
     k |- Palt
     --------------      k |- Re
     k |- S : Palt

     k |- Rj  для всех j=1,...,n
     ----------------------------
     k |- \{P1 R1; ... Pn Rn;}

14. Модули

Каждая программа на Рефале Плюс состоит из одного или нескольких модулей. Каждый модуль состоит из д вух частей: интерфейса модуля и реализации модуля.

Интерфейс модуля содержит те части модуля, которые доступны из других модулей, в то время как реализация модуля содержит те части модуля, которые недоступны из других модулей.

В системе MSDOS каждый модуль MMMM занимает два файла. А именно, интерфейс модуля хранится в файле MMMM.RFI, а реализация - в файле MMMM.RF.

$    ИнтерфейсМодуля =
$         { Объявление }.
$    Объявление =
$         ОбъявлениеКонстант | ОбъявлениеЯщиков |
$         ОбъявлениеВекторов | ОбъявлениеСтрок |
$         ОбъявлениеТаблиц | ОбъявлениеКаналов |
$         ОбъявлениеФункции.

$    РеализацияМодуля =
$         { Импорт } { ДирективаРеализации }.
$    ДирективаРеализации =
$         Объявление |
$         ДирективаОтладки |
$         ОпределениеФункции.

$    Импорт = "$use" { ИмяМодуля } ";".
$    ИмяМодуля = Слово.

Если внутри реализации модуля XXXX требуется получить доступ к именам, объявленным в интерфейсе модуля YYYY, следует поместить внутри реализации модуля XXXX директиву $use YYYY следующим образом:

-----------------------------------------------------------
/* Файл XXXX.RFI */
/* Интерфейс модуля XXXX. */
......
-----------------------------------------------------------
/* Файл XXXX.RF */
$use ... YYYY ... ;
/* С этого места доступны имена, объявленные в YYYY.RFI */
......
-----------------------------------------------------------
/* Файл YYYY.RFI */
/* Интерфейс модуля YYYY. */
......
-----------------------------------------------------------
/* Файл YYYY.RF */
/* Реализация модуля YYYY. */
......
-----------------------------------------------------------

15. Исполнение программы

Программа на Рефале Плюс может состоять из нескольких модулей, один из которых обязательно должен экспортировать функцию Main. Эта функция называется главной функцией программы. Главная функция всегда должна иметь объявление

$func Main = e;

Если же из какого-то модуля экспортируется функция с именем Main имеющая другое объявление, это считается ошибкой.

Исполнение Рефал-программы заключается в вычислении вызова функции Main с пустым аргументом

          <Main >

Модуль, содержащий определение главной функции, может не иметь интерфейсной части, поскольку если компилятор не находит файл, содержащий интерфейс модуля, он считает, что интерфейс модуля состоит из единственного объявляния функции

$func Main = e;
Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r2 < r1 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback