ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ

Вопросы:

 

· Лисповская память состоит из списочных ячеек

· Значение представляется указателем

· CAR и CDR выбирают поле указателя

· CONS создает ячейку и возвращает на нее указатель

· У списков могут быть общие части

· Логическое и физическое равенство не одно и то же

· Точечная пара соответствует списочной ячейке

· Варианты точечной и списочной записей

· Управление памятью и сборка мусора

· Вычисления, изменяющие и не изменяющие структуру

· RPLACA и RPLACD изменяют содержимое полей

· Изменение структуры может ускорить вычисления

 

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

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

 

Лисповская память состоит из списочных ячеек

Оперативная память машины, на которой работает Лисп-система, логически разбивается на маленькие области, которые называются списочными ячейками (memory сell, list cell, cons cell или просто cons).

Списочная ячейка состоит из двух частей, полей CAR и CDR. Каждое из полей содер­жит указатель (pointer). Указатель может ссылаться на другую списочную ячейку или на некоторый другой лисповский объект, как, например, атом. Указатели между ячейками образуют как бы цепочку, по которой можно из предыдущей ячейки попасть в следующую и так, наконец, до атомарных объектов. Каждый известный системе атом записан в определенном месте памяти лишь один раз. (B действительности в Коммон Лиспе можно использо­вать много пространств имен, в которых атомы с одинаковыми именами хранятся в разных местах и имеют различную интерпретацию.)

Рис.1.

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

 

Значение представляется указателем

Указателем списка является указатель на первую ячейку списка. На ячейку могут указывать не только поля CAR н CDR других ячеек, но и используемый в качестве переменной символ, указатель из которого ссылается на объект, являющийся значением символа. Указатель на значение хранится вместе с символом в качестве его систем­ного свойства. Кроме значения системными свойствами символа могут быть определение функции, представленное в виде лямбда-выражения, последовательность знаков, задающая внешний вид переменной (print name), выражение, определяющее пространство, в которое входит имя, и список свойств (property list). Эти системные свойства, которые мы рассмотрим подробнее в следующей главе, не будут отражены на наших рисунках.

Побочным эффектом функции присваивания SETQ является замещение указателя в поле значения символа. Например, следующий вызов:

 

_(setq список '(a b c))

(АВС)

 

создает в качестве побочного эффекта изображенную на рис.2 штриховую стрелку.

Рис.2.

Изображение одноуровнего списка состоит из последовательности ячеек, связанных друг с другом через указатели в правой части ячеек. Правое поле последней ячейки списка в качестве признака конца списка ссылается на пустой список, т.е. на атом NIL. Графически ссылку на пустой список часто изображают в виде перечеркнутого поля. Указатели из полей САR ячеек списка ссылаются на структуры, являющиеся элементами списка, в данном случае на атомы A, B н C.

CAR и CDR выбирают поле указателя

Работа селекторов CAR н CDR в графи­ческом представлении становится со­вершенно очевидной. Если мы приме­ним функцию CAR к списку СПИСОК, то результатом будет содержимое лево­го поля первой списочной ячейки, т. е. символ A:

 

_(car список)

A

Соответственно вызов

 

_(cdr список)

(В С)

возвращает значение из правого поля первой списочной ячейки, т.е. список (B C).

 

⇐ Предыдущая123Следующая ⇒

Поделиться: