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

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


examination:flp:question38

Деструктивные (разрушающие) операции

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

В частности, идеальный Лисп не имеет возможности модифицировать структуру списка. Единственная базисная функция, влияющая на структуру списка - это 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. Это преобразующая список функция, которая преобразует копию своего аргумента, реорганизуя подструктуру

www.intuit.ru_department_pl_lisp_10_10_01.jpg

в структуру из тех же атомов:

www.intuit.ru_department_pl_lisp_10_10_02.jpg

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

Изменение состоит в следующем:

www.intuit.ru_department_pl_lisp_10_10_03.jpg

Пусть новое машинное слово строится как (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 выполнялось, а ее значение игнорировалось.

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

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