Тема 1 Основы функционального программирования

Лекция №6

Тема 1 Основы функционального программирования

 

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

Вопросы:

 

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

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

· 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.

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

Любой список можно записать в точечной нотации. Преобразование можно осуществить (на всех уровнях списка) следующим образом:

(а1 a2.. aN)

Û

(а1. (а2.... (aN. N1L)... ))

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

 

(a b (с d) e)

Û

(а. (b. ((c. (d. NIL)). (е. NIL))))

 

Признаком списка здесь служит NIL в поле CDR последнего элемента списка, символизирующий его окончание.

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

 

(а1. (a2 a3)) Û (а1 я2 a3)

(а1. (а2. а3)) Û (а1 а2. a3)

(а1 а2. NIL) Û (a1 а2. ()) Û (a1 а2)

Точка останется в выражении лишь в случае, если в правой части пары находится атом, отличный от NIL.

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

 

_'(а. (b. (с. (d)))

(ABCD)

_'((а b). (b c))

((А В) ВС)

_'(а. nil)

(А)

_'(а. (b. c))

(АВ. C)

_'((((nil. a). b). c). d)

((((NIL. А). B). C). D)

 

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

 

(а b с)

записанная в виде списка, требует трех ячеек, хотя же данные можно представить в виде

 

(а b. c)

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

Точечные пары применяются в теории, книгах справочниках по Лиспу. Часто с их помощью обозначают список заранее неизвестной длины в виде

(голова. хвост)

Точечные пары используются совместно с некоторым типами данных и с ассоциативными списками, а также

Системном программировании. Большинство програм­мистов не используют точечные пары, поскольку по сравнению с требуемой в таком случае вниматель­ностью получаемый выигрыш в объеме памяти и скорости вычислений обычно не заметен.

 

Лекция №6

Тема 1 Основы функционального программирования

 

123Следующая ⇒

Поделиться: