Списки и атомы

Основы символьной обработки

Идеальный Лисп изначально поддерживает программирование в функциональном стиле. Его основа - выбор подходящей структуры данных и базового набора функций над выбранной структурой. Информационная обработка в языке Лисп отличается от стандартных подходов к программированию тремя важными особенностями:

Структуры данных

Любые структуры данных строятся из более простых составляющих, простейшие из которых – элементарные данные. В Лиспе элементарные данные называют атомами. Для начала примем, что атом – это последовательность из букв и цифр, начинающаяся с буквы.

A
Nil
ATOM
LISP
Занятие2
Новый_год
ВотДлинныйАтомНуОченьДлинныйНоЕслиНадоАтомМожетБытьЕщеДлинннее 
Ф4длш139к131б

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

Более сложные данные в Лиспе выстраиваются из одинаково устроенных бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти, выделяемому системой программирования при организации и обработке структур данных. Выделение блока памяти и размещение в нем пары данных выполняет функция CONS (от слова consolidation), а извлечение левой и правой частей из блока выполняют функции CAR и CDR соответственно ("content of address part of register" , "content of decrement part of register").

При работе с системой соответствующие выражения показаны ниже:

Типичная форма записи символьных выражений называется списочной записью ( list-notation ). Элементы списка могут быть любой природы.

Список – это перечень произвольного числа элементов, разделенных пробелами, заключенный в круглые скобки.

По соглашению атом Nil выполняет роль пустого списка. Бинарный узел, содержащий пару атомов ATOM и Nil, рассматривается как одноэлементный список (ATOM ):

или для наглядности:

Если вместо атома " ATOM " подставлять произвольные атомы, а вместо " Nil " - произвольные списки, затем вместо атомов - построенные списки и так далее, то мы получим множество всех возможных списков. Можно уточнить, что список - это заключенная в скобки последовательность из разделенных пробелами атомов или списков.

(C )

(B C )

(C (A B))

(рис 3.2) 
Упражнения 3.1.: Нарисуйте диаграммы для списков вида:
((A B) C)

((A B)  (D C))

((A B)(D(C E)))
Любой список  может быть построен из пустого списка и атомов  с помощью CONS  и любая его часть может быть выделена с помощью подходящей композиции CAR-CDR.
CONS  - Функция, которая строит списки из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается  в левой части бинарного узла, а второй, являющийся списком, - в правой.
CAR  – Функция, обеспечивающая доступ к первому элементу списка - его "голове".
CDR  – Функция, укорачивающая список   на один элемент. Обеспечивает доступ к "хвосту" списка, т.е. к остатку списка после удаления его головы.
ATOM   - Функция, различающая составные и атомарные объекты.  На атомах  ее значение "истина", а на более сложных структурах данных – "ложь".
EQ  – Функция, которая проверяет атомарные объекты на равенство.
Элементарные функции над списками. Примеры соответствия между аргументами и результатами элементарных функций обработки списков.
Функция
		 
Аргументы
		 
Результат
Конструирование структур данных
CONS
A   и  Nil
(A )

CONS
(A  B)  и  Nil
((A  B) )

CONS
CONS

A   и   (B)
(Результат предыдущего  CONS)   и  ( C )

(A  B)
((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
CAR

(A B C)
Результат предыдущего CDR

(B  C)
B


CAR
CAR

(A   C)
Результат предыдущего CAR

A
Не определен


CONS
CAR

A  и   (B)
Результат предыдущего CONS

(A  B)
A


CONS
CDR

A   и  (B)
Результат предыдущего CONS

(A  B)
(B)


Предикаты:
Атомарность – неделимость
ATOM
VeryLongStringOfLetters
T

ATOM
( A  B )
Nil - выполняет  роль ложного значения

CDR
ATOM

( A  B )
Результат предыдущего  CDR

(B)
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


Различие истинностных значений  в Лиспе принято отождествлять с разницей между пустым списком и остальными объектами, которым программист может придать в программе некоторый другой смысл. Таким образом, значение "ложь" – это всегда Nil.
Если требуется явно изобразить значение "истина", то используется стандартная константа – атом T (true), но роль значения "истина" может выполнить любой, отличный от пустого списка, объект.
Упражнение 3.2. Посмотрите, что сделает Лисп-система с ниже приведенными  выражениямиЛатинский шрифт используется исключительно ради простоты набора текстов. Вполне допустима кириллица , сравнивая результаты с данными из таблицы 3.1:
(CONS 'Head  Nil )
(CONS 'Head  '(Body Tail) )
(CAR '(Head Body Tail))
(CDR '(Head Body Tail))
(ATOM  'Body)
(ATOM  '(Body))
(ATOM  ())
(ATOM  (CAR '(Head Body Tail)))
(EQ Nil ())
Точечная нотация
При реализации Лиспа в качестве единой универсальной базовой структуры для конструирования символьных выражений  использовалась так называемая "точечная нотация"  ( dot-nоtation ),  согласно которой левая и правая части бинарного узла равноправны и могут хранить данные любой природы.
Бинарный узел, содержащий пару атомов ATOM1  и ATOM2,
можно представить как запись вида:
( ATOM1 .  ATOM2 )
Если вместо атомов " ATOM1 ", " ATOM2 " рекурсивно подставлять произвольные атомы, затем построенные из них пары и так далее, то мы получим множество всех возможных составных символьных выражений – S-выражений.
S-выражение  - это или атом  или заключенная в скобки пара из двух S-выражений, разделенных точкой.
Все сложные данные создаются из одинаково устроенных  блоков - бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти.
Списки – это подмножество S-выражений, движение вправо по которым завершается атомом Nil.
(A . B)
(C . (A . B))
(рис 3.3) 
Любое S-выражение  может быть построено из атомов  с помощью CONS  и любая его часть может быть выделена с помощью CAR-CDR.
Упражнение 3.3.  Нарисуйте диаграммы для следующих S-выражений:
((A . B) . C)
((A . B) . (D . C))
((A . B) . (D . (C . E)))
Расширение типа данных, допускаемых в качестве второго аргумента " CONS ", ни в малейшей степени не усложняет реализацию этой функции, равно как и реализацию функций " CAR " и " CDR ", зато их описания становятся проще:
CONS   - Функция, которая строит бинарный узел и заполняет его парой объектов, являющихся значениями пары ее аргументов. Первый аргумент размещается в левой части бинарного узла, а второй - в правой.
CAR  – Функция, обеспечивающая доступ к объектам, расположенным слева от точки в точечной нотации, т.е. в левой части бинарного узла.
CDR  - Функция, обеспечивающая доступ к объектам, расположенным справа от точки в точечной нотации, т.е. в правой части бинарного узла.
Элементарные функции  над произвольными S-выражениями
Функция
		 
Аргументы
		 
Результат
Конструирование структур данных
CONS
A   и B
(A . B)

CONS
(A . B)  и  C
((A . B) . C)

CONS
CONS

A    B
(Результат предыдущего  CONS)   и   C

(A . B)
((A . B) . C)


Доступ к компонентам структуры данных:
Слева
CAR
(A .  B)
A

CAR
((A . B) . C)
(A . B)

Справа
CDR
(A . B)
B

CDR
(A . (B . C))
(B . C)

Обработка данных:
CDR
CAR

(A . (B . C))
Результат предыдущего CDR

(B . C)
B


CDR
CAR

(A .  C)
Результат предыдущего CDR

C
Не определен


CONS
CAR

A  и   B
Результат предыдущего CONS

(A . B)
A


CONS
CDR

A   и  B
Результат предыдущего CONS

(A . B)
B


Тождества:(на произвольных объектах)
CONS
CAR

Два произвольных объекта  x  и  y.
Результат предыдущего CONS

Исходный объект  x
(первый аргумент CONS )


CONS
CDR

Два произвольных объекта  x  и  y.
Результат предыдущего CONS.

Исходный объект   y
(второй аргумент CONS )


CAR
CDR
CONS

Произвольный составной объект   x  - не атом.
Тот же самый объект   x.
Результаты предыдущих  CAR   и   CDR

Исходный объект   x

Предикаты:
Атомарность – неделимость
ATOM
( A . B )
Nil - выполняет роль ложного значения

CDR
ATOM

( A . B )
Результат предыдущего  CDR

B
T


Равенство
EQ
(A . B)  (A . B)
Не определен


Точечная нотация  может точно представлять логику хранения любых структур данных в памяти и доступа к компонентам структур данных. В виде списков можно представить лишь те S-выражения, в которых при движении вправо в конце концов обнаруживается атом Nil, символизирующий завершение списка.
Упражнение 3.4. Посмотрите, что делает Лисп-система с ниже приведенными выражениями, сравнивая результаты с данными из таблицы 3.2:
(CONS 'Head  'Tail )
(CAR '(Head . Tail))
(CDR '(Head . Tail))
(ATOM  'Atom)
(ATOM  ())
(ATOM  (CAR '(Head . Tail)))
(EQ Nil ())
Атом Nil, рассматриваемый как представление пустого списка (), выполняет роль ограничителя в списках. Одноэлементный список  (A)  идентичен S-выражению (A . Nil). Список (A1 A2 … Ak)  может быть представлен как S-выражение  вида:
(A1 . (A2 . ( … . (Ak . Nil) … ))).
В памяти это фактически одна и та же структура данных.
Соответствие списков и равнозначных им 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)

(A B . C)
(A . (B . C))


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

		  
Композиции 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)


Упражнение 3.5. Посмотрите, что делает Лисп-система с ниже приведенными выражениями, сравнивая результаты с данными из таблицы 3.3:
(cAAr '((A) B C) )
(cADr '(A B C))
(cADDr '(A B C) )
(cADADr '(A (B C) D))
Clisp: Функции для работы с данными
(Append Список … )
Сцепляет списки, полученные как аргументы

(Assoc  Атом А-список)
Находит в А-списке пару, левая часть которой – Атом

Atom
Проверка на атомарность

Car
Первый элемент списка или левый элемент структуры

Cdr
Результат удаления первого элемена из списка или правый элемент структуры

Cons
Создание узла из двух элементов

(Eq  Данное1 Данное2)
Истина при идентичных данных

(Equal  Структура1 Структура2 )
Истина при эквивалентных структурах

(Delete  Объект Список )
Строит копию Списка без заданного объекта

(Intersection  Список … )
Пересечение списков

(Last  Список )
Последний элемент структуры, представляющей список. Можно задавать длину завершающего отрезка списка.

(Length  Список )
Длина списка

(List  Форма … )
Строит список из значений Форм

(Member  Объект Список )
Ищет Объект в Списке

(Null  Форма)
Истина для Nil

(Pairlis  Атомы Данные А-спиок)
Пополняет А-список парами из Атомов и значений, соответствующих Данных.

(Reverse Список )
Копия Списка с обратным порядком элементов

(Set-difference Список … )
Разность множеств, представленных Списками

(Sort Список Предикат )
Упорядочивает Список согласно Предикату

(Sublis  А-список Структура )
Преобразует Структуру согласно А-списку методом подстановки данных вместо связанных с ними атомов.

(Subst  Новое Старое Структура )
Преобразует Структуру, заменяя Старое на Новое.

(Union Список … )
Объединение множеств, представленных Списками.


Выводы:
Список – это перечень произвольного числа элементов, разделенных пробелами, заключенный в круглые скобки.
Элементы списка могут быть любой природы.
S-выражение  - это или атом  или заключенная в скобки пара из двух S-выражений, разделенных точкой. Список  – частный случай S-выражения.
Любое S-выражение  может быть построено из атомов  с помощью CONS  и любая его часть может быть выделена с помощью CAR-CDR.
Для изображения S-выражений используют различные нотации: графическую, точечную и списочную.
Базис Лиспа содержит элементарные функции CAR, CDR, CONS, EQ, ATOM.