Язык RL
Определения
Выражения
Мы начнем с определений и поясняющих их примеров.
Символом (или атомом) мы будем называть любую последовательность,
составленную из букв; при этом под буквами мы понимаем буквы
английского алфавита, причем большие и маленькие буквы считаем
одинаковыми; знак подчеркивания тоже считается буквой.
Примеры:
A, B, symbol, AnotherSymbol — символы
НеСимвол, a2, abc-d — не символы
НеСимвол, a2, abc-d — не символы
Термом называется любой символ, а также любое выражение,
заключенное в скобки. При этом выражением называется любая (в том
числе и пустая) последовательность термов, разделенных пробелами.
Примеры выражений:
A B CCC D — состоит из четырех символов
(A B) — состоит из одного терма,
(()) B CCC — выражение из трех термов,
— пустое выражение
(A B) — состоит из одного терма,
представляющего собой выражение
из двух символов в скобках
из двух символов в скобках
первый из которых есть выражение из единственного
терма в скобках
терма в скобках
Обратите внимание, что пробелы вокруг скобок ставить не обязательно.
Программы и функции
В языке RL все объекты — программы, входные данные, результаты
Программа на языке RL представляет собой выражение, состоящее из
одного или нескольких термов. Эти термы называются функциями.
Каждая функция имеет следующий вид:
(NAME (ARG_1... ARG_n) BODY),
где
NAME — символ, называемый именем функции;
ARG_1... ARG_n — символы, называемые аргументами функции;
BODY — терм, называемый телом функции.
Число аргументов может быть равным нулю — в
этом случае в описании функции закрывающая скобка следует сразу за
открывающей.
Имена функций, описанных в программе, не должны совпадать.
Каждая функция вычисляет некоторое выражение, называемое ее значением
и зависящее от значений аргументов. Результатом работы программы
является значение первой функции программы при значениях ее
аргументов, заданных пользователем при запуске программы.
Значением функции называется значение терма — ее тела. Что такое
значение терма, определяется в следующих разделах.
Параметры. Значение терма при данных значениях параметров
Для каждого терма определяется список символов, называемых
параметров. Значениями термов, как и их параметров, являются выражения, а
также специальный символ НЕОПРЕДЕЛЕНО.
Значения и параметры данного терма определяются через значения и
параметры термов, входящих в этот терм. Ясно, что этот процесс
должен когда-то заканчиваться, так что некоторые термы должны
получать значения непосредственно.
Стандартные термы
Терм (ABORT) не имеет параметров, и его значением является
символ НЕОПРЕДЕЛЕНО.
Пусть имеется выражение X.
Терм (QUOTE X) не имеет параметров, и его значением является выражение X.
Например, значением терма (QUOTE) является пустое выражение, а
значением терма (QUOTE (A) () B) является выражение из трех термов:
(A) () B
Другим примером терма, значение которого определяется непосредственно,
является аргумент функции. Его значение определяется при вызове функции
(об этом подробнее будет рассказано позже), в частности, в начале
работы программы пользователь задает значения всех аргументов первой
(возможно, единственной) функции программы. Значения всех остальных термов
определяются через уже известные значения.
Пусть T_1... T_n — термы, значT_1 ... значT_n — выражения,
являющиеся их значениями.
Параметры всех описываемых далее термов — все параметры термов
T_1... T_n, входящих в их описание.
Значение терма (FIRST T_1 ) — это первый терм выражения значT_1.
Если же выражение значT_1 пусто или не определено, значением этого терма
считается символ НЕОПРЕДЕЛЕНО.
Значением терма (BF T_1) является выражение, полученное отбрасыванием
первого терма выражения значT_1. Если выражение значT_1 пусто или не
определено, то значением этого терма является символ НЕОПРЕДЕЛЕНО.
Аналогично определяются значения термов
(LAST T_1) и (BL T_1). Значением терма (LAST T_1) является значение
последнего терма выражения значT_1; значением терма (BL T_1)
является выражение, полученное отбрасыванием последнего терма выражения
значT_1.
Значением функции называется значение терма — ее тела.
Упражнение 2.1. Чему равно значение терма (BL T_1), если значT_1 состоит
из одного терма?
2.1 Опишите функцию SECOND, значение которой — второй терм
выражения, являющегося значением ее аргумента.
Решение: Второй терм выражения, являющегося значением терма X — это
первый терм выражения (BF X). Значит, мы можем записать:
(SECOND (X)
(FIRST (BF X))
)
Если при этом значение X не определено, то значение (BF X)
тоже не определено, значит, не определено и значение (FIRST (BF X)).
Если же значение X состоит из одного терма, то значение терма (BF X) --
пустое выражение, а значение (FIRST (BF X)) снова не определено.
Опишите функцию, значением которой является выражение, состоящее из
двух термов: первого и последнего терма значения ее аргумента.Решение:
(FIRSTandLAST (X)
(EXPR
(FIRST X)
(LAST X)
)
)
Замечание. Приведенная функция имеет небольшой "дефект": если
значение X состоит из одного терма, то значением этой функции
будет выражение, состоящее из дважды повторенного значения X.
Значение терма (EQUAL T_1 T_2) есть символ TRUE, если выражения значT_1 и
значT_2 определены и совпадают, символ FALSE, если эти выражения
определены, но не совпадают, и символ НЕОПРЕДЕЛЕНО, если хотя бы одно
из этих выражений не определено.
Значение терма (SYMBOL T_1) есть символ TRUE, если значение выражения
значT_1 определено и состоит из одного символа, символ FALSE, если оно
определено и состоит из одного терма — выражения в скобках, и символ
НЕОПРЕДЕЛЕНО во всех остальных случаях (То есть не определено или
является выражением, состоящим более чем из одного терма.).
Значение терма (IF T_1 T_2 T_3) есть выражение значT_2, если выражение
значT_1 есть символ TRUE; выражение значT_3, если выражение значT_1 есть
символ FALSE; символ НЕОПРЕДЕЛЕНО во всех остальных случаях.
2.4 Описать функцию, значение которой на выражении A равно B, на
выражении B равно A, а на остальных выражениях не определено.
Решение:
(AB (X)
(IF (EQUAL X (QUOTE A))
(QUOTE B)
(IF (EQUAL X (QUOTE B))
(QUOTE A)
(ABORT)
)
)
)
Значением терма (BR T_1) является выражение, состоящее из одного терма,
представляющего собой выражение значT_1 в скобках.
Значение терма (CONT T_1) есть выражение X, если значT_1 есть выражение
X, заключенное в скобки; символ НЕОПРЕДЕЛЕНО во всех остальных случаях.
Теперь мы можем определить значение терма
(CALL NAME PAR_1... PAR_n)
при данных значениях параметров и при данной программе. При
этом терм NAME должен быть символом, функция с именем NAME должна
быть описана в данной программе и число ее аргументов должно быть
равно n — если хотя бы одно из этих требований не выполнено, то
значение терма не определено. Если же эти требования выполнены,
то значение терма (CALL NAME PAR_1... PAR_n) равно значению
функции с именем NAME на аргументах, равных значениям термов
PAR_1... PAR_n.
Другими словами, для вычисления значения терма (CALL NAME
PAR_1... PAR_n) мы должны сначала вычислить значения термов
PAR_1... PAR_n (при данных значениях параметров и данной программе), а
затем вычислить значение терма — тела функции NAME при значениях
ARG_1... ARG_n, равных значениям PAR_1... PAR_n, то есть
вычислить значение этого терма при соответствующих значениях аргументов.
Упражнение 2.3. Попробуйте применить наши правила к такой функции:
(BAD (X)
(CALL BAD X)
)
Решение: По правилам значение этой функции на выражении E
равно значению терма (CALL BAD X), когда значение его параметра
X равно E. Но значение этого терма по определению равно
значению функции BAD на аргументе E — получился порочный круг.
Мы будем считать, что если наши правила определения значений не
другому, другое — к третьему и т.п.), то значение является неопределенным.