Структуры данных в языке LISP
Одним из первых языков обработки списков был LISP2 [McCarthy, 1960]. За четыре десятилетия, которые прошли после появления его первой версии, язык неоднократно, модифицировался и расширялся, но в основе своей изменился мало. Разработчики языка утверждали, что LISP отличается от прочих языков программирования следующими свойствами [McCarthy et al, I960]:
- основной структурой
данных в нем является список;
- программы на этом языке
также имеют списочную структуру;
- его базовыми операциями
являются операции над списками.
Базовым блоком в структуре данных языка LISP является символическое выражение. Простое символическое выражение использует атомарные символы, или атомы — строки буквенно-цифровых символов, которые начинаются с буквы, например WOMBAT. (Допустимая длина строки варьируется в зависимости от версии исполняющей системы.) Во внутренней структуре данных атом представлен ячейкой памяти. Отдельным атомом является символ Т, которым представляется константа "True" — истина. Другой специальный атом, NIL, представляет, с одной стороны, константу "False"—ложь, а с другой — пустой список.
Составные выражения объединяются в древовидной структуре, при этом используется очевидное соответствие между символическими выражениями и представлением конечных деревьев. Читатели, склонные к математическим формулировкам, найдут более строгое изложение этого соответствия во врезке 4.2.
Списки представляют собой довольно гибкие структуры данных, поскольку могут объединять элементы разных типов и иметь произвольную длину и размерность (вложенность). Например, в LISP возможен такой список:
("а" (9) () N (? (WOMBAT)) (A . В) NIL 0.9)
Этот список содержит элементы разных типов — строки, числа с фиксированной и плавающей точкой, атомы, булевы значения, точечные пары и другие списки.
Но списки имеют и определенные недостатки, из-за которых в LISP были включены и другие структуры данных. Списки в LISP представляют собой стеки, т.е. доступ к ним возможен только с одного конца списка. Манипулируя только таким списком, невозможно обратиться к элементу списка по его позиции, как это делается с элементом массива. Поэтому для представления больших совокупностей относительно постоянных или редко меняющихся данных в LISP были включены другие типы структур. В современных версиях LISP поддерживаются массивы, хэш-таблицы и структуры, подобный записям, которые позволяют эффективнее использовать пространство памяти и повысить скорость доступа.
4.2.
Списки и точечные пары
Любой атом является символическим выражением.
Если А1 и А2 суть символические выражения, то (А1 A2)— это также символические выражения.
Если S = (А,. (А2 . (.... (Ап-1. AJ ....))) — суть символическое выражение для некоторого п>0, то S — список тогда и только тогда, когда Аn =NIL.
В соответствии с этим определением, если п=0, то S представляет собой пустой список, NIL. Такое определение допускает существование списка списков, а также списка атомов. Если S1 S2, ..., Sn— символические выражения, то мы будем представлять список
S1.(S2.(.... (Sn. NIL)....))) в виде
(S1 S2.... Sn)
Таким образом, (А . (В . NIL)) является списком. Он представляет список (А В), но (А . (В. С)) списком не является, поскольку (С=NIL)).
Символическое выражение, которое не является ни атомом, ни списком, называется точечной парой. Если (А . В) — точечная пара, то А — это голова пары, а B — ее хвост. Точечные пары могут иметь произвольную сложность. Так, ((А . В). С) — тоже точечная пара, так же, как и ((А . В) . (С. D)). Благодаря наличию соответствия между точечными парами и списками, понятия головы и хвоста определены и для списков. Поскольку список (А В) — это (А . (В . NIL)), то очевидно, что А — голова в списке (А В), а хвост — это (В), но не В. Хвостом списка (В) является NIL