Обработксписков
Языку LISP можно дать очень лаконичное формальное определение. Большинство LISP-программ можно специфицировать, используя только пять простейших операторов над символическими выражениями (см. врезку 4.4) и одну специальную форму (условное выражение). Эта элегантность и красота языка LISP часто не заметна неопытному взгляду, поскольку большинство LISP-приложений включает множество дополнительных операторов, собственно к LISP не относящихся. Современные диалекты LISP в буквальном смысле задыхаются от программных конструкций, заимствованных из языка FORTRAN, некоторые из которых оказались полезными, а другие просто вызывают отвращение (справедливости ради, нужно отметить, что некоторые обладают и тем и другим).
Как оказалось, структурой, наиболее подходящей для нечисловых вычислений, являются списки. Именно такие вычисления необходимо выполнять в процессе поиска решения в пространстве альтернатив, как это было показано в главе 2. В списке можно держать в поле зрения те альтернативные варианты, которые уже были рассмотрены ранее, не которые еще предстоит рассмотреть, и т.д. Поскольку между списками и древовидными ориентированными графами существует изоморфизм, естественно представлять развернутое пространство состояний в виде одного или более списков.
4.4. Примитивы в LISP
В языке LISP имеется пять операций, которые, хотя и не имеют специальных наименований, лежат в основе всех остальных. LISP использует их в качестве виртуального машинного кода" при построении более сложных примитивов. Например, в LISP имеются полиморфные предикаты равенства.
Пусть s — множество символических выражений. Можно, например, записать:
Е(Х , Y): S x S -> {Т, NIL}
Это означает, что Е является функцией двух аргументов, причем оба аргумента — символические выражения из множества S, которые могут принимать значение либо Т, либо NIL.
(1)Е(Х , Y): S x S -> {Т, NIL} проверяет, равны ли два атома.
(2)А(Х): S -> {Т, NIL} проверяет, является ли символическое выражение атомом.
(З)Н(Х): S -> S извлекает голову символического выражения, которое не является атомом; если х — атом, то результат функции не определен.
(4) Т(Х): S —> S извлекает хвост символического выражения, которое не является атомом; если х — атом, то результат функции не определен.
(5)С(Х , Y): S х S —> S формирует символическое выражение; если А и в являются символическими выражениями , то можно сформировать новое символическое выражение (А . В).
Совокупности операции композиции функций и условного оператора описанных оераций вполне достаточно для того, чтобы вычислить любую обобщенную рекурсивную функцию. Композиция функций — это способность сделать значение одной срункции аргументом другой, т.е. организовать гнездование функций, например С(Н(Х), У).
Фактически система, состоящая из трех компонентов
(1) единственного атома NIL;
(2) условного выражения, проверяющего равенство, в форме
if E(X, NIL) then ... else ... 3) функций Н(Х), Т(Х), С(ХД)
к которым добавлена операция композиции функций, вполне позволяет реализовать машину Тьюринга (см. [Minsky, 1972, Chapter 10]).
Можно использовать списки и для представления ассоциативной связи одних символов с другими. Например, список
((Alabama Montgomery) (Alaska Juneau) (Arizona Phoenix) ... )
позволяет представить столицы пятидесяти штатов. Представленная ниже LISP-программа сможет затем извлечь название столицы заданного штата из этого ассоциативного списка.
(defun assoc (key alist)
(cond ((null alist) NIL)
((eq (first (first a list)) key) (first alist))
(T (assoc key (rest alist)))) )
Если обратиться к этой функции с помощью, например, выражения (assoc 'Alaska '((Alabama Montgomery) (Alaska Juneau) (Arizona Phoenix) ... ), то функция возвратит список
(Alaska Juneau) .
NULL — это предикат, который проверяет, не пуст ли список, EQ — предикат, который проверяет равенство двух атомов, FIRST — функция, которая возвращает головной элемент списка, a REST — функция, которая возвращает хвост списка (см.
врезку 4.4).
Основным условным выражением в LISP является COND. В приведенном выше фрагменте программного LISP-кода это условное выражение может быть расшифровано следующим образом:
если alist это null, то вернуть NIL, иначе
{
если головной элемент головного элемента alist равен key, то вернуть головной элемент alist,
иначе вернуть результат применения функции assoc к хвосту alist. }
Условное выражение COND можно представить в терминах примитива if-then-else, описанного во врезке 4.4. Выражение COND может включать сколько угодно вложенных конструкций if-then-else.
Конечно, ассоциативные списки — это не самое лучшее средство хранения данных, но наш пример с таким списком помог вам представить, как в LISP организуется рекурсивная обработка списков.
