?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
Иммутабельность мешает иммутабельности
nyaload
_winnie
Всё-таки мутабельность объектов в небольших пределах - иногда весьма облегчает написание алгоритмов. Это здорово, когда можно в небольшом обозримом участке кода создать объект A, перебросить на него указатели из другого уже созданного объекта B (который мы только что создали), и отложить заполнение полей A до того момента, когда они станут известны. Но в иммутабельном языке - невозможно создать объект, пока мы не знаем все параметры для его создания, и это дико мешает при переложении известных алгоритмов на такой язык. Нужно вводить дополнительные структуры данных, чтобы поменять порядок создания объектов A и B, так как мы в случае иммутабельности не можем создать A, а потом провести из него указатель в B.

Например, пусть пишем персистентное дерево. Персистентное - это значит слегка изменённые клоны этого дерева создаются легко, и при этом мы не теряем оригинал. Как дерево директорий файловой системы в системе контроля версий - мы при модификации этого дерева и файлов в нём не разрушаем информацию о предыдущих версиях (подробней о сортах персистентности).
То есть, если нам надо создавать персистентные структуры данных, то с одной стороны в иммутабельном ЯП и не можем сделать не-персистентные, что типа должно помогать. С другой стороны - он мешает реализовать промежуточную постройку таких структур в недостроенном состоянии, требуя построить шпиль башни до её фундамента, и запрещая все иные способы постройки.

Это, например, мешает переписывать из википедии алгоритм персистентного красно-черного дерева на такой язык. Там есть подзадача, похожая на такую: в односвязном списке поменять значение ноды с удаляемым значением где-то внутри списка на значение из ноды в конце списка. Список персистентный, поэтому "поменять" означает "создать клон с нужным изменением".
В языке, где можно менять значения полей объекта - всё тривиально, решается в один проход от начала до конца списка.
Идем от начала до нужной внутренней ноды списка, пока идём - создаем дубликаты проходимых нод. Когда нашли нужную ноду - запоминаем указатель на её дубликат, доходим до конца списка, копируем значение в созданный дубликат. Лишней памяти, при условии что нам надо сохранить и старый список (персистентность в copy-on-write её варианте) - не тратится.


В случае же иммутабельного языка программирования - нельзя начать создавать новый список, пока мы полностью не разобрались, какое значение положить в его середине.
Так как пока не найдена нужная нода с изменяемым значением - мы не можем создать все ноды перед перед ней, включая первую. А ноду с изменяемым значением мы не можем создать, так как не знаем новое значение из конца списка.
Получается, что мы тратим дополнительные мозги на изобретение того, как же перевернуть задом наперед заполнение списка, и тратим на это память (иногда неявно, на параметры глубокой рекурсии).


  • 1
А готового дерева нет?

Мне для самообразования. 10 лет использую std::map/TreeMap, и боялся смотреть внутрь.

Так же было интересно написать имено персистетное дерево, его можно с пользой использовать для понятных фичей для пользователей типа "быстрое и глубокое Undo", "интерактивная и быстрая история документа".

Так же в тех вариантах персистентных rb-деревьев не для Haskell - жуткие простыни разбора случаев, а мне удалось написать более компатно:
Например, функция удаления ноды из дерева.
мой вариант - http://pastebin.com/T0vu1Sw8 (а комменты в коде - ведут на картинки из википедии, они уже мне помогли пофиксать опечатки).

вариант который быстро находится гуглем по запросам
"js persistent rb tree" - http://pastebin.com/FzvG3nJ8 , взято с https://github.com/mikolalysenko/functional-red-black-tree/blob/master/rbtree.js )
"java persistent rb tree" http://pastebin.com/qZJPCupy , взято с http://wiki.edinburghhacklab.com/PersistentRedBlackTreeSet
Вариант с Хаскелла - его мне сложно переложить на другой язык, так чтобы получилось не ужасно, вот он - https://hackage.haskell.org/package/RBTree-0.0.5/docs/src/Data-Tree-RBTree.html#deleteOrdList
В Хаскелле слишком легко определять в 10 букв много крошечных абстраций (типа topMostZip), которые сильно раздуваются при прямолинейном переписывании





Edited at 2015-11-04 10:19 pm (UTC)

Я лет 10-15 назад писал RB и AVL. RB жутковато, конечно, но вроде никакой магии. Как оно пишется функционально-иммутабельно (а уж тем более что из этого делает компилятор) никогда не задумывался.

однако не рассказывайте про это адептам ФП - всё равно не поймут.
по существу вот:
http://kouzdra.livejournal.com/2684228.html
ещё есть дискуссия о "недоязыках":
https://github.com/facebook/immutable-js/issues/259

По ссылке у kouzdra - не "черно-красное дерево", а "кусочек упрощенной балансировки в функции добавления", а самое сложное - это на самом деле удаление. Я там подробней прокомментировал.

Ещё не вник в тему с деревом, но насчёт "создать указатель на незаполненный объект" - разве ленивость не для этого?

Хотя, конечно, понятно, что мутабельные структуры данных могут оказаться быстрее иммутабельных - просто потому, что позволяют всё то же самое и ещё кое-что. И в этом случае оптимальным кажется спрятать мутабельность под капот (всё равно ж внутри любого языка с иммутабельными данными - куча всего мутабельного... Взять хотя бы кучу в Хаскеле).

Тредом ниже как раз обсудили ленивость.
Да, ленивость хоть и стоит дополнительных затрат, но в данном случае они пошли в дело, и позволили не запоминать копию списка целиком для переворачивания его создания.

Хм, в случае хаскеля тривиальное решение выглядит не так уж грустно:
change :: Eq a => a -> [a] -> [a]
change val (x:xs) = if x==val then last xs : xs
                              else x : change val xs
change val [] = []

Все иммутабельно, список обходится ровно один раз, лишний раз не копируется и не разворачивается, стек не съедается, вроде (ибо идет ленивая манипуляция графом значений в куче).

Угу, не так уж и плохо. Я даже переписал на C++, чтобы осознать что происходит - https://gist.github.com/dobrokot/0ebc9c9fbd55050dcee7

Почему хорошо с памятью - ленивость прячет "разрушающее копирование" и даёт возможность отложить создание указателей. Интересно получилось.

( Ещё осознал, что та же ленивость позволяет создавать циклы в графе ссылок, неразруливыемые счетчиком ссылок shared_ptr ).

Edited at 2015-11-04 10:01 am (UTC)

А что такое "разрушающее копирование" в данном случае?

Перевод прикольный получился. Я правильно понимаю, что лямбды тут продолжают жить в узлах списка и после срабатывания, держа счетчики ссылок? Как правильно поосвобождать замыкания - обнулить next_getter после использования?

> А что такое "разрушающее копирование" в данном случае?
То, что cached_next нельзя объявить как const и инициализировать при создании.

> Как правильно поосвобождать замыкания - обнулить next_getter после использования?
Про это я не подумал, что можно так оптимизировать. Конкретно данный код и без этого работает без утечек памяти.

А если мы сделаем классический список чисел фиббоначи через zipWith с самим собой - то это не поможет.
Вот тут valgrind жалуется на утечку памяти: https://gist.github.com/dobrokot/0ebc9c9fbd55050dcee7
Чтобы их поосвобождать - нужен garbage collector, можно переписать на питоне/JavaScript/Java.

Edited at 2015-11-04 12:33 pm (UTC)

> ленивость прячет "разрушающее копирование" и даёт возможность отложить создание указателей. Интересно получилось.

Да.

В более сложных случаях для этого можно использовать фьючерку, которая передаётся и сохраняется как readonly view для промиса, который где-то там когда-то установит значение.

А разве last xs не дает нам второй обход списка? Или тут какая-то магия?

Он продолжает первый обход - до искомого элемента шагает ф-я change, после искомого до конца списка шагает last, а change уже не идет дальше.

Осознал, спасибо! Да, логично, после того как заменяемый элемент найден - хвост перебирать надо только чтоб найти тот, на который заменяем, а для нового списка можно прицепить как есть.

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

Решение на D:
http://dpaste.dzfl.pl/d35215cb3983
Тут change строит список мутабельно в один проход и без лишних выделений памяти, но возвращает его как immutable.
(не обошлось без одного каста внутри, но он не существенен)

Такое и в Хаскеле есть, впрочем. Смысл иммутабельности в Хаскеле не сама иммутабельность, а сохранение ссылочной прозрачности, поэтому Data.STRef и Control.Monad.ST вполне работают (тоже можно создать что-то внутри монады мутабельно, а потом вернуть результат как значение).

Re: Иммутабельность мешает иммутабельности

Да!

Но иногда так хочется сказать: Но не до такой же степени!!!

И всё же лучше иметь возможность, но редко ей пользоваться, чем не иметь вообще возможности и выслушивать, что это - единственно правильное решение, что всем - трудно!

Re: Иммутабельность мешает иммутабельности


Да, кажется все пытались сэкономить, и переиспользовать список в параметрах, и вляпывались :)

Впрочем, замечательно эксплуатируется в маленьких скриптах (в больших скриптах как обычно встаёт вопрос "а когда кеш надо инвалидировать").

def get_something_heavy(key, __cache = {}): ... а вдруг ответ уже в кеше ///


слушай, ну иммутабельные структуры требуют отдельных подходов и других алгоритмов всё таки

Immutable не лекарство, а выбор для определённого подмножества ситуаций. Если не вписывается - значит нафиг. И если таки рассматривать immutable, то там есть более приличные структуры данных, чем cons-списки. Без сопутствующих проблем с Big O, кэшами процессора и невозможностью распараллеливания.

Лет 7 назад читал на эту тему занимательный цикл статей про переписывание старых игр на Эрланге.

http://prog21.dadgum.com/23.html

Согласен. Неизменяемость полезная штука и в некоторых случаях работает хорошо, но, например, языки, в которых все переменные константные, это уже через край.

а нет ли возможности почитать Окасаки?

А там в Окасаки есть функция удаления из rb-tree? Я слышал, что её все стесняются показывать.

rb-tree - конкретная задача (балансирования дерева).

Окасаки решает задачи построения эффективных алгоритмов с ленью и оценки их стоимости. Его нужно читать именно потому, что построение алгоритмов с ленью отличается от императивных / мутабельных подходов.

  • 1