Реализация символических структур на языке LISP. Структуры данных в языке 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 поддерживаются массивы, хэш-таблицы и структуры, подобный записям, которые позволяют эффективнее использовать пространство памяти и повысить скорость доступа.
Списки и точечные пары
Пусть задан оператор "." для комбинирования ячеек в древовидной структуре. Тогда определение символического выражения в LISP можно сформулировать следующим образом.
Любой атом является символическим выражением.
Если А1 и А2 суть символические выражения, то (А1 A2)– это также символические выражения.
Если S = (А,. (А2. (…. (Аn-1. AJ….))) – суть символическое выражение для некоторого n>0, то S – список тогда и только тогда, когда Аn =NIL.
В соответствии с этим определением, если п=0, то S представляет собой пустой список, NIL. Такое определение допускает существование списка списков, а также списка атомов. Если S1 S2,…, Sn– символические выражения, то мы будем представлять список: S1.(S2.(…. (Sn. NIL)….))) в виде: (S1 S2…. Sn).
Таким образом, (А. (В. NIL)) является списком. Он представляет список (А В), но (А. (В. С)) списком не является, поскольку (С=NIL)).
Символическое выражение, которое не является ни атомом, ни списком, называется точечной парой. Если (А. В) – точечная пара, то А – это голова пары, а B – ее хвост. Точечные пары могут иметь произвольную сложность. Так, ((А. В). С) – тоже точечная пара, так же, как и ((А. В). (С. D)).
Благодаря наличию соответствия между точечными парами и списками, понятия головы и хвоста определены и для списков. Поскольку список (А В) – это (А. (В. NIL)), то очевидно, что А – голова в списке (А В), а хвост – это (В), но не В. Хвостом списка (В) является NIL.