globalf5-240972240972 (850810), страница 9
Текст из файла (страница 9)
При интерпретации выражений учитывается следующее:атомарное выражение обычно понимается как переменная. Длянего следует найти связанное с ним значение. Например, могутбыть переменные вида x, elem, смысл которых зависит отконтекста, в котором они вычисляются;константы, представленные как аргументы функции QUOTE,можно просто извлечь из списка ее аргументов.
Например,значением константы (QUOTE T) является атом T, обычносимволизирующий значение "истина";условное выражение требует специального алгоритма дляперебора предикатов и выбора нужной ветви. Например,интерпретация условного выражения(COND ((ATOM x) x)((QUOTE T) (first (CAR x)) ))должна обеспечивать выбор ветви в зависимости от атомарностизначения аргумента. Семантика чистого Лиспа не определяетзначение условного выражения при отсутствии предиката созначением "истина".
Но во многих реализациях и диалектах Лиспатакая ситуация не рассматривается как ошибка, а значениемсчитается NIL. Иногда это придает условным выражениямлаконичность;остальные формы выражений рассматриваются по общей схемекак список из функции и ее аргументов. Обычно аргументывычисляются, а затем вычисленные значения передаются50Л.В. ГородняяОсновы функционального программированияфункции для интерпретации ее определения. Так обеспечиваетсявозможность писать композиции функций.
Например, ввыражении (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)) )51Л.В.
ГородняяОсновы функционального программирования) ) )Таким образом, интерпретациявзаимодействие четырех подсистем:функцийосуществляетсякакобработка структур данных ( 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 определен только для атомов.)52Л.В. ГородняяОсновы функционального программированияОпределение EQUAL иллюстрирует условное выражение внутриусловного выражения (двухуровневое условное выражение и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)) ; = NILSUBST — функция трех аргументов 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))53Л.В. ГородняяОсновы функционального программирования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, т.е.
на нее расходуется больше памяти.Основные методы обработки списковСледующие функции полезны, когда рассматриваются лишь списки.APPEND — функция двух аргументов x и y, сцепляющая два списка водин.(DEFUN append (x y)(COND((null x) y)((QUOTE T)(CONS (CAR x)54Л.В. ГородняяОсновы функционального программирования(append (CDR x) y)))) )(append '(A B) '(C D E)); = (A B C D E)MEMBER — функция двух аргументов x и y, выясняющая, встречаетсяли S-выражение x среди элементов списка y .(DEFUN member (x y)(COND((null y) (QUOTE NIL) )((equal x (CAR y)) (QUOTE T) )((QUOTE T) (member x (CDR y)) )) )(member '(a) '(b (a) d)) ; = T(member 'a '(b (a) d)); = NILPAIRLIS — функция аргументов x, y, al строит список парсоответствующих элементов из списков x и y и присоединяет их ксписку al.
Полученный список пар, похожий на таблицу с двумястолбцами, называется ассоциативным списком или ассоциативнойтаблицей. Такой список может использоваться для связывания именпеременныхифункцийприорганизациивычисленийинтерпретатором.(DEFUN pairlis (x y al)(COND((null x) al)((QUOTE T) (CONS(CONS (CAR x)(CAR Y) )(pairlis (CDR x)(CDR y)al)))) )(pairlis '(A B C)'(u t v)'((D . y)(E .
y)) ); = ((C . v)(B . t)( A . u) (D . y)(E . y))55Л.В. ГородняяОсновы функционального программированияASSOC — функция двух аргументов, x и al. Если al —ассоциативный список, подобный тому, что формирует функцияpairlis, то assoc выбирает из него первую пару, начинающуюся сx. Таким образом, это функция поиска определения или значения потаблице, реализованной в форме ассоциативного списка .(DEFUN assoc (x al)(COND((equal x (CAAR al)) (CAR al) )((QUOTE T) (assoc x (CDR al)) )) )Частичная функция — рассчитана на наличие ассоциации.(assoc 'B '((A . (m n))(B .
(CAR x))(C . w)(B . (QUOTE T)) )); = (B . (CAR x))SUBLIS — функция двух аргументов al и y, предполагается, чтопервый из аргументов AL устроен как ассоциативный список вида((u1 . v1) ... (uK . vK)), где u есть атомы, а второйаргумент Y — любое S-выражение. Действие sublis заключается вобработке Y, такой, что вхождения переменных Ui, связанные вассоциативном списке со значениями Vi, заменяются на эти значения.Другими словами в S-выражении Y вхождения переменных Uзаменяются на соответствующие им V из списка пар AL. Вводимвспомогательную функцию SUB2, обрабатывающую атомарные Sвыражения, а затем — полное определение SUBLIS:(DEFUN sub2 (al z)(COND((null al) z)((equal (CAAR al) z) (CDAR al) )((QUOTE T) (sub2 (CDR al) z) )) )56Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
