OberonCore

В докладе на Оберон День 2017 я рассказывал про библиотеку контейнеров .
И про то, что можно на её основе сделать персистентные контейнеры, то есть контейнеры, которые запоминают каждую свою модификацию и при желании можно вернуться к предыдущей версии и посмотреть что там было.
В итоге реализовал такое дерево. Для того, чтобы лучше понимать, что именно оно делает, вот тест:

Единственное, остался один неясный момент. При добавлении в обычное дерево, я сначала вызываю функцию Allocate и только затем Insert, то есть Insert не может провалиться из-за нехватки памяти. Сейчас же при модификации основного дерева, для запоминания предыдущего состояния, выделяется память для хранения новой модификации указателя (по сути вместо обычного указателя в памяти, я реализовал дерево указателей, у которых ключ - это номер версии). И на каком-то этапе может так произойти, что не хватит памяти для сохранения этой истории. И из-за этого основной алгоритм тоже может провалиться. По идее надо бы расчитать точно, сколько вращений может быть в AVL дереве в худшем случае при удалении или добавлении и сколько при этом указателей может измениться. А затем до попытки добавления в дерево или удаления из него необходимо разом выделить максимальное количество памяти под указатели, которые могут измениться, чтобы алгоритм ни при каких обстоятельствах не столкнулся с нехваткой памяти.
Как вам данный подход? Может быть у вас есть идеи по лучше?

Вы в докладе говорили, что рассматривали и деревья в виде массивов (видимо, однородных структур). Такие структуры можно восстанавливать из персистентных файлов за одно аллокирование. Дерево-массив -> Externalize -> Передача по сети -> Internalize (за 1 NEW) -> дерево-массив.

А зачем нужна эта история? Если предполагается нечто вроде мини-СУБД, то обычно в подобных случаях функционал шире со спецификой предметки (к примеру, версии нужны в контексте транзакций, журналов операций, существует возможность сброса/загрузки на диск и т.д.). Но исходя из презентации речь, вроде как, об универсальных контейнерах и алгоритмах, аля STL. Однако типовая сфера применения "персистентных" универсальных контейнеров -- immutable-коллекции как в функциональных языках, или по их мотивам -- на примере facebook-фреймворка для JavaScript:
http://facebook.github.io/immutable-js/

, где версии, как таковы, используются для внутренней реализации "виртуального копирования" структур, в стиле:
A = [1,2,3,4,5,6];
B = A;
B[1] = 12234;

Здесь при присваивании "B = A" не выполняется копирования контейнера (массива), лишь используется указатель. При изменении данных вида "B[1] = 12234" создаются "версии" только необходимых элементов, части исходной структуры. В последующем "история" освобождается при уничтожении объектов (т.е. при выходе из области определения переменных и т.п.). В дополнение, практика обычно требует и транзитных преобразований, т.е. "по месту", временный перевод структур из immutable в mutable (плюс "ленивые" вычисления по вкусу, как тип Seq по ссылке выше -- для избегания по возможности создания промежуточных структур при различных вычислениях).
Для таких техник необходимы:
- реализация политики каких-то smart-pointer, для разруливания владения, освобождения и т.д.;
- предположение, что в виртуальных копиях обычно выполняется лишь частичная модификация данных (т.е. не передел всего и вся, иначе нет никакой эффективности).

Такова типовая необходимость в "версиях" в стандартных контейнерах, и нет концептуальных непоняток с их "накоплением".
Однако, в дополнение возникает сомнение, зачем подобные техники и "STL" в целом в языке, который целенаправленно не приспособлен к обобщённым алгоритмам. И Ваша презентация тому кричащий пример, как и некоторые темы здесь на форуме. Согласно презентации, необходимость реализации "типов-ключей" и соответствующих операций вида "AssignAddrToAddr", "CompareKeyAddr" и т.д., фактически, для каждого случая применения, а особенно при использовании стандартных же базовых типов -- чисел, строк и т.д., в том числе и как составных данных, со стандартными же операциями -- мягко говоря, не юзабельно.

Вот здесь был пример реализации "STL" для Pascal при отсутствии generic-ов:
viewtopic.php?f=26&t=2036&start=100#p101400

, где, в некотором смысле, имеется схожий подход в архитектуре. Не в курсе, насколько подобные выкрутасы целесообразны в Оберонах (не использую, имею лишь поверхностные знания), но взглянуть есть смысл. Там также применялись "типы-ключи", но по-иному -- как "типы-поля" для структур данных, в которых "перехватываются" ключевые операции от контейнеров (был интерфейс и для деревьев).
Правда, для удобства в том же Pascal-е были (и есть) некоторые базовые языковые конструкции. К примеру, определение операций "индексации" для произвольных "свойств" в структурах аля:
n.Map[3.14] := 'Pi'

Или применение встроенных типов вида "variant" или "TVarRec" (или как там тип-запись назывался для аргументов функций, определяемых как "array of const") для передачи "открытых" массивов как variadic-параметров.
Не знаю, как подобные удобняшки стандартно реализуются в Обероне, но есть подозрение, что окольными путями (вряд ли тогда в них есть смысл).

P.S. Документация от проекта AntiDot:

Слово персистентный имеет несколько значений. Иногда, да говорят о данных, которые переживают время запуска программы, то есть выгружаются и загружаются из какой-то формы (сериализация).
В википедии по поводу персистентных структур данных немного другое определение:
https://en.wikipedia.org/wiki/Persistent_data_structure

Я придерживаюсь этого определения.

Персистентные структуры данных можно использовать, например, для текстового редактора с поддержкой undo. Можно редактировать текст и откатываться к предыдущим версиям при необходимости.

Или же можно использовать, для запоминания, каких-нибудь преобразований.
Допустим, есть предикат:
0) х + х + х = 3*x
1) 3*x = 3*x
2) TRUE
Будет возможность видеть всю цепочку преобразований, а не только конечный результат TRUE.

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

В статейке ниже пара слов насчёт undo:

Я всего лишь хочу сказать, что подобные задачи, как правило, гораздо шире, чем версии данных в стандартном контейнере (кстати, в данном случае immutable-коллекции могут оказаться полезными -- множество "клиентов" к одной структуре данных, а у каждого клиента свой поднабор, может даже со своим аля multi_index из C++ Boost).
В общем, контейнеры всякие разные нужны.

Но проблема в таком языке как Оберон -- как строить универсальный интерфейс аля STL, даже для Ваших деревьев (генерировать требуемые реализации операций, к примеру). Здесь могу предложить варианты:
- макросы в стиле С, например как:
https://gcc.gnu.org/viewcvs/gcc/trunk/g ... rev=165314
, что вряд ли приемлемо общественностью;

- велосипед-кодогенератор. У каждого свой, или какой-то универсальный, к примеру:
https://nedbatchelder.com/code/cog/

- макросы как в Rust -- ограниченные, в виде функций:
https://doc.rust-lang.org/1.7.0/book/macros.html

- макросы как в Scala, прежде всего -- квазицитаты в виде спецстрок q"..." (по мотивам Лиспа):
http://docs.scala-lang.org/overviews/qu ... intro.html

Мне кажется, что практично -- макросы как Rust-функции вида "search!(cont, [val1, val2])", но с реализацией на квазицитатах. Однако, впечатление, что "meta-фишки" не приветствуются в Оберон-сообществе (но я могу ошибаться). Но я воспользуюсь след. предложением технологии:
Zero-Overhead Exeption Handling Using Metaprogramming

Т.е. runtime-метатехнологии предлагаются. Причём в подобных техниках нет compiletime деклараций, в том смысле, что, к примеру, какие-то процедуры являются обработчиками ошибок -- лишь какое-то "устное соглашение", мол если надо, то реализуй такие-то процедуры, с такими-то параметрами, с такими-то именами и т.п.
Когда те же макросы-функции могут явно, целенаправленно (с контролем типов, безопасности вводимых имён и пр.) хоть тип, к примеру, удобно задавать, со всеми "мета-атрибутами" (аля "make_mytype!(type_name, [<матрица_данных>])" в секции интерфейса модуля).

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