В различных диалектах языка допустимы вариации, но смысл остается тем же. В частности, в диалекте Common LISP используется сокращенная форма

(defun SQUARE (X) (X X)).

В любом случае имя функции, в данном случае SQUARE, ассоциируется в определении с лямбда-выражением. Выражение (LAMBDA (X) (X X)) — это просто синтаксический вариант ((ЛХ) (X X)). Фактически, если определено SQUARE, в любом диалекте LISP имеем

(SQUARE 3) = ((LAMBDA (X)

(X X)) 3) = ((АХ)(Х Х))(3) = 9.

Обратите внимание на то, что LAMBDA не является функцией. Это специальный оператор в лямбда-исчислении.

Синтаксическая форма вызова функции в языке LISP имеет вид

(<функция> <аргумент>... <аргумент>).

Это не самая сложная синтаксическая форма, а вместе с QUOTE, LAMBDA и условными выражениями этим фактически исчерпывается все, что необходимо знать о синтаксисе языка LISP. Тем, кто по каким-то иррациональным причинам испытывает тягу к запятым, двоеточиям, точкам с запятой, палиндромам вроде (if... ft, case... esac) и тому подобному, будет поначалу трудно свыкнуться с мыслью, что в LISP единственным ограничителем являются круглые скобки. Программа на языке LISP — это просто структура данных, и другая LISP-программа ее может читать, записывать и обрабатывать точно так же, как любой другой набор данных.

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

Языку 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 формирует символическое выражение; если А и в являются символическими выражениями, то можно сформировать новое символическое выражение (А. В).

Совокупности операции композиции функций и условного оператора описанных оераций вполне достаточно для того, чтобы вычислить любую обобщенную рекурсивную функцию. Композиция функций — это способность сделать значение одной срункции аргументом другой, т.е. организовать гнездование функций, например С(Н(Х), У).