Деструктивные (разрушающие) операции
Идеальный Лисп универсален в смысле теории вычислимых функций от символьных выражений. Но для практичности системы программирования Лиспу требуется дополнительный инструмент, увеличивающий выразительную силу и эффективность языка.
В частности, идеальный Лисп не имеет возможности модифицировать структуру списка. Единственная базисная функция, влияющая на структуру списка - это cons, а она не изменяет существующие списки, а создает все новые и новые. Функции, описанные в чистом Лиспе, такие как subst, в действительности не модифицируют свои аргументы, но делают модифицированную копию оригинала.
Идеальный Лисп работает как расширяемая система, в которой информация как бы никогда не пропадает. Set внутри Prog лишь формально смягчает это свойство, сохраняя ассоциативный список и моделируя присваивания теми же CONS.
Теперь же Лисп обобщается с точки зрения структуры списка добавлением разрушающих средств - деструктивных базисных операций над списками rplaca и rplacd. Эти операции могут применяться для замены адреса или декремента любого узла в списке подобно стандартным присваиваниям. Они используются ради их воздействия на память и относятся к категории псевдо-функций.
(rplaca x y) заменяет адресную часть x на y. Ее значение - x, но x, отличное от того, что было раньше. На языке значений rplaca можно описать равенством
(rplaca x y) = (cons y (cdr x))
Но действие совершенно различно: никакие cons не вызываются и новые слова не создаются.
(rplacd x y) заменяет декремент x на y.
Деструктивные операции должно применять с осторожностью! Они могут совершенно преобразить существующие определения и основную память. Их применение может породить циклические списки, возможно, влекущие бесконечную печать или выглядящие бесконечными для таких функций как equal и subst.
Такие функции используются при реализации списков свойств атома и ряда эффективных, но небезопасных, функций Clisp-а, таких как nconc, mapc и т.п.
Для примера вернемся к функции grp. Это преобразующая список функция, которая преобразует копию своего аргумента, реорганизуя подструктуру
в структуру из тех же атомов:
Выше приведенное определение функции делает это созданием новой структуры и использует для этого четыре cons. Из-за того, что в оригинале только три слова, по крайней мере один cons необходим, а grp можно переписать с помощью rplaca и rplacd.
Изменение состоит в следующем:
Пусть новое машинное слово строится как (cons (cadr x) (cddr x)) . Тогда указатель на него заготавливает форма:
(rplaca (cdr x) (cons (cadr x) (cddr x)))
Другое изменение состоит из удаления указателя из второго слова на третье. Оно делается как (rplaca (cdr x) NIL).
Новое определение функции pgrp можно определить как соотношение:
(pgrp x)=(rplacd(rplaca(cdr x)(cons(cadr x)(cddr )x)))NIL)
Функция pgrp используется в сущности ради ее действия. Ее значением, неиспользуемым, является подструктура ((B C)). Поэтому необходимо, чтобы pgrp выполнялось, а ее значение игнорировалось.
Расширенный деструктивными функциями Лисп хорошо приспособлен к оптимизации программ. Любые совпадающие подвыражения можно локализовать и вынести за скобки.
"Сборка мусора" - повторное распределение памяти
Самым интересным, можно сказать революционным, механизмом работы с памятью в Лиспе бесспорно явилась "сборка мусора". С начала 60-ых годов методам такой работы посвящены многочисленные исследования, продолжающиеся до наших дней и сильно активизировавшиеся в связи с включением похожего механизма в реализацию языка Java.
Общая идея всех таких методов достаточно проста:
пока памяти хватает, о ней можно не беспокоиться и располагать новые данные в новых блоках памяти,если памяти вдруг не оказалось, то надо выполнить "сборку мусора", при которой можно найти блоки, ставшие бесполезными для программы, если память нашлась, ее снова можно беззаботно тратить.
Специальная программа "сборка мусора" выполняет анализ достижимости всех блоков памяти просто пометкой узлов, видимых из конечного числа рабочих регистров системы программирования. К таким регистрам относятся промежуточные результаты вычислений, активная часть стека, ассоциативный список, таблица атомов и др. После пометки все непомеченные узлы объединяются в список свободной памяти, передающий их для повторного использования новым вызовам функции CONS. Такая автоматизация не лишена недостатков, но они обнаруживаются лишь в сравнительно сложных процессах, требования которых мы сейчас сознательно не рассматриваем.
| (Gensym ) | Создает новый уникальный атом |
| (Get Атом Индикатор) | Выдает адрес свойства Атома, помеченного заданным Индикатором. |
| (Set Форма Данное ) | Устанавливает значение переменной, одноименной с атомом, полученным при вычислении Формы. |
| Setf | |
| (Setq Атом Данное ) | Устанавливает значение Атома-переменной |
| Symbol-function | |
| Symbol-plist | |
| Symbol-value | |
| Remprop | |
| (Nconc Список … ) | Сцепляет списки без копирования, т.е. заменяя последний Nil очередного списка на указатель следующего списка. |
| (Rplaca Пара Объект ) | Заменяет левый элемент Пары на Объект. |
| (Rplacd Пара Объект ) | Заменяет правый элемент Пары на Объект. |
Списки свойств атомов
До сих пор атом рассматривался как уникальный указатель, обеспечивающий быстрое выяснение различимости имен, названий или символов. В настоящем разделе описываются списки свойств, начинающиеся в указанных ячейках. (Образно говоря, переходим от химии к физике.)
Каждый атом имеет список свойств. Как только атом появляется (вводится) впервые, так сразу для него создается список свойств. Список свойств характеризуется специальной структурой, подобной записям в Паскале, но поля в такой записи сопровождаются индикаторами, символизирующими смысл или назначение хранимой информации. Первый элемент этой структуры расположен по адресу, который задан в указателе атома. Остальные элементы доступны по этому же указателю с помощью ряда специальных функций. Элементы структуры содержат различные свойства атома. Каждое свойство помечается атомом, называемым индикатором, или расположено в фиксированном поле структуры.
Согласно стандарту Common Lisp глобальные значения переменных и определения функций хранятся в фиксированных полях структуры атома. Они доступны с помощью специальных функций symbol-value и symbol-function соответственно. Полный список свойств можно получить функцией symbol-plist. Функция remprop в Clisp удаляет первое вхождение заданного индикатором свойства атома. Новое свойство атома можно ввести формой вида:
(setf (get Атом Индикатор ) Свойство)
Числа представляются в Лиспе как специальный тип атома без списка свойств. Атом такого типа состоит из указателя с тэгом, специфицирующим слово как число, тип числа (целые, дробные, вещественные), и адрес собственно числа, код которого может быть произвольной длины. В отличие от обычного атома одинаковые числа не совмещаются при хранении
| (get Атом Индикатор ) | Дает адрес свойства атома, соответсвующее индикатору |
| (remprop атом индикатор) | удаляет первое вхождение заданного индикатором свойства атома |
| (setf адрес свойство) | Размещает новое значение свойства по заданному адресу |
| (symbol-function атом) | Выдает определение функции |
| (symbol-plist атом) | Список всех свойств атома |
| (symbol-value атом) | глобальное значение переменной |
Структура списков и памяти
До этого момента списки рассматривались на уровне текстового диалога человека с Лисп-системой. В настоящем разделе рассматривается кодовое представление списков внутри памяти машины и механизм "сборки мусора", обеспечивающий повторное использование памяти.
В памяти машины списки хранятся не как последовательности символов, а в виде структурных форм, построенных из машинных слов как частей деревьев, подобно записям в Паскале при реализации односвязных списков. Адреса в таких записях сопровождаются так называемыми тегами, специфицирующими тип данного, расположенного по указателю. При схематичном изображении структуры списка в виде диаграммы машинное слово рисуется как прямоугольник, разделенный на две части: адрес и декремент.
Теперь можно дать правило представления S-выражений в машине. Представление атомов будет пояснено ниже.
Преимущества структур списков для хранения S -выражений в памяти:
Размер и даже число выражений, с которыми программа будет иметь дело, можно не предсказывать. Кроме того, исключаются трудности размещения произвольных выражений в блоках памяти фиксированной длины.Ячейки можно переносить в список свободной памяти, как только исчезнет необходимость в них. Даже возврат одной ячейки в список свободной памяти имеет смысл. Но если бы выражения хранились линейно, то было бы труднее организовать использование лишнего или освободившегося пространства из разрозненных блоков ячеек.Выражения, являющиеся продолжением нескольких выражений, можно хранить только в одном экземпляре.
Для примера рассмотрим типичную двухуровневую структуру (A (B C)).
Она может быть построена из A, B и C с помощью
(cons 'A (cons (cons 'B(cons 'C NIL))NIL))
или, используя функцию list,1) можно то же самое записать как
(list 'A (list 'B 'C))
Если дан список x из трех атомов x = (A B C), то аргументы A, B и C, используемые в предыдущем построении, можно найти как
A = (car x) B = (cadr x) C = (caddr x)
Исходную структуру из такого списка можно получить функцией grp, строящей (X (Y Z)) из списка вида (X Y Z).
(grp x)=(list(car x)(list(cadr x)(caddr x)))
Здесь grp применяется к списку X в предположении, что он заданного вида.
Списки свойств атомов обеспечивают прямой
Списки свойств атомов обеспечивают прямой доступ к значениям и определениям, а также к произвольным свойствам, как встроенным, так и программируемым.Деструктивные операции могут повысить эффективность вычислений ценой надежности программирования.Автоматическое перераспределение памяти позволяет программисту не отвлекаться от решения своих задач на технические проблемы, связанные с планированием структур данных.
