Инструменты пользователя

Инструменты сайта


examination:flp:question35

Внутреннее представление списков в РС – Лиспе.

Внутреннее представление списков

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

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

  Оперативная память машины, на которой работает Лисп-система, логически разбивается на маленькие области, которые называются списочными ячейками (cons). Списочная ячейка состоит из двух частей, полей first и rest. Каждое из полей содержит указатель. Указатель может ссылаться на другую списочную ячейку или на некоторый другой Lisp объект, как, например, атом. Указатели между ячейками образуют как бы цепочку, по которой можно из предыдущей ячейки попасть в следующую и так, наконец, до атомарных объектов. Каждый известный системе атом записан в определённом месте памяти лишь один раз. (В действительности в данной реализации языка можно использовать много пространств имён, в которых атомы с одинаковыми именами хранятся в разных местах и имеют различную интерпретацию.)

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

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

  Указателем списка является указатель на первую ячейку списка. На ячейку могут указывать не только поля first и rest других ячеек, но и используемый в качестве переменной символ, указатель из которого ссылается на объект, являющийся значением символа. Указатель на значение хранится вместе с символом в качестве его системного свойства. Кроме значения системными свойствами символа могут быть определение функции, представленное в виде лямбда-выражения, несколько знаков, задающая внешний вид переменной, выражение, определяющее пространство, в которое входит имя, и список свойств.   Побочным эффектом функции присваивания setq является замещение указателя в поле значения символа. Например, следующий вызов:

(nil setq list '(a b c))

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

  Список состоит из нескольких ячеек, связанных друг с другом через указатели в правой части ячеек. Правое поле последней ячейки списка в качестве признака конца списка ссылается на пустой список, т.е. на атом nil. Графически ссылку на пустой список часто изображают в виде перечёркнутого поля. Указатели из полей first ячеек списка ссылаются на структуры, являющиеся элементами списка, в данном случае на атомы a, b и c.

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

  Работа селекторов first и rest в графическом представлении становится совершенно очевидной. Если мы применим функцию first к списку list, то результатом будет содержимое левого поля первой списочной ячейки, т.е. символ a:

(list first)

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

(list rest)

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

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

  Допустим, что у нас есть два списка:

(nil setq head '(b c))

nil

(nil setq tail '(a b c))

nil   Вызов функции

(nil cons head tail)

((b c) a b c) строит новый список из ранее построенных списков head и tail так, как это показано на рисунке.

  cons создаёт новую списочную ячейку (и соответствующий ей список). Содержимым левого поля новой ячейки станет значение первого аргумента вызова, а правого - значение второго аргумента. Обратите внимание, что одна новая списочная ячейка может связать две большие структуры в одну новую структуру. Это довольно эффективное решение с точки зрения создания структур и их представления в памяти. Заметим, что применение функции cons не изменило структуры списков, являющихся аргументами, и не изменило значений переменных head и tail.

examination/flp/question35.txt · Последние изменения: 2014/01/15 08:17 (внешнее изменение)