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

Если А₁ и А₂ суть символические выражения, то (А₁ A₂)— это также символические выражения.

Если S = (А,. (А₂. (.... (А_п-1. AJ....))) — суть символическое выражение для некоторого п>0, то S — список тогда и только тогда, когда А_n =NIL.

В соответствии с этим определением, если п=0, то S представляет собой пустой список, NIL. Такое определение допускает существование списка списков, а также списка атомов. Если S₁ S₂,..., S_n— символические выражения, то мы будем представлять список

S₁.(S₂.(.... (S_n. NIL)....)))

В виде

(S₁ S₂.... S_n)

Таким образом, (А. (В. NIL)) является списком. Он представляет список (А В), но (А. (В. С)) списком не является, поскольку (С=NIL)).

Символическое выражение, которое не является ни атомом, ни списком, называется точечной парой. Если (А. В) — точечная пара, то А — это голова пары, а B — ее хвост. Точечные пары могут иметь произвольную сложность. Так, ((А. В). С) — тоже точечная пара, так же, как и ((А. В). (С. D)). Благодаря наличию соответствия между точечными парами и списками, понятия головы и хвоста определены и для списков. Поскольку список (А В) — это (А. (В. NIL)), то очевидно, что А — голова в списке (А В), а хвост — это (В), но не В. Хвостом списка (В) является NIL

Структура LISP-программы

Как использовать список в качестве базовой структуры данных, понятно. Сложнее представить себе, как можно организовать программу или выражение программы в виде списка. Например, список

(+ X Y) представляет математическое выражение в форме

(<функция> <1-й аргумент> <2-й аргумент>),

которое обозначает сложение двух чисел. Такой метод обозначений (нотация) отличается от привычного нам обозначения функции п переменных в виде f(x₁,... x_n). Но возникает вопрос, как компилятор или интерпретатор отличает данные от программы, если и то и другое представлено списками.

Необходимо иметь возможность определить значение такого выражения— например, значение выражения (+ X Y). Для этого нужно отыскать определение функции (в данном случае — функции +). В этом определении должна содержаться та последовательность элементарных операций, которую нужно применить к аргументам, чтобы определить значение функции.

Нужно иметь средства сформировать определение функции и применить это определение к аргументам, т.е. к действительным, а не формальным параметрам. Механизм определения функции и приложения функции базируется на логической системе, названной лямбда-исчислением (см. [Church, 1941]). Лямбда-исчисление является скорее функциональным, чем исчислением отношений, и в этом состоит различие между ним и исчислением предикатов первого порядка. В функциональном исчислении первичным понятием является отношение "многие-к-одному", а не "многие-ко-многим". Так, отец — это функциональное отношение, а брат — более общее отношение, поскольку каждый человек может иметь только одного отца, а братьев может быть несколько. Ниже в этой главе мы более подробно остановимся на связях между языком LISP и лямбда-исчислением.

Нужно располагать средствами доступа к текущим значениям переменных (или формальных параметров), таких как X и Y. Вычисление каждого символического выражения выполняется в контексте формирования переменных. Нужно располагать средствами сохранения и восстановления этого контекста при вычислении значений сложных символических выражений, т.е. вычисления и комбинирования значений содержащихся в них подвыражений.

При вычислении сложных символических выражений, когда необходимо вычислять значения его компонентов, которые являются сложными выражениями, нужно располагать средствами сохранять текущее выражение и промежуточные результаты. Необходимо также обладать средствами копирования символических выражений.

Нужно уметь подавлять вычислительную обработку списков, которые не являются операторами программы, а структурами данных. Например, не нужно пытаться вычислять выражение, подобное следующему:

((1 2 3)(4 5 6)(7 8 9))