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

Программа выглядит так:(DEFUN MEMBER (A X);определение проверки входит ли атом в список(COND((NULL X)Nil)((EQ A (CAR X)) T)(T(MEMBER A (CDR X)) )))(DEFUN UNION (X Y);определение объединения двух множеств(COND((NULL X) Y)((MEMBER (CAR X) Y) (UNION (CDR X) Y) )(T (CONS (CAR X) (UNION (CDR X) Y))) )) )))(DEFUN INTERSECTION (X Y);определение пересечения двух множеств(COND((NULL X) NIL)((MEMBER (CAR X) Y) (CONS (CAR X) (INTERSECTION (CDRX) Y)) )(T (INTERSECTION (CDR X) Y))))(INTERSECTION '(A1 A2 A3) '(Al A3 A5));тест на пересечение двух множеств(UNION '(X Y Z) '(U V W X));тест на объединение двух множествЭта программа предлагает Лисп-системе вычислить пять различных форм.

Первые триформы сводятся к применению псевдо-функции DEFUN. Значение четвертой формы - (A1A3). Значение пятой формы - (Y Z C B D X). Анализ пути, по которому выполняетсярекурсия, показывает, почему элементы множества появляются именно в таком порядке.Псевдо-функция - это функция, которая выполняется ради ее воздействия на систему, тогдакак обычная функция - ради ее значения. DEFUN заставляет функции стать определенными идопустимыми в системе равноправно со встроенными функциями.

Ее значение - имяопределяемой функции, в данном случае - MEMBER, UNION, INTERSECTION. Можносказать более точно, что полная область значения псевдо-функции DEFUN включает в себянекоторые доступные ей части системы, обеспечивающие хранение информации о15функциональных объектах, а формальное ее значение – атом, символизирующий определениефункции.В этом примере продемонстрировано несколько элементарных правил написанияфункциональных программ, выбранных при реализации интерпретатора Лисп 1.5 вдополнение к идеализированным правилам, сформулированным в строгой теории Лиспа,которая описана в предыдущем разделе.1) Программа состоит из последовательности вычисляемых форм.

Если форма список,то ее первый элемент интерпретируется как функция. Остальные элементы списка –аргументы для этой функции. Они вычисляются с помощью EVAL, а функция применяется кним с помощью APPLY и полученное значение выводится как результат программы.2) Нет особого формата для записи программ.

Границы строк игнорируются. Форматпрограммы, включая идентификацию, выбран просто для удобства чтения.3) Любое число пробелов и концов строк можно разместить в любой точке программы, ноне внутри атома.4) Не используются (QUOTE T), (QUOTE NIL). Вместо них используется T, NIL, что влечетсоответствующее изменение определения EVAL.5) Атомы должны начинаться с букв, чтобы легко отличаться от чисел.6) Точечная нотация может быть привлечена наряду со списочной записью.

Любое числопробелов перед или после точки, кроме одного, будет игнорироваться (один пробелобязательно нужен).7) Точечные пары могут появляться как элементы списка, и списки могут быть элементамиточечных пар.Например:((A . B) X (C . (E F D))) - есть допустимое S-выражение.Оно может быть записано как((A . B) . ( X . ((C . (E . ( F . (D . Nil))) ) .

Nil)))или((A . B) X (C E F D))168) Форма типа (A B C . D) есть сокращение для (A . ( B . ( C . D) )). Любая другаярасстановка запятых или точек на одном уровне есть ошибка, например, (A. B C) или (A B . CD) не соответствуют никакой структуре данных. (Реализационное расширение списочнойзаписи. “. D” здесь означает, что вместо Nil, по умолчанию завершающего список, в даннойструктуре размещен атом “D”)9) Набор основных функций обеспечен системой.

Другие функции могут бытьвведены программистом. Любая функция может использоваться в определениидругой функции с учетом иерархии построений.Вывод S-выражений на печать и в файлы выполняет псевдо-функция PRINT, чтение данныхобеспечивает псевдо-функция READ. Программа из файла может быть загружена псевдофункцией LOAD.Пример:(LOAD 'TEST.LSP)При наборе форм в диалоге интерпретатор сам напечатает результаты, а при загрузкепрограммы их файла надо позаботиться о выводе результатов программы с помощью псевдофункции PRINT.Пример:(PRINT (INTERSECTION '(A1 A2 A3) '(Al A3 A5)) )(PRINT (UNION '(X Y Z) '(U V W X)) )(PRINT (UNION (READ) '(1 2 3 4)) ); объединение вводимого списка со списком '(1 2 3 4)Именование значений и подвыраженийПеременная - это символ, который используется для представления аргумента функции.Атом может быть как переменной, так и фактическим аргументом.

Некоторые сложностивызывает то обстоятельство, что иногда аргументы могут быть переменными, вычисляемымивнутри вызова другой функции.Часть интерпретатора, которая при вычислении функций связывает переменные, называетсяAPPLY. Когда APPLY встречает функцию, начинающуюся с LAMBDA, список переменныхпопарно связывается со списком аргументов и добавляется к началу ассоциативного списка.17Часть интерпретатора, которая потом вычислит переменные, называется EVAL. Привычислении тела функции EVAL может обнаружить переменные. Она их ищет вассоциативном списке.

Если переменная встречается там несколько раз, то используетсяпоследнее или самое новое значение.Проиллюстрируем это рассуждение на примере. Предположим, интерпретатор получаетследующее S-выражение:((LAMBDA (X Y) (CONS X Y)) 'A 'B)Функция:(LAMBDA (X Y) (CONS X Y))Аргументы: (A B)EVAL передает эти аргументы функции APPLY. (См. 6).(apply #’(LAMBDA (X Y) (CONS X Y)) ‘(A B) Nil )APPLY свяжет переменные и передаст функцию и удлинненный а-список EVALвычисления.для(eval ‘(CONS X Y) ‘ ((X . A) (Y B) Nil))EVAL вычисляет переменные и сразу передает их функции CONS, строящий из нихбинарный узел.(Cons ‘A ’B) = (A . B)Можно добиться большей прозрачности сложных определений функций, используяиерархию контекстов и средства именования выражений.

Специальная функция Letсопоставляет локальным переменным независимые выражения. С ее помощью можновынести из сложного определения любые совпадающие подвыражения.Пример:18(defun UNION- (x y) (let ( (a-x (CAR x))(d-x (CDR x)) )(COND ((NULL x)y)((MEMBER a-x y) (UNION d-x y) )(T(CONS a-x (UNION d-x y)) ) )))Обычно переменная считается связанной в области действия лямбда-конструктора функции,который связывает переменную внутри тела определения функции методом размещенияпары из имени и значения в начале ассоциативного списка (а-списка). В том случае, когдапеременная всегда имеет определенное значение независимо от текущего состояния а-списка,она будет называться константой. Такую неизменяемую связь можно установить, размещаяпару (a .

v) в конец a-списка. Но в реальных системах это организовано с помощью такназываемого списка свойств атома, являющегося представлением переменной. Каждыйатом имеет свой список свойств (property list - р-список), доступный через хэш-таблицуидентификаторов, что работает эффективнее, чем a-список. С каждым атомом связанаспециальная структура данных, в которой размещается имя атома, его значение, определениефункции, представляемой этим же атомом, и список произвольных свойств, помеченныхиндикаторами.

При вычислении переменных EVAL исследует эту структуру до поиска в асписке. Такое устройство констант не позволяет им служить переменными в а-списке.Глобальные переменные реализованы аналогично, но их значение можно изменять спомощью специальной функции SET.Особый интерес представляет тип констант, которые всегда означают себя – Nil и T, примерытаких констант. Такие константы как T, Nil и другие самоопределимые константы (числа,строки) не могут использоваться в качестве переменных. Числа и строки не имеют спискасвойств.Ситуация, когда атом обозначает функцию, реализационно подобна той, в которой атомобозначает аргумент. Если функция рекурсивна, то ей надо дать имя. Это делаетсясвязыванием названия с определением функции в ассоциативном списке.

Название связано сопределением функции точно также, как переменная связана со своим значением.На практике связывание в ассоциативном списке для функций используется редко. Удобнеесвязывать название с определением другим способом - размещением определения функции всписке свойств атома, символизирующего ее название. Выполняет это псевдо-функцияDEFUN, описанная в начале этого параграфа. Когда APPLY интерпретирует функцию,представленную атомом, она исследует р-список до исследования текущего состояния асписка.Тот факт, что большинство функций - константы, определенные программистом, а непеременные, изменяемые программой, происходит отнюдь не вследствие какого-либонедостатка понятий Лиспа.

Напротив, этот резерв указывает на потенциал подхода, которыймы не научились использовать лучшим образом.19Некоторые функции вместо определений с помощью S-выражений закодированыкакзамкнутые машинные подпрограммы. Такая функция будет иметь особый индикатор в спискесвойств с указателем, который позволяет интерпретатору связаться с подпрограммой.Существует три случая, в которых низкоуровневая подпрограмма может быть включена всистему:1) Подпрограмма закодирована внутри Лисп-системы.2) Функция кодируется пользователем вручную на языке типа ассемблера.3) Функция сначала определяется с помощью S-выражения, затем транслируетсякомпилятором. Компилированные функции могут выполняться гораздо быстрее, чеминтерпретироваться.Обычно EVAL вычисляет аргументы функций до применения к ним функций с помощьюAPPLY.