Lisp: основное правило вычисления

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск

В базовом Лиспе есть только два типа объектов: атомы и списки. Под списком подразумевается любая последовательность допустимых объектов, то есть атомов или снова списков (а значит, допускаются вложенные списки). Атомы бывают двух видов: константы (1, 2, …, T для истины и Nil для лжи или пустого списка) и «символы». Символы очень похожи на идентификаторы (имена переменных, функций и т. п.) в привычных языках программирования, однако имеются особенности. Можно сказать, что каждый символ имеет два значения: обычное значение и функциональное значение (однако любое из них может быть пустым). «Функциональное значение» означает, что с любым символом может быть связана некоторая функция.

Любой объект в Лиспе вычисляется по достаточно простому основному правилу вычисления.

  1. Константы вычисляются к своему собственному значению.
  2. Символы вычисляются к своему обычному значению.
  3. Списки вычисляются так: первый элемент списка (обычно — символ, иначе ошибка) вычисляется к своему функциональному значению, последующие элементы сначала вычисляются с помощью данного основного правила рекурсивно, а полученные в результате этого значения передаются полученной от первого элемента списка функции в качестве аргументов.

Таким образом, любое нетривиальное вычисление в Лиспе выглядит как список, первый элемент которого это «имя» функции. Например:

> (+ 1 2)
3

(Здесь символ > означает, что этот пример вводится в окно интерпретатора Lisp.) В свете основного правила очевидно, что следующая запись приведёт к ошибке.

> (1 + 2)
*** - EVAL: 1 не является именем функции


Довольно часто возникает необходимость отложить вычисление тех или иных объектов. Пример: для каких-либо целей нужен список символов TO BE OR NOT TO BE. Это 6 символов, которым покамест не приписано никаких значений (ни обычных, ни функциональных). Самый простой способ получить в Лиспе список — использовать круглые скобки. Таким образом, можно было бы написать:

> (TO BE OR NOT TO BE)
*** - EVAL: функция TO не определена

Однако по правилу вычисления списков транслятор обязан найти функциональное значение символа TO, затем найти обычные значения символов BE, OR и т. д. Ясно, что это приводит к ошибке. Чтобы отменить вычисление этого списка следует использовать «квотирование»:

> '(TO BE OR NOT TO BE)
(TO BE OR NOT TO BE)

В этом случае интерпретатор остался довольным и вывел результат введённого выражения — нужный нам список.

Правило вычисления квотированных объектов звучит так: квотированный объект всегда вычисляется к самому себе. То есть, к примеру, символ вычисляется к символу, а не к своему обычному значению (как в основном правиле), список остаётся списком и т. д.

Если необходимо ввести список, часть элементов которого нужно вычислить (скажем, некоторое арифметическое выражение), квотировать его целиком нельзя. В этом случае можно использовать специальную функцию построения списков list:

> (list (+ 1 2) NO PASARAN)
*** - SYSTEM::READ-EVAL-PRINT: variable NO has no value

Мы попытались объявить список из трёх объектов (список (+ 1 2) и два символа), однако, следуя основному правилу, для успешного вычисления символы должны иметь обычные значения, которые мы не задавали. Запретить транслятору вычисление символов без значений можно с помощью квот:

> (list (+ 1 2) 'NO 'PASARAN)
(3 NO PASARAN)