4.3.4. Обработка списков

Языку 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 организуется рекурсивная обработка списков.