Точечная нотация

Исторически при реализации Лиспа в качестве единой базовой структуры для конструирования S-выражений использовалась так называемая "точечная нотация" (dot-nоtation), согласно которой левая и правая части бинарного узла равноправны и могут хранить данные любой природы.

Бинарный узел, содержащий пару атомов  ATOM1 и ATOM2, можно представить в виде S-выражения вида:

( ATOM1 . ATOM2 )

Таблица 2.1. Операции над списками. Примеры соответствия аргументов и результатов

ФункциияАргументыРезультат Конструирование структур данных  Доступ к компонентам структуры данных:  Слева  Справа  Смешанная обработка данных:  Предикаты:  Атомарность — неделимость  Равенство 

CONS	A и Nil	(A )
CONS	(A B) и Nil	((A B) )
CONS	A и (B)	(A B)
CONS	(Результат предыдущего CONS) и (C)	((A B) C)
CONS	A и (B C)	(A B C)
CAR	(A B C)	A
CAR	(A (B C))	A
CAR	((A B) C)	(A B)
CAR	A	не определен
CDR	(A )	Nil
CDR	(A B C D)	(B C D)
CDR	(A (B C))	((B C))
CDR	((A B) C)	(C)
CDR	A	не определен
CDR	(A B C)	(B C)
CAR	результат предыдущего CDR	B
CAR	(A C)	A
CAR	результат предыдущего CAR	не определен
CONS	A и (B)	(A B)
CAR	результат предыдущего CONS	A
CONS	A и (B)	(A B)
CDR	результат предыдущего CONS	(B)
ATOM	VeryLongStringOfLetters	T
CDR	(A B)	(B)
ATOM	результат предыдущего CDR	Nil
ATOM	Nil	T
ATOM	( )	T
EQ	A A	T
EQ	A B	Nil
EQ	A (A B)	Nil
EQ	(A B) (A B)	не определен
EQ	Nil и ( )	T

Если вместо атомов ATOM1, ATOM2 рекурсивно подставлять произвольные атомы, затем построенные из них пары и так далее, то получим множество всех возможных S-выражений. Можно сказать, что S-выражение — это или атом или заключенная в скобки пара из двух S-выражений, разделенных точкой. Все сложные данные выстраиваются из одинаково устроенных блоков — бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти.

ATOM (A . B) (C . (A . B)) ((A . B) . C) ((A . B) . (D . C)) ((A .
B) . (D . (C . E)))

Любое S- выражение может быть построено из атомов с помощью CONS, и любая его часть может быть выделена с помощью CAR-CDR.

Расширение типа данных, допускаемых в качестве второго аргумента CONS, ни в малейшей степени не усложняет реализацию этой функции, равно как и реализацию функций CAR и CDR, зато их описания становятся проще. Функция CONS строит бинарный узел и заполняет его парой объектов, являющихся значениями пары ее аргументов. Первый аргумент размещается в левой части бинарного узла, а второй — в правой. Функция CAR обеспечивает доступ к объектам, расположенным слева от точки, а функция CDR — справа.

Таблица 2.2. Операции над произвольными S-выражениямиФункцияАргументыРезультат Конструирование структур данных  Доступ к компонентам структуры данных:  Слева  Справа  Смешанная обработка данных:  Тождества: (на произвольных объектах)  

Предикаты:   Атомарность — неделимость  Равенство: 

CONS	A и B	(A . B)
CONS	(A . B) и C	((A . B) . C)
CONS	A B	(A . B)
CONS	(результат предыдущего CONS) и C	((A . B) . C)
CAR	(A . B)	A
CAR	((A . B) . C)	(A . B)
CDR	(A . B)	B
CDR	(A . (B . C))	(B . C)
CONS	A и B	(A . B)
CAR	результат предыдущего CONS	A
CONS	A и B	(A . B)
CDR	результат предыдущего CONS	B
CDR	(A . (B . C))	(B . C)
CAR	результат предыдущего CDR	B
CDR	(A . C)	C
CAR	результат предыдущего CDR	не определен
CONS	два произвольных объекта x и y	(x . y)
CAR	результат предыдущего CONS	исходный объект x (первый аргумент CONS)
CONS	два произвольных объекта x и y	(x . y)
CDR	результат предыдущего CONS	исходный объект y (второй аргумент CONS)
CAR	произвольный составной объектx	(CAR x)
CDR	тот же самый объект x - не атом	(CDR x)
CONS	результаты предыдущих CAR и CDR	исходный объект x
ATOM	(A . B)	Nil - выполняет роль ложного значения
CDR	(A . B)	B
ATOM	результат предыдущего CDR	T
EQ	(A . B) (A . B)	не определен

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


Практически сразу была предложена более лаконичная запись наиболее употребимого подкласса S-выражений в виде списков произвольной длины вида (A B C D E F G H ). В виде списков можно представить лишь те S-выражения, в которых при движении вправо в конце концов обнаруживается атом Nil, символизирующий завершение списка.

Атом Nil, рассматриваемый как представление пустого списка (), играет роль ограничителя в любом списке. Одноэлементный список (A) идентичен S-выражению (A . Nil). Список (A1 A2 ... Ak) может быть представлен как S-выражение вида:

(A1 . (A2 . ( ... . (Ak . Nil) ... ))).

В памяти это фактически одна и та же структура данных. (Запятая в качестве разделителя элементов списка в первых реализациях Лиспа поддерживалась, но не прижилась. Пробел оказался удобнее.)

Для многошагового доступа к отдельным элементам такой структуры удобно пользоваться мнемоничными обозначениями композиций из многократных CAR-CDR. Имена таких композиций устроены как цепочки из "a" или "d", задающие маршрут движения из шагов CAR и CDR, соответственно, расположенный между "c" и "r". Указанные таким способом CAR-CDR исполняются с ближайшего к аргументу шага, т.е. в порядке, обратном записи.

Таблица 2.3. Соответствие списков и равнозначных им S-выраженийList-notation — списочная запись объектаDot-notation — точечная нотация того же объекта

(A B C)	(A . (B . (C . Nil)))
((A B) C)	((A . (B . Nil)) . (C . Nil))
(A B (C E))	(A . (B . ((C . (E . Nil)). Nil)))
(A)	(A . Nil)
((A))	((A . Nil) . Nil)
(A (B . C))	(A . ((B . C) . Nil))
(())	(Nil . Nil)

Таблица 2.4. Примеры многошагового доступа к элементам структуры Многократные CAR-CDR Вычисляются в порядке, обратном записи:

Caar	((A) B C)	A
Cadr	(A B C)	B — CDR затем CAR
Caddr	(A B C)	C — (дважды CDR) затем CAR
Cadadr	(A (B C) D)	C — два раза (CDR затем CAR)

Содержание раздела

---

---