Основной единицей данных для LISP-системы является список.
Списки задаются следующим индуктивным определением.
Элементами списка (l1, . . . , ln) называются l1, . . . , ln. Равенство списков задается следующим индуктивным определением.
Пример 8.2.2. Все списки (), (()), ((())) и т. д. различны. Различны также и списки nil, (nil, nil), (nil, nil, nil) и так далее. Попарно различны и списки ((a,b), c), (a, (b,c)), (a,b,c), где a, b, c - различные атомы.
Поскольку понятие, задаваемое индуктивным определением, должно строиться в результате конечного числа шагов применения определения, мы исключаем списки, ссылающиеся сами на себя. Списки в нашем рассмотрении изоморфны упорядоченным конечным деревьям, листьями которых являются nil либо атомы.
Вершины списка l задаются следующим индуктивным определением.
Длиной списка называется количество элементов в нем. Глубиной списка называется максимальное количество вложенных пар скобок в нем. Соединением списков (l1, . . . , ln) и (k1, . . . , km) называется список
(l1, . . . , ln, k1, . . . , km).
Замена вершины a списка l на атом либо список m получается заменой поддерева l, соответствующего a, на дерево для m. Замена обозначается l[a | m]. Через l[a || m] будем обозначать результат замены нескольких вхождений вершины a на m.
Атомами в языке lisp являются числа, имена, истина T. Ложью служит пустой список nil, который в принципе атомом не является, но в языке lisp при проверке на то, является ли он атомом, выдается истина. Точно так же выдается истина и при проверке, является ли он списком. Однако все списковые операции применимы к nil, а те, которые работают с атомами, часто к нему неприменимы.