Универсальная функция

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

Определим универсальную функцию eval от аргумента expr — выражения, являющегося произвольной вычислимой формой языка Лисп.

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

атомарное выражение обычно понимается как переменная. Для него следует найти связанное с ним значение. Например, могут быть переменные вида x, elem, смысл которых зависит от контекста, в котором они вычисляются;
константы представленные как аргументы функции QUOTE, можно просто извлечь из списка ее аргументов. Например, значением константы (QUOTE T) является атом T, обычно символизирующий значение "истина";
условное выражение требует специального алгоритма для перебора предикатов и выбора нужной ветви. Например, интерпретация условного выражения

(COND ((ATOM x) x) ((QUOTE T) (first (CAR x)) ) )

должна обеспечивать выбор ветви в зависимости от атомарности значения аргумента. Семантика чистого Лиспа не определяет значение условного выражения при отсутствии предиката со значением "истина". Но во многих реализациях и диалектах Лиспа такая ситуация не рассматривается как ошибка, а значением считается Nil. Иногда это придает условным выражениям лаконичность;
остальные формы выражений рассматриваются по общей схеме как список из функции и ее аргументов. Обычно аргументы вычисляются, а затем вычисленные значения передаются функции для интерпретации ее определения. Так обеспечивается возможность писать композиции функций.
Например, в выражении (first (CAR x)) внутренняя функция CAR сначала получит в качестве своего аргумента значение переменной x, а потом свой результат передаст как аргумент более внешней функции first;
если функция представлена своим названием, то среди названий различаются имена встроенных функций, такие как CAR, CDR, CONS и т.п., и имена функций, введенных в программе, например first. Для встроенных функций интерпретация сама "знает", как найти их значение по заданным аргументам, а для введенных в программе функций — использует их определение, которое находит по имени;
если функция использует лямбда-конструктор, то прежде чем его применять, понадобится связывать переменные из лямбда-списка со значениями аргументов. Функция, использующая лямбда-выражение,

(LAMBDA (x) (COND ((ATOM x) x) ((QUOTE T) (first (CAR x)) ) ) )

зависит от одного аргумента, значение которого должно быть связано с переменной x. В определении используется свободная функциональная переменная first, которая должна быть определена в более внешнем контексте;
если представление функции начинается с LABEL, то понадобится сохранить имя функции с соответствующим ее определением так, чтобы корректно выполнялись рекурсивные вызовы функции. Например, предыдущее LAMBDA-определение безымянной функции становится рекурсивным, если его сделать вторым аргументом специальной функции LABEL, первый аргумент которой — fisrt, имя новой функции.

(LABEL first (LAMBDA (x) (COND ((ATOM x) x) ((QUOTE T) (first (CAR x)) ) ) ) )

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

обработка структур данных (cons, car, cdr, atom, eq);
конструирование функциональных объектов (lambda, label);
идентификация объектов (имена переменных и названия функций);
управление логикой вычислений и границей вычислимости (композиции, quote, cond, eval).

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

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

Начнем с общих методов обработки S-выражений.

AMONG — проверка, входит ли заданный атом в данное S-выражение.

(DEFUN among (x y) (COND ((ATOM y) (EQ x y)) ((among x (CAR y)) (QUOTE T)) ((QUOTE T) (among x (CDR y) )) ) ) (among 'A '(C (A B))) ; = T (among 'A '(C D B)) ; = NIL

Символ ";" - начало примечания (до конца строки).

EQUAL — предикат, проверяющий равенство двух S-выражений. Его значение "истина" для идентичных аргументов и "ложь" для различных. (Элементарный предикат EQ определен только для атомов.) Определение EQUAL иллюстрирует условное выражение внутри условного выражения (двухуровневое условное выражение и двунаправленная рекурсия).

(DEFUN equal (x y) (COND ((ATOM x) (COND ((ATOM y) (EQ x y)) ((QUOTE T) (QUOTE NIL)) ) ) ((equal (CAR x)(CAR y)) (equal (CDR x)(CDR y)) )

((QUOTE T) (QUOTE NIL) ) ) ) (equal '(A (B)) '(A (B))) ; = T (equal '(A B) '(A . B)) ; = NIL

SUBST — функция трех аргументов x, y, z, строящая результат замены S-выражением x всех вхождений y в S-выражение z.

(DEFUN subst (x y z) (COND ((equal y z) x) ((ATOM z) z) ((QUOTE T)(CONS (subst x y (CAR z)) (subst x y (CDR z)) ) ) ) ) (subst '(x . A) 'B '((A . B) . C)) ; = ((A . (x . A)) . C)

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

(subst 'x '(B C D) '((A B C D)(E B C D)(F B C D))) ; = ((A . x) (E . x) (F . x))

NULL — предикат, отличающий пустой список от остальных S-выражений. Позволяет выяснять, когда список исчерпан. Принимает значение "истина" тогда и только тогда, когда его аргумент — Nil.

(DEFUN null (x) (COND ((EQ x (QUOTE Nil)) (QUOTE T)) ((QUOTE T) (QUOTE Nil)) ) )

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

(DEFUN pair_to_list (x) (CONS (CAR x) (CONS (CDR x) Nil)) ) (pair_to_list '(A B)) ; = (A B)

(DEFUN list_to_pair (x) (CONS (CAR x) (CADR x)) ) (list_to_pair '(A B C)) ; = (A . B)

По этим определениям видно, что списочная запись строится большим числом CONS, т.е. на нее расходуется больше памяти.