Приложение "Описание подмножества базисного Рефала"
Краткое описание подмножества
Данные, которые обрабатывает Рефал
Основной обрабатываемой структурой данных является объектное выражение. Объектное выражение — это структура данных, представляющая собой последовательность переменной длины (возможно пустую) объектных термов. Объектный терм может представлять собой либо атом — неделимую средствами языка Рефал (без учёта встроенных библиотечных функций) сущность, например, число, символ, имя (идентификатор) или что-либо другое (состав атомов в разных диалектах различается), либо т.н. скобочный терм — терм, содержащий внутри себя другое объектное выражение. Рассмотрим подробнее разные виды термов.1. Атом-число. Представляет абстракцию числа в математике, в зависимости от диалекта могут поддерживаться целые числа ограниченного диапазона, целые числа неограниченной разрядности, действительные числа, при этом атомы целых и действительных чисел различаются.
Примеры чисел: 1, 2222, 1234567890, 3.14, 3e8, -273,15.
Далее будем считать, что наш диалект поддерживает только небольшие целые числа в качестве значений этой разновидности атомов.
2. Атом-символ. Является абстракцией печатного символа как элемента текста, также в зависимости от диалекта может быть как ASCII-, так и UNICODE-символом. Атомы-символы будем записывать, как символы в одинарных кавычках. Если в рефал-выражении несколько символов идут подряд, то будем записывать их слитно, т.е. вместо 'Ж' '0' 'П' 'A' будем записывать 'Ж0ПA'.
3. Атом-идентификатор или атом-имя. В большинстве диалектов представляет собой некоторое имя, представляющее само себя (хотя в некоторых диалектах, например Рефал 2 или Рефал 7, идентификатор представляет и одноимённую функцию из той же области видимости). Как правило, атомы-имена записываются как "слова", начинающиеся с заглавной латинской буквы, после которой следует некоторое (возможно нулевое) количество букв, цифр, знаков _ и -. Будем считать, что регистр идентификаторов различается, т.е. имена Name и NAME различаются.
4. Скобочный терм. Содержит внутри себя объектное выражение, записывается как объектное выражение, окружённое круглыми скобками. Например (Position 102 'filename.ext') представляет собой скобочный терм.
Другие диалекты могут поддерживать ряд других значений атомов, например, замыкания, дескрипторы файлов или других объектов, ссылки на статические или динамические объекты. Если это будет необходимо, расскажем об этом по-подробнее.
Объектное выражение записывается как перечисление содержащих его термов без каких-либо разделителей. Например Identifier (Position 102 'filename.ext') 'Name' представляет собой выражение из 6 термов, первый из которых является именем, второй — скобочным термом, последние четыре — символы. Второй терм содержит внутри себя выражение, содержащее имя, число и 12 символов.
Само по себе понятие объектного выражения статично, поэтому для описания выполнения программы в динамике вводятся два расширения: введение активных термов и введение переменных, заменяющих некоторые неизвестные части объектного выражения.
Объектное выражение, пополненное активными термами, называется активным выражением, объектное выражение, пополненное переменными, называется образцовым выражением, объектное выражение, пополненное и тем и другим, называется результатным выражением. Множество объектных выражений является подмножеством множеств активных, образцовых и результатных выражений, множества активных и образцовых выражений являются подмножествами множества результатных выражений.
Активным термом называется конструкция записи вызова функции, записывается как активное (или результатное) выражение, слева от которого находится открывающая угловая скобка и имя функции, записанное непосредственно за ней, а справа — закрывающая угловая скобка. Угловые скобки называются скобками активации, скобками конкретизации или скобками вызова функции. Выражение, находящееся между скобками активации, является аргументом функции. Примеры активных термов: <Factorial 100>, <Length 'Some string'>, <Mul 10 <Fact <Sub 10 1>>>.
Активное или результатное выражение, будем называть пассивным, если оно не содержит скобок активации.
Переменные — это специальный вид термов, который может заменять некоторые части выражения. Обычно вводится 3 вида переменных: e-переменные, которые могут принимать значения любого объектного выражения, t-переменные, способные принимать значения любого объектного терма и s-переменные, способные принимать значения любого атома. Некоторые диалекты вводят v-переменные, которые могут принимать значения только непустого (содержащего не менее одного терма) выражения. В примерах кода ниже мы не будем пользоваться v-переменными. Переменная записывается как вид.имя, где имя — непустая последовательность латинских букв, цифр и знаков '- и '_. Таким образом t.1, s.Number, e.Begin и t.SymTable являются именами переменных.
При подстановке вместо переменных соответствующих значений из образцового выражения получается объектное выражение, из результатного выражения — активное выражение. Например, при подстановке в образцовое выражение e.Begin 'мыла' e.End значений переменных e.Begin == 'Мама ' и e.End == ' раму', получим объектное выражение 'Мама мыла раму'. При подстановке в результатное выражение <Mul s.N <Fact <Dec s.N>>> вместо переменной s.N значения 10 получим активное выражение <Mul 10 <Fact <Dec s.N>>>.
Семантика выполнения программы
Семантику Рефала принято описывать вводя понятие абстрактной рефал-машины. Рефал-машина содержит две области памяти: поле зрения, которое содержит обрабатываемые данные и полностью описывает состояние вычислений и поле програмы, содержащее определения всех функций программы. Структура поля зрения представляет собой активное выражение. Рефал-машина производит вычисление за ряд дискретных шагов. За один шаг рефал-машина выбирает крайне левый терм активации, не содержащий внутри себя других термов активации (т.е. пассивное рефал-выражение) и вызывает функцию, которая находится справа от открывающей скобки активации с аргументом, находящимся внутри этого терма. Такой терм называется первичным. В результате выполнения функция возвращает некоторое активное выражение, на которое и заменяется терм активации фукнции. На этом шаг заканчивается. Как не трудно догадаться, рефал-машина производит вычисления до тех пор, пока поле зрения не станет пассивным.А теперь, про то, как выполняются функции. Функция на Рефале (как и прежде, здесь под Рефалом понимается подмножество базисного Рефала), представляет собой набор предложений, причём под предложением понимается пара вида образец = результат, где образец и результат — это, соответственно, образовое и результатное выражение. Далее по тексту для определения функций будем использовать запись, показанную на листинге BAD TAG: listno: funsyntax, т.е. предложения отделяются друг от друга точкой с запятой, последовательность выражений заключена в фигурные скобки. На имя функции накладываются те же ограничения, что и на атом-имя.
/* Листинг 1 */
ИмяФункции {
Образец1 = Результат1;
Образец2 = Результат2;
......................
ОбразецN = РезультатN
}Семантика выполнения функции основана на понятиях сопоставления с образцом и замены на результат. Под сопоставлением объектного выражения OE с образцовым выражением PE (обозначается OE : PE) называется поиск таких значений переменных из PE, которые при подстановке в образец PE превратят его в OE. Если таких значений переменных не существует, то говорят, что сопоставление невозможно. Распространена ситуация, когда существует несколько различных подстановок значений переменных в PE, дающих в результате OE. В таком случае выбирается та подстановка, при котором крайняя левая переменная принимает кратчайшее значение. Если это условие не разрешает противоречия, выбирается следующяя по счёту подстановка.
Пример.
20 '-' 12 '-' 3 '-' 1 : e.1 '-' e.2 '-' e.3
даёт 3 разных подстановки
e.1 == 20, e.2 == 12, e.3 = 3 '-' 1 e.1 == 20, e.2 == 12 '-' 3, e.3 = 1 e.1 == 20 '-' 12, e.2 == 3, e.3 = 1
Кратчайшим значением переменной e.1 (которая является самой левой) является значение 20, но это не разрешает противоречия, т.к. в этом случае остаются два варианта подстановки. Выбирая кратчайшее значение 12 для второй слева переменной e.2 получаем единственную подстановку e.1 == 20, e.2 == 12, e.3 = 3 '-' 1.
Выполнение функции выполняется в следующем порядке. Область видимости функции инициализируется пустым множеством. Выполняется сопоставление аргумента функции с первым образцом. При успешном сопоставлении с образцом область видимости пополняется переменными образца и производится подстановка найденных значений переменных в результат. Таким образом, в результате не могут находиться переменные, отсутствующие в области видимости (в случае базисного Рефала — в образце данного выражения). Активное выражение, полученное в результате подстановки, становится результатом выполнения функции. Если сопоставление с первым образцом завершилось неуспешно, аналогичным образом происходит выполнение второго предложение – сопоставление со вторым образцом и в случае успешного сопоставление — подстановка переменных во второй результат. Аналогичным образом обрабатываются и остальные предложения функции.
В случае неуспешности выполнения всех образцов функции генерируется ошибка невозможности распознавания, которая приводит к остановке всей рефал-машины. Ряд диалектов Рефала (Рефал 2, Рефал 5, Модульный и Простой Рефалы) в этой ситуации делают дамп всего поля зрения, чтобы программист мог найти ошибку в программе.
Описание сопоставления выше (подбор таких значений переменных, подстановка которых в образец даёт аргумент функции) ничего не говорит ни о конкретном порядке вычислений, ни об эффективности осуществления тех или иных сопоставлений с образцом. Поэтому приведём ниже чёткий алгоритм сопоставления объектного выражения с образцом (алгоритм позаимствован из руководства к языку Рефал 5, но подходит и для нашего случая; авторский курсив сохранён; атомы в руководстве по Рефалу 5 символами).
Алгоритм сопоставления с образцом
Вхождения символов, скобок и переменных будут называться элементами выражений. Пропуски между элементами будут называться узлами. Сопоставление Е : Р определяется как процесс отображения, или проектирования, элементов и узлов образца Р на элементы и узлы объектного выражения Е.Общие требования к отображению `Р` на `Е` (сопоставлению `Е : Р`)
Следующие очевидные требования должны проверяться на каждой стадии сопоставления:1. Если узел N2 расположен в Р правее узла N1, то проекция N2 в Е может либо совпадать с проекцией N1, либо располагаться справа от неё (линии проектирования не могут пересекаться).
2. Скобки и символы должны совпадать со своими проекциями.
3. Проекции переменных должны удовлетворять синтаксическим требованиям их значений; т.е., быть символами, термами или произвольными выражениями для s-, t- и e-переменных соответственно. Различные вхождения одной переменной должны иметь одинаковые проекции.
Предполагается, что в начале сопоставления граничные узлы Р отображаются в граничные узлы Е. Процесс отображения описывается при помощи следующих шести правил. На каждом шаге отображения правила 1-4 определяют следующий элемент, подлежащий отображению; таким образом, каждый элемент из Р получает при отображении уникальный номер.
Правила отображения
1. После того, как отображена скобка, следующей подлежит отображению парная ей скобка.2. Если в результате предыдущих шагов оба конца вхождения некоторой e-переменной уже отображены, но эта переменная еще не имеет значения (ни одно другое ее вхождение не было отображено), то эта переменная отображается следующей. Такие вхождения называются закрытыми e-переменными. Две закрытые e-переменные могут появиться одновременно; в этом случае та, что слева, отображается первой.
3. Вхождение переменной, которая уже получила значение, является повторным. Скобки, символы, s-переменные, t-переменные и повторные вхождения e-переменных в Р являются жёсткими элементами. Если один из концов жесткого элемента отображен, проекция второго конца определена однозначно. Если Правила 1 и 2 неприменимы, и имеется несколько жёстких элементов с одним спроектированным концом, то из них выбирается самый левый. Если возможно отобразить этот элемент, не вступая в противоречие с общими требованиями 1-3, приведенными выше, тогда он отображается, и процесс продолжается дальше. В противном случае объявляется тупиковая ситуация.
4. Если Правила 1-3 неприменимы и имеются несколько e-переменных с отображённым левым концом, то выбирается самая левая из них. Она называется открытой e-переменной. Первоначально она получает пустое значение, т.е., ее правый конец проектируется на тот же узел, что и левый. Другие значения могут присваиваться открытым переменным через удлинение (см. Правило 6).
5. Если все элементы Р отображены, это значит, что процесс сопоставления успешно завершён.
6. В тупиковой ситуации процесс возвращается назад к последней открытой e-переменной (т.е., к той, что имеет максимальный номер проекции), и ее значение удлиняется; т.е., проекция ее правого конца в Е подвигается на один терм вправо. После этого процесс возобновляется. Если переменную нельзя удлинить (из-за Общих требований 1-3), удлиняется предшествующая открытая переменная, и т.д. Если не имеется подлежащих удлинению открытых переменных, процесс сопоставления не удался. (Конец цитаты.)
Введём дополнительно следующие понятия: вес и длина объектного выражения.
Len(obj) = | 0, если obj --- пустое выражение | Len(subobj) + 1, если obj == t.X + subobj W(obj) = Wt(obj[1]) + Wt(obj[2]) + ... + Wt(obj[Len(obj)]), где Wt(term) = | C1, если term --- атом | С2 + Len(obj), если term == (obj)
Здесь obj[i] — i-й терм объектного выражения obj, Wt — вспомогательная функция, вычисляющая вес терма, С1 и С2, константы, зависящие от постановки задачи. Можно сказать, что W(obj) = O(Na) + O(Nb), где Na и Nb — это соответственно общее количество атомов и скобок в объектном выражении.
Анализируя алгоритм, можно заключить, что если атомы и скобки отождествляются за постоянное время, то сопоставление одноимённых t- и e-переменных может потребовать неявного рекурсивного анализа всей внутренней структуры этих переменных со сложностью O(W(переменная)), где W(obj) — вес объектного выражения, сканирование по каждой e-переменной имеет сложность O(maxlen(e-переменная)), где функция maxlen определяет максимальную длину, которую способна принять e-переменная в процессе сканирования, сложность сопоставления всего образца равна произведению сложностей сопоставления каждого элемента образца.
Как было сказано выше, выполнение программы на Рефале подразумевает последовательность преобразований поля зрения как череду выборов следующего терма активации и замен их на результат выполнения функции, содержащейся в этом терме. Однако не было сказано, каким же образом инициализируется исходное содержимое поля зрения. Очевидно, что чтобы программа выполнялась, изначально поле зрения должно содержать хотя бы один терм активации. В большинстве диалектов при старте программы поле зрения содержит терм активации <Go>, т.е. выполнение программы начинается с вызова функции Go с пустым аргументом.
Разбиение программы на модули
Большинство (если не все) реализаций Рефала поддерживают разбиение программы на несколько файлов исходного текста, компилируемых раздельно (в дальнейшем файлы исходного текста, компилируемые раздельно, будем называть модулями). Каждый модуль может как использовать функции (а ничего кроме функций модуль содержать не может) других модулей, т.е. импортировать функции, так и позволять вызывать извне свои функции, т.е. экспортировать их. Чтобы сделать функцию экспортируемой, надо в определении функции перед её именем записать ключевое слово $ENTRY, например, как показано в листинге 2./* Листинг 2 */
$ENTRY Square {
s.Value = <Mul s.Value s.Value>;
}Запись $ENTRY Square делает функцию Square экспортируемой, т.е. другие модули, импортировав функцию Square, могут её вызывать в своих функциях. Для экспорта функций используется ключевое слово $EXTERN, после которого следуют перечисленные через запятую имена экспортируемых функций, список которых завершается точкой с запятой. Пример использования ключевого слова $EXTERN показан на листинге 3.
/* Листинг 3 */ $EXTERN Square, StrFromNumber;
Полный пример программы из двух модулей показан на листинге 4.
/* Листинг 4 */
/* Файл square.ref */
$EXTERN Mul;
$ENTRY Square {
s.Value = <Mul s.Value s.Value>;
}
/* Файл main.ref */
$EXTERN Square, StrFromNumber, WriteLine;
$ENTRY Go {
=
<WriteLine
'Квадрат числа ' <StrFromNumber 100> ' равен '
<StrFromNumber <Square 100>>
>;
}
В листинге 4 есть ряд нюансов. Во-первых, функция Go объявлена как $ENTRY. В большинстве реализаций стартовая функция Go вызывается извне средой времени выполнения, поэтому должна экспортироваться наружу. Во-вторых, здесь предполагается, что импортируемые функции Mul, StrFromNumber и WriteLine, экспортируются библиотекой времени выполнения, которая прилинковывается в процессе компоновки. В ряде диалектов Рефала такие функции называются встроенными и не требуют явного описания как импортируемых, т.е. как бы незримо присутствуют в каждом модуле исходного текста (так обстоят дела в Рефале 5, 6 и 7). В дальнейшем будем предполагать, что у нас нет встроенных функций и все функции откуда-то импортируются.
Примеры выполнения программы
Рассмотрим процесс выполнения программы на листинге 4. На листинге ниже показана последовательность шагов рефал-машины в виде последовательных шагов поля зрения.<Go> <WriteLine 'Квадрат числа ' <StrFromNumber 100> ' равен ' <StrFromNumber <Square 100>>> <WriteLine 'Квадрат числа 100 равен ' <StrFromNumber <Square 100>>> <WriteLine 'Квадрат числа 100 равен ' <StrFromNumber <Mul 100 100>>> <WriteLine 'Квадрат числа 100 равен ' <StrFromNumber 10000>> <WriteLine 'Квадрат числа 100 равен 10000'> /* Здесь происходит вывод на экран строки 'Квадрат числа 100 равен 10000'. */ /* пусто */
В качестве другого примера рассмотрим процесс выполнения программы, обращающей строку, введённую пользователем (код программы на листинге 5, процесс выполнения на листинге 6).
/* Листинг 5 */
$EXTERN WriteLine, ReadLine;
$ENTRY Go {
= <WriteLine 'Введите строку'> <PerformReverse <ReadLine>>;
}
PerformReverse {
e.Line =
<WriteLine
'Строка "' e.Line '" в обратном направлении выглядит как "'
<Reverse e.Line> '"'
>;
}
Reverse {
s.First e.Last = <Reverse e.Last> s.First;
/* пусто */ = /* пусто */;
}/* Листинг 6 */ <Go> <WriteLine 'Введите строку'> <PerformReverse <ReadLine>> /* Выводится на экран 'Введите строку'. */ <PerformReverse <ReadLine>> /* Функция ожидает ввода с клавиатуры. Допустим, пользователь ввёл унитаз'. */ <PerformReverse 'унитаз'> <WriteLine 'Строка "унитаз" в обратном направлении выглядит как "' <Reverse 'унитаз'> '"'> <WriteLine 'Строка "унитаз" в обратном направлении выглядит как "' <Reverse 'нитаз'> 'у"'> <WriteLine 'Строка "унитаз" в обратном направлении выглядит как "' <Reverse 'итаз'> 'ну"'> <WriteLine 'Строка "унитаз" в обратном направлении выглядит как "' <Reverse 'таз'> 'ину"'> <WriteLine 'Строка "унитаз" в обратном направлении выглядит как "' <Reverse 'аз'> 'тину"'> <WriteLine 'Строка "унитаз" в обратном направлении выглядит как "' <Reverse 'з'> 'атину"'> <WriteLine 'Строка "унитаз" в обратном направлении выглядит как "' <Reverse> 'затину"'> <WriteLine 'Строка "унитаз" в обратном направлении выглядит как "затину"'> /* Тут происходит вывод на экран строки 'Строка "унитаз" в обратном направлении выглядит как "затину"'. */ /* пустое поле зрения, рефал-машина останавливается */
