Именование значений и подвыражений
Переменная - это символ, который используется для представления аргумента функции.
Атом может быть как переменной, так и фактическим аргументом. Некоторые сложности вызывает то обстоятельство, что иногда аргументы могут быть переменными, вычисляемыми внутри вызова другой функции.
Часть интерпретатора, которая при вычислении функций связывает переменные, называется APPLY. Когда APPLY встречает функцию, начинающуюся с LAMBDA, список переменных попарно связывается со списком аргументов и добавляется к началу ассоциативного списка.
Часть интерпретатора, которая потом вычислит переменные, называется 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) ))
EVAL вычисляет переменные и сразу передает их функции CONS, строящий из них бинарный узел.
(Cons 'A 'B) = (A . B)
Можно добиться большей прозрачности сложных определений функций, используя иерархию контекстов и средства именования выражений. Специальная функция Let сопоставляет локальным переменным независимые выражения. С ее помощью можно вынести из сложного определения любые совпадающие подвыражения.
(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)) ) ) ))
Пример 8.1.
(html, txt)
Обычно переменная считается связанной в области действия лямбда-конструктора функции, который связывает переменную внутри тела определения функции методом размещения пары из имени и значения в начале ассоциативного списка (а-списка).
В том случае, когда переменная всегда имеет определенное значение независимо от текущего состояния а-списка, она будет называться константой. Такую неизменяемую связь можно установить, размещая пару (a . v) в конец a-списка. Но в реальных системах это организовано с помощью так называемого списка свойств атома, являющегося представлением переменной. Каждый атом имеет свой список свойств (property list - р-список), доступный через хэш-таблицу идентификаторов, что работает эффективнее, чем a-список. С каждым атомом связана специальная структура данных, в которой размещается имя атома, его значение, определение функции, представляемой этим же атомом, и список произвольных свойств, помеченных индикаторами. При вычислении переменных EVAL исследует эту структуру до поиска в а-списке. Такое устройство констант не позволяет им служить переменными в а-списке.
Глобальные переменные реализованы аналогично, но их значение можно изменять с помощью специальной функции SET.
Особый интерес представляет тип констант, которые всегда означают себя – Nil и T, примеры таких констант. Такие константы как T, Nil и другие самоопределимые константы (числа, строки) не могут использоваться в качестве переменных. Числа и строки не имеют списка свойств.
Ситуация, когда атом обозначает функцию, реализационно подобна той, в которой атом обозначает аргумент. Если функция рекурсивна, то ей надо дать имя. Это делается связыванием названия с определением функции в ассоциативном списке. Название связано с определением функции точно также, как переменная связана со своим значением.
На практике связывание в ассоциативном списке для функций используется редко. Удобнее связывать название с определением другим способом - размещением определения функции в списке свойств атома, символизирующего ее название. Выполняет это псевдо-функция DEFUN, описанная в начале этого параграфа. Когда APPLY интерпретирует функцию, представленную атомом, она исследует р-список до исследования текущего состояния а-списка.
Тот факт, что большинство функций - константы, определенные программистом, а не переменные, изменяемые программой, происходит отнюдь не вследствие какого-либо недостатка понятий Лиспа.
Напротив, этот резерв указывает на потенциал подхода, который мы не научились использовать лучшим образом.
Некоторые функции вместо определений с помощью S-выражений закодированы как замкнутые машинные подпрограммы. Такая функция будет иметь особый индикатор в списке свойств с указателем, который позволяет интерпретатору связаться с подпрограммой. Существует три случая, в которых низкоуровневая подпрограмма может быть включена в систему:
Подпрограмма закодирована внутри Лисп-системы.Функция кодируется пользователем вручную на языке типа ассемблера.Функция сначала определяется с помощью S-выражения, затем транслируется компилятором. Компилированные функции могут выполняться гораздо быстрее, чем интерпретироваться.
Обычно EVAL вычисляет аргументы функций до применения к ним функций с помощью APPLY. Таким образом, если EVAL задано (CONS X Y), то сначала вычисляются X и Y, а потом работает CONS над полученными значениями. Но если EVAL задано (QOUTE X), то X не будет вычисляться. QUOTE - специальная форма, которая препятствует вычислению своих аргументов.
Специальная форма отличается от других функций двумя чертами. Ее аргументы не вычисляются до того, как специальная форма сама просмотрит свои аргументы. COND, например, имеет свой особый способ вычисления аргументов с использованием EVCON. Второе отличие от функций заключается в том, что специальные формы могут иметь неограниченное число аргументов.
Определение рекурсивной функции можно преобразовать к безымянной форме. Техника эквивалентных преобразований позволяет поддерживать целостность системы функций втягиванием безымянных вспомогательных функций внутрь тела основного определения. Верно и обратное: любую конструкцию из лямбда-выражений можно преобразовать в систему отдельных функций. Техника функциональных определений и их преобразований позволяет рассматривать решение задачи с естественной степенью подробности, гибкости и мобильности.
Специальная функция FUNCTION обеспечивает доступ к функциональному объекту, а функция FUNCALL обеспечивает применение функции к произвольному числу ее аргументов.
(funcall f a1 a2 ... ) = (apply f (list a1 a2 ...))
Разрастание числа функций, манипулирующих функциями, связано с реализационным различием структурного представления данных и представляемых ими функций.
NULL x) y)
(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)) ) ) )) |
Пример 8.1. |
Закрыть окно |
defun UNION-
( 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)) ) ) ))
Пример (CAR '(A B))
(CAR '(A B)) = (CAR (QUOTE(A B))) |
Пример 8.2. |
Закрыть окно |
Пример (CONS 'A '(B . C))
(CONS 'A '(B . C)) |
Пример 8.3. |
Закрыть окно |
Пример CDR (QUOTE (C . D)
(CONS '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) ) |
Пример 8.4. |
Закрыть окно |
Пример (CONS '(CAR (QUOTE (A . B)))
(CONS '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )
Программы для Лисп-интерпретатора.
Цель этой части - помочь на первых шагах избежать некоторых общих ошибок.
(CAR '(A B)) = (CAR (QUOTE(A B)))
Пример 8.2.
(html, txt)
Функция: CAR
Аргументы: ((A B))
Значение есть A. Заметим, что интерпретатор ожидает список аргументов. Единственным аргументом для CAR является (A B). Добавочная пара скобок возникает т.к. APPLY подается список аргументов.
Можно написать (LAMBDA(X)(CAR X)) вместо просто CAR. Это корректно, но не является необходимым.
(CONS 'A '(B . C))
Пример 8.3.
(html, txt)
Функция: CONS
Аргументы: (A (B . C))
Результат (A . (B . C)) программа печати выведет как (A B . C)
(CONS '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )
Пример 8.4.
(html, txt)
Функция: CONS
Аргументы: ((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))
Значением такого вычисления будет ((CAR (QUOTE (A . B))) . (CDR (QUOTE (C . D))))
Скорее всего это отнюдь не то, что ожидал новичок. Он рассчитывал вместо (CAR (QUOTE (A . B)) получить A и ожидал (A . D) в качестве итогового значения CONS. Кроме очевидного стирания апострофов:
(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))) )
ниже приведены еще три правильных способа записи нужной формы. Первый состоит в том, что CAR и CDR части функции задаются с помощью LAMBDA в определении функции. Второй - в переносе CONS в аргументы и вычислении их с помощью EVAL при пустом а-списке. Третий - в принудительном выполнении константных действий в представлении аргументов,
((LAMBDA (X Y) (CONS (CAR X) (CDR Y))) '(A . B) '(C . D))
Функция:
(LAMBDA (X Y) (CONS (CAR X) (CDR Y)))
Аргументы:
((A . B)(C . D))
(EVAL '(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D)))) Nil)
Функция: EVAL
Аргументы:
((CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D)))) Nil)
Значением того и другого является (A . D)
((LAMBDA (X Y) (CONS (EVAL X) (EVAL Y))) '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )
Функция:
(LAMBDA (X Y) (CONS (EVAL X) (EVAL Y)))
Аргументы:
((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))
Решения этого примера показывают, что грань между функциями и данными достаточно условна - одни и те же вычисления можно осуществить при разном распределении промежуточных вычислений внутри выражения, передвигая эту грань.
(Defconstant Атом Форма ) | Глобальная константа |
(Defparameter Атом Форма ) | Глобальная переменная |
(Defun Название Параметры Форма ) | Определение функции |
(Flet ((Название Параметры Форма) … (Спецификации … Формы …)) | Вводит локальные нерекурсивные функции |
(Labels ( (Название Параметры Форма) … (Спецификации … Формы …) ) | Вводит локальные рекурсивные функции |
Цель этой части - помочь на первых шагах избежать некоторых общих ошибок.
(CAR '(A B)) = (CAR (QUOTE(A B)))
Пример 8.2.
Функция: CAR
Аргументы: ((A B))
Значение есть A. Заметим, что интерпретатор ожидает список аргументов. Единственным аргументом для CAR является (A B). Добавочная пара скобок возникает т.к. APPLY подается список аргументов.
Можно написать (LAMBDA(X)(CAR X)) вместо просто CAR. Это корректно, но не является необходимым.
(CONS 'A '(B . C))
Пример 8.3.
Функция: CONS
Аргументы: (A (B . C))
Результат (A . (B . C)) программа печати выведет как (A B . C)
(CONS '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )
Пример 8.4.
Функция: CONS
Аргументы: ((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))
Значением такого вычисления будет ((CAR (QUOTE (A . B))) . (CDR (QUOTE (C . D))))
Скорее всего это отнюдь не то, что ожидал новичок. Он рассчитывал вместо (CAR (QUOTE (A . B)) получить A и ожидал (A . D) в качестве итогового значения CONS. Кроме очевидного стирания апострофов:
(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))) )
ниже приведены еще три правильных способа записи нужной формы. Первый состоит в том, что CAR и CDR части функции задаются с помощью LAMBDA в определении функции. Второй - в переносе CONS в аргументы и вычислении их с помощью EVAL при пустом а-списке. Третий - в принудительном выполнении константных действий в представлении аргументов,
((LAMBDA (X Y) (CONS (CAR X) (CDR Y))) '(A . B) '(C . D))
Функция:
(LAMBDA (X Y) (CONS (CAR X) (CDR Y)))
Аргументы:
((A . B)(C . D))
(EVAL '(CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D)))) Nil)
Функция: EVAL
Аргументы:
((CONS (CAR (QUOTE (A . B))) (CDR (QUOTE (C . D)))) Nil)
Значением того и другого является (A . D)
((LAMBDA (X Y) (CONS (EVAL X) (EVAL Y))) '(CAR (QUOTE (A . B))) '(CDR (QUOTE (C . D))) )
Функция:
(LAMBDA (X Y) (CONS (EVAL X) (EVAL Y)))
Аргументы:
((CAR (QUOTE (A . B))) (CDR (QUOTE (C . D))))
Решения этого примера показывают, что грань между функциями и данными достаточно условна - одни и те же вычисления можно осуществить при разном распределении промежуточных вычислений внутри выражения, передвигая эту грань.
(Defconstant Атом Форма ) | Глобальная константа |
(Defparameter Атом Форма ) | Глобальная переменная |
(Defun Название Параметры Форма ) | Определение функции |
(Flet ((Название Параметры Форма) … (Спецификации … Формы …)) | Вводит локальные нерекурсивные функции |
(Labels ( (Название Параметры Форма) … (Спецификации … Формы …) ) | Вводит локальные рекурсивные функции |
Чтобы выполнить вычисление на реальном
Чтобы выполнить вычисление на реальном Лисп-интерпретаторе необходимо уточнить ряд правил по оформлению текста Лисп-программы.Определения функций можно сделать обозримее именованием выражений. Это дает и экономию на времени вычисления совпадающих форм.При реализации практичной системы программирования возникают дополнительные механизмы, такие как списки свойств атома, повышающие скорость доступа к необходимой информации.Некоторые функции системы необходимо реализовывать в виде машинных подпрограмм. Они образуют ядро системы.При подготовке программ для Лисп-интерпретатора грань между программой и данными может устанавливаться в зависимости от требований к решению задачи.