Язык 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 — получился порочный круг.

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