Учебник по Lisp (Материалы к экзамену и коллоквиумам 2013-го года), страница 6

A) 'B '((A . B) . C)); = ((A . (x . A)) . C)(subst 'x '(B C D) '((A B C D)(E B C D)(F B C D))) ;= ((A . x)(E . x)(F . x))Символ «;» - начало комментария.Использование equal в этом определении позволяет подстановку осуществлять и вболее сложных случаях. Например, для редукции совпадающих хвостовподсписков:(DEFUN Подстановка (x y z) (subst x y z))(Подстановка '(x . A) 'B '((A .

B) . C));= ((A . (x . A)) . C)NULL - предикат, отличающий пустой список от всех остальных S-выражений.Используется, чтобы выяснять, когда список исчерпан. Принимает значение"истина" тогда и только тогда, когда его аргумент - Nil.(DEFUN null (x) (COND((EQ x (QUOTE Nil)) (QUOTE T))((QUOTE T) (QUOTE Nil))))При необходимости можно компоненты точечной пары разместить вдвухэлементном списке и наоборот, из первых двух элементов списка построитьв точечную пару.(DEFUN pair_to_list (x) (CONS (CAR x) (CONS (CDR x) Nil)) )(DEFUN list_to_pair (x) (CONS (CAR x) (CADR x)) )По этим определениям видно, что списочная запись строится большим числомCONS, т.е. на нее расходуется больше памяти.Основные методы обработки списковСледующие функции используются, когда рассматриваются лишь списки.35APPEND - функция двух аргументов x и y, сцепляющая два списка в один.(DEFUN append (x y) (COND((null x) y)((QUOTE T) (CONS(CAR x)(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 x) (QUOTE Nil))((equal x (CAR y)) (QUOTE T))((QUOTE T) (member x (CDR y))))PAIRLIS - функция трех аргументов 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)));= ((A . u)(B . t)(C .

v)(D . y)(E . y))36ASSOC - функция двух аргументов 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))))(DEFUN sublis (al y) (COND((ATOM y) (sub2 al y))((QUOTE T)(CONS(sublis al (CAR y))(sublis al (CDR y))) )))Пример.(sublis '((x . Шекспир)(y . (Ромео и Джульетта))) '(x написал трагедию y))37;= (Шекспир написал трагедию (Ромео и Джульетта))INSERT – вставка z перед вхождением ключа x в список al.(DEFUN insert (al x z) (COND((null al) Nil)((equal (CAR al) x) (CONS z al))((QUOTE T) (CONS (CAR al) (insert (CDR al) x z))))(insert ‘(a b c) ‘b ‘s); = (a s b c)ASSIGN – модель присваивания переменным, хранящим значения вассоциативном списке.

Замена связанного с данной переменной в первой парезначения на новое заданное значение. Если не было пары вообще, то новую паруиз переменной и ее значения размещаем в конец а-списка, чтобы она моглаработать как глобальная.(DEFUN assign (x v al) (COND((Null al) (CONS (CONS x v) Nil ))((equal x (CAAR al))(CONS (CONS x v) (CDR al)))((QUOTE T) (CONS (CAR al) (assign x v (CDR al))))(assign ‘a 111 ‘((a .

1)(b . 2)(a . 3)))(assign ‘a 111 ‘((c . 1)(b . 2)(a . 3)))(assign ‘a 111 ‘((c . 1)(d . 3)));= ((a . 111)(b . 2)(a . 3));= ((c . 1)(b . 2)(a . 111));= ((c . 1)(d . 3) (a . 111))Упражнение: Введите функции с именами – Пусто, Пара_в_список,Список_в_пару, входит_ли, Соединение, Элемент, Связывание, Ассоциация,Ряд_подстановок, Вставка, Присваивание, как аналогивышеприведенныхфункций.Задание: Напишите определение функции REVERSE – обращение спискаОтвет:(defun reverse (m) (cond ((null m) NIL)(T (append(reverse(cdr m))(list(car m)) )) ))38Теперь посмотрим ее вариант как пример использования накапливающихпараметров и вспомогательных функций:.(defun rev (m n) (cond ((null m) N)(T (rev(cdr m) (cons (car m) n)))))(defun reverse (m) (rev m Nil))Выводы:-Синтаксис Лиспа очень прост.

В некотором смысле это сосредотачиваетразработчиков на семантике, что породило большое количество диалектов.-Форма - это выражение, которое может быть вычислено. Формамиявляются переменные и списки, начинающиеся с QUOTE, COND или спредставления некоторой функции.-Выполнение программы на Лиспе устроено как интерпретация данных,представляющих выражения, имеющие значение.395. ИнтерпретаторТеперь рассмотрим определение операционной семантики Лиспа в видеуниверсальной функции, задающей правила вычисления форм и примененияфункций к аргументам.-Требования к определению.Синтаксическая сводка.Определение универсальной функцииEVAL-APPLY.Предикаты и истинность.Интерпретация или универсальная функция - это функция, которая умеетвычислять значение любой формы, включая формы, сводимые к вычислениюпроизвольной заданной функции, применяемой к представленным в этой же формеаргументам, по доступному описанию данной функции.

(Конечно, если функция,которой предстоит интерпретироваться, имеет бесконечную рекурсию, тоинтерпретация будет повторяться бесконечно.)Определим универсальную функцию eval от аргумента expr - выражения,являющегося произвольной вычислимой формой языка Лисп.Универсальная функция должна предусматривать основные виды вычисляемыхформ, задающих значения аргументов, а также представления функций, всоответствии со сводом вышеприведенных правил языка. При интерпретациивыражений учитывается следующее:- Атомарное выражение обычно понимается как переменная.

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

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

Функция, использующая лямбда-выражение,(LAMBDA (x) (COND ((ATOM x) x)((QUOTE T) (first (CAR x) )) ))зависит от одного аргумента, значение которого должно быть связано спеременной x. В определении используется свободная функциональнаяпеременная first, которая должна быть определена в более внешнем контексте.-Если представление функции начинается с DEFUN, то понадобится сохранитьимя функции с соответствующим ее определением так, чтобы корректновыполнялись рекурсивные вызовы функции. Например, предыдущееLAMBDA-определение безымянной функции становится рекурсивным, еслиего сделать вторым аргументом специальной функции DEFUN, первыйаргумент которой – fisrt, имя новой функции.(DEFUN first (x) (COND ((ATOM x) x)((QUOTE T) (first (CAR x) )) ))Можно сказать, что DEFUN замыкает выражение, содержащее функциональнуюпеременную.Таким образом, интерпретация функций осуществляется как взаимодействиечетырех подсистем:- обработка структур данных (cons, car, cdr, atom, eq),41- конструирование функциональных объектов (lambda, defun),- идентификация объектов (имена переменных и названия функций),- управление порядком вычислений (композиции, quote, cond, eval).Определение универсальной функцииУниверсальная функция eval, которую предстоит определить, должнаудовлетворять следующему условию: если представленная аргументом формасводится к функции, имеющей значение на списке аргументов этой жеформы, то это значение и является результатом функции eval.(eval '(fn arg1 ...