 |
Внутреннее представление списков
|
|
|
|
Как представляются списки и атомы в памяти машины?
Специальные функции, с помощью которых можно изменять внутреннюю структуру списков, в чистом функциональном программировании не используются.
В чистом функциональном программировании лишь создаются новые структуры путем анализа, расчленения и копирования ранее созданных структур, и созданные структуры никогда не изменяются и не уничтожаются структуры, значения которых не нужны.
Только в том случае, когда не хватает оперативной памяти для создания новых структур, Лисп-система вызывает так называемый "мусорщик", который удаляет из памяти ненужные структуры (это те структуры, к которым нет доступа, и они в дальнейшем не могут использоваться). Сборка мусора обычно осуществляется в "фоновом" режиме.
 |
Оперативная память, с точки зрения Лисп-системы, состоит из списочных ячеек. Списочная ячейка имеет два поля, содержащие указатели на другие списочные ячейки или на другие лисповские объекты (например, атомы) (рис.1).
Рис. 1. Списочная ячейка
Каждый известный системе атом записывается в память лишь один раз.
Указатель на список - указывает на первую ячейку списка. Указатель, связанный с символом, указывает на объект, который содержит:
· значение символа;
· внешний вид символа (print name);
· определение функции, для которой данный символ является именем;
· список так называемых "свойств" символа.
 |
Список представляется в памяти в виде последовательности списочных ячеек, так список (A B C) состоит из трех ячеек (рис. 2).
Рис. 2. Список (A B C) в памяти
 |
При выполнении (setq список '(A B C)) побочный эффект вычисления функции setq заключается в замещении указателя в поле значения символа (в данном случае символа список) (рис. 3).
|
|
|
Рис. 3. Значение символа
Функции first и rest возвращают значения указателей CAR и CDR. Функция cons создает ячейку и возвращает на нее указатель. Так, например, результат вычисления выражения
(cons голова хвост)
 |
список ((B C) A B C) представлен на рис. 4.
Рис. 4. Функция cons
Функция cons не меняет структуры списков и значения переменных голова и хвост. Логически идентичные атомы хранятся в системе один раз.
У списков могут быть общие части (рис. 5).
 |
Рис. 5. Список (1 2 1 3)
Логически идентичные списки могут быть представлены различными списочными ячейками. В качестве примера, результат вызова (setq список1 '((b c) a b c)) имеет следующее представление в памяти (рис. 6).
 |
Рис. 6. Представление значения символа список1
Но логически эквивалентный список можно создать и по-другому:
(setq bc '(b c))
(setq abc (cons 'a bc))
(setq список2 (cons bc abc))
На рис. 7 показаны последовательные изменения списочных ячеек в памяти.
Логическая структура списка всегда имеет вид бинарного дерева. Физическая структура может быть ациклическим графом (ветви могут сходиться).
Рис.7. Представление значения символа список2
РЕКУРСИЯ
Простая рекурсия
Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.
Рекурсия встречается не только в математике, но и в обыденной жизни. Каждый сталкивается с рекурсией, когда стоит с зеркальцем перед большим зеркалом. Рекурсия встречается обычно и в природе: деревья имеют рекурсивное строение (ветки образуются из других веток), реки образуются из впадающих в них рек. Клетки делятся рекурсивно. Продолжение жизни связано с рекурсивным процессом. Молекулы ДНК и вирусы размножаются, копируя себя, живые существа имеют потомство, которое, в свою очередь, тоже имеет потомство и т. д. Рекурсия распространена и в языке, и в поведении так же, как и в способах рассуждения и познания. Рекурсия в языке, например, может быть в структуре или в содержании:
|
|
|
“Петя сказал, что Вася сказал, что...”
“Знаю, что знаю, но не помню”
“Сделать; заставить сделать; заставить, чтобы заставили сделать;...”
“Замени x этим предложением”
“Запомни и передай это сообщение”
...
Литературным примером может служить "рассказ в рассказе", как-то: известное стихотворение "У попа была собака,...", роман Яна Потоцкого "Рукопись, найденная в Сарагосе", рассказ Хулио Кортасара “Непрерывность парков” или рассказ Виктора Пелевина ”Водонапорная башня” (и по форме - состоит из одного предложения, и по содержанию). Музыкальные формы и действия также могут быть рекурсивными во многих отношениях (например, канон, в котором мелодия сопровождается той же мелодией с задержкой, и другие). Целенаправленное поведение и решение проблем также являются рекурсивными процессами.
Лисп основан на рекурсивном подходе.
Мы будем говорить, что применяется простая рекурсия, если рекурсивный вызов соответствует простому циклу в процедурном программировании.
|
|
|
