Стили и методы программирования


Списки и функциональные выражения


Основной единицей данных для LISP-системы является список.

Списки задаются следующим индуктивным определением.

  1. Пустой список () (обозначаемый также nil) является списком.
  2. Если l1,. . . , ln, n
    1 — атомы либо списки, то (l1, . . . , ln) — также список.

Элементами списка (l1, . . . , ln) называются l1, . . . , ln. Равенство списков задается следующим индуктивным определением.

  1. l = nil тогда и только тогда, когда l также есть nil.
  2. (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 задаются следующим индуктивным определением.

  1. Элементы списка являются его вершинами.
  2. Вершины элементов списка являются его вершинами.

Длиной списка называется количество элементов в нем. Глубиной списка называется максимальное количество вложенных пар скобок в нем. Соединением списков (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, а те, которые работают с атомами, часто к нему неприменимы.


Начало  Назад  Вперед



Книжный магазин