Здравствуйте, vdimas, Вы писали:
V>Первоклассные сущности имели неизвестную структуру, именно поэтому вопросы передачи и возврата таких значений тогдашние компиляторы были вынуждены брать на себя. V>"Ортогональность" появилась позже, по мере развития ЯВУ, но тогда и определение надо было доработать.
Какая неизвестная структура у int? А если б была известная, то компилятор не брал бы на себя и программист ручками электроны двигал? Или как ты себе это представляешь?
А сейчас структуры в Си можно передавать по значению? Они перестали быть известными?
Здравствуйте, vdimas, Вы писали: V>Вдогонку, у дотнета уже были интерфейсы, описывающие АПИ иммутабельных коллекций, навроде IReadOnlySet и т.д.
Вы по-прежнему не понимаете смысл иммутабельности. IReadOnlySet, IReadOnlyList и прочие никакого отношения к иммутабельности не имеют. V>Выбранное название неймспейса сбивает с толку, бо там речь не об иммутабельности как таковой, а об эффективных способах порожения read-only коллекций. ))
Нет. Речь там именно об иммутабельности, а не о read-only.
V>Например, неэффективной будет реализация на основе некоего FrozenSet, т.к. потребует копирования коллекций целиком при порождении новых коллекций, т.е. "изменения" их в ФП-стиле.
А то.
V>Наверно, стоило этот неймспейс так и назвать FpStyle. ))
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, T4r4sB, Вы писали: TB>А объект и сообщение — это получается по факту просто вызов метода?
Да, это — самая эффективная реализация ожидания обработки сообщения, на которое нам нужен синхронный ответ.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, Sinclair, Вы писали: S>> ImmutableValue(T && value) : value_(value) {} S>>Хм. А там точно будет ссылка на оригинал, а не дубликат?
V>Там будет и не ссылка, и не дубликат.
V>Тогда мы храним ссылку, а не значение, т.е. теряем контроль над другими потенциальными ссылками на это значение. V>Я ж не просто так храню именно значение. ))
S>>Покажите мне пример кода, в котором вы изготавливаете из мутабельного объекта иммутабельный, и продемонстрируйте, что вы после этого не можете этот иммутабельный изменить.
V>
V>template<typename T>
V>class ImmutableValue {
V> const T value_;
V>public:
V> ImmutableValue(T && value) : value_(move(value)) {}
V> const T & value() const { return value_; }
V>};
V>int main()
V>{
V> using namespace std;
V> typedef ImmutableValue<string> istring;
V> string s1 = "it is a long enough string";
V> istring s2 = move(s1);
V> assert(s2.value() == "it is a long enough string");
V> assert(s1 == "");
V> s1 = "42";
V> assert(s2.value() == "it is a long enough string");
V> assert(s1 == "42");
V> return 0;
V>}
V>
Понятно. Вижу, вы исправили ошибку — теперь у вас в коде 2 move. Исходный код, который вы привели, падал на assert(s1 == "").
V>Здесь "it is a long enough string/0" выделяется в динамической памяти, затем через std::move перемещается в иммутабельную строку s2, при этом строка s1 теряет своё содержимое.
V>Далее мы изменяем значение строки s1, в то время как зачение s2 не изменяется. V>Изменить законными способами значение переменной s2 нельзя;
Осталось понять, что изменится, если мы поубираем ключевые слова const из вашего шаблонного кода. Перестанет ли isting быть иммутабельным?
V>
V> istring s3 = s2; // создание копии строки
V> assert(s3.value() == "it is a long enough string");
V> assert(s2.value().data() != s3.value().data()); // именно копии, по разным адресам
V> s2 = s3; // ошибка компиляции: operator=(const ImmutableValue<std::string> &) удалён
V>
V>Последняя строка тоже важна для понимания — получив однажды ссылку на ImmutableValue<std::string> я могу быть уверен, что переменную не затрут.
Вот этот фрагмент непонятен. Зачем вы производите копии иммутабельного объекта? Он же гарантированно иммутабельный, это как раз и даёт ссылочную прозрачность.
V>>>Далее в своём коде используешь шаблонный ImmutableMap. S>>Вот прямо так сразу использовать шаблонный ImmutableMap не получится. Вы, как водится, привели тот самый фрагмент кода, который был очевиден и без обсуждения. S>>Как вы реализуете метод add(const TKey & key, const TValue & value)? V>Никак. V>Для иммутабельных типов это будут внешние ф-ии и операторы, разумеется. V>Просто в дотнете сплошные методы. ))
Методы гораздо удобнее выстраивать в цепочку. Запись вида list.add(1).add(2).add(42) читать гораздо комфортнее, чем add(add(add(list, 1), 2), 42))).
Но это дело вкуса. Покажите, как вы будете реализовывать внешний метод add.
V>Можно.
V>Зря сомневаешься.
Ну, не с первого раза, но, вроде бы, удалось. Правда, ваш тип зачем-то создаёт избыточные копии на ровном месте, ну это ладно. Наверное, можно научить людей избегать передачи по значению, хоть это и неудобно.
V>Это смотря, какова природа/структура и объемы данных. V>copy-on-write для небольших объемов линейно-расположенных в памяти данных работает лучше иммутабельного графа.
Началось виляние. Узнаю коллегу вдимаса. V>Но это мы уже ответвились в другую область — в область алгоритмов и структур данных, а они зависят от конкретных задач (или классов задач, бо практически все задачи уже известны, бгг).
Конкретная задача хорошо известна — реализовать иммутабельные структуры так, чтобы они были а) надёжными, б) эффективными.
V>В моём случае не придётся для сценария, скажем, для которого разработали FrozenDictionary в 8-м дотнете.
Да, для этого экзотического сценария можно сделать реализацию эффективнее, чем ImmutableDictionary. Обратите внимание на две вещи:
1. Ваша реализация оказалась уместна только для экзотического частного случая; для более общего частного случая она непригодна.
2. В дотнете как-то обошлись без магии ключевого слова const. Выходит, любые виды неизменности реализуемы и без него. Сюрприз-сюрприз!
V>И странно, что оно не было сделано еще лет 20 назад, когда тема иммутабельных деревьев была модной на слуху.
Сначала удовлетворяются потребности 90% аудитории. Потом — 9%. Потом — 0.9%. Вот теперь дошла очередь и до 0.1%.
V>В C# ключевое слово const у мемберов объявляет аналог статического readonly поля объекта.
V>Тебе нужны были железобетонные гарантии — ну и вот.
Так гарантии по-прежнему обеспечены дизайном класса, а не ключевым словом const.
V>Если же речь об алгоритмах и структурах данных — ну так пиши эти структуры и алгоритмы над ними. V>Весь механизм для этого есть.
V>Это именно реализация некоторых иммутабельных алгоритмов над некоторыми иммутабельными структурами данных. V>Collections.Immutable не приносит в язык иммутабельность как таковую, эта либа лишь реализует некоторые структуры и алгоритмы, доказавшие свою полезность в ФП.
По-видимому, вы так и не понимаете, что такое иммутабельность как таковая.
V>Я могу нарушать гарантии интерфейсов, например, реализовывать тип как мутабельный и возвращать this из методов.
Интерфейсов — да. Классов — нет.
S>>Вот мой метод: S>>
S>>Попробуйте "сломать" его, передав в него мутабельный state.
V>У тебя ошибка, должно быть так:
Нет никакой ошибки. state — immutable, _visited — mutable.
V>И это у тебя оно гарантируется из-за использования конкретного типа ImmutableDictionary<,>, а если сделать так: V>
V>то прощай гарантии, можно начинать хулиганить. ))
Ну, так поэтому я и не стал писать так, чтобы вы начинали хулиганить.
V>В плюсах, напротив, можно определить некий концепт ImmutableMap и юзать так: V>
V>Где концепт ImmutableMap требует, например, быть инстансом шаблонного типа ImmutableMapWrapper, которому в кач-ве аргумента подали тип, удовлетворяющий публичному интерфейсу std::map.
И чем это будет отличаться от конкретного ImmutableMapWrapper<std::map>?
V>Что касается ключевой фишки иммутабельных списков/графов, т.е. что касается шаренья узлов между инстансами, этого можно достичь или через счётчики ссылок, или через техники навроде региональной памяти, чтобы не возиться со счётчиками.
Эффективность упадёт на дно.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>Методы гораздо удобнее выстраивать в цепочку. Запись вида list.add(1).add(2).add(42) читать гораздо комфортнее, чем add(add(add(list, 1), 2), 42))). S>Но это дело вкуса. Покажите, как вы будете реализовывать внешний метод add.
Вариант №1:
let add x xs = List.append xs [x]
let () =
let xs = [] in
let xs = xs |> add 1 |> add 2 |> add 42 in
printfn "%A\n" xs
=>
Вариант №2:
let (++) xs x = List.append xs [x]
let () =
let xs = [9000] in
let xs = xs ++ 1 ++ 2 ++ 42 in
printfn "%A\n" xs
Здравствуйте, Sinclair, Вы писали:
V>>Вдогонку, у дотнета уже были интерфейсы, описывающие АПИ иммутабельных коллекций, навроде IReadOnlySet и т.д. S>Вы по-прежнему не понимаете смысл иммутабельности.
Всякий раз забавно видеть, как ты пытаешься примитивщину выдавать за откровения.
Лучше бы ты не маялся этой хернёй, а говорил тезисами, которые можно подтвердить или опровергнуть.
S>IReadOnlySet, IReadOnlyList и прочие никакого отношения к иммутабельности не имеют.
Имеют такое же отношение, как и IImutableList и Ко.
Это высказывание — вполне себе тезис.
V>>Выбранное название неймспейса сбивает с толку, бо там речь не об иммутабельности как таковой, а об эффективных способах порожения read-only коллекций. )) S>Нет. Речь там именно об иммутабельности, а не о read-only.
Я на это уже отвечал — там речь лишь о некоторых алгоритмах над некоторыми иммутабельныим структурами данных.
Есть несколько конекретных типов, помеченные как sealed, которые согласно дизайну являются иммутабельными.
А система реализованных интерфейсов — нет, это просто "вербальные соглашения".
Никаких ср-в обечпечения иммутабельности для других аналогичных алгоритмов и структур данных поверх предоставленных интерфейсов этот неймспейс не содержит.
Например, интерфейс IImutableDictionary может быть реализован не только на красно-чёрных деревьях.
И может быть реализован не только в иммутабельном виде.
V>>Например, неэффективной будет реализация на основе некоего FrozenSet, т.к. потребует копирования коллекций целиком при порождении новых коллекций, т.е. "изменения" их в ФП-стиле. S>А то.
Что, однако, верно только для сценариев, где данные активно изменятся.
FrozenXXX были созданы для других сценариев — где данные читаются намного чаще, чем изменяются.
Для сравнения, есть структура-обертка ImmutableArray, в нём данные при изменении каждый раз копируются.
Собсно, до введения такого типа в стандартные либы, аналогичная обёртка была, наверно, в каждой конторе, которые разрабатывают под дотнет.
По смыслу поведение этого типа больше просится во Frozen-неймспес, бо та же стратегия... но уже реализовали ранее в Immutable, бгг...
У нас в core-библиотеке эта обертка называется ReadOnlyArray. В Unity тоже и вообще ты можешь найти многие сотни аналогичных реализаций в открытых проектах на дотнете.
Еще пара замечаний относительно FrozenXXX:
нет никаких требований копирования при реализации, ты можешь рядом делать свои реализации со своей стратегией;
методы-расширения, типа ToFrozenSet(), берут на входе неиммутабельные последовательности (или множества) и создают копии данных, т.е. в точности как в вслучае ToImmutableSet();
ImmutableSet<T> — это абстрактный класс, есть несколько его реализаций, все они иммутабельны by design;
идея Frozen-коллекций — это расположить данные в памяти таким образом, чтобы они на современной аппаратуре были эффективны для чтения.
Например, реализация SmallFrozenSet хранит данные в линейном массиве и ищет их линейным поиском, а хеш-реализации имеют более эффективное представление корзин в памяти на тру-иммутабельных структурах Bucket { int StartIndex; int EndIndex; };
мы именно с тобой обсуждали N-арные деревья, т.е. ты должен хорошо понимать, что нет никакого запрета строить иммутабельные деревья из таких структур данных, сбалансированных с точностью от 1 до некоего выбранного max N узлов; т.е., при создании нового корня дерева в общем случае будут создаваться копии меньшего кол-ва узлов, чем для двоичных узлов, но в каждом узле будет больше элементов. До какого-то N это выгодная стратегия на современном оборудовании, потому что деревянная в памяти структура в общем случае обладает худшей локальностью, т.е. синтетические тесты, где в памяти только содаются узлы тестируемого дерева, могут сильно врать насчёт его эффективности.
N-арное дерево в этом смысле — это обеспеченный ручками некий фактор локальности данных. В идеале, конечно, было бы удобно иметь ср-ва располагать такие "корзины" по границам кеш-линееек проца, но дотнету такие радости недоступны. Зато мы в нейтиве пользуем этот приём аж в путь и он даёт заметный профит.
В любом случае, рассуждать об иммутабельности или нет немспейса Frozen было заведомо глупо — типы данных там точно так же иммутабельны by design, как и в неймспейсе Immutable.
Это просто "еще одна реализации иммутабельности" для еще одного популярного сценария.
Сравнить с тем же AST, где количество операций чтения обычно примерно равно кол-ву операций записи.
Разумеется, для сценария построения и обработки AST выгодней брать иммутабельные графы, как оно есть в AST-графе того же Рослина — там AST описано на основе иммутабельных типов.
Жаль, на момент разработки Рослина еще не было типов ImmutableList или ImmutableStack, поверх которых легко строить иммутабельные лиспоподобные графы, бгг.
Однако, если по однажды построенной иммутабельной AST многократно работает некий "вычислитель" (допустим, стековая машинка), то выгодней представить это AST в линейном виде в памяти, собсно, как оно и есть в реализации Frozen-коллекций.
Здравствуйте, korvin_, Вы писали:
_>Вариант №1:
_>
_>let add x xs = List.append xs [x]
_>let () =
_> let xs = [] in
_> let xs = xs |> add 1 |> add 2 |> add 42 in
_> printfn "%A\n" xs
_>
_>=>
_>Вариант №2:
_>
_>let (++) xs x = List.append xs [x]
_>let () =
_> let xs = [9000] in
_> let xs = xs ++ 1 ++ 2 ++ 42 in
_> printfn "%A\n" xs
_>
_>=>
_>
_>[1; 2; 42]
_>
Это какой язык? Сходу непонятно. Тут-то речь идёт о C++ и его волшебной const-магии.
Когда у вас в язык встроен иммутабельный список с заранее оптимизированными add, то вопросов нет. Интересно становится, когда он не встроен.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, vdimas, Вы писали: V>Всякий раз забавно видеть, как ты пытаешься примитивщину выдавать за откровения. V>Лучше бы ты не маялся этой хернёй, а говорил тезисами, которые можно подтвердить или опровергнуть.
S>>IReadOnlySet, IReadOnlyList и прочие никакого отношения к иммутабельности не имеют.
V>Имеют такое же отношение, как и IImutableList и Ко. V>Это высказывание — вполне себе тезис.
Ну да, совершенно верно. Это — ошибочный тезис.
Иммутабельность означает не просто отсутствие модифицирующих операций, но и наличие операций по построению новых значений на основе существующих.
V>Я на это уже отвечал — там речь лишь о некоторых алгоритмах над некоторыми иммутабельныим структурами данных.
Ткните пальцем хотя бы в один "алгоритм" в этом неймспейсе.
V>Есть несколько конекретных типов, помеченные как sealed, которые согласно дизайну являются иммутабельными.
А то. V>А система реализованных интерфейсов — нет, это просто "вербальные соглашения".
Всё верно. Причём достаточно внятные вербальные соглашения. В принципе, любой интерфейс, помимо названий методов, оперирует некоторыми вербальным соглашениями. Нарушение которых компилятором не карается, но может привести к неожиданному поведению (в том числе и к багам).
V>Например, интерфейс IImutableDictionary может быть реализован не только на красно-чёрных деревьях.
А то. У нас с одногруппником в качестве курсовой работы была реализация IImmutableList и IImmutableDictionary на другой основе. V>И может быть реализован не только в иммутабельном виде.
Может, но это всё сломает. А вот в read-only виде его реализовать эффективно очень затруднительно, если вообще возможно.
V>Что, однако, верно только для сценариев, где данные активно изменятся. V>FrozenXXX были созданы для других сценариев — где данные читаются намного чаще, чем изменяются.
Да, для специального узкого случая.
Вы готовы навскидку сказать, насколько они эффективнее Immutable-аналогов?
V>* мы именно с тобой обсуждали N-арные деревья, т.е. ты должен хорошо понимать, что нет никакого запрета строить иммутабельные деревья из таких структур данных, сбалансированных с точностью от 1 до некоего выбранного max N узлов; т.е., при создании нового корня дерева в общем случае будут создаваться копии меньшего кол-ва узлов, чем для двоичных узлов, но в каждом узле будет больше элементов. До какого-то N это выгодная стратегия на современном оборудовании, потому что деревянная в памяти структура в общем случае обладает худшей локальностью, т.е. синтетические тесты, где в памяти только содаются узлы тестируемого дерева, могут сильно врать насчёт его эффективности.
Мы не просто это обсуждали. Я такую структуру реализовывал самостоятельно.
V>N-арное дерево в этом смысле — это обеспеченный ручками некий фактор локальности данных. В идеале, конечно, было бы удобно иметь ср-ва располагать такие "корзины" по границам кеш-линееек проца, но дотнету такие радости недоступны.
Прекрасно доступны, надо просто уметь их готовить.
V>В любом случае, рассуждать об иммутабельности или нет немспейса Frozen было заведомо глупо — типы данных там точно так же иммутабельны by design, как и в неймспейсе Immutable.
Тогда зачем вы притащили его обсуждение в эту ветку?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Понятно. Вижу, вы исправили ошибку — теперь у вас в коде 2 move. Исходный код, который вы привели, падал на assert(s1 == "").
Ты просил показать схематично — я прямо тут и набросал, без проверки. ))
Проверил, когда ты стал сомневаться, бывает.
В своё оправдание этой ужасной ошибки могу сказать лишь, что по сигнатуре ImmutableValue(T && value) должен был быть понятен замысел, т.к. rvalue && используется в плюсах для семантики перемещения.
V>>Изменить законными способами значение переменной s2 нельзя; S>Осталось понять, что изменится, если мы поубираем ключевые слова const из вашего шаблонного кода. Перестанет ли isting быть иммутабельным?
На очевидные вопросы я отвечал заранее:
Ключевое слово const даст гарантии сильнее "вербальных соглашений", которые в реальной жизни не обеспечиваются ничем, кроме добросовестности программиста. ))
Даже правильно спроектированный под конкретную задачу тип затем может быть поломан из-за невнимательности, при добавлении мутабельных методов.
С одной стороны, это не более чем эксплуатация выразительных ср-в языка, что мы гарантии прописываем через синтаксис (а не комментарии) и контроллируем их через систему типов.
С другой стороны, компилятор позволяет себе больше оптимизаций над const-данными.
Уже два профита.
(в дотнете вокруг readonly аналогично)
V>>Последняя строка тоже важна для понимания — получив однажды ссылку на ImmutableValue<std::string> я могу быть уверен, что переменную не затрут. S>Вот этот фрагмент непонятен. Зачем вы производите копии иммутабельного объекта? Он же гарантированно иммутабельный, это как раз и даёт ссылочную прозрачность.
На это тоже уже отвечал:
Что касается ключевой фишки иммутабельных списков/графов, т.е. что касается шаренья узлов между инстансами, этого можно достичь или через счётчики ссылок, или через техники навроде региональной памяти, чтобы не возиться со счётчиками.
Семантика типов-классов в С++ изначально value-type, ссылочная семантика добавляется явно при надобности.
Создание копий иммутабельных данных может быть полезным для региональной памяти, когда необходимо сохранить данные в своём регионе.
S>Эффективность упадёт на дно.
Счётчики обычно дергаются при перестроении, допустим, графа на иммутабельных узлах, поэтому доп. накладные расходы не настолько уж велики, чтобы говорить о дне, бо перестраивается только часть узлов.
А региональная память — это когда некая подсистема сама распределяет память на низком уровне, обращаясь к операционке только за относительно большими страницами памяти.
В таких распределителях память обычно выделяется как grow-only, простым смещением текущего указателя свободной области, т.е. выделение происходит с эффективностью дотнета.
А освобождается затем и вовсе бесплатно, целиком одной операцией возврата операционке страницы (страниц).
В целом оно на порядки эффективнее, чем в дотнете.
В наших проектах мы активно используем такой подход, благо аллокатор пишется один раз и далее где угодно используется.
V>>Для иммутабельных типов это будут внешние ф-ии и операторы, разумеется. S>Методы гораздо удобнее выстраивать в цепочку. Запись вида list.add(1).add(2).add(42) читать гораздо комфортнее, чем add(add(add(list, 1), 2), 42))). S>Но это дело вкуса. Покажите, как вы будете реализовывать внешний метод add.
Я бы назвал его merge, и добавил бы сигнатуры добавления не только отдельных значений, но и готовых set.
Что касается синтаксиса многократного добавления за раз — тоже не вижу проблем в условиях Arg... ср-в языка С++.
Внешне это может выглядеть так:
auto newSet = merge(oldSet, 1, 2, 3, anotherSet1, anotherSet2);
с произвольным кол-вом аргументов, бо это всё статика — компилятор видит кол-во аргументов, а шаблонный код опять же статически итерируется по аргументам, порождая линейный код длинной в кол-во аргументов, где каждая псевдо-итерация соответствует своему типу аргумента. (на недопустимых типах аргумента компиляция сломается, ес-но).
При вызове merge(oldSet, 1, 2, 3, anotherSet1, anotherSet2) код раскроется в merge(merge(merge(merge(merge(merge(oldSet, 1), 2), 3), anotherSet1), anotherSet2))
merge — потому что такова природа сущности "множество". ))
Уникальность и всё в таком роде.
Для multiset чуть другая семантика, без уникальности, но merge тоже подходит по смыслу.
S>Правда, ваш тип зачем-то создаёт избыточные копии на ровном месте, ну это ладно. Наверное, можно научить людей избегать передачи по значению, хоть это и неудобно.
Зачем учить?
Это просто данная сверху бесплатная функциональность, бо компилятор порождает конструкторы копирования и перемещения автоматически (хотя их и можно переопределить).
А семантику ты выбираешь уже исходя из сценариев и природы данных.
Для случая активного изменения данных я выберу ссылочную семантику, для случая frozen-данных выберу семантику по-значению, разумеется.
Т.е., св-ва языка позволяют орудовать подробностями реализации гибче, без необходимости прибивать гвоздями функциональность к неймспейсам и алгоритмам.
Например, некий HashNode изначально описывается как value-type и затем можно быть размещён в массиве по значению или по указателю, смотря какой алгоритм/стратегия его использует.
V>>copy-on-write для небольших объемов линейно-расположенных в памяти данных работает лучше иммутабельного графа. S>Началось виляние. Узнаю коллегу вдимаса.
Чего? ))
Я рядом давал тебе ссылку на исходники SmallFrozenSet.
Это ж известная фишка — ортогональность семантики и подробности реализации.
Для различных сценариев работы с данными одна и та же семантика может быть реализована различными стратегиями.
V>>Но это мы уже ответвились в другую область — в область алгоритмов и структур данных, а они зависят от конкретных задач (или классов задач, бо практически все задачи уже известны, бгг). S>Конкретная задача хорошо известна — реализовать иммутабельные структуры так, чтобы они были а) надёжными, б) эффективными.
Да не бывает никакой абстрактной эффективности.
Бывает эффективность в конкретной задаче (на конкретных данных).
Наша задача как программиста — распознать сценарий и выбрать наиболее эффективный способ реализации этого сценария.
Ну и, не забыть провести сравнительные тестирования. ))
V>>В моём случае не придётся для сценария, скажем, для которого разработали FrozenDictionary в 8-м дотнете. S>Да, для этого экзотического сценария можно сделать реализацию эффективнее, чем ImmutableDictionary. Обратите внимание на две вещи: S>1. Ваша реализация оказалась уместна только для экзотического частного случая; для более общего частного случая она непригодна.
Я даже не знаю, что отвечать на утверждение, что сценарий, где данные намного чаще читаются, чем пишутся — это экзотический сценарий в сравнении со сценарием, где данные чаще пишутся или читаютсяи пишутся примерно с одинаковым трафиком.
Это ты уже подключаешь сугубо эмоциональные "усилители" в сугубо техническое обсуждение.
И это я еще не начал спорить о том, что в моей практике обычно ровно наоборот — чаще встречаются сценарии, где данные читаются на порядки чаще, чем изменяются.
При чём, во всех областях, в которых работал — что в автоматизации бухучёта, что в цифровом документооборота, что в цифровой телефонии, что в области бирж.
S>2. В дотнете как-то обошлись без магии ключевого слова const.
Не обошлись, там точно такая же магия для структур в ключевом слове readonly.
Но для классов этого модификатора нет, увы.
А было бы неплохо и для интерфейсов-классов, где IImuttableList мог быть объявлен как readonly interface IImuttableList, соответственно, все реализующие его классы должны были бы быть readonly IImuttableList : ImuttableList {...}
S>Выходит, любые виды неизменности реализуемы и без него. Сюрприз-сюрприз!
А точно ли сюрприз? ))
Разве нельзя расписать иммутабельность, скажем, на ассемблере? — конечно можно.
Но ты просил гарантии, поэтому я и продемонстрировал ср-ва для выражения гарантий.
Например, новомодные лямбды в С++ иммутабельны уже по-умолчанию (что позволяет эффективно их инлайнить), но при надобности описать мутабельную лямбду, её надо объявлять с ключевым словом mutable.
V>>И странно, что оно не было сделано еще лет 20 назад, когда тема иммутабельных деревьев была модной на слуху. S>Сначала удовлетворяются потребности 90% аудитории. Потом — 9%. Потом — 0.9%. Вот теперь дошла очередь и до 0.1%.
Да не уверен, если честно, бо 90% всё-равно пользуются тем, что дано изкаробки.
Будь подобные типы изначально в коробке, ими пользовались более 0.1%, просто потому что "оно уже есть".
И многие идущие в поставке библиотеки тоже могли бы пользовать immutable-типы с гораздо большим процентом.
Думаю, твои оценки потенциальной популярности не верны для платформы с GC, бо именно на такой платформе иммутабельность достаточно дешевое удовольствие.
А значит — полезное! ))
V>>Тебе нужны были железобетонные гарантии — ну и вот. S>Так гарантии по-прежнему обеспечены дизайном класса, а не ключевым словом const.
Ключевое слово const ограничивает дизайн класса, т.е. является частью контракта.
Пусть по-мелочам больше думает машина, чем программист.
V>>Collections.Immutable не приносит в язык иммутабельность как таковую, эта либа лишь реализует некоторые структуры и алгоритмы, доказавшие свою полезность в ФП. S>По-видимому, вы так и не понимаете, что такое иммутабельность как таковая.
Чтобы эта фраза не была пустозноством, тебе стоит хотя бы озвучить моё понимание иммутабельности (каким оно тебе кажется) и показать, чем моё понимание отличается от твоего.
По мне — подобные заявления крайне стрёмные, бо иммутабельность — это примитивщина, в сравнении с остальным, чем приходится оперировать в реальной работе.
V>>Я могу нарушать гарантии интерфейсов, например, реализовывать тип как мутабельный и возвращать this из методов. S>Интерфейсов — да. Классов — нет.
Хорошо, что согласился хоть с чем-то. ))
Проблематика заданного именно тобой обсуждения как раз в интерфейсах — ты хотел писать обобщённые алгоритмы в условиях гарантий.
Увы, увы, на дотнете этого пока невозможно.
Но я не утверждаю, что этого будет невозможно и в будущем.
Таки, введения readonly interface и readonly class потребует совсем косметических доработок платформы...
Глядишь, может когда и сделают.
V>>У тебя ошибка, должно быть так: S>Нет никакой ошибки. state — immutable, _visited — mutable.
Тю, неинтересно. ))
Оно и так в реальной жизни отродясь иммутабельно для State и до введения готовых Immutable-реализаций.
Если бы тебе приходилось упражняться в написании лексеров и парсеров (и вообще ДКА), ты бы это знал на уровне мозжечка и так.
V>>И это у тебя оно гарантируется из-за использования конкретного типа ImmutableDictionary<,>, а если сделать так: V>>то прощай гарантии, можно начинать хулиганить. S>Ну, так поэтому я и не стал писать так, чтобы вы начинали хулиганить.
Во-от!
И тем самым наложил ограничение на конкретную реализацию словаря, хотя по семантике не требовалось.
Смотри, как одни компромиссы тянут за собой другие. ))
V>>В плюсах, напротив, можно определить некий концепт ImmutableMap и юзать так: V>>
V>>Где концепт ImmutableMap требует, например, быть инстансом шаблонного типа ImmutableMapWrapper, которому в кач-ве аргумента подали тип, удовлетворяющий публичному интерфейсу std::map. S>И чем это будет отличаться от конкретного ImmutableMapWrapper<std::map>?
Э-э-э... я тут столько распинаюсь...
В общем, будет отличаться тем, бо абстракция ImmutableMapWrapper бесплатна, а обёрнут может быть не только конкретный std::map.
Ну и, из-за наличия частичного определения шаблонов, может быть обёрнут даже тип, который не совместим по публичному интерфейсу в std::map.
В общем, у плюсов достаточно своих плюшек в деле расписания абстракций, это не только "машинно-эффективный" язык, это еще уровень абстрагирования, сравнимый с мощными ФП-языками.
На одной эффективности С++ так не выехал бы, разумеется, бо в период набора им популярности существовали сравнимые по эффективности языки, тот же Object Pascal от Борланд.
А сейчас, при добавлении концептов в плюсы, т.е. с удобными теперь выразительными ср-вами описания ограничений на типы, местами уровень выразительности/абстрагирования получается на уровне Хаскеля.
А как тебе arg... — семантика?
Статически делается то, что в ФП-языках отродясь делалось динамически, хотя потенциальная возможность перевести в статику есть, просто современные машины слишком слабы для выполнения оптимизирующим компилятором редукций ФП-кода "до самого дна".
В этом смысле С++ "приближен к реальности" не только из-за "близости языка к машине", но решения в дизайне языка пляшут от возможностей компиляторов на современной технике.
Компромиссы, компромиссы.. всегда они...
Здравствуйте, Sinclair, Вы писали:
S>Это какой язык? Сходу непонятно.
Какой-нить ML-семейства с возможностью определения операторов.
S>Тут-то речь идёт о C++ и его волшебной const-магии.
Чёт уже в голос...
Сколько я с тобой обсуждал этот несчастный const — ты его то недооцениваешь, то переоцениваешь.
Ключевое слово const — оно не само в себе весчь, в разных синтаксических конструкциях имеет разную семантику.
Соотв., обсуждать можно только конкретные синтаксические конструкции, где допустимо это ключевое слово.
Предлагаю впредь поступать именно так, дабы не испытывать терпение коллег-читателей.
S>Когда у вас в язык встроен иммутабельный список с заранее оптимизированными add, то вопросов нет. Интересно становится, когда он не встроен.
В примере акцент не на списке (и откуда ты взял про "эффективность?"), а на внешний вид выражений.
В плюсах тоже можно описать некий operator|(Set, Set), чтобы выглядело примерно так:
auto newSet = set1 | set2 | value3 | value4;
В дотнете, кстате, тоже.
Я бы еще определил для множеств операторы &, -, ^ (исключающее ИЛИ, симметричная разность), \ (дополнение), * (декартово произведение), <, >, ==, !=, <=, >=.
======================
Ну и, согласно семантики, для multiset я бы выбрал operator+(Set, Set) для выражения операции объединения мн-в вместо логического оператора |.
Здравствуйте, vdimas, Вы писали:
V>На очевидные вопросы я отвечал заранее: V>
V>Ключевое слово const даст гарантии сильнее "вербальных соглашений", которые в реальной жизни не обеспечиваются ничем, кроме добросовестности программиста. ))
V>Даже правильно спроектированный под конкретную задачу тип затем может быть поломан из-за невнимательности, при добавлении мутабельных методов.
Эти слова я читал. Я не понимаю, как вы будете их применять. Что именно помешает "по невнимательности" добавить в ImmutableValue<T> мутирующих методов?
V>С одной стороны, это не более чем эксплуатация выразительных ср-в языка, что мы гарантии прописываем через синтаксис (а не комментарии) и контроллируем их через систему типов. V>Создание копий иммутабельных данных может быть полезным для региональной памяти, когда необходимо сохранить данные в своём регионе.
Это опять какие-то вырожденные экзотические сценарии, нужные примерно никогда.
V>Счётчики обычно дергаются при перестроении, допустим, графа на иммутабельных узлах, поэтому доп. накладные расходы не настолько уж велики, чтобы говорить о дне, бо перестраивается только часть узлов.
Счётчики ссылок, очевидно, дёргаются при любом копировании. Как раз "перестроенные" узлы, которых мало, получают счётчики == 1.
V>А региональная память — это когда некая подсистема сама распределяет память на низком уровне, обращаясь к операционке только за относительно большими страницами памяти. V>В таких распределителях память обычно выделяется как grow-only, простым смещением текущего указателя свободной области, т.е. выделение происходит с эффективностью дотнета. V>А освобождается затем и вовсе бесплатно, целиком одной операцией возврата операционке страницы (страниц).
Это если у вас хватает размера региона на полную работу алгоритма. Заранее сказать, сколько потребуется памяти для хранения мусора, порождаемого компилятором при анализе AST, весьма затруднительно.
А как только вы исчерпали регион — добро пожаловать в честное копирование. V>В целом оно на порядки эффективнее, чем в дотнете.
"В целом" — вряд ли. В частных случаях — может быть. То, что вы называете "региональной памятью", другие люди называют ареной, и это, в целом, аналог поколений в современных GC, только на ручном приводе.
И применяется, как правило, там, где потребности в памяти можно предсказать — либо мало кросс-ссылок между данными. Какой-нибудь видео и аудиопроцессинг с этим будет работать хорошо, а вот компиляторы и прочие трансформации графов — вряд ли.
V>Я бы назвал его merge, и добавил бы сигнатуры добавления не только отдельных значений, но и готовых set.
Да я вас не про сигнатуру спрашиваю. Сигнатура — штука очевидная.
V>merge — потому что такова природа сущности "множество". ))
Вы распишите, что у вас там вместо // .... Поскольку у вас под капотом — заранее неизвестный мутабельный тип, то всё, что вы можете — это состряпать его копию, к которой потом будет применена манипуляция с изменением. Ваш схематично набросанный подход придётся переписать, т.к. выбранные вами сигнатуры даже не позволяют создать эту копию однократно.
V>Для случая активного изменения данных я выберу ссылочную семантику, для случая frozen-данных выберу семантику по-значению, разумеется.
Просто при передаче вашего ImmutableValue() по значению, будет создаваться deep-копия вложенных в него данных. Со стоимостью O(N).
V>Чего? )) V>Я рядом давал тебе ссылку на исходники SmallFrozenSet.
Да при чём тут ссылка? Вы просто опять уходите в решения для каких-то экзотических частных случаев.
V>Ну и, не забыть провести сравнительные тестирования. ))
V>Не обошлись, там точно такая же магия для структур в ключевом слове readonly.
Я говорю конкретно про иммутабельность. Много ли readonly вы видите в System.Collections.Immutable? V>Но для классов этого модификатора нет, увы.
V>А было бы неплохо и для интерфейсов-классов, где IImuttableList мог быть объявлен как readonly interface IImuttableList, соответственно, все реализующие его классы должны были бы быть readonly IImuttableList : ImuttableList {...}
Это — бесполезная идея. Она одновременно не даст никаких гарантий иммутабельности (потому, что внутри реализации ImmutableList — ссылка, которая, в том числе, может быть и на mutable данные),
и помешает некоторым сценариям, где иммутабл-объект изменяется в процессе конструирования.
V>Но ты просил гарантии, поэтому я и продемонстрировал ср-ва для выражения гарантий. Повторюсь: гарантии в продемонстрированном вами подходе никак не зависят от применения ключевого слова const.
Если вы его уберёте, ImmutableValue<> останется ровно на столько же иммутабельным, как и был.
V>Пусть по-мелочам больше думает машина, чем программист.
Непонятно, что вы имеете в виду. Я всё ещё не вижу сценария, который вы предотвращаете при помощи этого ключевого слова.
V>Хорошо, что согласился хоть с чем-то. )) V>Проблематика заданного именно тобой обсуждения как раз в интерфейсах — ты хотел писать обобщённые алгоритмы в условиях гарантий.
Разве? Может, я что-то подзабыл. Можно указать, где именно я настаивал на интерфейсах?
V>Оно и так в реальной жизни отродясь иммутабельно для State и до введения готовых Immutable-реализаций.
"Оно" — это кто?
V>Э-э-э... я тут столько распинаюсь... V>В общем, будет отличаться тем, бо абстракция ImmutableMapWrapper бесплатна, а обёрнут может быть не только конкретный std::map. V>Ну и, из-за наличия частичного определения шаблонов, может быть обёрнут даже тип, который не совместим по публичному интерфейсу в std::map.
Как только вы обернёте не только конкретный sdd::map, появится и возможность "хулиганить".
V>А как тебе arg... — семантика?
У меня со времён params в С# такой синтаксис удивления не вызывает. А семантика, на первый взгляд, слабже — не так удобно извлекать коллекцию, и принудительная замена итерации рекурсией не выглядит шибко привлекательно. Вот если бы ещё шарп починили, разрешив приписывать params к параметру любого типа, который реализован массивом. В частности, IEnumerable<T> и IList<T>.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, Sinclair, Вы писали:
S>>Это какой язык? Сходу непонятно.
V>Какой-нить ML-семейства с возможностью определения операторов.
S>>Тут-то речь идёт о C++ и его волшебной const-магии.
V>Чёт уже в голос...
V>Ключевое слово const — оно не само в себе весчь, в разных синтаксических конструкциях имеет разную семантику. V>Соотв., обсуждать можно только конкретные синтаксические конструкции, где допустимо это ключевое слово. V>Предлагаю впредь поступать именно так, дабы не испытывать терпение коллег-читателей.
Начните с себя. Вот ваша цитата:
Через const в С++ можно выразить абсолютно все сценарии вокруг иммутабельности целиком, но это будет лишь небольшая вершинка айсберга всех сценариев, покрываемых const.
Что ж вы тут обсуждаете не конкретные синтаксические конструкции, а испытываете терпение коллег-читателей?
V>В примере акцент не на списке (и откуда ты взял про "эффективность?"), а на внешний вид выражений.
А зачем мне внешний вид выражений? Внешний вид я и сам какой угодно придумаю.
Вопрос в реализации — будет ли у вас там O(N) копирование на каждый чих, и будет ли добавление K элементов стоить O(N*K).
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>>>IReadOnlySet, IReadOnlyList и прочие никакого отношения к иммутабельности не имеют. V>>Имеют такое же отношение, как и IImutableList и Ко. V>>Это высказывание — вполне себе тезис. S>Ну да, совершенно верно. Это — ошибочный тезис. S>Иммутабельность означает не просто отсутствие модифицирующих операций, но и наличие операций по построению новых значений на основе существующих.
Ну что опять за детсад, мистер коллега с большим стажем?
Речь про встроенные в язык "операции" или библиотечного уровня?
Если второе (а оно второе), то тезис перестаёт быть ошибочным, т.к. есть возможность написать аналогичную функциональность над готовыми read-only-design типами с публичными конструкторами.
(или защищёнными такими конструкторами... облом расписывать всю комбинаторику достаточных условий)
V>>Я на это уже отвечал — там речь лишь о некоторых алгоритмах над некоторыми иммутабельныим структурами данных. S>Ткните пальцем хотя бы в один "алгоритм" в этом неймспейсе.
Например, алгоритм балансировки RB-дерева внутри ImmutableSet и ImmutableDictionary.
Если мне нужны другие алгоритмы, берутся интерфейсы IImmutableSet и IImmutableDictionary, и делаются другие реализации.
Поэтому, абстрактный код над иммутабельными типами данных стоит писать на основе интерфейсов (ограничений в интерфейсах, в т.ч. для value-type реализаций, которые имеют смысл фасада над внутренними ссылочными узлами дерева), а не конкретных классов.
И тут мы возвращаемся в самое начало — для интерфейсов никакой иммутабельной реализации не гарантируется.
Круг замкнулся. ))
V>>Есть несколько конекретных типов, помеченные как sealed, которые согласно дизайну являются иммутабельными. S>А то.
А то, что это убого в рассуждениях — нельзя подменять иммутабельность как таковую на достаточно узкую конкретную реализацию.
А потом имеешь нахальство утверждать, что окружающие "не понимают иммутабельности".
Окружающие всё понимают и потихоньку ржут или недоумевают.
Уверен, каждый первый коллега, дочитавший до сюда, многократно сделает рука-лицо...
Разве что совсем новичкам в отрасли будет полезны наши бодания.
V>>А система реализованных интерфейсов — нет, это просто "вербальные соглашения". S>Всё верно. Причём достаточно внятные вербальные соглашения.
Да хоть какие внятные, они вербальные.
Про вербальные соглашения изначально не имело смысла спорить.
S>В принципе, любой интерфейс, помимо названий методов, оперирует некоторыми вербальным соглашениями. Нарушение которых компилятором не карается, но может привести к неожиданному поведению (в том числе и к багам).
Разумеется.
Но "железная" гарантия иммутабельности даёт возможность одновременного доступа к данным без блокировок, а это уже не семантическая потенциальная ошибка, а вполне себе хардкорная техническая, которая, будучи совершённой, приводит к плохообнаруживаемым достаточно серьёзным проблемам.
V>>Например, интерфейс IImutableDictionary может быть реализован не только на красно-чёрных деревьях. S>А то. У нас с одногруппником в качестве курсовой работы была реализация IImmutableList и IImmutableDictionary на другой основе.
Т.е. понимаешь аргументы оппонента, но всё-равно споришь. ))
V>>И может быть реализован не только в иммутабельном виде. S>Может, но это всё сломает.
При гарантиях read-only не сломает при одновременном доступе.
Тут опять дихотомия необходимости и достаточности.
Read-only — одна из необходимостей для описанного выше.
Еще необходимо совместное владение данными из разных потоков с контролем времени жизи.
Immutable+GC — достаточность, автоматом покрывает необходимости read-only + совместного владения в конкретном сценарии.
Но это не единственная связка, образующая достаточность, ес-но.
И встроенных immutable-гарантий для интерфейсов и абстрактных классов в дотнете нет, увы.
S>А вот в read-only виде его реализовать эффективно очень затруднительно, если вообще возможно.
Ой, блин...
Все типы неймспейса Immutable — они read-only by design.
Примерно как String, где Substring или operator+ порождают другой экземпляр.
Одно синоним другому, как и константность ("постоянство" по-русски).
V>>Что, однако, верно только для сценариев, где данные активно изменятся. V>>FrozenXXX были созданы для других сценариев — где данные читаются намного чаще, чем изменяются. S>Да, для специального узкого случая.
Э, нет, случай как раз не узкий.
Я понимаю, что ты мне вернул определение "узкий", но я говорил про "узость" реализации, а не сценариев.
Это две прям очень большие разницы.
Сценарии широки и там, и там, бо это два основных общих сценария работы с данными.
S>Вы готовы навскидку сказать, насколько они эффективнее Immutable-аналогов?
От данных зависит.
Разве ты не знаешь оценки сложности сверху сбалансированного дерева и хеш-таблицы?
Да и при оценке снизу затраты на линейный поиск на небольшой выборке в 2-3 раза меньше, чем на хеш-таблицу или обход графа таких же размеров.
V>>* мы именно с тобой обсуждали N-арные деревья, т.е. ты должен хорошо понимать, что нет никакого запрета строить иммутабельные деревья из таких структур данных, сбалансированных с точностью от 1 до некоего выбранного max N узлов; т.е., при создании нового корня дерева в общем случае будут создаваться копии меньшего кол-ва узлов, чем для двоичных узлов, но в каждом узле будет больше элементов. До какого-то N это выгодная стратегия на современном оборудовании, потому что деревянная в памяти структура в общем случае обладает худшей локальностью, т.е. синтетические тесты, где в памяти только содаются узлы тестируемого дерева, могут сильно врать насчёт его эффективности. S>Мы не просто это обсуждали. Я такую структуру реализовывал самостоятельно.
Поэтому и обсуждали.
Но тесты-то синтетические, неявно обеспечивали локальность данных для сравниваемого чистого бинарного дерева.
V>>N-арное дерево в этом смысле — это обеспеченный ручками некий фактор локальности данных. В идеале, конечно, было бы удобно иметь ср-ва располагать такие "корзины" по границам кеш-линееек проца, но дотнету такие радости недоступны. S>Прекрасно доступны, надо просто уметь их готовить.
Они доступны только через unmanaged, но это тогда ср-ва чуть ли не чистого Си, включенного в C# как подмножество.
И ты не сможешь эффективно ссылаться из таких структур на GC-типы, только через GC-handle, а это тормоза, т.е. профанация изначальной идеи сбацать реализацию пошустрее.
V>>В любом случае, рассуждать об иммутабельности или нет немспейса Frozen было заведомо глупо — типы данных там точно так же иммутабельны by design, как и в неймспейсе Immutable. S>Тогда зачем вы притащили его обсуждение в эту ветку?
Обиделся? ))
А зачем ты притащил Immutable?
Я притащил для демонстрации, конечно.
Демонстрации того, что парадигма не равна конкретной реализации.
Конкретная реализация может придерживаться некоей стратегии, исходя из знаний (предположений) о характере данных и способах оперирования ими.
Здравствуйте, Sinclair, Вы писали:
V>>Ключевое слово const — оно не само в себе весчь, в разных синтаксических конструкциях имеет разную семантику. V>>Соотв., обсуждать можно только конкретные синтаксические конструкции, где допустимо это ключевое слово. V>>Предлагаю впредь поступать именно так, дабы не испытывать терпение коллег-читателей. S>Начните с себя. Вот ваша цитата: S>
S>Через const в С++ можно выразить абсолютно все сценарии вокруг иммутабельности целиком, но это будет лишь небольшая вершинка айсберга всех сценариев, покрываемых const.
S>Что ж вы тут обсуждаете не конкретные синтаксические конструкции, а испытываете терпение коллег-читателей?
Для тех, кто владеет плюсами, — это истинное выражение.
Остальные могли бы уточнять, вместо споров, бо спор предполагает достаточные знания по предметной области.
В этом смысле ты нарушаешь логику спора.
(хотя, я могу не сильно ошибаться, предполагая, что ты специально провоцируешь коллег на манер шимжы, дабы они несли тебе инфу на блюдечке... но вообще достаточно просто спросить)
V>>В примере акцент не на списке (и откуда ты взял про "эффективность?"), а на внешний вид выражений. S>А зачем мне внешний вид выражений? Внешний вид я и сам какой угодно придумаю.
Это был ответ на твоё
Методы гораздо удобнее выстраивать в цепочку. Запись вида ... читать гораздо комфортнее, чем ...
Для цепочки бинарных операций удобнее всего использовать бинарные же синтаксические операции, разумеется.
Особенно если удачно их подобрать, с учётом встроенного в язык приоритета операций. ))
S>Вопрос в реализации — будет ли у вас там O(N) копирование на каждый чих, и будет ли добавление K элементов стоить O(N*K).
Будет зависеть от реализации.
Для сбалансированного дерева будет O(log N), для иммутабельной хеш-таблицы близко к O(N/K), где K — отношение кол-ва элементов и уникальных хеш-кодов по модулю N.
Кстате, пример хеш-таблиц как раз для случая, когда контейнер намного эффективнее для чтения, чем для изменений.
Просто в дотнете хеш-таблицы недоделанные, вызывают удивление.
По классике при перестроении хеш-таблицы необходимо подбирать гаммирующую функцию для минимизации конфликтов хеш-кодов, соотв. алгоритмы в теории есть.
В дотнете эта стадия опущена.
Т.е., дотнетная хеш-таблица — "компромисс на все случаи жизни", бгг...
Кстате, надо будет взглянуть на FrozenHashTable, что там происходит в процессе построения...
Здравствуйте, 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>Вы распишите, что у вас там вместо // .... Поскольку у вас под капотом — заранее неизвестный мутабельный тип, то всё, что вы можете — это состряпать его копию, к которой потом будет применена манипуляция с изменением.
И чем плоха копия такого объекта:
class ImmutableSet<T> {
const RBNode<T> * root_;
};
где ImmutableSet<T> используется с семантикой значения, в данном случае значения-ссылки.
Так для чего ж тогда 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>Да при чём тут ссылка? Вы просто опять уходите в решения для каких-то экзотических частных случаев.
Наоборот, говорил, что в плюсах есть возможность писать более обще, потому что у меня есть возможность распространять гарантии.
Обрати внимание на сигнатуры парами:
Константное поле у меня лишь в декораторе 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>.
То сделали бы эти случаи неразличимыми/конфликтующими, в то время как м/у ними сильное различие с т.з. эффективности.
В кишках дотнета голые массивы весьма входу и популярны.
Где приходится бороться за эффективность на юзверском уровне — тоже.
Здравствуйте, Sinclair, Вы писали:
S>Иммутабельность означает не просто отсутствие модифицирующих операций, но и наличие операций по построению новых значений на основе существующих.
Думаю, надо расставить все точки на i, а то ты окончательно запутал потенциальных читаталей.
Иммутабельность — это именно то, что означает этот термин.
Это некие гарантии ЯП неизменности неких значений.
наличие операций по построению новых значений на основе существующих
Если речь про структурное построение, а не про арифметические или логические вычисления, то этим св-вом обладают все языки, в которых можно описывать структуры, кортежи или их аналоги.
Наверно ты имел некие св-ва, которая даёт иммутабельность программе?
Например:
1. свойство ссылочной прозрачности, т.к. состояние лямбд неизменно, то любые лямбды становятся чистыми ф-иями;
2. детерминированность по чтению при доступе из разных потоков.
Каждое из этих св-в имеет вполне ощутимые последствия.
(1) даёт возможность не разыменовывать ссылки с целью копирования результата (ссылки на ф-ии в том числе), то бишь можно отложить вычисления "на потом", а будучи однажды вычисленным — заменить ссылку и/или выражение на его значение. При этом, доступ к любым данным по "фиксированному адресу" (например, по коль-угодно глубокому графу) можно заменить ленивой функцией с мемоизацией, которая вычислится лишь однажды.
(2) дает возможность эффективного распараллеливания программ, т.е. без блокировок. Распараллеливания не только по данных, но и вообще по вычислениям, что в связке с мемоизацией, по-сути, выполняет бесконечную бета-редукцию прямо в процессе работы программы, связывая термы с конкретными аргументами.
Что касается неймспейса Immutable и реализаций типов в нём, то, помимо собственно гарантий иммутабельности описанных типов, те реализации позволяют эксплуатировать совсем небольшое подможество св-в иммутабльных типов данных, а именно — детерминированность по чтению из разных потоков. Всё.
Большинство типов из неймспейса Immutable не представляют практического интереса для программиста, такие как ImmutableArray, ImmutableList, ImmutableQueue и т.д., т.к. в реальных сценариях экономят совсем мало на реализации своих аналогов. Иммутабельные хеш-таблицы из этого неймспейса можно вовсе смело сжечь. Более-менее интерес представляют лишь иммутабельный словарь и множество, оба на основе сбалансированного дерева. Единственные, мать его, полезные два типа из всего неймспейса.
Но в этих типах не будет ни ссылочной прозрачности (о которой "знал" бы компилятор или некий пользовательский код, строящий и исполняющий лямбды "на лету"), ни автоматического распараллеливания вычислений с потенциальной мемоизацией (подменой ссылок на термы в процессе аппликации вычисленными значениями) — ничего этого нет. Потому что эти типы неотличимы от мутабельных с т.з. системы типов языка. Да и в самом языке нет пребразований над иммутабельными типами данных и ф-иями/ламбдами поверх них за отсутствием оных.
Плюс рядом же в исходниках появился еще неймспейс Frozen, который описывает иммутабельные типы с точно такими же гарантиями, но обладают меньшей эффективностью при изменении данных.
Зато в неймспесе Frozen уже все представленные типы представляют интерес, т.к. был сделан упор на эффективный лейаут данных в памяти, оптимизированный для чтения на современных архитектурах.
Что же касается "гарантий", который требовал Синклер — он имел ввиду защиту от дурака на уровне ср-в языка.
Например, можно описать обычные типы данных без гарантий иммутабельности, т.е. ни защитив сами данные ни const/readonly, ни дизайном ООП-типов через инкапсуляцию.
Иммутабельность данных может быть обеспечена самим сценарием. Это примерно то же самое, что инкапсуляция на уровне объекта, только уровнем повыше — на уровне некоей подсистемы, если спроектировать её так, чтобы "абстракции не протекали", т.е., чтобы не нарушалась принятая в системе стратегия рассматривать некие данные как иммутабельные, т.е. будучи однажды созданными, сохраняющие затем неизменность до тех пор, пока на эти данные есть ссылки, т.е. пока они нужны.
Здравствуйте, vdimas, Вы писали: V>Если речь про структурное построение, а не про арифметические или логические вычисления,
Вы зря противопоставляете эти две концепции.
var a = 5; var a1 = a + 1;
var d = DateTime.Now(); var d2 = d.AddDays(1);
var l = (new {42}).ToImmutableList(); var l2 = l.Add(1);
Во всех трёх строчках происходит одно и то же — конструируется новое значение на основе старого, старое остаётся неизменным.
То, что первая и вторая строчка = "арифметические операции", а третья — "структурное построение", ещё менее важно, чем различия в синтаксисе между оператором + и вызовом метода.
V>то этим св-вом обладают все языки, в которых можно описывать структуры, кортежи или их аналоги.
Ну конечно же нет. Вовсе не любой язык даст вам возможность сконструировать иммутабельную структуру, кортеж или их аналог по образцу, но с некоторым отличием.
Ну, то есть формально говоря так можно сделать в любом языке, но если в синтаксисе языка нет таких средств, вы просто не захотите писать в таком стиле.
Запись в стиле p.Text = "Hello", которая изменяет значение поля в структуре p, есть примерно везде.
А вот радости писать p1 = new Foo(p.Field1, p.Field2, p.Field3, new Bar(p.Field4.Field1, p.Field4.Field2), p.Field5 + 1, "Hello", p.Field7) — крайне мало.
На С++, наверное, можно что-то намутить через лямбды, которые будут скармливаться "конструктору модификации" — но это опять-таки с необходимостью требует наличия двух различных классов, работающих в тандеме — мутабельная основа и иммутабельная обёртка.
Точно так же неудобно расписывать каждый раз
var tmp = new List<int>(l); tmp.Add(1); var p2 = tmp.ToImmutableList();
Далее — даже если у вас есть синтаксически приемлемый способ конструировать новое значение на основе предыдущего (например, для списка это так в С++), нужна ещё и приемлемая производительность. В этом месте перспектива "да я сейчас напишу однократно универсальный шабонный wrapper для любого mutable типа" начинает растворяться.
V>Например: V>1. свойство ссылочной прозрачности, т.к. состояние лямбд неизменно, то любые лямбды становятся чистыми ф-иями;
Лямбды и иммутабельность связаны примерно никак. И состояние лямбд может быть мутабельным, и иммутабельность может быть полезна и без лямбд.
Опять — у вас в голове каша, где ортогональные понятия спутаны во что-то одно. V>2. детерминированность по чтению при доступе из разных потоков.
Слова "по чтению" тут лишние. Детерминированность при доступе из разных потоков при иммутабельности работает всегда.
В частности, ничего не должно мешать одному потоку выполнять list.Add(5), а другому одновременно выполнять list.Remove(0). Детерминированность вполне сохраняется и здесь.
V>(1) даёт возможность не разыменовывать ссылки с целью копирования результата (ссылки а ф-ии в том числе), то бишь отложить вычисления "на потом", а будут однажды вычисленным — заменить ссылку и/или выражение на его значение.
Это утверждение не имеет физического смысла вне контекста лямбд. V>(2) дает возможность эффективного распараллеливания программ, т.е. без блокировок. Распараллеливания не только по данных, но и вообще по вычислениям.
V>Большинство типов из неймспейса Immutable не представляют практического интереса для программиста, такие как ImmutableArray, ImmutableList, ImmutableQueue и т.д., т.к. в реальных сценариях экономят совсем мало на реализации своих аналогов. Иммутабельные хеш-таблицы из этого неймспейса можно смело сжечь. Более-менее интерес представляют лишь иммутабельный словарь и множество, оба на основе сбалансированного дерева. Единственные, мать его, полезные два типа из всего неймспейса. .
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>>>Там не совсем тот P-код. Там просто упакованноое в удобное для интерпретации представление AST было V>>Там коды "инструкций" Бейсика. НС>Там коды ключевых слов.
В ассемблере тоже "коды ключевых слов".
Или ключевые слова для кодов, на вкус.
НС>Причем организовано это строго как написано.
Скорее, наоборот — написать можно строго как положено согласно семантике инструкции.
Ты не сможешь написать строку программы, содержащую ошибку — тебе не дадут выполнить Enter в таких системах, пока ошибка не будет исправлена.
НС>А если посмотреть код "компилятора", то там простейший парсинг и просто подмена символов на их коды.
Верно, как в ассемблере.
НС>Причем оригинал не сохраняется, а восстанавливается при необходимости по этому коду.
Прям обычный дизассеблинг, разве что вместо адресов переменных используются их имена из словаря.
НС>Все. На Р-код это похоже исключительно в силу того, что на Р-код похож сам исходник того бейсика.
Да пофик. Если существует возможность "железной" реализации инструкций бейсика в гипотетическом CPU, то можно смело обзывать p-кодом.
Целиком сокращение означает "псевдо-код", если еще развернуть — "код для псевдо-ЦПУ".
НС>Но смысл этого — сэкономить память на хранении программы и убрать из интерпретатора парсинг, а не обеспечить переносимость.
Портабельность — это просто автоматически получаемое кач-во, хосподя, коль отсутствует привязка к конкретной архитектуре, тогда все архитектуры получаются равнозначными для хостинга виртуальной машинки.
Смысл псевдокода зачастую в компактности и готовности к исполнению прямо в своём виде.
Закодированный код Бейсика полностью удовлетворяет этим требованиям.
Например, MS P-Code был разработан и использовался в VB/VBA из соображений компактности и эффективности, а не соображений портируемости.
НС>>>а в описываемых Паскалях это был машинный код виртуального CPU, как сейчас в Java и дотнете. V>>Немного не понимаю, почему прицепились именно к Паскалю? )) НС>Я же процитировал: НС>Two early compilers generating p-code were the Pascal-P compiler in 1973, by Kesav V. Nori, Urs Ammann, Kathleen Jensen, Hans-Heinrich Nageli, and Christian Jacobi, and the Pascal-S compiler in 1975, by Niklaus Wirth.
Я на это уже отвечал — впервые оно было не в Паскале и позже широко использовалось тоже не в Паскале.
Понятие псевдокода существовало задолго до 73-го года.
V>>Технология впервые была использована в другом языке. НС>Было что то похожее. А в полноценном виде это были именно Паскали.
1. В полноценном виде существовали Паскали и до 73 безо-всякого p-кода.
2. Полноценно эта технология использовалась и до реализации на ней Паскалей.
Из одной из разработок Паскаля родился мем p-code как сокращение от псевдо-код, и ничем более Паскаль в этой истории не примечателен. ))
Сама та разработка идиотская, ИМХО, т.к. Вирт породил Паскаль упростив Алгол-60, т.е. выкинув оттуда прилично конструкций.
Одной из целей создания языка Паскаль Никлаус Вирт считал обучение студентов структурному программированию. До сих пор Паскаль заслуженно считается одним из лучших языков для начального обучения программированию.
Нахрена учебному языку создавать переносимый бинарный код?
V>>Мой поинт был в отделении понятия "язык программирования", как совокупности ситнаксиса и семантики от способа реализации этой семантики на стадии исполнения кода НС>И при этом ты привел в пример спектрумовский бейсик в котором никакого отделения синтаксиса не было, был просто вынос стадии парсинга на этап сохранения строки в память.
Ну, дык, отличный пример отделения языка от реализации.
Для сравнения, реализация VB For DOS честно компиллировала текстовый исходник в честный бинарь.
При этом язык практически тот же (проги из спектрумовского Бейсика компилировались без изменений, если не лезли в память напрямую).
V>>Спекулировать тут можно только насчёт того, что в том же дотнете рефлексия, ExpressionTree и Roslyn идут в базовой поставке и являются частью стандарта, а в С++ это дополнительный инструментарий, НС>Вот именно. Нет ABI — все, куча сценариев закрывается.
ABI есть, но для конкретного компилятора/платформы.
Например, COM ввел часть устоявшегося на x86 С++ ABI в кач-ве своего стандарта (в разделе виртуальных ф-ий, их организации и вызова).
НС>Но вы тут опять с терминами устроили кашу, уж не знаю, случайно или намеренно. Р-код это непосредственно императивные инструкции и это отдельная песня.
Это ты озвучиваешь своё эвристическое понимание.
P-код — это то же, что и псевдокод. Всё.
НС>А rtti — это другая песня, хоть и упаковываетcя она в те же файлы. Зачем пытаться это все обсуждать одновременно — непонятно.
Была поставлена задача передать код на другую платформу и исполнить.
Потом выяснилось, что задача звучит не так, ну да ладно...
Здравствуйте, korvin_, Вы писали:
V>>Во времена, когда этот мем появился, чаще нельзя было передавать пользовательские типы данных по значению. _>При чём тут мемы?
fist class citizen — это мем.
V>>Первоклассные сущности имели неизвестную структуру, именно поэтому вопросы передачи и возврата таких значений тогдашние компиляторы были вынуждены брать на себя. _>Какая неизвестная структура у указателя?
Хотя бы расположение бит и их итерпретация.
Например, far указатель унутре составной, часть бить отвечает за сегмент, часть за смещение сегмента.
Простая конкатенация бит адреса не создаёт реальный адрес, поэтому сравнивать произвольные far адреса нельзя.
Можно сранивать адреса только из одного сегмента.
Или более строго — из одного выделенного по malloc блока.
V>>"Ортогональность" появилась позже, по мере развития ЯВУ, но тогда и определение надо было доработать. _>Определение и доработали, я приводил цитату из 4-х пунктов.
Ты привёл из вики, т.е. совершил напрасный труд. ))
И почему ты споришь со мной?
Там коллега сказал, что Expression<T> — это первоклассная сущность.
Ну вот и спроси у него, чем его Expression<T> первокласснее моих неких MyExpression<T>?
V>>Строго говоря, первоклассной сущностью в C# являются ссылки на объекты, но не сами объекты, внезапно. _>Строго говоря, это словоблудие. Косвенность сегодня никого особо не волнует.
Косвенность не волнует только в иммутабельных системах типов, а иначе волнует, конечно.
_>P. S. Дополнение к примеру syntax-case: _>
_>(library (syntax-utils)
_>
Это какая-то нестандартная Схема? ))
Вроде бы так:
(library "<name>" "<scheme>"
_>— всё, никаких шаблонов. Да и syntax-case можно убрать вообще, убрав даже (_ . body)
Любые примитивы из стандарта, навроде let, могут быть реализованы как встроенные.
Показанная тобой реализация предназначена для динамического исполнения машинкой, ес-но.
Поэтому, опять мимо.
