Деструктивные и недеструктивные операции

Разбираемся с самой коварной темой работы со списками: операциями, которые молча портят существующие ячейки.

Недеструктивная операция строит новый результат, не трогая исходные данные. Деструктивная операция переиспользует и физически изменяет существующие cons-ячейки ради экономии. В Common Lisp многие функции существуют в обеих версиях, и путать их опасно.

Это, пожалуй, самая важная для безопасности тема всего раздела о списках. В уроке про построение мы узнали, что списки могут делить общие хвосты. Теперь посмотрим, что бывает, когда такой общий хвост изменяют «на месте». Деструктивные операции дают выигрыш в скорости и памяти, но порождают целый класс трудноуловимых багов — и понимать их природу обязан каждый, кто пишет на Lisp всерьёз.

Две философии изменения

Представьте, что у вас есть список и вы хотите получить его без некоторого элемента. Возможны два подхода. Недеструктивный: построить новый список, скопировав нужные ячейки и пропустив ненужную; исходный список при этом остаётся нетронутым. Деструктивный: пройти по существующему списку и «перепаять» ссылки cdr так, чтобы ненужная ячейка оказалась исключена из цепочки; новых ячеек не создаётся, но исходный список меняется. Первый подход безопаснее, второй экономнее.

Common Lisp прагматично предоставляет обе версии большинства операций, и их легко различать по именам. Недеструктивные обычно имеют «обычные» имена (remove, append, reverse, substitute), а их деструктивные двойники — имена с приставкой или изменённые (delete, nconc, nreverse, nsubstitute). Приставка n в nconc, nreverse означает «destructive» (исторически — «no copy»). Это соглашение об именах — важная карта, которую стоит держать в голове.

remove против delete

Разберём пару на примере. remove возвращает новый список без указанных элементов, не трогая оригинал. delete делает то же логически, но имеет право разрушить исходный список, перепаивая его ячейки. Результат у них одинаковый, но судьба исходных данных — разная.

;; remove не трогает оригинал:
(defparameter a '(1 2 3 2 1))
(remove 2 a)       ; => (1 3 1)   новый список
a                  ; => (1 2 3 2 1)   оригинал ЦЕЛ

;; delete может разрушить оригинал (a после неё непредсказуем):
(defparameter b '(1 2 3 2 1))
(delete 2 b)       ; => (1 3 1)   тот же результат
;; но b теперь использовать НЕЛЬЗЯ — его ячейки перепаяны

Ключевой нюанс: после delete переменную b использовать нельзя, потому что её ячейки изменены, и она может указывать на «обрубок» структуры. Поэтому деструктивные функции почти всегда вызывают так, чтобы сразу присвоить результат обратно: (setf b (delete 2 b)). Полагаться на то, что исходная переменная после деструктивной операции содержит что-то осмысленное, — прямой путь к багу.

Почему деструктивные операции опасны: общие ячейки

Главная опасность раскрывается, когда деструктивная операция касается ячеек, которые делят несколько списков. Вспомним из урока про построение: списки могут иметь общий хвост. Если деструктивно изменить такой хвост через один список, изменения «протекут» во все остальные, ссылающиеся на те же ячейки, — иногда совершенно неожиданно для программиста.

;; Два списка делят общий хвост:
(defparameter shared '(2 3 4))
(defparameter x (cons 1 shared))   ; x = (1 2 3 4)
(defparameter y (cons 9 shared))   ; y = (9 2 3 4)

;; Деструктивно меняем хвост через x...
(setf (car shared) 999)
;; ...и это протекает в ОБА списка, ведь хвост общий:
x        ; => (1 999 3 4)
y        ; => (9 999 3 4)   неожиданно изменился тоже!

Вот квинтэссенция проблемы: мы тронули данные через shared, а пострадали x и y, потому что физически это одни и те же ячейки. С недеструктивными операциями такого не бывает — они строят новое, оставляя общие ячейки в покое. Именно поэтому новичкам настоятельно советуют по умолчанию пользоваться недеструктивными версиями: они предсказуемы, а ловушку разделяемой структуры обходят стороной.

reverse против nreverse

Ещё одна показательная пара. reverse создаёт новый развёрнутый список, не трогая исходный. nreverse разворачивает список, перепаивая его собственные ячейки, — это быстрее и не требует памяти на копию, но разрушает оригинал. nreverse особенно популярна в идиоме «накопить с головы, потом развернуть»: список строят через push (получая обратный порядок), а в конце разворачивают nreverse, поскольку промежуточный список всё равно одноразовый и его не жалко разрушить.

;; Классическая идиома: накопить push-ем, развернуть nreverse-ом
(defun squares-up-to (n)
  (let ((acc '()))
    (dotimes (i n)
      (push (* i i) acc))     ; копим в ОБРАТНОМ порядке
    (nreverse acc)))          ; разворачиваем (acc одноразовый — можно разрушить)

(squares-up-to 5)   ; => (0 1 4 9 16)

Эта идиома — образец правильного применения деструктивной операции: мы разрушаем acc, но это локальная временная переменная, которая больше нигде не используется и сразу после разворота выбрасывается. Деструктивность безопасна именно тогда, когда вы — единственный владелец данных и точно знаете, что на них никто больше не ссылается.

setf: универсальный инструмент изменения

В основе всех деструктивных операций со списками лежит один механизм — setf, универсальная форма присваивания Common Lisp. setf умеет менять не только переменные, но и «места» внутри структур: поле car или cdr конкретной ячейки, элемент по индексу, поле записи. Именно через присваивание в (car ячейка) или (cdr ячейка) и реализуется «перепаивание» ссылок, делающее операцию деструктивной. Понять setf над ячейками — значит понять механику деструктивности в самом её корне.

;; setf меняет поля существующей ячейки на месте:
(defparameter lst (list 1 2 3))
(setf (car lst) 99)        ; меняем голову
lst                        ; => (99 2 3)
(setf (cdr lst) '(7 8))    ; меняем хвост
lst                        ; => (99 7 8)

;; nconc склеивает БЕЗ копирования, перепаивая cdr:
(defparameter p (list 1 2 3))
(defparameter q (list 4 5 6))
(nconc p q)                ; => (1 2 3 4 5 6)
;; теперь последняя ячейка p физически указывает на q!
p                          ; => (1 2 3 4 5 6)   p ИЗМЕНИЛСЯ

Здесь хорошо видно, чем nconc отличается от append: append скопировал бы p, оставив оригинал целым, а nconc просто нашёл последнюю ячейку p и присвоил её cdr ссылку на q — без единой новой ячейки, но p теперь навсегда «срощен» с q. Это и есть деструктивность в чистом виде: изменение полей существующих ячеек через setf вместо создания новых через cons.

Когда деструктивность оправдана

Из сказанного складывается ясное правило применения. Деструктивные операции уместны, когда выполнены два условия: список локальный и одноразовый (вы его только что построили и больше нигде не делили) и вам важна производительность или экономия памяти (например, в горячем цикле или при работе с очень большими списками). Если хоть одно условие под вопросом — список мог быть передан извне, мог делиться с другими, может ещё понадобиться в исходном виде — берите недеструктивную версию. Цена ошибки (молчаливая порча чужих данных) куда выше выигрыша в скорости.

Стоит отметить и философский контраст с другими языками. В Clojure, современном Lisp, по умолчанию используются неизменяемые структуры данных — там деструктивных операций над списками попросту нет, что исключает целый класс багов ценой некоторых накладных расходов. Common Lisp же даёт выбор и доверяет программисту, а Scheme занимает промежуточную позицию. Это отражает общий тренд: индустрия постепенно склоняется к неизменяемости как к более безопасному умолчанию, и понимание опасностей деструктивных операций объясняет, почему.

Полезно также понимать реальный масштаб выигрыша, чтобы не переоценивать его. Деструктивные операции экономят на создании ячеек и копировании, и в горячем коде, перемалывающем большие списки, это действительно может дать ощутимое ускорение и снизить нагрузку на сборщик мусора. Но в типичном прикладном коде разница чаще всего незаметна, а риск внести трудноуловимый баг — вполне реален. Поэтому зрелое правило звучит так: пишите недеструктивно по умолчанию, а к деструктивным версиям переходите только тогда, когда профилировщик показал, что именно это место — узкое, и вы доказали себе, что списки здесь локальны и никем не разделяются. Преждевременная деструктивная «оптимизация» — классический пример усложнения кода ради выигрыша, которого вы, скорее всего, даже не заметите.

Как это работает под капотом

На уровне ячеек разница предельно конкретна. Недеструктивный reverse создаёт N новых ячеек (по числу элементов), а старые оставляет нетронутыми — отсюда расход памяти, но полная безопасность. Деструктивный nreverse не создаёт ни одной новой ячейки: он проходит список и у каждой ячейки разворачивает поле cdr, чтобы оно указывало на предыдущую ячейку вместо следующей, — отсюда экономия, но разрушение исходной цепочки. То же касается append (копирует начальные списки) против nconc (просто перенаправляет cdr последней ячейки первого списка на второй, ничего не копируя).

Понимание этой механики снимает всю «магию»: деструктивная операция — это буквально присваивание в поля car/cdr существующих ячеек через setf, тогда как недеструктивная — создание новых ячеек функцией cons. Зная, какие именно ячейки трогает операция, вы можете точно предсказать, какие списки пострадают, а какие нет, — и это превращает работу с деструктивными операциями из лотереи в инженерный расчёт.

Частые ошибки

Первая и самая частая ошибка — вызвать деструктивную функцию и не сохранить результат: написать (delete 2 lst) и ждать, что lst сам изменится правильно. Деструктивные функции возвращают результат, но исходную переменную оставляют в непредсказуемом состоянии, поэтому нужно (setf lst (delete 2 lst)). Особенно коварно, что для некоторых входов это «случайно работает», усыпляя бдительность.

Вторая ошибка — деструктивно изменить список, пришедший извне (аргумент функции, глобальную константу, разделяемые данные). Вы можете не знать, что этот список делится с другими частями программы, и ваша «оптимизация» молча испортит данные где-то ещё. Правило: не применяйте деструктивные операции к спискам, которые вы не создали сами и не контролируете полностью.

Третья ошибка — деструктивно менять цитируемые литералы. Список-литерал вроде '(1 2 3) в коде формально является константой, и его деструктивное изменение через nreverse или setf car — неопределённое поведение: компилятор вправе разделять одинаковые литералы между разными местами кода, и порча одного «протечёт» в другие. Если список нужно изменять, создавайте его через list или copy-list, а не цитированием.

Итоги

• Недеструктивные операции строят новый результат, не трогая исходные данные; деструктивные переиспользуют и физически меняют существующие ячейки.
• Пары: remove/delete, append/nconc, reverse/nreverse; приставка n означает деструктивность.
• Главная опасность — изменение общих ячеек: деструктивная правка хвоста «протекает» во все списки, делящие его.
• Деструктивность оправдана только для локальных одноразовых списков, которые вы полностью контролируете; результат всегда сохраняйте через setf.
• Нельзя деструктивно менять данные, пришедшие извне, и цитируемые литералы; индустрия (Clojure) склоняется к неизменяемости как безопасному умолчанию.