Структуры данных
Любые структуры данных строятся из более простых составляющих, простейшие из которых – элементарные данные. В Лиспе элементарные данные называют атомами. Для начала примем, что атом – это последовательность из букв и цифр, начинающаяся с буквы.
A Nil ATOM LISP Занятие2 Новый_год ВотДлинныйАтомНуОченьДлинныйНоЕслиНадоАтомМожетБытьЕщеДлинннее Ф4длш139к131б
Пример 3.1.
(html, txt)
Одинаково выглядящие атомы не различимы по своим свойствам. Термин "атом" выбран по аналогии с химическими атомами, строение которых – предмет другой науки. Согласно этой аналогии атом может иметь достаточно сложное строение, но атом не предназначен для разбора на части базовыми средствами языка.
Более сложные данные в Лиспе выстраиваются из одинаково устроенных бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти, выделяемому системой программирования при организации и обработке структур данных. Выделение блока памяти и размещение в нем пары данных выполняет функция CONS (от слова consolidation), а извлечение левой и правой частей из блока выполняют функции CAR и CDR соответственно ("content of address part of register" , "content of decrement part of register").
| Cons |
Атом X | ( Атом . X ) | |
| Car | ( Атом . X ) | Атом | |
| Cdr | ( Атом . X ) | X |
При работе с системой соответствующие выражения показаны ниже:
| Cons |
Атом X | (CONS 'ATOM ' X ) | |
| Car | ( Атом . X ) | (CAR '(ATOM . X ) | |
| Cdr | ( Атом . X ) | (CDR '(ATOM . X ) |
Типичная форма записи символьных выражений называется списочной записью (list-notation). Элементы списка могут быть любой природы.
Список – это перечень произвольного числа элементов, разделенных пробелами, заключенный в круглые скобки.
По соглашению атом Nil выполняет роль пустого списка. Бинарный узел, содержащий пару атомов ATOM и Nil, рассматривается как одноэлементный список (ATOM ) :
или для наглядности:
Если вместо атома "ATOM" подставлять произвольные атомы, а вместо "Nil" - произвольные списки, затем вместо атомов - построенные списки и так далее, то мы получим множество всех возможных списков. Можно уточнить, что список - это заключенная в скобки последовательность из разделенных пробелами атомов или списков.
(C )
(B C )
(C (A B))
Пример 3.2.
(html, txt)
Можно уточнить, что список - это заключенная в скобки последовательность из разделенных пробелами атомов или списков.
(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 | (A B) (A B) | Не определен |
| EQ | Nil и () | T |
Если требуется явно изобразить значение "истина", то используется стандартная константа – атом T (true), но роль значения "истина" может выполнить любой, отличный от пустого списка, объект.
Упражнение 3.2. Посмотрите, что сделает Лисп-система с ниже приведенными выражениями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 ())
