Введение в программирование на Лиспе
Структуры данных
Любые структуры данных строятся из более простых составляющих, простейшие из которых – элементарные данные. В Лиспе элементарные данные называют атомами. Для начала примем, что атом – это последовательность из букв и цифр, начинающаяся с буквы.
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)