Pull to refresh

Comments 25

UFO just landed and posted this here
Я бы сказал, что мы можем легко реализовать XPath на базе зипперов. Но если строго, то нет, это не XPath.
Я бы скорее сказал, что это расширение идеи итераторов, но если в плюсах они по сути в обычный курсор влево вправо превращаются, то тут всё немного интереснее.
Ограничение на только <персистентных структур данных> сводит на нет ценность зипперов.
Инструменты для работы с деревом данных достаточно развиты и ничего нового зипперы не дают.
В MUMPS для работы с деревом данных используются 3 функции
1 Next — следующий или предыдущий узел на том же уровне.
2 Qery — следующий или предыдущий узел с данными на уровне ниже текущего.
3 Data — состояние вершины. Есть ли в ней данные и есть ли потомки у узла.
Хотя для работы с деревом хватило бы и одной функции Next.
Такого интерфейса вполне достаточно для работы с любым деревом и без дополнительных ограничений.
К сожалению я о MUMPS узнал только что из вашего комментария, поэтому приходится только догадываться как вы предполагаете реализовывать изменение дерева с помощью одной только Next.
Похоже, что речь идет об изменении в прямом классическом смысле этого слова, в смысле mutation. У этого подхода есть ряд проблем, и основная — он вносит в систему время, вносит его без надобности, чем увеличивает сложность системы в разы, если не на порядки. Причем сложность эта как правило не обусловлена задачей, так называемая accidental complexity.
Во времена дефицита оперативной памяти и крутящихся дисков малого объема этот подход был оправдан просто потому что никак иначе было нельзя, грубо говоря место приходилось экономить. Времена эти давно прошли. Поэтому то мы наблюдаем нарастающую активность в функциональным программировании.
Крайне рекомендую ознакомиться с первыми 30 минутами вот этого видео. В нем дядюшка Боб обрисовывает текущие тренды и рассказывает чего следует ждать в ближайшее десятилетие. Очень полезное видео.
Конечно, всегда останется некоторый спектр задач с ограничениями по ресурсам, в которых функциональный подход будет не применим. И в некоторых из них лучшим инструментом, возможно, будет MUMPS. В таком случае мы с вами скажем, что зипперы ничего нового не дают при решении задач из этого спектра.
Я вынес из статьи, что речь идет о доступе к иерархическим данным и поэтому об этом и написал. Изменение данных в MUMPS осуществляется командой Set. Как при этом вносится время мне не понятно. Команда одномоментно изменяет структуру данных. Если изменения выполняются в одном потоке то коллизий не возникает, если в разных заданиях то есть примитивы синхронизации. Но это по моему всегда так. По поводу экономии места на диске и в ОП то же не понял. Ведь речь шла об интерфейсе к деревянным данным независимо от способа хранения этих данных.
Извините дядюшку Боба понять не в состоянии, английским не владею.
Речь шла о функциональном концепте работы с деревьями. Вы привели пример, если я все верно понял, нефункционального языка. Из того, что вы сочли персистентность данных излишним требованием, я делаю вывод, что Set мутирует свой параметр (некоторым образом изменяет данные в нем самом).
Ссылка на Боба, и рассуждения про память с дисками это способ подчеркнуть тот факт, что тенденция, то в сторону функционального программирования. И это не причуды или дело вкуса, а реальный процесс.
На счет времени.
Когда наша программа выдержана в функциональном стиле, мы грубо говоря имеем чистую обработку данных. Функция: на входе данные — параметр, на выходе другие данные — результат. Нет времени "до" и "после" обработки, есть просто вход и выход.
Когда наша программа не выдержана в функциональном стиле. В ней имеются участки наподобие такого:

Tree sampleTree = {"a" 1};
...
println(sampleTree); //момент времени До Set 
sampleTree.Set("a", 5);
println(sampleTree); //момент времени После Set 

в котором у нас возникает "до" и "после". С этим очень сложно работать. Тратятся колоссальные усилия чтобы синхронизировать нужные вызовы с нужными моментами во времени.
Пример на MUMPS
Set A=5
Write A
; до этого момента имеем старое значение и никакого времени нет
Set A=6
; здесь новое значение =6 момент определен командой Set причем тут время? Какие проблемы могут здесь возникать?
UFO just landed and posted this here
Выход конечно славный. Но я слабо представляю как это можно практически осуществить, кроме как остановив корректировку сделав копию в сторонку и работать с этой копией. Технически это возможно сделать. Но практически достаточно затратно и долго. Я в подобной ситуации работаю с кривоватыми данными. Заморозить всю систему и делать копию не выход. Хотя можно отложить корректировку до определенного момента времени, но тогда возникнут проблемы на рабочем месте у корректирующего данные.
UFO just landed and posted this here
Давайте попробуем так. Попробуйте сформулировать ответ на вопрос "почему\для чего нужны транзакции?" Транзакции как способ изменения данных.
Ну допустим в MUMPS транзакции есть. А нужны они для сохранения целостности данных. Но проблему формирования отчета из одного состояния данных. транзакции не решают.
Сделайте еще шаг в рассуждении: Когда и почему может нарушаться целостность данных?
Дело не в дефиците оперативной памяти или крутящихся дисках. А скорее в неразвитости методов функционального программирования и отсутствии продвинутых трансляторов и сред исполнения. Потому как в своё время (вторая половина 1980-х) при ограничениях на оперативную память и скорость работы дисков существовал такой язык — SISAL, в котором SAL — это Single Assignment Language, и этот язык производительностью получаемого кода уделывал и Си, и чемпиона того времени — Фортран. То есть, вычисления с устойчивыми данными могут быть весьма эффективными.

Современный фокус внимания на таком подходе к вычислениям, скорее всего, связан не с эффективностью, а с необходимостью писать распределённые приложения, в которых изменчивость данных создаёт чрезмерно много конусов времени (ну, в терминологии векторных часов Лампорта), с которыми после некоторого предела уже невозможно надёжно работать. Поэтому, среди прочего, у нас всякие CRDT вместо баз данных и прочее, прочее.
Возможно вы просто более глубоко понимаете проблему. Я обычно пытаюсь понять до уровня простых слов, а дальше бросаю, из за лени природной. В простых словах — не видно никаких других причин изменять, удалять данные кроме прямой необходимости делать это. Конечно необходимость эта была вызвана не неразвитостью методов, а прямыми техническими ограничениями, а чуть позднее естественной инертностью связанной с legacy, системой образования и тп. Прямые технические ограничения направляли умы на решение задач типа распределенных транзакций в большей степени, потому что это были задачи из той реальности, практические задачи. Как только реальность изменилась, начали возникать вопросы типа: а нужны ли нам транзакции вообще? можно ведь не изменять данные, а просто накапливать. Тут нет вопроса неразвитости метода. Нет метода — создадим. Отсутствует среда исполнения — напишем. Главное технических ограничений теперь нет.
Ограничение на только <персистентных структур данных> сводит на нет ценность зипперов.
Ну так в Clojure все родные структуры персистентные. Так что ценность на 0 не сведена.
А насчет MUPS… Вы уже не раз на Хабре высказывались, что это ответ на главный вопрос жизни, вселенной и вообще. Спасибо за повторение.
Целая статья про зипперы и ни одного слова про то, что это производная от алгебраического представления структуры данных?!
В целом, верное замечание. Статья правда практически ориентированная, с объяснением на пальцах, как бы алгебраические структуры данных не помешали восприятию. Но я подумаю, как их можно обыграть как минимум для расширения кругозора. Спасибо за идею.
производная от алгебраического представления структуры данных?!

Те кто умеет мыслить такими терминами, т.е. разбирается в алгебре им эта статья врядли чем-то поможет и чему-то научит. А вот таким как я, подобные "заумности" явно ни к чему. Оно понятно, что математика полезное дело. Не спорю. Очень полезное. Но во всем нужна золотая середина. Между "заумностью" и практичностью. Введя "заумности" такие как я не осилили бы и отложили бы прочтение на потом ;)
Вполне возможно делать это в 2 статьи или доп параграфом, т.к. часто возникают вопросы, а как правильно сделать зипперы для той или иной структуры данных и эти "заумности" дают весьма точный ответ. В принципе добавления общей информации и ссылки на статьи вполне достаточно, например, тем кто представляет что такое зипперы, но не теорию за этим стоящую.
Готово, еще раз спасибо за ценное замечание.
Правильно ли понимаю, что zipper'ы можно использовать и для итерации по произвольному графу?
В случае с BSP, QuadTree, OcTree zipper'ы выглядят практично.
Хороший вопрос. На счет произвольности, меня смущает цикличный вариант. Есть мнение, что и этот вариант можно реализовать через доп абстракцию, например представление графа в виде некоторого замыкания относительно его структуры, а уже на базе этого замыкания создавать зиппер. В любом случае это вопрос конкретной задачи, в каком виде нужно получать результаты и какие манипуляции проделывать с графами. Будет время обязательно попробую с циклами. Если вы этим занимаетесь, буду также рад прочитать о результатах ваших экспериментов.
Да, можно с любой структурой данных, если в конкретном алгоритме проход по ней можете представить в виде дерева. То есть, сама структура данных может в виде дерева не существовать. И вообще не существовать. Потомки могут быть вычислимыми. Поэтому zipper-ы можно использовать для всяких переборных задач с back-tracking-ом. Ну, а то, что Вы перечислили так и вообще деревья в своём исходном определении. Поэтому, никаких проблем.
Sign up to leave a comment.

Articles