Несколько слов о программной реализации

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

Каждый объект занимает в памяти машины какое-то место. Однако атомы представляют собой указатели (адреса) на ячейки, в которых содержатся объекты. В этом случае пара z = x : y графически может быть представлена так, как показано на следующем рисунке.

Рисунок 1. Представление пары в памяти компьютера

Адрес ячейки, которая содержит указатели на x и y, и есть объект z. Как видно на рисунке, пара представлена двумя адресами — указатель на голову и указатель на хвост. Традиционно первый указатель (на рисунке выделен голубым цветом) называется a-поле, а второй указатель (на рисунке — зеленоватый) называется d-поле.

Для удобства представления объекты, на которые указывают a- и d-поля, в дальнейшем будут записываться непосредственно в сами поля. Пустой список будет обозначаться перечеркнутым квадратом (указатель ни на что не указывает).

Таким образом, списочная структура, которая рассмотрена несколькими параграфами ранее ([a₁, [a₂, a₃, [a₄]], a₅]) может быть представлена так, как показано на следующем рисунке:

Рисунок 2. Графическое представление списочной структуры [a1, [a2, a3, [a4]], a5]

На этом рисунке также хорошо проиллюстрировано понятие уровня вложенности — атомы a₁ и a₅ имеют уровень вложенности 1, атомы a₂ и a₃ — 2, а атом a₄ — 3 соответственно.

Остается отметить, что операция prefix требует расхода памяти, ибо при конструировании пары выделяется память под указатели. С другой стороны обе операции head и tail не требуют памяти, они просто возвращают адрес, который содержится соответственно в a- или d-поле.

Вернуться в оглавление