Списки и функциональные выражения
Основной единицей данных для LISP-системы является список.
Списки задаются следующим индуктивным определением.
- Пустой список () (обозначаемый также nil) является списком.
- Если l1,. . . , ln, n ≥ 1 - атомы либо списки, то (l1, . . . , ln) - также список.
Элементами списка (l1, . . . , ln) называются l1, . . . , ln. Равенство списков задается следующим индуктивным определением.
- l = nil тогда и только тогда, когда l также есть nil.
- (l1, . . . , ln) = (k1, . . . , km) тогда и только тогда, когда n = m и соответствующие li = ki.
Пример 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, а те, которые работают с атомами, часто к нему неприменимы.
Например, попытка присваивания значения выдает ошибку.
Основная операция для задания списков (list a b . . . z). Она вычисляет свои аргументы и собирает их в список. Для этой операции без вычисления аргументов есть скоропись '(a b . . . z). Она является частным случаем функции quote (сокращенно обозначаемой '), которая запрещает всякие вычисления в своем аргументе и копирует его в результат так, как он есть.
По традиции, элементарные операции разбора списков обозначаются именами, которые начинаются с c и кончаются на r, а в середине идет некоторая последовательность букв a и d; (car s) выделяет голову (первый член списка), (cdr s) - хвост (подсписок всех членов, начиная со второго). Буквы a и d применяются, начиная с конца. Общее число символов в получающемся атоме должно быть не больше шести. Рассмотрим фрагмент диалога, иллюстрирующий эти операции. Как только в диалоге вводится законченное выражение, оно вычисляется либо выдается ошибка.
[13]>(setq a '(b c (d e) f g)) (B C (D E) F G) [14]> (cddr a) ((D E) F G) [15]> (cddar a) *** - CDDAR: B is not a list 1. Break [16]> ^Z [17]> (caaddr a) D [18]> (cdaddr a) (E)
