4.3.1. Структуры данных в языке LISP

Одним из первых языков обработки списков был LISP² [McCarthy, 1960]. За четыре десятилетия, которые прошли после появления его первой версии, язык неоднократно, модифицировался и расширялся, но в основе своей изменился мало. Разработчики языка утверждали, что LISP отличается от прочих языков программирования следующими свойствами [McCarthy et al, I960]:

• основной структурой данных в нем является список;
  
• программы на этом языке также имеют списочную структуру;
  
• его базовыми операциями являются операции над списками.
  

В 1960 году выбор списков в качестве базовой структуры языка программирования рассматривался как революционный шаг. Сейчас большинство языков программирования общего назначения тем или иным образом поддерживает операции над списочными структурами, хотя от программистов обычно требуется запрашивать выделение памяти для формирования списка, а затем после его использования — возвращать память системе. В LISP еще на ранних стадиях развития в исполняющую систему был встроен механизм "уборки мусора", и программисту не требовалось следить за распределением памяти.

Базовым блоком в структуре данных языка LISP является символическое выражение. Простое символическое выражение использует атомарные символы, или атомы — строки буквенно-цифровых символов, которые начинаются с буквы, например WOMBAT. (Допустимая длина строки варьируется в зависимости от версии исполняющей системы.) Во внутренней структуре данных атом представлен ячейкой памяти. Отдельным атомом является символ Т, которым представляется константа "True" — истина. Другой специальный атом, NIL, представляет, с одной стороны, константу "False"—ложь, а с другой — пустой список.

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

Списки представляют собой довольно гибкие структуры данных, поскольку могут объединять элементы разных типов и иметь произвольную длину и размерность (вложенность). Например, в LISP возможен такой список:

("а" (9) () N (? (WOMBAT)) (A . В) NIL 0.9)

Этот список содержит элементы разных типов — строки, числа с фиксированной и плавающей точкой, атомы, булевы значения, точечные пары и другие списки.

Но списки имеют и определенные недостатки, из-за которых в LISP были включены и другие структуры данных. Списки в LISP представляют собой стеки, т.е. доступ к ним возможен только с одного конца списка. Манипулируя только таким списком, невозможно обратиться к элементу списка по его позиции, как это делается с элементом массива. Поэтому для представления больших совокупностей относительно постоянных или редко меняющихся данных в LISP были включены другие типы структур. В современных версиях LISP поддерживаются массивы, хэш-таблицы и структуры, подобный записям, которые позволяют эффективнее использовать пространство памяти и повысить скорость доступа.

4.2. Списки и точечные пары

Пусть задан оператор "." для комбинирования ячеек в древовидной структуре. Тогда определение символического выражения в LISP можно сформулировать следующим образом.

Любой атом является символическим выражением.

Если А₁ и А₂ суть символические выражения, то (А₁ A₂)— это также символические выражения.

Если S = (А,. (А₂ . (.... (А_п-1. AJ ....))) — суть символическое выражение для некоторого п>0, то S — список тогда и только тогда, когда А_n =NIL.

В соответствии с этим определением, если п=0, то S представляет собой пустой список, NIL. Такое определение допускает существование списка списков, а также списка атомов. Если S₁ S₂, ..., S_n— символические выражения, то мы будем представлять список

S₁.(S₂.(.... (S_n. NIL)....)))

в виде

(S₁ S₂.... S_n)

Таким образом, (А . (В . NIL)) является списком. Он представляет список (А В), но (А . (В. С)) списком не является, поскольку (С=NIL)).

Символическое выражение, которое не является ни атомом, ни списком, называется точечной парой. Если (А . В) — точечная пара, то А — это голова пары, а B — ее хвост. Точечные пары могут иметь произвольную сложность. Так, ((А . В). С) — тоже точечная пара, так же, как и ((А . В) . (С. D)). Благодаря наличию соответствия между точечными парами и списками, понятия головы и хвоста определены и для списков. Поскольку список (А В) — это (А . (В . NIL)), то очевидно, что А — голова в списке (А В), а хвост — это (В), но не В. Хвостом списка (В) является NIL