====%%(wacko wrapper=text wrapper_align=center) Язык RL %%==
=====%%(wacko wrapper=text wrapper_align=center) Определения %%==
Выражения
Мы начнем с определений и поясняющих их примеров.
Символом (или атомом) мы будем называть любую последовательность, составленную из букв; при этом под буквами мы понимаем буквы английского алфавита, причем большие и маленькие буквы считаем одинаковыми; знак подчеркивания тоже считается буквой. Примеры: A, B, symbol, AnotherSymbol -- символы НеСимвол, a2, abc-d -- не символы
Термом называется любой символ, а также любое выражение, заключенное в скобки. При этом выражением называется любая (в том числе и пустая) последовательность термов, разделенных пробелами.
Примеры выражений: A B CCC D -- состоит из четырех символов (A B) -- состоит из одного терма, представляющего собой выражение из двух символов в скобках (()) B CCC -- выражение из трех термов, первый из которых есть выражение из единственного терма в скобках -- пустое выражение
Обратите внимание, что пробелы вокруг скобок ставить не обязательно.
Программы и функции
В языке 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, входящих в их описание.
Значение терма (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 -- получился порочный круг.
Мы будем считать, что если наши правила определения значений не позволяют его определить из-за порочного круга (одно значение сводится к другому, другое -- к третьему и т.п.), то значение является неопределенным.
---- адрес оригинала: ((/OnerXaum/RL1/ОписаниеRL))