Основы функционального программирования

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


Исторически при реализации Лиспа в качестве единой базовой структуры для конструирования 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)

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