Здесь мы введем понятие списка и установим его связь с атомом и точечной парой.

Основным фундаментальным типом данных в языке LISP является список. Название языка LISP образовано от "LISt Processing" ("обработка списка").

Список рекурсивно определяется так:


        Список  ::=  NIL | (S-выражение . Список)

Согласно этому определению любой непустой список является точечной парой.

Приведем примеры списков:


   (LISP Functional language)
   (5 6 (8 (9)) 23 NIL)

Важно выделить понятие пустого списка, который не содержит элементов, он обозначается () или атомом NIL. Например, (NIL ()) - список, состоящий из двух пустых списков.

Замечание. Один из парадоксов языка LISP состоит в том, что пустой список () - это атом NIL!

Одни говорят, что так первоначально было сделано в связи со спецификой системы машинных команд очень старой вычислительной машины 709. Другие уверены в том, что такое тождество всегда считалось удобным с программистской точки зрения. Никто точно причины не знает.

Часто в литературе используется и другое изображение списков - графическая нотация. Она более наглядно передает структуру списков. В графической нотации легко, например, изобразить циклический список, который можно организовать средствами языка LISP, но в символьной нотации изобразить невозможно! Графическая нотация целиком и полностью опирается на ссылочную структуру списков языка LISP.

Оперативная память компьютера, на котором "работает" LISP, логически разбивается на маленькие области, которые называются списочными ячейками.

Списочная ячейка состоит из полей с именами CAR и CDR, каждое из которых содержит указатель. Указатель может ссылаться на другую списочную ячейку или на другой объект языка LISP, например, на атом.

Указатели между ячейками образуют как бы цепочку, по которой можно из предыдущей ячейки попасть в следующую и так, наконец, до атомарных объектов. Каждый атом, известный системе, записан в определенном месте памяти лишь один раз.

Графически списочную ячейку будем представлять прямоугольником, разделенным на поля CAR и CDR. Указатель изображается в виде стрелки, начинающейся в одной из частей прямоугольника и заканчивающейся на изображении другой ячейки или атоме, на который ссылается указатель.

Пример 1. Изобразим список (A B C D) в графической нотации:

Рис.1. Список (A B C D)

Пример 2. Изобразим список (A (16 (A 25)) (B) (21)) в графической нотации:

Рис.2. Список (A (16 (A 25)) (B) (21))

Пример 3. Структуре, изображенной в графической нотации как

Рис.3. Пример структуры

соответствует выражение в списочной нотации: ((B) A B).

В этом отношении она полностью эквивалентна структуре, изображенной ниже (рис.4):

Рис.4. Пример эквивалентной структуры

Обратите внимание на разное количество лисповских ячеек!

Теперь мы расскажем о графическом представлении точечных пар.

При синтаксическом представлении списка с помощью списочной нотации (последовательность элементов, заключенная в скобки) подразумевается, что завершающий CDR-указатель указывает на атом NIL, например список

Рис.5. Список (A B C)

записывается как (A B C).

Иногда желательно иметь возможность включить в последний элемент списка CDR-указатель, указывающий на атом, отличный от NIL. В этом случае можно использовать другую систему обозначений, называемую точечной нотацией, в которой каждый элемент списка записывается в виде пары подэлементов, представляющих CAR и CDR-поля элемента. Подэлементы заключаются в скобки и отделяются один от другого точкой.

В следующем примере наряду с графическим представлением точечных пар используется представление точечных пар в виде бинарных деревьев с размеченными листьями.

Пример 4. Структура, графическое представление которой имеет вид:

Рис.6. Структура и графическое представление

записывается в точечной нотации как (A . NIL).

Структура с графическим представлением

Рис.7. Структура и графическое представление

записывается как (A . (B . NIL)) в точечной нотации.

Теперь элемент с графическим представлением

Рис.8. Структура и графическое представление

который невозможно было представить в списочной нотации, с помощью точечной нотации записывается как (A . B).

Структура с графическим представлением

Рис.9. Структура и графическое представление

записывается как (A . (B . C)).

Структура

Рис.10. Структура и графическое представление

записывается как ((A . (B . NIL)) . (C . NIL)).

Структура

Рис.11. Структура и графическое представление

записывается как ((D . E) . ((A . C) . B)).

Точечная запись списков обладает некоторыми преимуществами по сравнению со списочной записью. Она является более общей, так как любой список можно переписать в точечных обозначениях, но уже простейшее точечное выражение (A . B) - не может быть представлено списочной записью. Когда выражение строится из небольшого, и главное, заранее известного количества элементов, точечные конструкции предпочтительнее. Если же число элементов сравнительно велико и может быть переменным, то целесообразнее пользоваться списочными конструкциями.

Существует правило, позволяющее упростить запись точечных выражений. Для возврата от точечной записи к списочной, когда такой возврат возможен (!), поступайте так: если точка стоит перед открывающей скобкой, то замените ее пробелом, выбросив одновременно эту открывающую и парную ей закрывающую скобку.Это же правило позволяет избавиться и от лишних NIL, если вспомнить, что NIL эквивалентен паре рядом стоящих скобок (). Полученную точечную запись будем называть сокращенной точечной записью.

Заметим, что это правило разрешается применять к любому правильно построенному S-выражению, если даже оно не сводится в конечном счете к списку.

Приведем примеры:


   запись  (A . (B . C))       эквивалентна (A B . C),
   запись ((A . B) . (C . D))  эквивалентна ((A . B) C . D).

Легко убедиться, что по сокращенной точечной записи можно восстановить полную точечную запись. Для этого каждый пробел заменяется точкой, за которой ставится открывающая скобка. Соответствующая закрывающая скобка вставляется непосредственно перед ближайшей справа от этого пробела закрывающей скобкой, не имеющей парной открывающей скобки также справа от пробела.

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

Используя точечную нотацию, можно сократить объем необходимой памяти. Например, структура данных (A B C), представленная в виде списочной записи, требует трех ячеек, хотя те же данные можно представить в виде (A B . C), требующем только двух ячеек. Более компактное представление может сократить объем вычислений за счет меньшего количества обращений к памяти.

В соответствии со сказанным, в памяти компьютера должны быть выделены по крайней мере две группы ячеек - группа информационных ячеек атомов и группа ячеек, соответствующая точечным парам. Эти группы действительно выделяются - обычно в виде связных участков памяти. Участок, на котором размещаются информационные ячейки атомов, по традиции называется списком объектов, а участок, на котором размещаются пары, - областью списочной памяти. Оба названия не совсем удачны. Список объектов не представляет собой список в том смысле, в каком этот термин используется в языке. Ячейки области списочной памяти могут быть связаны не только в цепочки, изображающие списки, по схеме

но и в иные структуры. Причем возможны структуры, не допускающие описания языковыми средствами. Простейший пример изображен ниже:

Рис.12. Пример структуры

На следующем шаге мы начнем знакомиться с основными функциями языка LISP.

Предыдущий шаг Содержание Следующий шаг