Деструктивные (разрушающие) преобразования структуры списков
Теория рекурсивных функций, изложенная в лекции 2, будет упоминаться далее как строгий, чистый или элементарный Лисп. Хотя этот язык универсален в смысле теории вычислимых функций от символьных выражений, он непрактичен как система программирования без дополнительного инструмента, увеличивающего выразительную силу и эффективность языка.
В частности, элементарный Лисп не имеет возможности модифицировать структуру списка. Единственная базисная функция, влияющая на структуру списка — это cons, а она не изменяет существующие списки, только создает новые. Функции, описанные в чистом Лиспе, такие как subst, в действительности не модифицируют свои аргументы, но делают модификации, копируя оригинал.
Элементарный Лисп работает как расширяемая система, в которой информация как бы никогда не пропадает. Set внутри Prog лишь формально смягчает это свойство, сохраняя ассоциативный список и моделируя присваивания теми же CONS.
Теперь же Лисп обобщается с точки зрения структуры списка добавлением структуроразрушающих средств — деструктивных базисных операций над списками rplaca и rplacd. Эти операции могут применяться для замены адреса или декремента любого слова в списке. Они используются ради их действия так же, как и ради их значения и называются псевдо-функциями.
(rplaca x y) заменяет адрес из x на y, эквивалент (car x) := y. Ее значение — x, но x, несколько отличающийся от того, что было раньше. На языке значений rplaca можно описать равенством
(rplaca x y) = (cons y (cdr x))
Но действие различное: никакие cons не вызываются и новые слова не создаются.
(rplacd x y) заменяет декремент x на y, эквивалент (cdr x) := y.
Эти операции должны применяться с осторожностью! Они могут в корне преобразить существующие определения и основную память. Их применение может породить циклические списки, приводящие к бесконечной печати или выглядящие бесконечными для таких функций как equal и subst.
Деструктивные функции используются при реализации списков свойств атома и ряда эффективных, но небезопасных, функций
Clisp-а, таких как nconc, mapc и т.п.
Для примера рассмотрим функцию mltgrp. Это преобразующая список функция, которая преобразует копию своего аргумента. Подфункция grp реорганизует подструктуру
Рис. 1.13. подструктура
в структуру из тех же атомов:
Рис. 1.14. структура из тех же атомов
Исходная функция делает это, создавая новую структуру и используя четыре cons. Из-за того, что в оригинале только три слова, по крайней мере, один cons необходим, а grp можно переписать с помощью rplaca и rplacd. Изменение состоит в следующем:
Рис. 1.15. новая структура
Пусть новое машинное слово строит (cons (cadr x) (cddr x)). Тогда указатель на него встраивается в 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)). Поэтому для mltgrp необходимо, чтобы pgrp выполнялось, а ее значение игнорировалось. Поскольку верхний уровень не должен копироваться, mltgrp не обязательно должна основываться на cons.
(pmltgrp L) =(COND ((null L) NIL) (T (pgrp (cdr L)) (pmltgrp (cdr L)) )))
prog2 — функция, вычисляющая свои аргументы. Ее значение — второй аргумент.
Значение pmltgrp — NIL. pgrp и pmltgrp — псевдо-функции.
