Сообщение Re[18]: понимание ООП Алана Кея от 29.03.2023 20:00
Изменено 29.03.2023 20:38 vdimas
Re[18]: понимание ООП Алана Кея
Здравствуйте, Sinclair, Вы писали:
S>Эти слова я читал. Я не понимаю, как вы будете их применять. Что именно помешает "по невнимательности" добавить в ImmutableValue<T> мутирующих методов?
Если поля описаны как const, то мутировать их никак.
Есть еще ключевое слово mutable — это когда к полю можно обращаться из const this метода.
Например, интрузивные счётчики ссылок часто описывают как mutable, потому что они работают над совместным владением объектами, без вмешательства в потенциально read-only семантику прикладных данных. Чаще всего такие счётчики размещают как приватные в неких базовых классах, т.е. эти счётчики недоступны затем наследуемому "прикладному" коду, предоставляя, однако, через функциональность этих базовых классов требуемую инфраструктуру по ссылочному шаренью целевых данных.
V>>С одной стороны, это не более чем эксплуатация выразительных ср-в языка, что мы гарантии прописываем через синтаксис (а не комментарии) и контроллируем их через систему типов.
V>>Создание копий иммутабельных данных может быть полезным для региональной памяти, когда необходимо сохранить данные в своём регионе.
S>Это опять какие-то вырожденные экзотические сценарии, нужные примерно никогда.
Коль мы возимся с иммутабельностью эффективности ради, то "примерно никогда" на практике трасформируется в "часто".
Серебрянной пули для эффективности нет, сие аксиома. ))
В каждом конкретном случае используется комплекс мер для обеспечения эффективности этого случая, коль эффективность вообще требуется.
V>>Счётчики обычно дергаются при перестроении, допустим, графа на иммутабельных узлах, поэтому доп. накладные расходы не настолько уж велики, чтобы говорить о дне, бо перестраивается только часть узлов.
S>Счётчики ссылок, очевидно, дёргаются при любом копировании.
Дергаются не у всего дерева, а только у непосредственных детей вновь создаваемых узлов при перестроении, а это log N.
Т.е. еще зависит от вида дерева — RB, AVL или еще какие с арностью более 2 — тогда будет еще меньше дерганий счётчиков ссылок.
Плюс, в промежуточных операциях (при нескольких поворотах, например, вставка может породить два поворота, а удаление из AVL до 5-ти поворотов) можно исключить дерганье счётчиков ссылок в процессе, пробежавшись по новым узлам уже по окончании операций.
S>Как раз "перестроенные" узлы, которых мало, получают счётчики == 1.
У непосредственных детей новых узлов надо увеличить счётчик ссылок — мы же шарим имеющиеся узлы, не перестраиваемые при повороте.
И опять же, смотря как реализовано дерево. Ссылочные ноды RB-деревьев могут хранить value-кластер тройки узлов {R, B, R}, т.е. в общем случае меньше дерганий счетчиков ссылок (вдвое меньше "ссылочная" высота дерева), как и для более арных деревьев.
V>>А региональная память — это когда некая подсистема сама распределяет память на низком уровне, обращаясь к операционке только за относительно большими страницами памяти.
V>>В таких распределителях память обычно выделяется как grow-only, простым смещением текущего указателя свободной области, т.е. выделение происходит с эффективностью дотнета.
V>>А освобождается затем и вовсе бесплатно, целиком одной операцией возврата операционке страницы (страниц).
S>Это если у вас хватает размера региона на полную работу алгоритма.
Память выделяется страницами, выделенные страницы хранятся по единственной ссылке, бо связаны в однонаправленный список.
Аллокаторы обычно настраиваются compile-time константами-параметрами, например, размером страницы и величиной выравнивания (выравнивание порой нужно не на слово, а на линейку кеша).
Эти техники, считай, обязательные в реализациях нейтивных веб-серверов, баз данных, компиляторов и т.д., бо региоальная память хорошо себя показывает в сценариях "выделить память для отдельной операции и всю её освободить по окончании операции". Боюсь даже представить, как работали бы БД или компиляторы без региональной памяти, на обычном malloc на каждый чих. ))
Плюс, в отличие от распределителей на основе пула ячеек одинакового размера (аллокатор по степени двойки связывает ячейки одинакового размера в линейные списки, где пустые ячейки друг на друга ссылаются, т.е. первое слово свободной ячейки интерпретируется как адрес следующей ячейки), у региональной памяти всё неплохо с локальностью. Зато плохо с долгоживучестью у grow-only аллокатора, поэтому сей подход и нашел себя в обслуживании указанных относительно короткоживущих сценариев.
S>Заранее сказать, сколько потребуется памяти для хранения мусора, порождаемого компилятором при анализе AST, весьма затруднительно.
А оно и не требуется.
Каждая трансформация — отдельная операция, т.е. для временных данных можно юзать такие аллокаторы, длительностью жизни в операцию.
Потом у аллокатора вызывается некий reset и он переиспользуется для другой операции и т.д.
В общем, когда память не держит некие ресурсы (хендлы), а просто представляет из себя размеченную память для целей вычислений над данными, то требования к финализации испаряются — просто возвращаем страницу памяти целиком в пул свободных страниц и ву-а-ля.
Это ж азы, а не "уникальность".
Это сегодня мы разбалованы современными высокоуровневыми подходами...
В более хардокорном прошлом это всё из разряда не уникальности, а must have, то бишь, не новинка, а наоборот, традиции.
S>А как только вы исчерпали регион — добро пожаловать в честное копирование.
Регион — это несколько страниц.
Вот у тебя тройка указателей:
Курсор просто ползёт до page_end, после этого выделяется новая страница, а на старую ссылаются в первом слове новой страницы.
Соответственно, у первой выделенной страницы первое слово всегда null — конец списка.
V>>В целом оно на порядки эффективнее, чем в дотнете.
S>"В целом" — вряд ли. В частных случаях — может быть.
В целом — это сам этот подход.
Просто можно и его испортить, разумеется. ))
Например, в дотнете аллокатор расположен в TLS-слоте (что тоже далеко не верх эффективности — просто получить ссылку на аллокатор, у которого попросить память).
В твоей же реализации могут быть разные подходы — тоже на TLS или некий передаваемый в операции явно context (а в нём даже несколько таких аллокаторов для нескольких подсистем) и т.д.
Разумеется, чтобы был ожидаемый выхлоп, жизненный путь данных тщательно анализируется, а достижения тестируются.
S>То, что вы называете "региональной памятью", другие люди называют ареной
Регион, арена...
Термин не так давно устоялся, что забавно и то, из-за использованных идентификаторов в некоторых реализациях и языках.
S>и это, в целом, аналог поколений в современных GC, только на ручном приводе.
Не скажи...
Например, нулевое поколение — это просто список объектов с некоей "головы".
Затем уплотнения может и не быть (не было неявных освобождений), но голову по окончании цикла GC переназначат.
Сравнивать эти подходы сложновато, потому что в их основе лежат принципиально разные стратегии из-за принципиально разных принятых допущений.
"Просто другая стратегия", всё.
Не обязательно пытаться найти ассоциативную связь со знакомым материалом. ))
За одно только сязывание выделяемых объектов в списки в GC-системах убить мало. ))
S>И применяется, как правило, там, где потребности в памяти можно предсказать — либо мало кросс-ссылок между данными.
Ес-но, граф владения разрабатывается под механику этого владения.
А так-то можно на любой чих получить зацикливание на тех же счётчиках ссылок, привет VB/VBA. ))
Или ссылка на байты в регионе может улететь наружу — привет нежданчик.
Накосячить можно где угодно, конечно.
Однако, язык даёт ср-ва для описания как низкоуровневых ограничений, так и высокоуровневых контрактов, удовлетворяющих принятым в дизайне механикам с их ограничениями.
Разумеется, автоматическое управление памятью кое-где сильно развязывает руки.
А кое-где сильно связывает.
Не изобрели еще серебрянной пули. ))
S>Какой-нибудь видео и аудиопроцессинг с этим будет работать хорошо, а вот компиляторы и прочие трансформации графов — вряд ли.
Компиляторы часто используют аллокаторы пулов ячеек одинакового размера для хранения относительно персистентных данных и регионы для промежуточных данных затратных операций.
Видео и аудио-процессинги мимо — там предвыделяются буфера для пайплайна алгоритма, никаких аллокаций/освобождений памяти в процессе работы кодеков быть не может, конечно.
Память аллоцируется только в момент создания объекта-кодека.
V>>merge — потому что такова природа сущности "множество". ))
S>Вы распишите, что у вас там вместо // .... Поскольку у вас под капотом — заранее неизвестный мутабельный тип, то всё, что вы можете — это состряпать его копию, к которой потом будет применена манипуляция с изменением.
И чем плоха копия такого объекта:
где ImmutableSet<T> используется с семантикой значения, в данном случае значения-ссылки.
В отличие от дотнетного неймспейса Immutable, я именно так реализовывал свои аналоги в дотнете еще черти когда.
Т.е., ссылочная семантика нужна только для узла.
Так для чего ж тогда ImmutableSortedSet<> объявлен ссылочным типом?
А, ну да, ну да...
— из-за встроенного дефолтного конструктора value-типов, который хоть уже и можно переопределить, но он вызывается не всегда.
Пусть в своём коде я могу обложиться Debug.Assert() и требовать, чтобы был вызван недефолтный конструктор или статический метод-фабрика, но в библиотеке платфрменного уровня таких дыр быть не должно, она должна быть защищена от дурака.
Вот тебе еще один плюсик плюсам — там у меня вопрос не стоит, бо описанный мною дефотный конструктор будет вызван явно в любом случае, когда не вызван конструктор с аргументами.
S>Ваш схематично набросанный подход придётся переписать, т.к. выбранные вами сигнатуры даже не позволяют создать эту копию однократно.
Позволяют что угодно, хосподя.
Как напишешь — так и будет.
Мой схематичный подход через "обертки" позволяет гарантировать иммутабельность для изначально описанных мутабельных типов.
Например, узел Node может быть описан мутабельным, но если мы создаём эти узлы внутри реализации и помещаем в константную ссылку/указатель, то тип становится readonly.
Т.е., реализация builder-а не требует дополнительных флагов, типа frozen (как в дотнетной реализации Immutable-узлов, и это почему появилсь отдельные read-only Frozen типы, где не требуется управлять еще и этими флагами). Достаточно по окончании построения присвоить граф константной ссылке/указателю (как говорил с самого начала).
В вашем подопечном-защищаемом дотнетном Immutable совсем всё смешно — набили дерево мильоном узлов в билдере, а потом сказали ему Freeze() — и оно пошло честной стековой рекурсией обходить дерево для установки флага.
"Не об этом я мечтала, когда замуж выходила..." (С) ))
V>>Для случая активного изменения данных я выберу ссылочную семантику, для случая frozen-данных выберу семантику по-значению, разумеется.
S>Просто при передаче вашего ImmutableValue() по значению, будет создаваться deep-копия вложенных в него данных. Со стоимостью O(N).
Deep-копия автоматом только для плоской памяти.
По указателю если — это надо расписывать ручками.
Если используется интрузивный счётчик ссылок и иммутабельность, то копирование вызовет лишь +1 у счётчика cсылок корня:
Рыба такая:
V>>Я рядом давал тебе ссылку на исходники SmallFrozenSet.
S>Да при чём тут ссылка? Вы просто опять уходите в решения для каких-то экзотических частных случаев.
Наоборот, говорил, что в плюсах есть возможность писать более обще, потому что у меня есть возможность распространять гарантии.
Обрати внимание на сигнатуры парами:
По константной ссылке-указателю может быть вызвана только const-this версия метода, соответственно, у меня одно описание на все случаи жизни.
См. тут:
Константное поле у меня лишь в декораторе ImmutableSet<TSet>, далее констрантность распространяется.
Что я могу себе позволить, чтобы мои абстракции не протекли:
— дефолтный конструктор ImmutableSet (в примере auto empty = ImmutableSet<AvlTreeSet<int>>())
— конструктор от значений или других ImmutableSet.
Чего нельзя:
— публичные конструкторы от мутабельных типов.
Ф-ии навроде mutable_merge или immetable_merge могут быть внешними. При непосредственном вызове этих ф-ий над иммутабельными типами ничего гарантировать нельзя, разумеется.
Наверно, тебя именно это беспокоило несколько лет назад и в этом обсуждении снова.
Я же тебе говорил, что я могу распространить гарантии так, что они не протекут.
На самый худой конец их можно распространить на самое дно — поля целевых типов. ))
Просто никто так не делает обычно.
А как делают — показал.
Т.е. распространяют гарантии константности и создают невозможность протечки абстракций через доступное публичное АПИ.
В целях эффективности класс ImmutableSet может содержать вложенный класс Builder, который манипулирует мутабельным TSet на стадии напихивания данных, и в какой-то момент передаёт владение набором данных в иммутабельный ImmutableSet. Т.е. классу Builder будет доступен приватный конструктор декоратора ImmutableSet, а тебе нет. И что забавно, всего одна реализация ImmutableSet и Builder на все реализации set с нужными наборами методов.
V>>Не обошлись, там точно такая же магия для структур в ключевом слове readonly.
S>Я говорю конкретно про иммутабельность. Много ли readonly вы видите в System.Collections.Immutable?
Я там вообще мало чего интересного вижу и вряд ли когда буду пользоваться этой неэффективной реализацией.
В упор не понимаю, чем тебя заинтересовало это убожество.
Это ж для хомячков.
"Чтобы было!" (С)
V>>А было бы неплохо и для интерфейсов-классов, где IImuttableList мог быть объявлен как readonly interface IImuttableList, соответственно, все реализующие его классы должны были бы быть readonly IImuttableList : ImuttableList {...}
S>Это — бесполезная идея.
"Это потому что ты не понимаешь иммутабельности" (С)
Для структур оказалась крайне полезной, потому что иначе возникал диссонанс с readonly-полями value-типов.
Пришлось ввести readonly-методы, что есть полный аналог const-this методов в С++.
S>Она одновременно не даст никаких гарантий иммутабельности
В плюсах я распространяю константность в зависимости от константной или нет сигнатуры метода.
В дотнете распространять константность можно было бы автоматом для ссылочных readonly типов, как оно есть для readonly структур.
Т.е. такие типы могли бы содержать лишь readonly структуры и readonly классы/интерфейсы как поля.
S>потому, что внутри реализации ImmutableList — ссылка, которая, в том числе, может быть и на mutable данные
Хосподя, ну так за этим и предлагается, иначе смысла не будет.
S>и помешает некоторым сценариям, где иммутабл-объект изменяется в процессе конструирования.
В конструкторе поля можно изменять многократно, это не проблема.
А утекание абстракций контроллировать компилятором/верификатором, чтобы он запрещал изменение полей после того как из конструктора утёк this (будучи переданным некоему аргументу, допустим, для регистрации созданного объекта где-то там).
В этой схеме невозможно создать циклические ссылки объектов друг на друга, как их невозможно создать в ФП, но никто не жалуется.
Если уж требуются наработки иммутабельности из ФП — то берите их готовые.
V>>Но ты просил гарантии, поэтому я и продемонстрировал ср-ва для выражения гарантий.
S>
Повторюсь: гарантии в продемонстрированном вами подходе никак не зависят от применения ключевого слова const.
-1
Рассуждая таким образом можно договориться до того, что и язык Ассемблера даёт такие же гарантии.
Конечно, С++ даёт несравнимо больше гарантий в плане проектирования иммутабельных типов.
Тебе надо просто взять однажды компилятор и чуть поупражняться в проектировании иммутабельных иерархий в плюсах, чтобы ты понял о чём речь.
Сколько раз компилятор подсказывает о константности, т.е. не пропускает компиляции при нарушении контракта — это тебе не передать.
В случае же подхода Immutable из дотнета — это только тестами корректность проверять и то, плохо понятно как именно, бо приватные кишки классов не проверишь.
Остается верить на слово, бгг...
По отношению к иммутабельности дотнет находится в сравнении с плюсами примерно там же, где скриптовые нетипизированные языки находятся в сравнении с языками со строгой статической типизацией.
Говорить "это одно и то же" — сверкать ярчайшим нубством, сорри.
Хоть бы посмотрел на readony ref, scope и readonly методы структур в дотнете.
Похоже, ты со всем этим еще не разбирался, но мнение имеешь.
S>Если вы его уберёте, ImmutableValue<> останется ровно на столько же иммутабельным, как и был.
Это из-за необычно сильно ограниченного твоего мышления, через которое я уже устал продираться.
Как тебе недавно введенные управляемые ссылки как поля ref-структур?
Я об этом говорил еще примерно в 2005-м, но некоторые столь же узко мыслящие даже не понимали — а зачем?
Ты хоть понимаешь — зачем?
И почему это стало возможно только с введением readonly ref?
Я так думаю, что ты малость отстал от последних версий платформы, с тобой реально сложно разговаривать, хоть ты себя и позиционируешь как спец по дотнету. ))
V>>Пусть по-мелочам больше думает машина, чем программист.
S>Непонятно, что вы имеете в виду. Я всё ещё не вижу сценария, который вы предотвращаете при помощи этого ключевого слова.
Да пофик.
Первый раз сказал "не вижу" — объяснили.
Если и после этого "не вижу" — списали на берег.
V>>Хорошо, что согласился хоть с чем-то. ))
V>>Проблематика заданного именно тобой обсуждения как раз в интерфейсах — ты хотел писать обобщённые алгоритмы в условиях гарантий.
S>Разве? Может, я что-то подзабыл. Можно указать, где именно я настаивал на интерфейсах?
Ты говорил, дословно, "как мне знать, что тип иммутабельный"?
Разночтений быть не может, ты говорил о неизвестном потенциальном типе для своих алгоримов, соответственно, речь должна были идти об абстракциях.
А дотнете абстракции живут на интерфейсах и на ограничениях ими генериков.
V>>Оно и так в реальной жизни отродясь иммутабельно для State и до введения готовых Immutable-реализаций.
S>"Оно" — это кто?
Это объект-состояние ДКА для автомата.
V>>В общем, будет отличаться тем, бо абстракция ImmutableMapWrapper бесплатна, а обёрнут может быть не только конкретный std::map.
V>>Ну и, из-за наличия частичного определения шаблонов, может быть обёрнут даже тип, который не совместим по публичному интерфейсу в std::map.
S>Как только вы обернёте не только конкретный sdd::map, появится и возможность "хулиганить".
Не появится, я выше дал полный список обеспечения гарантий.
Просто, блин, ты поразительно недогадлив, с ложечки кормить приходится.
V>>А как тебе arg... — семантика?
S>У меня со времён params в С# такой синтаксис удивления не вызывает.
В дотнете это массив в куче, днамическое итерирование по params в цикле, в плюсах статика времени компиляции, линейная раскрутка кода.
В дотнете в params могут быть одинаковые типы (или наследники для случая ссылочных типов), в плюсах произвольные, допустимые обработчиками.
S>А семантика, на первый взгляд, слабже — не так удобно извлекать коллекцию
Я вообще удивляюсь, как ты дожил до своих лет и тебя до сих пор не прибили за аксиматическую позицию "все вокруг дураки", когда реальность подтверждает обратное? ))
S>и принудительная замена итерации рекурсией не выглядит шибко привлекательно.
ЧТД, вот тебе пример того, что дураков вовсе не вокруг искать надо.
При вычислении вложенных вызовов ф-ий для arg... получается линейный код вычисления аргументов ф-ий от самых глубоких к внешним.
Это абсолютно линейный код верхнего уровня, последовательность call.
Итерация там только в процессе работы компилятора.
А как бы оно вообще могло работать, неужели даже не попытался представить?
В любом случае, я тебе показал во что реально превращается тот код.
S>Вот если бы ещё шарп починили, разрешив приписывать params к параметру любого типа, который реализован массивом. В частности, IEnumerable<T> и IList<T>.
То сделали бы эти случаи неразличимыми/конфликтующими, в то время как м/у ними сильное различие с т.з. эффективности.
В кишках дотнета голые массивы весьма входу и популярны.
Где приходится бороться за эффективность на юзверском уровне — тоже.
S>Эти слова я читал. Я не понимаю, как вы будете их применять. Что именно помешает "по невнимательности" добавить в ImmutableValue<T> мутирующих методов?
Если поля описаны как const, то мутировать их никак.
Есть еще ключевое слово mutable — это когда к полю можно обращаться из const this метода.
Например, интрузивные счётчики ссылок часто описывают как mutable, потому что они работают над совместным владением объектами, без вмешательства в потенциально read-only семантику прикладных данных. Чаще всего такие счётчики размещают как приватные в неких базовых классах, т.е. эти счётчики недоступны затем наследуемому "прикладному" коду, предоставляя, однако, через функциональность этих базовых классов требуемую инфраструктуру по ссылочному шаренью целевых данных.
V>>С одной стороны, это не более чем эксплуатация выразительных ср-в языка, что мы гарантии прописываем через синтаксис (а не комментарии) и контроллируем их через систему типов.
V>>Создание копий иммутабельных данных может быть полезным для региональной памяти, когда необходимо сохранить данные в своём регионе.
S>Это опять какие-то вырожденные экзотические сценарии, нужные примерно никогда.
Коль мы возимся с иммутабельностью эффективности ради, то "примерно никогда" на практике трасформируется в "часто".
Серебрянной пули для эффективности нет, сие аксиома. ))
В каждом конкретном случае используется комплекс мер для обеспечения эффективности этого случая, коль эффективность вообще требуется.
V>>Счётчики обычно дергаются при перестроении, допустим, графа на иммутабельных узлах, поэтому доп. накладные расходы не настолько уж велики, чтобы говорить о дне, бо перестраивается только часть узлов.
S>Счётчики ссылок, очевидно, дёргаются при любом копировании.
Дергаются не у всего дерева, а только у непосредственных детей вновь создаваемых узлов при перестроении, а это log N.
Т.е. еще зависит от вида дерева — RB, AVL или еще какие с арностью более 2 — тогда будет еще меньше дерганий счётчиков ссылок.
Плюс, в промежуточных операциях (при нескольких поворотах, например, вставка может породить два поворота, а удаление из AVL до 5-ти поворотов) можно исключить дерганье счётчиков ссылок в процессе, пробежавшись по новым узлам уже по окончании операций.
S>Как раз "перестроенные" узлы, которых мало, получают счётчики == 1.
У непосредственных детей новых узлов надо увеличить счётчик ссылок — мы же шарим имеющиеся узлы, не перестраиваемые при повороте.
И опять же, смотря как реализовано дерево. Ссылочные ноды RB-деревьев могут хранить value-кластер тройки узлов {R, B, R}, т.е. в общем случае меньше дерганий счетчиков ссылок (вдвое меньше "ссылочная" высота дерева), как и для более арных деревьев.
V>>А региональная память — это когда некая подсистема сама распределяет память на низком уровне, обращаясь к операционке только за относительно большими страницами памяти.
V>>В таких распределителях память обычно выделяется как grow-only, простым смещением текущего указателя свободной области, т.е. выделение происходит с эффективностью дотнета.
V>>А освобождается затем и вовсе бесплатно, целиком одной операцией возврата операционке страницы (страниц).
S>Это если у вас хватает размера региона на полную работу алгоритма.
Память выделяется страницами, выделенные страницы хранятся по единственной ссылке, бо связаны в однонаправленный список.
Аллокаторы обычно настраиваются compile-time константами-параметрами, например, размером страницы и величиной выравнивания (выравнивание порой нужно не на слово, а на линейку кеша).
Эти техники, считай, обязательные в реализациях нейтивных веб-серверов, баз данных, компиляторов и т.д., бо региоальная память хорошо себя показывает в сценариях "выделить память для отдельной операции и всю её освободить по окончании операции". Боюсь даже представить, как работали бы БД или компиляторы без региональной памяти, на обычном malloc на каждый чих. ))
Плюс, в отличие от распределителей на основе пула ячеек одинакового размера (аллокатор по степени двойки связывает ячейки одинакового размера в линейные списки, где пустые ячейки друг на друга ссылаются, т.е. первое слово свободной ячейки интерпретируется как адрес следующей ячейки), у региональной памяти всё неплохо с локальностью. Зато плохо с долгоживучестью у grow-only аллокатора, поэтому сей подход и нашел себя в обслуживании указанных относительно короткоживущих сценариев.
S>Заранее сказать, сколько потребуется памяти для хранения мусора, порождаемого компилятором при анализе AST, весьма затруднительно.
А оно и не требуется.
Каждая трансформация — отдельная операция, т.е. для временных данных можно юзать такие аллокаторы, длительностью жизни в операцию.
Потом у аллокатора вызывается некий reset и он переиспользуется для другой операции и т.д.
В общем, когда память не держит некие ресурсы (хендлы), а просто представляет из себя размеченную память для целей вычислений над данными, то требования к финализации испаряются — просто возвращаем страницу памяти целиком в пул свободных страниц и ву-а-ля.
Это ж азы, а не "уникальность".
Это сегодня мы разбалованы современными высокоуровневыми подходами...
В более хардокорном прошлом это всё из разряда не уникальности, а must have, то бишь, не новинка, а наоборот, традиции.
S>А как только вы исчерпали регион — добро пожаловать в честное копирование.
Регион — это несколько страниц.
Вот у тебя тройка указателей:
void * page_end;
void * cursor;
void * page_begin;Курсор просто ползёт до page_end, после этого выделяется новая страница, а на старую ссылаются в первом слове новой страницы.
Соответственно, у первой выделенной страницы первое слово всегда null — конец списка.
V>>В целом оно на порядки эффективнее, чем в дотнете.
S>"В целом" — вряд ли. В частных случаях — может быть.
В целом — это сам этот подход.
Просто можно и его испортить, разумеется. ))
Например, в дотнете аллокатор расположен в TLS-слоте (что тоже далеко не верх эффективности — просто получить ссылку на аллокатор, у которого попросить память).
В твоей же реализации могут быть разные подходы — тоже на TLS или некий передаваемый в операции явно context (а в нём даже несколько таких аллокаторов для нескольких подсистем) и т.д.
Разумеется, чтобы был ожидаемый выхлоп, жизненный путь данных тщательно анализируется, а достижения тестируются.
S>То, что вы называете "региональной памятью", другие люди называют ареной
Регион, арена...
Термин не так давно устоялся, что забавно и то, из-за использованных идентификаторов в некоторых реализациях и языках.
S>и это, в целом, аналог поколений в современных GC, только на ручном приводе.
Не скажи...
Например, нулевое поколение — это просто список объектов с некоей "головы".
Затем уплотнения может и не быть (не было неявных освобождений), но голову по окончании цикла GC переназначат.
Сравнивать эти подходы сложновато, потому что в их основе лежат принципиально разные стратегии из-за принципиально разных принятых допущений.
"Просто другая стратегия", всё.
Не обязательно пытаться найти ассоциативную связь со знакомым материалом. ))
За одно только сязывание выделяемых объектов в списки в GC-системах убить мало. ))
S>И применяется, как правило, там, где потребности в памяти можно предсказать — либо мало кросс-ссылок между данными.
Ес-но, граф владения разрабатывается под механику этого владения.
А так-то можно на любой чих получить зацикливание на тех же счётчиках ссылок, привет VB/VBA. ))
Или ссылка на байты в регионе может улететь наружу — привет нежданчик.
Накосячить можно где угодно, конечно.
Однако, язык даёт ср-ва для описания как низкоуровневых ограничений, так и высокоуровневых контрактов, удовлетворяющих принятым в дизайне механикам с их ограничениями.
Разумеется, автоматическое управление памятью кое-где сильно развязывает руки.
А кое-где сильно связывает.
Не изобрели еще серебрянной пули. ))
S>Какой-нибудь видео и аудиопроцессинг с этим будет работать хорошо, а вот компиляторы и прочие трансформации графов — вряд ли.
Компиляторы часто используют аллокаторы пулов ячеек одинакового размера для хранения относительно персистентных данных и регионы для промежуточных данных затратных операций.
Видео и аудио-процессинги мимо — там предвыделяются буфера для пайплайна алгоритма, никаких аллокаций/освобождений памяти в процессе работы кодеков быть не может, конечно.
Память аллоцируется только в момент создания объекта-кодека.
V>>merge — потому что такова природа сущности "множество". ))
S>Вы распишите, что у вас там вместо // .... Поскольку у вас под капотом — заранее неизвестный мутабельный тип, то всё, что вы можете — это состряпать его копию, к которой потом будет применена манипуляция с изменением.
И чем плоха копия такого объекта:
class ImmutableSet<T> {
const RBNode<T> * root_;
};где ImmutableSet<T> используется с семантикой значения, в данном случае значения-ссылки.
В отличие от дотнетного неймспейса Immutable, я именно так реализовывал свои аналоги в дотнете еще черти когда.
Т.е., ссылочная семантика нужна только для узла.
Так для чего ж тогда ImmutableSortedSet<> объявлен ссылочным типом?
А, ну да, ну да...
— из-за встроенного дефолтного конструктора value-типов, который хоть уже и можно переопределить, но он вызывается не всегда.
Пусть в своём коде я могу обложиться Debug.Assert() и требовать, чтобы был вызван недефолтный конструктор или статический метод-фабрика, но в библиотеке платфрменного уровня таких дыр быть не должно, она должна быть защищена от дурака.
Вот тебе еще один плюсик плюсам — там у меня вопрос не стоит, бо описанный мною дефотный конструктор будет вызван явно в любом случае, когда не вызван конструктор с аргументами.
S>Ваш схематично набросанный подход придётся переписать, т.к. выбранные вами сигнатуры даже не позволяют создать эту копию однократно.
Позволяют что угодно, хосподя.
Как напишешь — так и будет.
Мой схематичный подход через "обертки" позволяет гарантировать иммутабельность для изначально описанных мутабельных типов.
Например, узел Node может быть описан мутабельным, но если мы создаём эти узлы внутри реализации и помещаем в константную ссылку/указатель, то тип становится readonly.
Т.е., реализация builder-а не требует дополнительных флагов, типа frozen (как в дотнетной реализации Immutable-узлов, и это почему появилсь отдельные read-only Frozen типы, где не требуется управлять еще и этими флагами). Достаточно по окончании построения присвоить граф константной ссылке/указателю (как говорил с самого начала).
В вашем подопечном-защищаемом дотнетном Immutable совсем всё смешно — набили дерево мильоном узлов в билдере, а потом сказали ему Freeze() — и оно пошло честной стековой рекурсией обходить дерево для установки флага.
"Не об этом я мечтала, когда замуж выходила..." (С) ))
V>>Для случая активного изменения данных я выберу ссылочную семантику, для случая frozen-данных выберу семантику по-значению, разумеется.
S>Просто при передаче вашего ImmutableValue() по значению, будет создаваться deep-копия вложенных в него данных. Со стоимостью O(N).
Deep-копия автоматом только для плоской памяти.
По указателю если — это надо расписывать ручками.
Если используется интрузивный счётчик ссылок и иммутабельность, то копирование вызовет лишь +1 у счётчика cсылок корня:
Рыба такая:
template<typename T>
class SharedHolder {
intrusive_ptr<T> ptr_;
public:
T * get() {
return ptr_.get();
}
const T * get() const {
return ptr_.get();
}
};
template<typename T>
class Node;
template<typename T>
using NodeRef = SharedHolder<Node<T>>;
template<typename T>
class Node {
T value;
NodeRef<T> left_, right_;
public:
Node * left() { return left_.get(); }
const Node * left() const { return left_.get(); }
Node * right() { return right_.get(); }
const Node * right() const { return right_.get(); }
};
template<typename T>
class AvlTreeSet {
NodeRef<T> root_;
public:
typedef T value_type;
void insert(const T & value) {
root_ = mutable_merge(root_, value);
}
AvlTreeSet<T> insert(const T & value) const {
return immutable_merge(root_, value);
}
};
template<typename TSet>
class ImmutableSet {
const TSet set_;
explicit ImmutableSet(TSet && s) : set_(s) {}
public:
ImmutableSet() {}
const TSet & set() const {
return set_;
}
ImmutableSet<TSet> operator|(const typename TSet::value_type & b) const {
return ImmutableSet<TSet>(move(set_.insert(b)));
}
ImmutableSet<TSet> operator|(const ImmutableSet<TSet> & b) const {
TSet tmp = set_;
b.for_each([&](const auto & value) {
tmp = static_cast<const TSet &>(tmp).insert(value);
});
return ImmutableSet<TSet>(move(tmp));
}
};
int main()
{
using Set = ImmutableSet<AvlTreeSet<int>>;
auto s1 = Set() | 1 | 2 | 3;
return 0;
}V>>Я рядом давал тебе ссылку на исходники SmallFrozenSet.
S>Да при чём тут ссылка? Вы просто опять уходите в решения для каких-то экзотических частных случаев.
Наоборот, говорил, что в плюсах есть возможность писать более обще, потому что у меня есть возможность распространять гарантии.
Обрати внимание на сигнатуры парами:
T * get() {
const T * get() const {
Node * left() {
const Node * left() const {
Node * right() {
const Node * right() const {По константной ссылке-указателю может быть вызвана только const-this версия метода, соответственно, у меня одно описание на все случаи жизни.
См. тут:
void insert(const T & value) {
root_ = mutable_merge(root_, value);
}
AvlTreeSet<T> insert(const T & value) const {
return immutable_merge(root_, value);
}Константное поле у меня лишь в декораторе ImmutableSet<TSet>, далее констрантность распространяется.
Что я могу себе позволить, чтобы мои абстракции не протекли:
— дефолтный конструктор ImmutableSet (в примере auto empty = ImmutableSet<AvlTreeSet<int>>())
— конструктор от значений или других ImmutableSet.
Чего нельзя:
— публичные конструкторы от мутабельных типов.
Ф-ии навроде mutable_merge или immetable_merge могут быть внешними. При непосредственном вызове этих ф-ий над иммутабельными типами ничего гарантировать нельзя, разумеется.
Наверно, тебя именно это беспокоило несколько лет назад и в этом обсуждении снова.
Я же тебе говорил, что я могу распространить гарантии так, что они не протекут.
На самый худой конец их можно распространить на самое дно — поля целевых типов. ))
Просто никто так не делает обычно.
А как делают — показал.
Т.е. распространяют гарантии константности и создают невозможность протечки абстракций через доступное публичное АПИ.
Чего нельзя:
— публичные конструкторы от мутабельных типов.
В целях эффективности класс ImmutableSet может содержать вложенный класс Builder, который манипулирует мутабельным TSet на стадии напихивания данных, и в какой-то момент передаёт владение набором данных в иммутабельный ImmutableSet. Т.е. классу Builder будет доступен приватный конструктор декоратора ImmutableSet, а тебе нет. И что забавно, всего одна реализация ImmutableSet и Builder на все реализации set с нужными наборами методов.
V>>Не обошлись, там точно такая же магия для структур в ключевом слове readonly.
S>Я говорю конкретно про иммутабельность. Много ли readonly вы видите в System.Collections.Immutable?
Я там вообще мало чего интересного вижу и вряд ли когда буду пользоваться этой неэффективной реализацией.
В упор не понимаю, чем тебя заинтересовало это убожество.
Это ж для хомячков.
"Чтобы было!" (С)
V>>А было бы неплохо и для интерфейсов-классов, где IImuttableList мог быть объявлен как readonly interface IImuttableList, соответственно, все реализующие его классы должны были бы быть readonly IImuttableList : ImuttableList {...}
S>Это — бесполезная идея.
"Это потому что ты не понимаешь иммутабельности" (С)
Для структур оказалась крайне полезной, потому что иначе возникал диссонанс с readonly-полями value-типов.
Пришлось ввести readonly-методы, что есть полный аналог const-this методов в С++.
S>Она одновременно не даст никаких гарантий иммутабельности
В плюсах я распространяю константность в зависимости от константной или нет сигнатуры метода.
В дотнете распространять константность можно было бы автоматом для ссылочных readonly типов, как оно есть для readonly структур.
Т.е. такие типы могли бы содержать лишь readonly структуры и readonly классы/интерфейсы как поля.
S>потому, что внутри реализации ImmutableList — ссылка, которая, в том числе, может быть и на mutable данные
Хосподя, ну так за этим и предлагается, иначе смысла не будет.
S>и помешает некоторым сценариям, где иммутабл-объект изменяется в процессе конструирования.
В конструкторе поля можно изменять многократно, это не проблема.
А утекание абстракций контроллировать компилятором/верификатором, чтобы он запрещал изменение полей после того как из конструктора утёк this (будучи переданным некоему аргументу, допустим, для регистрации созданного объекта где-то там).
В этой схеме невозможно создать циклические ссылки объектов друг на друга, как их невозможно создать в ФП, но никто не жалуется.
Если уж требуются наработки иммутабельности из ФП — то берите их готовые.
V>>Но ты просил гарантии, поэтому я и продемонстрировал ср-ва для выражения гарантий.
S>
Повторюсь: гарантии в продемонстрированном вами подходе никак не зависят от применения ключевого слова const. -1
Рассуждая таким образом можно договориться до того, что и язык Ассемблера даёт такие же гарантии.
Конечно, С++ даёт несравнимо больше гарантий в плане проектирования иммутабельных типов.
Тебе надо просто взять однажды компилятор и чуть поупражняться в проектировании иммутабельных иерархий в плюсах, чтобы ты понял о чём речь.
Сколько раз компилятор подсказывает о константности, т.е. не пропускает компиляции при нарушении контракта — это тебе не передать.
В случае же подхода Immutable из дотнета — это только тестами корректность проверять и то, плохо понятно как именно, бо приватные кишки классов не проверишь.
Остается верить на слово, бгг...
По отношению к иммутабельности дотнет находится в сравнении с плюсами примерно там же, где скриптовые нетипизированные языки находятся в сравнении с языками со строгой статической типизацией.
Говорить "это одно и то же" — сверкать ярчайшим нубством, сорри.
Хоть бы посмотрел на readony ref, scope и readonly методы структур в дотнете.
Похоже, ты со всем этим еще не разбирался, но мнение имеешь.
S>Если вы его уберёте, ImmutableValue<> останется ровно на столько же иммутабельным, как и был.
Это из-за необычно сильно ограниченного твоего мышления, через которое я уже устал продираться.
Как тебе недавно введенные управляемые ссылки как поля ref-структур?
Я об этом говорил еще примерно в 2005-м, но некоторые столь же узко мыслящие даже не понимали — а зачем?
Ты хоть понимаешь — зачем?
И почему это стало возможно только с введением readonly ref?
Я так думаю, что ты малость отстал от последних версий платформы, с тобой реально сложно разговаривать, хоть ты себя и позиционируешь как спец по дотнету. ))
V>>Пусть по-мелочам больше думает машина, чем программист.
S>Непонятно, что вы имеете в виду. Я всё ещё не вижу сценария, который вы предотвращаете при помощи этого ключевого слова.
Да пофик.
Первый раз сказал "не вижу" — объяснили.
Если и после этого "не вижу" — списали на берег.
V>>Хорошо, что согласился хоть с чем-то. ))
V>>Проблематика заданного именно тобой обсуждения как раз в интерфейсах — ты хотел писать обобщённые алгоритмы в условиях гарантий.
S>Разве? Может, я что-то подзабыл. Можно указать, где именно я настаивал на интерфейсах?
Ты говорил, дословно, "как мне знать, что тип иммутабельный"?
Разночтений быть не может, ты говорил о неизвестном потенциальном типе для своих алгоримов, соответственно, речь должна были идти об абстракциях.
А дотнете абстракции живут на интерфейсах и на ограничениях ими генериков.
V>>Оно и так в реальной жизни отродясь иммутабельно для State и до введения готовых Immutable-реализаций.
S>"Оно" — это кто?
Это объект-состояние ДКА для автомата.
V>>В общем, будет отличаться тем, бо абстракция ImmutableMapWrapper бесплатна, а обёрнут может быть не только конкретный std::map.
V>>Ну и, из-за наличия частичного определения шаблонов, может быть обёрнут даже тип, который не совместим по публичному интерфейсу в std::map.
S>Как только вы обернёте не только конкретный sdd::map, появится и возможность "хулиганить".
Не появится, я выше дал полный список обеспечения гарантий.
Просто, блин, ты поразительно недогадлив, с ложечки кормить приходится.
V>>А как тебе arg... — семантика?
S>У меня со времён params в С# такой синтаксис удивления не вызывает.
В дотнете это массив в куче, днамическое итерирование по params в цикле, в плюсах статика времени компиляции, линейная раскрутка кода.
В дотнете в params могут быть одинаковые типы (или наследники для случая ссылочных типов), в плюсах произвольные, допустимые обработчиками.
S>А семантика, на первый взгляд, слабже — не так удобно извлекать коллекцию
При надобности оно рассматривается как initializer_list.Просто, блин, ты поразительно недогадлив, с ложечки кормить приходится.
Я вообще удивляюсь, как ты дожил до своих лет и тебя до сих пор не прибили за аксиматическую позицию "все вокруг дураки", когда реальность подтверждает обратное? ))
S>и принудительная замена итерации рекурсией не выглядит шибко привлекательно.
ЧТД, вот тебе пример того, что дураков вовсе не вокруг искать надо.
При вычислении вложенных вызовов ф-ий для arg... получается линейный код вычисления аргументов ф-ий от самых глубоких к внешним.
Это абсолютно линейный код верхнего уровня, последовательность call.
Итерация там только в процессе работы компилятора.
А как бы оно вообще могло работать, неужели даже не попытался представить?
В любом случае, я тебе показал во что реально превращается тот код.
S>Вот если бы ещё шарп починили, разрешив приписывать params к параметру любого типа, который реализован массивом. В частности, IEnumerable<T> и IList<T>.
То сделали бы эти случаи неразличимыми/конфликтующими, в то время как м/у ними сильное различие с т.з. эффективности.
В кишках дотнета голые массивы весьма входу и популярны.
Где приходится бороться за эффективность на юзверском уровне — тоже.
Re[18]: понимание ООП Алана Кея
Здравствуйте, Sinclair, Вы писали:
S>Эти слова я читал. Я не понимаю, как вы будете их применять. Что именно помешает "по невнимательности" добавить в ImmutableValue<T> мутирующих методов?
Если поля описаны как const, то мутировать их никак.
Есть еще ключевое слово mutable — это когда к полю можно обращаться из const this метода.
Например, интрузивные счётчики ссылок часто описывают как mutable, потому что они работают над совместным владением объектами, без вмешательства в потенциально read-only семантику прикладных данных. Чаще всего такие счётчики размещают как приватные в неких базовых классах, т.е. эти счётчики недоступны затем наследуемому "прикладному" коду, предоставляя, однако, через функциональность этих базовых классов требуемую инфраструктуру по ссылочному шаренью целевых данных.
V>>С одной стороны, это не более чем эксплуатация выразительных ср-в языка, что мы гарантии прописываем через синтаксис (а не комментарии) и контроллируем их через систему типов.
V>>Создание копий иммутабельных данных может быть полезным для региональной памяти, когда необходимо сохранить данные в своём регионе.
S>Это опять какие-то вырожденные экзотические сценарии, нужные примерно никогда.
Коль мы возимся с иммутабельностью эффективности ради, то "примерно никогда" на практике трасформируется в "часто".
Серебрянной пули для эффективности нет, сие аксиома. ))
В каждом конкретном случае используется комплекс мер для обеспечения эффективности этого случая, коль эффективность вообще требуется.
V>>Счётчики обычно дергаются при перестроении, допустим, графа на иммутабельных узлах, поэтому доп. накладные расходы не настолько уж велики, чтобы говорить о дне, бо перестраивается только часть узлов.
S>Счётчики ссылок, очевидно, дёргаются при любом копировании.
Дергаются не у всего дерева, а только у непосредственных детей вновь создаваемых узлов при перестроении, а это log N.
Т.е. еще зависит от вида дерева — RB, AVL или еще какие с арностью более 2 — тогда будет еще меньше дерганий счётчиков ссылок.
Плюс, в промежуточных операциях (при нескольких поворотах, например, вставка может породить два поворота, а удаление из AVL до 5-ти поворотов) можно исключить дерганье счётчиков ссылок в процессе, пробежавшись по новым узлам уже по окончании операций.
S>Как раз "перестроенные" узлы, которых мало, получают счётчики == 1.
У непосредственных детей новых узлов надо увеличить счётчик ссылок — мы же шарим имеющиеся узлы, не перестраиваемые при повороте.
И опять же, смотря как реализовано дерево. Ссылочные ноды RB-деревьев могут хранить value-кластер тройки узлов {R, B, R}, т.е. в общем случае меньше дерганий счетчиков ссылок (вдвое меньше "ссылочная" высота дерева), как и для более арных деревьев.
V>>А региональная память — это когда некая подсистема сама распределяет память на низком уровне, обращаясь к операционке только за относительно большими страницами памяти.
V>>В таких распределителях память обычно выделяется как grow-only, простым смещением текущего указателя свободной области, т.е. выделение происходит с эффективностью дотнета.
V>>А освобождается затем и вовсе бесплатно, целиком одной операцией возврата операционке страницы (страниц).
S>Это если у вас хватает размера региона на полную работу алгоритма.
Память выделяется страницами, выделенные страницы хранятся по единственной ссылке, бо связаны в однонаправленный список.
Аллокаторы обычно настраиваются compile-time константами-параметрами, например, размером страницы и величиной выравнивания (выравнивание порой нужно не на слово, а на линейку кеша).
Эти техники, считай, обязательные в реализациях нейтивных веб-серверов, баз данных, компиляторов и т.д., бо региоальная память хорошо себя показывает в сценариях "выделить память для отдельной операции и всю её освободить по окончании операции". Боюсь даже представить, как работали бы БД или компиляторы без региональной памяти, на обычном malloc на каждый чих. ))
Плюс, в отличие от распределителей на основе пула ячеек одинакового размера (аллокатор по степени двойки связывает ячейки одинакового размера в линейные списки, где пустые ячейки друг на друга ссылаются, т.е. первое слово свободной ячейки интерпретируется как адрес следующей ячейки), у региональной памяти всё неплохо с локальностью. Зато плохо с долгоживучестью у grow-only аллокатора, поэтому сей подход и нашел себя в обслуживании указанных относительно короткоживущих сценариев.
S>Заранее сказать, сколько потребуется памяти для хранения мусора, порождаемого компилятором при анализе AST, весьма затруднительно.
А оно и не требуется.
Каждая трансформация — отдельная операция, т.е. для временных данных можно юзать такие аллокаторы, длительностью жизни в операцию.
Потом у аллокатора вызывается некий reset и он переиспользуется для другой операции и т.д.
В общем, когда память не держит некие ресурсы (хендлы), а просто представляет из себя размеченную память для целей вычислений над данными, то требования к финализации испаряются — просто возвращаем страницу памяти целиком в пул свободных страниц и ву-а-ля.
Это ж азы, а не "уникальность".
Это сегодня мы разбалованы современными высокоуровневыми подходами...
В более хардокорном прошлом это всё из разряда не уникальности, а must have, то бишь, не новинка, а наоборот, традиции.
S>А как только вы исчерпали регион — добро пожаловать в честное копирование.
Регион — это несколько страниц.
Вот у тебя тройка указателей:
Курсор просто ползёт до page_end, после этого выделяется новая страница, а на старую ссылаются в первом слове новой страницы.
Соответственно, у первой выделенной страницы первое слово всегда null — конец списка.
V>>В целом оно на порядки эффективнее, чем в дотнете.
S>"В целом" — вряд ли. В частных случаях — может быть.
В целом — это сам этот подход.
Просто можно и его испортить, разумеется. ))
Например, в дотнете аллокатор расположен в TLS-слоте (что тоже далеко не верх эффективности — просто получить ссылку на аллокатор, у которого попросить память).
В твоей же реализации могут быть разные подходы — тоже на TLS или некий передаваемый в операции явно context (а в нём даже несколько таких аллокаторов для нескольких подсистем) и т.д.
Разумеется, чтобы был ожидаемый выхлоп, жизненный путь данных тщательно анализируется, а достижения тестируются.
S>То, что вы называете "региональной памятью", другие люди называют ареной
Регион, арена...
Термин не так давно устоялся, что забавно и то, из-за использованных идентификаторов в некоторых реализациях и языках.
S>и это, в целом, аналог поколений в современных GC, только на ручном приводе.
Не скажи...
Например, нулевое поколение — это просто список объектов с некоей "головы".
Затем уплотнения может и не быть (не было неявных освобождений), но голову по окончании цикла GC переназначат.
Сравнивать эти подходы сложновато, потому что в их основе лежат принципиально разные стратегии из-за принципиально разных принятых допущений.
"Просто другая стратегия", всё.
Не обязательно пытаться найти ассоциативную связь со знакомым материалом. ))
За одно только сязывание выделяемых объектов в списки в GC-системах убить мало. ))
S>И применяется, как правило, там, где потребности в памяти можно предсказать — либо мало кросс-ссылок между данными.
Ес-но, граф владения разрабатывается под механику этого владения.
А так-то можно на любой чих получить зацикливание на тех же счётчиках ссылок, привет VB/VBA. ))
Или ссылка на байты в регионе может улететь наружу — привет нежданчик.
Накосячить можно где угодно, конечно.
Однако, язык даёт ср-ва для описания как низкоуровневых ограничений, так и высокоуровневых контрактов, удовлетворяющих принятым в дизайне механикам с их ограничениями.
Разумеется, автоматическое управление памятью кое-где сильно развязывает руки.
А кое-где сильно связывает.
Не изобрели еще серебрянной пули. ))
S>Какой-нибудь видео и аудиопроцессинг с этим будет работать хорошо, а вот компиляторы и прочие трансформации графов — вряд ли.
Компиляторы часто используют аллокаторы пулов ячеек одинакового размера для хранения относительно персистентных данных и регионы для промежуточных данных затратных операций.
Видео и аудио-процессинги мимо — там предвыделяются буфера для пайплайна алгоритма, никаких аллокаций/освобождений памяти в процессе работы кодеков быть не может, конечно.
Память аллоцируется только в момент создания объекта-кодека.
V>>merge — потому что такова природа сущности "множество". ))
S>Вы распишите, что у вас там вместо // .... Поскольку у вас под капотом — заранее неизвестный мутабельный тип, то всё, что вы можете — это состряпать его копию, к которой потом будет применена манипуляция с изменением.
И чем плоха копия такого объекта:
где ImmutableSet<T> используется с семантикой значения, в данном случае значения-ссылки.
В отличие от дотнетного неймспейса Immutable, я именно так реализовывал свои аналоги в дотнете еще черти когда.
Т.е., ссылочная семантика нужна только для узла.
Так для чего ж тогда ImmutableSortedSet<> объявлен ссылочным типом?
А, ну да, ну да...
— из-за встроенного дефолтного конструктора value-типов, который хоть уже и можно переопределить, но он вызывается не всегда.
Пусть в своём коде я могу обложиться Debug.Assert() и требовать, чтобы был вызван недефолтный конструктор или статический метод-фабрика, но в библиотеке платфрменного уровня таких дыр быть не должно, она должна быть защищена от дурака.
Вот тебе еще один плюсик плюсам — там у меня вопрос не стоит, бо описанный мною дефотный конструктор будет вызван явно в любом случае, когда не вызван конструктор с аргументами.
S>Ваш схематично набросанный подход придётся переписать, т.к. выбранные вами сигнатуры даже не позволяют создать эту копию однократно.
Позволяют что угодно, хосподя.
Как напишешь — так и будет.
Мой схематичный подход через "обертки" позволяет гарантировать иммутабельность для изначально описанных мутабельных типов.
Например, узел Node может быть описан мутабельным, но если мы создаём эти узлы внутри реализации и помещаем в константную ссылку/указатель, то тип становится readonly.
Т.е., реализация builder-а не требует дополнительных флагов, типа frozen (как в дотнетной реализации Immutable-узлов, и это почему появилсь отдельные read-only Frozen типы, где не требуется управлять еще и этими флагами). Достаточно по окончании построения присвоить граф константной ссылке/указателю (как говорил с самого начала).
В вашем подопечном-защищаемом дотнетном Immutable совсем всё смешно — набили дерево мильоном узлов в билдере, а потом сказали ему Freeze() — и оно пошло честной стековой рекурсией обходить дерево для установки флага.
"Не об этом я мечтала, когда замуж выходила..." (С) ))
V>>Для случая активного изменения данных я выберу ссылочную семантику, для случая frozen-данных выберу семантику по-значению, разумеется.
S>Просто при передаче вашего ImmutableValue() по значению, будет создаваться deep-копия вложенных в него данных. Со стоимостью O(N).
Deep-копия автоматом только для плоской памяти.
По указателю если — это надо расписывать ручками.
Если используется интрузивный счётчик ссылок и иммутабельность, то копирование вызовет лишь +1 у счётчика cсылок корня:
Рыба такая:
V>>Я рядом давал тебе ссылку на исходники SmallFrozenSet.
S>Да при чём тут ссылка? Вы просто опять уходите в решения для каких-то экзотических частных случаев.
Наоборот, говорил, что в плюсах есть возможность писать более обще, потому что у меня есть возможность распространять гарантии.
Обрати внимание на сигнатуры парами:
По константной ссылке-указателю может быть вызвана только const-this версия метода, соответственно, у меня одно описание на все случаи жизни.
См. тут:
Константное поле у меня лишь в декораторе ImmutableSet<TSet>, далее констрантность распространяется.
Что я могу себе позволить, чтобы мои абстракции не протекли:
— дефолтный конструктор ImmutableSet (в примере auto empty = ImmutableSet<AvlTreeSet<int>>())
— конструктор от значений или других ImmutableSet.
Чего нельзя:
— публичные конструкторы от мутабельных типов.
Ф-ии навроде mutable_merge или immetable_merge могут быть внешними. При непосредственном вызове этих ф-ий над иммутабельными типами ничего гарантировать нельзя, разумеется.
Наверно, тебя именно это беспокоило несколько лет назад и в этом обсуждении снова.
Я же тебе говорил, что я могу распространить гарантии так, что они не протекут.
На самый худой конец их можно распространить на самое дно — поля целевых типов. ))
Просто никто так не делает обычно.
А как делают — показал.
Т.е. распространяют гарантии константности и создают невозможность протечки абстракций через доступное публичное АПИ.
В целях эффективности класс ImmutableSet может содержать вложенный класс Builder, который манипулирует мутабельным TSet на стадии напихивания данных, и в какой-то момент передаёт владение набором данных в иммутабельный ImmutableSet. Т.е. классу Builder будет доступен приватный конструктор декоратора ImmutableSet, а тебе нет. И что забавно, всего одна реализация ImmutableSet и Builder на все реализации set с нужными наборами методов.
V>>Не обошлись, там точно такая же магия для структур в ключевом слове readonly.
S>Я говорю конкретно про иммутабельность. Много ли readonly вы видите в System.Collections.Immutable?
Я там вообще мало чего интересного вижу и вряд ли когда буду пользоваться этой неэффективной реализацией.
В упор не понимаю, чем тебя заинтересовало это убожество.
Это ж для хомячков.
"Чтобы было!" (С)
V>>А было бы неплохо и для интерфейсов-классов, где IImuttableList мог быть объявлен как readonly interface IImuttableList, соответственно, все реализующие его классы должны были бы быть readonly IImuttableList : ImuttableList {...}
S>Это — бесполезная идея.
"Это потому что ты не понимаешь иммутабельности" (С)
Для структур оказалась крайне полезной, потому что иначе возникал диссонанс с readonly-полями value-типов.
Пришлось ввести readonly-методы, что есть полный аналог const-this методов в С++.
S>Она одновременно не даст никаких гарантий иммутабельности
В плюсах я распространяю константность в зависимости от константной или нет сигнатуры метода.
В дотнете распространять константность можно было бы автоматом для ссылочных readonly типов, как оно есть для readonly структур.
Т.е. такие типы могли бы содержать лишь readonly структуры и readonly классы/интерфейсы как поля.
S>потому, что внутри реализации ImmutableList — ссылка, которая, в том числе, может быть и на mutable данные
Хосподя, ну так за этим и предлагается, иначе смысла не будет.
S>и помешает некоторым сценариям, где иммутабл-объект изменяется в процессе конструирования.
В конструкторе поля можно изменять многократно, это не проблема.
А утекание абстракций контроллировать компилятором/верификатором, чтобы он запрещал изменение полей после того как из конструктора утёк this (будучи переданным некоему аргументу, допустим, для регистрации созданного объекта где-то там).
В этой схеме невозможно создать циклические ссылки объектов друг на друга, как их невозможно создать в ФП, но никто не жалуется.
Если уж требуются наработки иммутабельности из ФП — то берите их готовые.
V>>Но ты просил гарантии, поэтому я и продемонстрировал ср-ва для выражения гарантий.
S> Повторюсь: гарантии в продемонстрированном вами подходе никак не зависят от применения ключевого слова const.
-1
Рассуждая таким образом можно договориться до того, что и язык Ассемблера даёт такие же гарантии.
Конечно, С++ даёт несравнимо больше гарантий в плане проектирования иммутабельных типов.
Тебе надо просто взять однажды компилятор и чуть поупражняться в проектировании иммутабельных иерархий в плюсах, чтобы ты понял о чём речь.
Сколько раз компилятор подсказывает о константности, т.е. не пропускает компиляции при нарушении контракта — это тебе не передать.
В случае же подхода Immutable из дотнета — это только тестами корректность проверять и то, плохо понятно как именно, бо приватные кишки классов не проверишь.
Остается верить на слово, бгг...
По отношению к иммутабельности дотнет находится в сравнении с плюсами примерно там же, где скриптовые нетипизированные языки находятся в сравнении с языками со строгой статической типизацией.
Говорить "это одно и то же" — сверкать ярчайшим нубством, сорри.
Хоть бы посмотрел на readony ref, scope и readonly методы структур в дотнете.
Похоже, ты со всем этим еще не разбирался, но мнение имеешь.
S>Если вы его уберёте, ImmutableValue<> останется ровно на столько же иммутабельным, как и был.
Это из-за необычно сильно ограниченного твоего мышления, через которое я уже устал продираться.
Как тебе недавно введенные управляемые ссылки как поля ref-структур?
Я об этом говорил еще примерно в 2005-м, но некоторые столь же узко мыслящие даже не понимали — а зачем?
Ты хоть понимаешь — зачем?
И почему это стало возможно только с введением readonly ref?
Я так думаю, что ты малость отстал от последних версий платформы, с тобой реально сложно разговаривать, хоть ты себя и позиционируешь как спец по дотнету. ))
V>>Пусть по-мелочам больше думает машина, чем программист.
S>Непонятно, что вы имеете в виду. Я всё ещё не вижу сценария, который вы предотвращаете при помощи этого ключевого слова.
Да пофик.
Первый раз сказал "не вижу" — объяснили.
Если и после этого "не вижу" — списали на берег.
V>>Хорошо, что согласился хоть с чем-то. ))
V>>Проблематика заданного именно тобой обсуждения как раз в интерфейсах — ты хотел писать обобщённые алгоритмы в условиях гарантий.
S>Разве? Может, я что-то подзабыл. Можно указать, где именно я настаивал на интерфейсах?
Ты говорил, дословно, "как мне знать, что тип иммутабельный"?
Разночтений быть не может, ты говорил о неизвестном потенциальном типе для своих алгоримов, соответственно, речь должна были идти об абстракциях.
В дотнете абстракции живут на интерфейсах и на ограничениях ими генериков.
V>>Оно и так в реальной жизни отродясь иммутабельно для State и до введения готовых Immutable-реализаций.
S>"Оно" — это кто?
Это объект-состояние ДКА для автомата.
V>>В общем, будет отличаться тем, бо абстракция ImmutableMapWrapper бесплатна, а обёрнут может быть не только конкретный std::map.
V>>Ну и, из-за наличия частичного определения шаблонов, может быть обёрнут даже тип, который не совместим по публичному интерфейсу в std::map.
S>Как только вы обернёте не только конкретный sdd::map, появится и возможность "хулиганить".
Не появится, я выше дал полный список обеспечения гарантий.
Просто, блин, ты поразительно недогадлив, с ложечки кормить приходится.
V>>А как тебе arg... — семантика?
S>У меня со времён params в С# такой синтаксис удивления не вызывает.
В дотнете это массив в куче, днамическое итерирование по params в цикле, в плюсах статика времени компиляции, линейная раскрутка кода.
В дотнете в params могут быть одинаковые типы (или наследники для случая ссылочных типов), в плюсах произвольные, допустимые обработчиками.
S>А семантика, на первый взгляд, слабже — не так удобно извлекать коллекцию
Я вообще удивляюсь, как ты дожил до своих лет и тебя до сих пор не прибили за аксиматическую позицию "все вокруг дураки", когда реальность подтверждает обратное? ))
S>и принудительная замена итерации рекурсией не выглядит шибко привлекательно.
ЧТД, вот тебе пример того, что дураков вовсе не вокруг искать надо.
При вычислении вложенных вызовов ф-ий для arg... получается линейный код вычисления аргументов ф-ий от самых глубоких к внешним.
Это абсолютно линейный код верхнего уровня, последовательность call.
Итерация там только в процессе работы компилятора.
А как бы оно вообще могло работать, неужели даже не попытался представить?
В любом случае, я тебе показал во что реально превращается тот код.
S>Вот если бы ещё шарп починили, разрешив приписывать params к параметру любого типа, который реализован массивом. В частности, IEnumerable<T> и IList<T>.
То сделали бы эти случаи неразличимыми/конфликтующими, в то время как м/у ними сильное различие с т.з. эффективности.
В кишках дотнета голые массивы весьма входу и популярны.
Где приходится бороться за эффективность на юзверском уровне — тоже.
S>Эти слова я читал. Я не понимаю, как вы будете их применять. Что именно помешает "по невнимательности" добавить в ImmutableValue<T> мутирующих методов?
Если поля описаны как const, то мутировать их никак.
Есть еще ключевое слово mutable — это когда к полю можно обращаться из const this метода.
Например, интрузивные счётчики ссылок часто описывают как mutable, потому что они работают над совместным владением объектами, без вмешательства в потенциально read-only семантику прикладных данных. Чаще всего такие счётчики размещают как приватные в неких базовых классах, т.е. эти счётчики недоступны затем наследуемому "прикладному" коду, предоставляя, однако, через функциональность этих базовых классов требуемую инфраструктуру по ссылочному шаренью целевых данных.
V>>С одной стороны, это не более чем эксплуатация выразительных ср-в языка, что мы гарантии прописываем через синтаксис (а не комментарии) и контроллируем их через систему типов.
V>>Создание копий иммутабельных данных может быть полезным для региональной памяти, когда необходимо сохранить данные в своём регионе.
S>Это опять какие-то вырожденные экзотические сценарии, нужные примерно никогда.
Коль мы возимся с иммутабельностью эффективности ради, то "примерно никогда" на практике трасформируется в "часто".
Серебрянной пули для эффективности нет, сие аксиома. ))
В каждом конкретном случае используется комплекс мер для обеспечения эффективности этого случая, коль эффективность вообще требуется.
V>>Счётчики обычно дергаются при перестроении, допустим, графа на иммутабельных узлах, поэтому доп. накладные расходы не настолько уж велики, чтобы говорить о дне, бо перестраивается только часть узлов.
S>Счётчики ссылок, очевидно, дёргаются при любом копировании.
Дергаются не у всего дерева, а только у непосредственных детей вновь создаваемых узлов при перестроении, а это log N.
Т.е. еще зависит от вида дерева — RB, AVL или еще какие с арностью более 2 — тогда будет еще меньше дерганий счётчиков ссылок.
Плюс, в промежуточных операциях (при нескольких поворотах, например, вставка может породить два поворота, а удаление из AVL до 5-ти поворотов) можно исключить дерганье счётчиков ссылок в процессе, пробежавшись по новым узлам уже по окончании операций.
S>Как раз "перестроенные" узлы, которых мало, получают счётчики == 1.
У непосредственных детей новых узлов надо увеличить счётчик ссылок — мы же шарим имеющиеся узлы, не перестраиваемые при повороте.
И опять же, смотря как реализовано дерево. Ссылочные ноды RB-деревьев могут хранить value-кластер тройки узлов {R, B, R}, т.е. в общем случае меньше дерганий счетчиков ссылок (вдвое меньше "ссылочная" высота дерева), как и для более арных деревьев.
V>>А региональная память — это когда некая подсистема сама распределяет память на низком уровне, обращаясь к операционке только за относительно большими страницами памяти.
V>>В таких распределителях память обычно выделяется как grow-only, простым смещением текущего указателя свободной области, т.е. выделение происходит с эффективностью дотнета.
V>>А освобождается затем и вовсе бесплатно, целиком одной операцией возврата операционке страницы (страниц).
S>Это если у вас хватает размера региона на полную работу алгоритма.
Память выделяется страницами, выделенные страницы хранятся по единственной ссылке, бо связаны в однонаправленный список.
Аллокаторы обычно настраиваются compile-time константами-параметрами, например, размером страницы и величиной выравнивания (выравнивание порой нужно не на слово, а на линейку кеша).
Эти техники, считай, обязательные в реализациях нейтивных веб-серверов, баз данных, компиляторов и т.д., бо региоальная память хорошо себя показывает в сценариях "выделить память для отдельной операции и всю её освободить по окончании операции". Боюсь даже представить, как работали бы БД или компиляторы без региональной памяти, на обычном malloc на каждый чих. ))
Плюс, в отличие от распределителей на основе пула ячеек одинакового размера (аллокатор по степени двойки связывает ячейки одинакового размера в линейные списки, где пустые ячейки друг на друга ссылаются, т.е. первое слово свободной ячейки интерпретируется как адрес следующей ячейки), у региональной памяти всё неплохо с локальностью. Зато плохо с долгоживучестью у grow-only аллокатора, поэтому сей подход и нашел себя в обслуживании указанных относительно короткоживущих сценариев.
S>Заранее сказать, сколько потребуется памяти для хранения мусора, порождаемого компилятором при анализе AST, весьма затруднительно.
А оно и не требуется.
Каждая трансформация — отдельная операция, т.е. для временных данных можно юзать такие аллокаторы, длительностью жизни в операцию.
Потом у аллокатора вызывается некий reset и он переиспользуется для другой операции и т.д.
В общем, когда память не держит некие ресурсы (хендлы), а просто представляет из себя размеченную память для целей вычислений над данными, то требования к финализации испаряются — просто возвращаем страницу памяти целиком в пул свободных страниц и ву-а-ля.
Это ж азы, а не "уникальность".
Это сегодня мы разбалованы современными высокоуровневыми подходами...
В более хардокорном прошлом это всё из разряда не уникальности, а must have, то бишь, не новинка, а наоборот, традиции.
S>А как только вы исчерпали регион — добро пожаловать в честное копирование.
Регион — это несколько страниц.
Вот у тебя тройка указателей:
void * page_end;
void * cursor;
void * page_begin;Курсор просто ползёт до page_end, после этого выделяется новая страница, а на старую ссылаются в первом слове новой страницы.
Соответственно, у первой выделенной страницы первое слово всегда null — конец списка.
V>>В целом оно на порядки эффективнее, чем в дотнете.
S>"В целом" — вряд ли. В частных случаях — может быть.
В целом — это сам этот подход.
Просто можно и его испортить, разумеется. ))
Например, в дотнете аллокатор расположен в TLS-слоте (что тоже далеко не верх эффективности — просто получить ссылку на аллокатор, у которого попросить память).
В твоей же реализации могут быть разные подходы — тоже на TLS или некий передаваемый в операции явно context (а в нём даже несколько таких аллокаторов для нескольких подсистем) и т.д.
Разумеется, чтобы был ожидаемый выхлоп, жизненный путь данных тщательно анализируется, а достижения тестируются.
S>То, что вы называете "региональной памятью", другие люди называют ареной
Регион, арена...
Термин не так давно устоялся, что забавно и то, из-за использованных идентификаторов в некоторых реализациях и языках.
S>и это, в целом, аналог поколений в современных GC, только на ручном приводе.
Не скажи...
Например, нулевое поколение — это просто список объектов с некоей "головы".
Затем уплотнения может и не быть (не было неявных освобождений), но голову по окончании цикла GC переназначат.
Сравнивать эти подходы сложновато, потому что в их основе лежат принципиально разные стратегии из-за принципиально разных принятых допущений.
"Просто другая стратегия", всё.
Не обязательно пытаться найти ассоциативную связь со знакомым материалом. ))
За одно только сязывание выделяемых объектов в списки в GC-системах убить мало. ))
S>И применяется, как правило, там, где потребности в памяти можно предсказать — либо мало кросс-ссылок между данными.
Ес-но, граф владения разрабатывается под механику этого владения.
А так-то можно на любой чих получить зацикливание на тех же счётчиках ссылок, привет VB/VBA. ))
Или ссылка на байты в регионе может улететь наружу — привет нежданчик.
Накосячить можно где угодно, конечно.
Однако, язык даёт ср-ва для описания как низкоуровневых ограничений, так и высокоуровневых контрактов, удовлетворяющих принятым в дизайне механикам с их ограничениями.
Разумеется, автоматическое управление памятью кое-где сильно развязывает руки.
А кое-где сильно связывает.
Не изобрели еще серебрянной пули. ))
S>Какой-нибудь видео и аудиопроцессинг с этим будет работать хорошо, а вот компиляторы и прочие трансформации графов — вряд ли.
Компиляторы часто используют аллокаторы пулов ячеек одинакового размера для хранения относительно персистентных данных и регионы для промежуточных данных затратных операций.
Видео и аудио-процессинги мимо — там предвыделяются буфера для пайплайна алгоритма, никаких аллокаций/освобождений памяти в процессе работы кодеков быть не может, конечно.
Память аллоцируется только в момент создания объекта-кодека.
V>>merge — потому что такова природа сущности "множество". ))
S>Вы распишите, что у вас там вместо // .... Поскольку у вас под капотом — заранее неизвестный мутабельный тип, то всё, что вы можете — это состряпать его копию, к которой потом будет применена манипуляция с изменением.
И чем плоха копия такого объекта:
class ImmutableSet<T> {
const RBNode<T> * root_;
};где ImmutableSet<T> используется с семантикой значения, в данном случае значения-ссылки.
В отличие от дотнетного неймспейса Immutable, я именно так реализовывал свои аналоги в дотнете еще черти когда.
Т.е., ссылочная семантика нужна только для узла.
Так для чего ж тогда ImmutableSortedSet<> объявлен ссылочным типом?
А, ну да, ну да...
— из-за встроенного дефолтного конструктора value-типов, который хоть уже и можно переопределить, но он вызывается не всегда.
Пусть в своём коде я могу обложиться Debug.Assert() и требовать, чтобы был вызван недефолтный конструктор или статический метод-фабрика, но в библиотеке платфрменного уровня таких дыр быть не должно, она должна быть защищена от дурака.
Вот тебе еще один плюсик плюсам — там у меня вопрос не стоит, бо описанный мною дефотный конструктор будет вызван явно в любом случае, когда не вызван конструктор с аргументами.
S>Ваш схематично набросанный подход придётся переписать, т.к. выбранные вами сигнатуры даже не позволяют создать эту копию однократно.
Позволяют что угодно, хосподя.
Как напишешь — так и будет.
Мой схематичный подход через "обертки" позволяет гарантировать иммутабельность для изначально описанных мутабельных типов.
Например, узел Node может быть описан мутабельным, но если мы создаём эти узлы внутри реализации и помещаем в константную ссылку/указатель, то тип становится readonly.
Т.е., реализация builder-а не требует дополнительных флагов, типа frozen (как в дотнетной реализации Immutable-узлов, и это почему появилсь отдельные read-only Frozen типы, где не требуется управлять еще и этими флагами). Достаточно по окончании построения присвоить граф константной ссылке/указателю (как говорил с самого начала).
В вашем подопечном-защищаемом дотнетном Immutable совсем всё смешно — набили дерево мильоном узлов в билдере, а потом сказали ему Freeze() — и оно пошло честной стековой рекурсией обходить дерево для установки флага.
"Не об этом я мечтала, когда замуж выходила..." (С) ))
V>>Для случая активного изменения данных я выберу ссылочную семантику, для случая frozen-данных выберу семантику по-значению, разумеется.
S>Просто при передаче вашего ImmutableValue() по значению, будет создаваться deep-копия вложенных в него данных. Со стоимостью O(N).
Deep-копия автоматом только для плоской памяти.
По указателю если — это надо расписывать ручками.
Если используется интрузивный счётчик ссылок и иммутабельность, то копирование вызовет лишь +1 у счётчика cсылок корня:
Рыба такая:
template<typename T>
class SharedHolder {
intrusive_ptr<T> ptr_;
public:
T * get() {
return ptr_.get();
}
const T * get() const {
return ptr_.get();
}
};
template<typename T>
class Node;
template<typename T>
using NodeRef = SharedHolder<Node<T>>;
template<typename T>
class Node {
T value;
NodeRef<T> left_, right_;
public:
Node * left() { return left_.get(); }
const Node * left() const { return left_.get(); }
Node * right() { return right_.get(); }
const Node * right() const { return right_.get(); }
};
template<typename T>
class AvlTreeSet {
NodeRef<T> root_;
public:
typedef T value_type;
void insert(const T & value) {
root_ = mutable_merge(root_, value);
}
AvlTreeSet<T> insert(const T & value) const {
return immutable_merge(root_, value);
}
};
template<typename TSet>
class ImmutableSet {
const TSet set_;
explicit ImmutableSet(TSet && s) : set_(s) {}
public:
ImmutableSet() {}
const TSet & set() const {
return set_;
}
ImmutableSet<TSet> operator|(const typename TSet::value_type & b) const {
return ImmutableSet<TSet>(move(set_.insert(b)));
}
ImmutableSet<TSet> operator|(const ImmutableSet<TSet> & b) const {
TSet tmp = set_;
b.for_each([&](const auto & value) {
tmp = static_cast<const TSet &>(tmp).insert(value);
});
return ImmutableSet<TSet>(move(tmp));
}
};
int main()
{
using Set = ImmutableSet<AvlTreeSet<int>>;
auto s1 = Set() | 1 | 2 | 3;
return 0;
}V>>Я рядом давал тебе ссылку на исходники SmallFrozenSet.
S>Да при чём тут ссылка? Вы просто опять уходите в решения для каких-то экзотических частных случаев.
Наоборот, говорил, что в плюсах есть возможность писать более обще, потому что у меня есть возможность распространять гарантии.
Обрати внимание на сигнатуры парами:
T * get() {
const T * get() const {
Node * left() {
const Node * left() const {
Node * right() {
const Node * right() const {По константной ссылке-указателю может быть вызвана только const-this версия метода, соответственно, у меня одно описание на все случаи жизни.
См. тут:
void insert(const T & value) {
root_ = mutable_merge(root_, value);
}
AvlTreeSet<T> insert(const T & value) const {
return immutable_merge(root_, value);
}Константное поле у меня лишь в декораторе ImmutableSet<TSet>, далее констрантность распространяется.
Что я могу себе позволить, чтобы мои абстракции не протекли:
— дефолтный конструктор ImmutableSet (в примере auto empty = ImmutableSet<AvlTreeSet<int>>())
— конструктор от значений или других ImmutableSet.
Чего нельзя:
— публичные конструкторы от мутабельных типов.
Ф-ии навроде mutable_merge или immetable_merge могут быть внешними. При непосредственном вызове этих ф-ий над иммутабельными типами ничего гарантировать нельзя, разумеется.
Наверно, тебя именно это беспокоило несколько лет назад и в этом обсуждении снова.
Я же тебе говорил, что я могу распространить гарантии так, что они не протекут.
На самый худой конец их можно распространить на самое дно — поля целевых типов. ))
Просто никто так не делает обычно.
А как делают — показал.
Т.е. распространяют гарантии константности и создают невозможность протечки абстракций через доступное публичное АПИ.
Чего нельзя:
— публичные конструкторы от мутабельных типов.
В целях эффективности класс ImmutableSet может содержать вложенный класс Builder, который манипулирует мутабельным TSet на стадии напихивания данных, и в какой-то момент передаёт владение набором данных в иммутабельный ImmutableSet. Т.е. классу Builder будет доступен приватный конструктор декоратора ImmutableSet, а тебе нет. И что забавно, всего одна реализация ImmutableSet и Builder на все реализации set с нужными наборами методов.
V>>Не обошлись, там точно такая же магия для структур в ключевом слове readonly.
S>Я говорю конкретно про иммутабельность. Много ли readonly вы видите в System.Collections.Immutable?
Я там вообще мало чего интересного вижу и вряд ли когда буду пользоваться этой неэффективной реализацией.
В упор не понимаю, чем тебя заинтересовало это убожество.
Это ж для хомячков.
"Чтобы было!" (С)
V>>А было бы неплохо и для интерфейсов-классов, где IImuttableList мог быть объявлен как readonly interface IImuttableList, соответственно, все реализующие его классы должны были бы быть readonly IImuttableList : ImuttableList {...}
S>Это — бесполезная идея.
"Это потому что ты не понимаешь иммутабельности" (С)
Для структур оказалась крайне полезной, потому что иначе возникал диссонанс с readonly-полями value-типов.
Пришлось ввести readonly-методы, что есть полный аналог const-this методов в С++.
S>Она одновременно не даст никаких гарантий иммутабельности
В плюсах я распространяю константность в зависимости от константной или нет сигнатуры метода.
В дотнете распространять константность можно было бы автоматом для ссылочных readonly типов, как оно есть для readonly структур.
Т.е. такие типы могли бы содержать лишь readonly структуры и readonly классы/интерфейсы как поля.
S>потому, что внутри реализации ImmutableList — ссылка, которая, в том числе, может быть и на mutable данные
Хосподя, ну так за этим и предлагается, иначе смысла не будет.
S>и помешает некоторым сценариям, где иммутабл-объект изменяется в процессе конструирования.
В конструкторе поля можно изменять многократно, это не проблема.
А утекание абстракций контроллировать компилятором/верификатором, чтобы он запрещал изменение полей после того как из конструктора утёк this (будучи переданным некоему аргументу, допустим, для регистрации созданного объекта где-то там).
В этой схеме невозможно создать циклические ссылки объектов друг на друга, как их невозможно создать в ФП, но никто не жалуется.
Если уж требуются наработки иммутабельности из ФП — то берите их готовые.
V>>Но ты просил гарантии, поэтому я и продемонстрировал ср-ва для выражения гарантий.
S>
Повторюсь: гарантии в продемонстрированном вами подходе никак не зависят от применения ключевого слова const. -1
Рассуждая таким образом можно договориться до того, что и язык Ассемблера даёт такие же гарантии.
Конечно, С++ даёт несравнимо больше гарантий в плане проектирования иммутабельных типов.
Тебе надо просто взять однажды компилятор и чуть поупражняться в проектировании иммутабельных иерархий в плюсах, чтобы ты понял о чём речь.
Сколько раз компилятор подсказывает о константности, т.е. не пропускает компиляции при нарушении контракта — это тебе не передать.
В случае же подхода Immutable из дотнета — это только тестами корректность проверять и то, плохо понятно как именно, бо приватные кишки классов не проверишь.
Остается верить на слово, бгг...
По отношению к иммутабельности дотнет находится в сравнении с плюсами примерно там же, где скриптовые нетипизированные языки находятся в сравнении с языками со строгой статической типизацией.
Говорить "это одно и то же" — сверкать ярчайшим нубством, сорри.
Хоть бы посмотрел на readony ref, scope и readonly методы структур в дотнете.
Похоже, ты со всем этим еще не разбирался, но мнение имеешь.
S>Если вы его уберёте, ImmutableValue<> останется ровно на столько же иммутабельным, как и был.
Это из-за необычно сильно ограниченного твоего мышления, через которое я уже устал продираться.
Как тебе недавно введенные управляемые ссылки как поля ref-структур?
Я об этом говорил еще примерно в 2005-м, но некоторые столь же узко мыслящие даже не понимали — а зачем?
Ты хоть понимаешь — зачем?
И почему это стало возможно только с введением readonly ref?
Я так думаю, что ты малость отстал от последних версий платформы, с тобой реально сложно разговаривать, хоть ты себя и позиционируешь как спец по дотнету. ))
V>>Пусть по-мелочам больше думает машина, чем программист.
S>Непонятно, что вы имеете в виду. Я всё ещё не вижу сценария, который вы предотвращаете при помощи этого ключевого слова.
Да пофик.
Первый раз сказал "не вижу" — объяснили.
Если и после этого "не вижу" — списали на берег.
V>>Хорошо, что согласился хоть с чем-то. ))
V>>Проблематика заданного именно тобой обсуждения как раз в интерфейсах — ты хотел писать обобщённые алгоритмы в условиях гарантий.
S>Разве? Может, я что-то подзабыл. Можно указать, где именно я настаивал на интерфейсах?
Ты говорил, дословно, "как мне знать, что тип иммутабельный"?
Разночтений быть не может, ты говорил о неизвестном потенциальном типе для своих алгоримов, соответственно, речь должна были идти об абстракциях.
В дотнете абстракции живут на интерфейсах и на ограничениях ими генериков.
V>>Оно и так в реальной жизни отродясь иммутабельно для State и до введения готовых Immutable-реализаций.
S>"Оно" — это кто?
Это объект-состояние ДКА для автомата.
V>>В общем, будет отличаться тем, бо абстракция ImmutableMapWrapper бесплатна, а обёрнут может быть не только конкретный std::map.
V>>Ну и, из-за наличия частичного определения шаблонов, может быть обёрнут даже тип, который не совместим по публичному интерфейсу в std::map.
S>Как только вы обернёте не только конкретный sdd::map, появится и возможность "хулиганить".
Не появится, я выше дал полный список обеспечения гарантий.
Просто, блин, ты поразительно недогадлив, с ложечки кормить приходится.
V>>А как тебе arg... — семантика?
S>У меня со времён params в С# такой синтаксис удивления не вызывает.
В дотнете это массив в куче, днамическое итерирование по params в цикле, в плюсах статика времени компиляции, линейная раскрутка кода.
В дотнете в params могут быть одинаковые типы (или наследники для случая ссылочных типов), в плюсах произвольные, допустимые обработчиками.
S>А семантика, на первый взгляд, слабже — не так удобно извлекать коллекцию
При надобности оно рассматривается как initializer_list.Просто, блин, ты поразительно недогадлив, с ложечки кормить приходится.
Я вообще удивляюсь, как ты дожил до своих лет и тебя до сих пор не прибили за аксиматическую позицию "все вокруг дураки", когда реальность подтверждает обратное? ))
S>и принудительная замена итерации рекурсией не выглядит шибко привлекательно.
ЧТД, вот тебе пример того, что дураков вовсе не вокруг искать надо.
При вычислении вложенных вызовов ф-ий для arg... получается линейный код вычисления аргументов ф-ий от самых глубоких к внешним.
Это абсолютно линейный код верхнего уровня, последовательность call.
Итерация там только в процессе работы компилятора.
А как бы оно вообще могло работать, неужели даже не попытался представить?
В любом случае, я тебе показал во что реально превращается тот код.
S>Вот если бы ещё шарп починили, разрешив приписывать params к параметру любого типа, который реализован массивом. В частности, IEnumerable<T> и IList<T>.
То сделали бы эти случаи неразличимыми/конфликтующими, в то время как м/у ними сильное различие с т.з. эффективности.
В кишках дотнета голые массивы весьма входу и популярны.
Где приходится бороться за эффективность на юзверском уровне — тоже.