Списки и функциональные выражения
Основной единицей данных для 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)
