Обработка списков
Языку LISP можно дать очень лаконичное формальное определение. Большинство LISP-программ можно специфицировать, используя только пять простейших операторов над символическими выражениями (см. врезку 4.4) и одну специальную форму (условное выражение). Эта элегантность и красота языка LISP часто не заметна неопытному взгляду, поскольку большинство LISP-приложений включает множество дополнительных операторов, собственно к LISP не относящихся. Современные диалекты LISP в буквальном смысле задыхаются от программных конструкций, заимствованных из языка FORTRAN, некоторые из которых оказались полезными, а другие просто вызывают отвращение (справедливости ради, нужно отметить, что некоторые обладают и тем и другим).
Как оказалось, структурой, наиболее подходящей для нечисловых вычислений, являются списки. Именно такие вычисления необходимо выполнять в процессе поиска решения в пространстве альтернатив, как это было показано в главе 2. В списке можно держать в поле зрения те альтернативные варианты, которые уже были рассмотрены ранее, не которые еще предстоит рассмотреть, и т.д. Поскольку между списками и древовидными ориентированными графами существует изоморфизм, естественно представлять развернутое пространство состояний в виде одного или более списков.
Примитивы в 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 организуется рекурсивная обработка списков.