flow

Global Dispatch

Crosspost from: https://t.me/justy_tylor/4

This article describes Global Dispatch, a new approach for dispatching function calls over a set of specific signatures in programming languages, developed by me some time ago.

Let's start with the notion of types and values. As usual, if we have type A and type B, and every instance of B is also A, then B is a more specific pattern in signatures. Also, multiple inheritance (or multiple interfaces implementation, depending on language capabilities) is supported. There is no sorting order between different "is" facts, so no leaky things like C3 linearization are allowed. Also, there is no specificity for contravariant parameter types.

And here we have the first improvement over traditional approaches. The most specific patterns are values themselves. It can be an enum value or string value, whatever. If you have experience with professional C++ code then you are surely remember lots of cases where types are used instead of enum values. That's not right. It deserves proper fixing.

The next step will be moving to Multiple Dispatch. Dynamic, static, or mixed. The latter two do require compiler support, and dynamic can be performed by a library (in languages with enough dynamic nature or reflections). Here another improvement happens for dynamic dispatch. Collection types are recognized not by their defined covariant type parameters, but by the actual types of items they contain. So variable defined with type List[A] can at some moment consist only of instances of more specific B and will be correctly recognized as List[B]. The importance of this will be shown later.

Final step. We're moving to Global Dispatch. Instead of function parameters, just any reachable identifier can be used in a signature (and checked/specialized between signatures).

Fields of parameters: obj.parent.parent
Global variables: settings.os_version
Values from the outer scope in closures: why_not

Implications.

It's easier to specialize signatures for different environments (operating systems, graphical APIs). No need for C/C++ preprocessors or preprocessing-like features.

Testing made simple. Just write some alternative signatures for mocks with (mode is testing) specialization. No more dark patterns like "dependency injection".

It's easier to define application logic. Checking that the user has selected a list of items "of this specific type" in GUI on one panel and some context on the other panel. Or dispatch of low-level GUI events, where multiple stages of "if click happened in this type of view", "if this instrument was selected at the time", and "if this layer is not read-only" are replaced by simple signatures at once. Or filling menus and toolbars with correctly chosen actions.

When extending applications with plugins. Just define functions with correct signatures and annotations in a plugin, that's it.

And, last but not least, when writing compiler or writing EDSL in some general purpose host language.

Practice.

I have a rough prototype library for Global Dispatch in C#, it contains only features designed for my (compiler-related) needs.

Currently no support for GUI annotations, plugins, etc. But I already did things with GUI annotations and dynamic recognition of List[B] a long time ago (.15926 Editor, 2011), before Global Dispatch. So they are easy to repeat in C# or another (my own?) language.

Also, this approach goes far beyond programming languages. It offers a significant improvement over existing knowledge representation methods, such as RDF+OWL, ISO 15926-2, HQDM, Gellish, and many others. But that subject deserves a separate article.
flow

Планы

Решил опубликовать кусочек своих исследований, дающих новые возможности в языках программирования и способах представления знаний. Но livejournal (и его клоны вроде dreamwidth) такая хтонь, что публиковать сейчас на нём - примерно как публиковать что-то на GeoCities в конце двухтысячных.

Видимо заведу двуязычный канал в Telegram - с серьёзно-техническими постами на английском и какой-то мимолётностью на русском. Создавая копии серьёзного здесь, но только на первое время.
flow

Идентификаторы для ролей

Когда-то я написал пост "Идентификация 4D-документов через криптохэши", и с тех пор неоднократно давал на него ссылки. Реакции были как "примерно понятно, но терминология 3D/4D сложна для восприятия". Да и сами по себе BORO и ISO 15926-2, откуда я (привычно) взял эту терминологию, достаточно тяжеловесны.

Так что, в 2019 году я перешёл к использованию другого термина - "роль". Сначала сам, потихоньку оценивая, а после дискуссии https://ailev.livejournal.com/1470152.html?thread=16180424#t16180424 термин был применён ailev в новой редакции его книги "Системное мышление", хоть и не в таком широком определении, но тоже к месту. Настало время и мне обновить старые материалы.

Роль - то, что имеет идентификацию, но в разных контекстах представлено разными состояниями/значениями.

Роль "яблоко на столе". Час назад его не было, сейчас оно есть, через 5 минут будет надкушено. Это разные состояния в контексте. Роль "переменная app.current_view.selected_items", значение которой меняется в разные моменты времени. Роль "файл readme.md в git-репозитории такого-то проекта на github" - зависит от ветки и момента запроса или от выбранного коммита. Пост "путешествие" в блоге, который может быть отредактирован спустя некоторое время.

Но насколько хорошо специфицирована роль? Что если в контексте есть несколько столов с возможными яблоками? Что если в блоге несколько постов "путешествие", причём, некоторые из них в одни и те же дни? Ок, можно роль специализировать. "Яблоко на столе сразу слева от входа". Или завести реестр столов, с описаниями и номерами, и использовать "яблоко на столе N1". Аналогично, постам в блоге присваиваются номера или специальные псевдослучайные коды. Номер может быть присвоен через запрос к центральному реестру, которым резервируется данный номер для поста, и никак иначе. Но если реестр будет скомпрометирован или утрачен - идентификация сломается. Псевдослучайный код может быть сгенерирован без реестра, и, при достаточной длине, тоже будет уникально идентифицировать отдельно взятый пост "путешествие". Однако, любой злоумышленник может заявить, что данный код идентифицирует не ваш пост "путешествие", а его статью "100500 лайфхаков успешных людей". Но у этой проблемы есть решение.

В качестве идентификатора роли можно использовать криптохэш от полного описания роли на момент её создания.

Вы пишете пост "путешествие". Его содержимое плюс дата и подпись описывают как роль, так и инициальное состояние/значение этой роли. Далее для идентификации поста можно использовать криптохэш от его же блоба (например, role_sha256). Который изначально совпадает с идентификатором версии (например, data_sha256). Спустя пару дней вы редактируете пост, указывая, что новый документ представляет собой актуальную версию поста с таким-то role_sha256, но data_sha256 будет уже от блоба новой версии. А в ссылках на пост "путешествие" можно одновременно указывать и role_sha256, и data_sha256 той версии, которая была актуальна на момент создания ссылки. Если реципиентов устраивает подпись на новой версии (в большинстве случаев достаточно, чтобы это была та же подпись, что на первой), то они её принимают как актуальную.

Далее, у документов не обязательно только одна роль. Можно создать роль "Блог Васи" - описание, дата, подпись, посчитали sha256 от блоба. И далее указывать это значение как (например) role_of_whole_sha256 во всех постах блога. Можно отдельными документами создавать дайджесты - полные списки постов (и их актуальных версий) такого-то блога в разные моменты времени. Само описание роли может измениться со временем, и сменить название блога на "Блог Васи о путешествиях", не меняя идентификации. Таким образом решается вечная проблема Wikipedia, где при смене названий статей или вставке disambiguation pages часто остаются поломанные ссылки. Более того, "Блог Васи" может превратиться в "Блог Васи и Маши", если новое состояние этой роли содержит некое указание, что в блог теперь можно писать и с подписью Маши, а не только с подписью Васи.

В пределе описание роли может содержать смарт-контракт, описывающий все возможности изменения состояний, её представляющих. Однако, в большинстве случаев достаточно самого наличия первой версии документа и указания role_sha256 в любых последующих/альтернативных.
flow

Настоящие и фальшивые альтернативы вебу

Наряду с децентрализованными решениями по обмену информацией (тема, которая поднималась в https://justy-tylor.livejournal.com/257216.html), есть и противоположная тенденция - попытки создать решения, ещё больше отрывающие пользователя от своих данных и идентификации, путём создания федераций серверов, которым предлагается всё это передавать.

Причём, авторы этих предложений также используют риторику о децентрализации, но неуклонно сводят решение к замене "неправильной" олигополии интернет-гигантов на "правильную" монополию федерации. Ранее мне казалось, что это ошибка в рассуждениях, люди думают как привыкли. Но сейчас чётко осознал, что такая подмена делается намеренно, будь то очередные метания Тима Бернерса-Ли в виде SOLID или иные самобытные инициативы вроде https://mi3ch.livejournal.com/5043877.html

Основой экономики интернета является реклама. Те же Google и Facebook это формально технологические компании, но почти весь их доход это реклама (более 80% в случае Google, более 95% в случае Facebook). Вторая ниша это подписки и продажа контента (paywall), где основные доходы у онлайн-кинотеатров вроде Netflix, а основной шум и срачи создают отсталые новостные медиа.

Если у пользователя есть возможность получить данные не с "авторизованного сервера", а от соседа на флэшке или через DHT, то экономика меняется. Нет централизованных "просмотров" и "подписчиков". Некуда поставить paywall. Рекламный рынок преобразуется - исчезают самые массовые CPM и CPC механизмы, остаются только CPA и имиджевая реклама "звезда пользуется продукцией нашего бренда". Остаются донаты.

Так что, настоящая децентрализация это хорошо для всех, но не для всего. Однако, её можно совмещать с существующими коммерческими решениями. Если вы сняли видео и хотите донести его до широкой аудитории, то самый действенный вариант это одновременно опубликовать его и в децентрализованных сетях на базе DHT, где доступность будет зависеть от востребованности, и в традиционных сервисах вроде YouTube, где доступность обеспечивается за шанс показать рекламу, но контент могут в любой момент удалить из-за действий злоумышленников или внутренних ошибок копираст-бота. А если ваш заработок зависит от показов и подписчиков, то можете отложить официальную публикацию в децентрализованной сети на пару недель, всё равно получая максимум выгоды из двух миров.

Децентрализованные сервисы - без цензуры и без части способов монетизации контента - альтернативны, они не требуют перестраивать существующие коммерческие. Да, при развитии альтернатив тот же Facebook будет терять разумных пользователей и выручку, но это лишь повторит историю Myspace.

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

My comment to an entry 'Пора выпускать из пробирки лёд-9? (1/x)' by bacr

Тоже размышлял на эти темы ещё с 2010, когда начал заниматься темой интеграции данных, где необходимость поддержки альтернативных миров/версий естественным образом приводит к требованиям децентрализации. Основные выводы таковы:

1. Для обмена данными наиболее важны не протоколы, а форматы. Желательно бинарные бандлы с документами, где на каждом уровне поддерживаются произвольные бинарные вложения (с дедупликацией в пределах бандла), метаданные и подписи. И не важно, как они пришли — через решения на базе DHT, на флэшке или были скачаны с обычного сайта как "библиотека научных статей такого-то автора". Если контент подходит под критерии интересующего, а подписи под критерии приемлемого, значит данные полезны. API запросов, подписок и публикаций, а также их транспортные протоколы, могут различаться. Например, таким разным узлам как "база знаний компании" и "сервер агрегации обновлений" нужны разные их подмножества, и если разработчики стандарта увлекаются одним из случаев, то стандарт оказывается непригодным для других. Кстати, независимость формата и протоколов успешно работала ещё в фидо, где можно было раздельно выбирать мейлеры (с разным транспортом) и тоссеры. А вот в современных попытках решений на протоколы конкретно залипают.

2. Необходима система идентификации многоверсионных данных. Однако, подходы со случайными айди и синтетическими подобиями файловой системы создают лишний когнитивный мусор. Более того, для многих данных (таких как посты или комментарии в соцсетях) заранее неизвестно, будут ли они перезаписаны новыми (или дописаны альтернативными) версиями. Решение я нашёл в 2017 году, подробнее об этом в https://justy-tylor.livejournal.com/252597.html В частности, таким образом легко разделяются деревья обновлённых/альтернативных версий статей для разных сущностей с одинаковыми именами в вики (или наоборот, продолжается то же дерево, когда меняется основное имя статьи).

3. Начинать следует не с сети, а с локального пользователя. Может он создать у себя заметку о недавно прочитанной научной публикации и прикрепить туда pdf самой публикации через криптохэш (с учётом этой ссылки в локальном content-addressable storage)? Если да — хорошо, это идеально масштабируется до децентрализованной многопользовательской системы (как пример — ранние стадии развития git). Если нет, и требуются некие действия с сетью, либо меняется идентификация документа между локальным и "опубликованным" представлением, то неминуемо повторение сегодняшней веб-помойки.

View the entire thread this comment is a part of

flow

2019 - Компиляторное

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

Фактически, у меня не компилятор "алгоритмов и структур данных", а компилятор произвольных пользовательских требований, где основной проход это requirements gathering. В любой точке исходников, где доступен какой-либо тип, к этому типу могут быть добавлены новые требования, подобно тому как новая бизнес-логика добавляет триггеры в базе данных к существующей старой схеме. Для достижения этого типы и модули должны во время requirement gathering находиться в "многомировой" интерпретации, позволяя ситуации вроде нескольких одноимённых полей в типе, из которых при обращении выбирается нужное для контекста, а не привычный вариант с "заранее выкинуть остальные по ifdef". Если преждевременно создать варианты какого-нибудь типа Entity для нескольких контекстов (натив на сервере, SQL в базе данных, JS на клиенте), то и требования придётся дописывать к каждому из. Кроме того, не все из этих требований будут нужны в выбранном контексте. Например, какие-нибудь хинты по memory layout не являются условными, но применимы только в нативе. Теперь с этим хорошо.

Далее я сделал паузу, чтобы разобраться с другой темой. Синтез конфигураций, упомянутый в https://justy-tylor.livejournal.com/255577.html

Сначала я написал алгоритм с применением необычной many-valued логики, который плющит конфигурации. Затем подобрал удобный способ объявлять правила в мейнстримных языках программирования, не требующий интеграции логических движков. Для правил с простыми фильтрами и множествами - способы редактировать в UI и хранить в базе данных. И даже подход к решению Frame problem. В общем, увлёкся, благо легко и весело.

Но дальше оказалось хитрее. Окей, вот конфигурации в типах, типы наследуются, конфигурации в них плющатся, всё в порядке, ручного описания приоритетов конфигураций не требуется. Однако, программа или модуль при этом получается конфигурацией конфигураций. Даже тип это конфигурация конфигураций в тех случаях, когда язык содержит мощные инструменты кастомизации (как redeclare или constrainedby в Modelica). Есть ли для такой ситуации взаимодействия нескольких иерархий единый правильный способ вывода последовательности для "плющить", покрывающий все интересующие меня кейсы (сразу или с минимальной дополнительной разметкой)? Или потребуется модификация самого алгоритма? Или почти всё автоматически, но иногда с ручными приоритетами? Нарисовал кучу возможных решений, далее предстоит оценить и выбрать что-то работающее. Что, помимо прочего, хорошо повлияет на систему типов и систему модулей в языке.

С такими мыслями сейчас завершаю "компиляторный" 2019. А "танцевальный" и прочие пока продолжаются.
flow

Пользовательские идентификаторы-литералы

Когда-то давно (15 лет назад) я делал наброски языка разметки текстов. С использованием квадратных скобок [] для тэгов и фигурных {} для ссылок на какие-либо термины. Фактически, как в Wikitext для ссылок используется синтаксис [[имя статьи]], так и там {термин} или {имя статьи}. Но проблема, побудившая меня на размышления о решении, была одноразовой (помогал коллегам с восстановлением/переносом интранет-портала), а далее решений и полурешений в этой нише стало достаточно, чтобы к этому не возвращаться.

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

Чаще всего это будет полезно для URL: {https://en.wikipedia.org/}. Другая библиотека может распознавать даты по ISO 8601: {2019-12-17}. Или IPv4 и IPv6: {127.0.0.1}, {::1}. Пути в файловой системе (с автоматическим контролем целостности данных), UUID, что угодно, пока нет противоречий между используемыми библиотеками. Вплоть до тех же {термин} или {имя статьи}, если это уместно.

И кстати, сюда же прекрасно помещаются идентификации по IEC 81346. На эту тему мы много спорили в чатах с ailev, который утверждал о необходимости поддержки IEC 81346 на уровне языка, что, на мой взгляд, превращает любой язык в нишевую самобытную игрушку для инженеров. Однако, использования различных {=J1=HE01} как ещё одного доступного способа идентификации (при использовании библиотеки, распознающей IEC 81346) решает это противоречие, фича для одних не мешает другим.

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

Данное решение не ограничено спецификой моих разработок, оно подойдёт для любого языка, где возможна работа пользовательских библиотек в compile time или (с меньшей надёжностью) используется динамическая типизация. Но в случае "все скобочки уже заняты" будет выглядеть чуть менее элегантно.
flow

Польза из сочетания случайностей

Живя в городах мы привыкли к сквозной нумерации домов, "улица такая-то, дом такой-то". Мы знаем, что с большой вероятностью найдём дом 6 между домами 4 и 8, при этом дом 7 будет на противоположной стороне улицы, а дом 32 где-то вдали, в том же направлении, что от 6 к 8. Это удобно.

Однако, такой подход работает только при сочетании нескольких факторов:
1. Квартальная городская застройка (а не "микрорайонная с пустырями", например).
2. Грамотность пользователя, который должен уметь читать и считать. Начиная с двадцатого века мы воспринимаем это как данность, но так было не всегда. Да и сейчас трудности с распознаванием латиницы или кириллицы могут быть, например, у туриста из Китая.
3. Традиция и практика размещения хорошо читаемых табличек с номерами домов.

Ок, у нас есть грамотные пользователи и мы можем так строить. Эти условия сложились случайно, независимо от нас. Можно добавить сквозную нумерацию домов и получить пользу.

Мне кажется, что данный пример хорошо показывает работу архитектора информационных систем - нахождение новой пользы в существующей случайной данности. Да и работу инженера/изобретателя вообще.
flow

Merkle tree для идентификации

Криптохэши прекрасно подходят для идентификации статичных данных. Запросили из content-addressable storage (CAS) файлик (точнее blob) по криптохэшу, вот он пришёл, всё можно проверить, ничего нельзя подменить (с поправкой на стойкость криптохэш-функции). Но проверить можно только целиком. А если идентификация не совпала - можно попробовать перекачать, снова целиком, так как неизвестно, какие фрагменты скачаны с ошибками. Для мелких данных ок, для гигабайтных блобов уже нет. Стандартный приём - построить Merkle tree, на нижнем уровне считая криптохэши от фрагментов в N байт, а на каждом следующем криптохэш от списка криптохэшей предыдущего уровня.

Как идентифицировать выбранный алгоритм построения Merkle tree (учитывая разные возможные подходы)? На мой взгляд, удобно задать Merkle tree через криптохэш-функцию и параметр N как максимальный размер и фрагментов данных, и неразрывных фрагментов списков криптохэшей. Например, выбрали SHA-256 и N = 64KiB (2**16) - это фрагменты до 65536 байт данных на нижнем уровне и до 2048 полных криптохэшей SHA-256 на верхних. Тогда получившуюся функцию можно обозначить как SHA-256-P64K (или sha256p64k). При таком подходе идентификация блобов до 64KiB включительно совпадёт с SHA-256, идентификация от 64KiB+1 до 128MiB включительно потребует одного уровня косвенности, и так далее. Обращаемся к CAS, получаем по SHA-256-P64K содержимое файла или карту фрагментов следующего уровня, которые можно параллельно скачивать и проверять, хоть с этого же CAS (с любым приемлемым количеством соединений), хоть с других доверенных источников.

Людей, знакомых с рассматриваемыми технологиями, могла насторожить фраза "идентификация блобов до 64KiB включительно совпадёт с SHA-256". Каждый уровень Merkle tree принято наделять маркером, используемом при вычислении криптохэша на этом уровне. Можно, например, вставить байт 00 перед вычислением криптохэшей от фрагментов данных, байт 01 перед вычислением криптохэшей от фрагментов списков криптохэшей нижнего уровня, и так далее. Без этого идентификация через Merkle tree теряет уникальность, те же байты могут идентифицировать и сами данные, и их "карту", чем могут воспользоваться злоумышленники.

Но я вижу и другое решение. Вместо использования уровня косвенности в качестве префикса при вычислении каждого конкретного криптохэша - использовать это значение в операции xor с последним байтом получаемого криптохэша. В этом случае (для примера с SHA-256-P64K) фрагменты блобов на нижнем уровне будут идентифицироваться по SHA-256, фрагменты списков криптохэшей на следующем - по результату SHA-256 с (hash[31] ^= 1), и так далее с (hash[31] ^= indirection_level). Такая операция возвращает уникальность и обладает тем интересным свойством, что идентификация данных какого-либо уровня и их "карты" расходятся только в последнем байте. Что упрощает отладку и поддержку CAS.

Покрутил я эту модель, прикинул различные сценарии поведения (вплоть до случаев memory error, с учётом прочих метаданных в CAS), и пока выглядит оптимально. Если у вас есть свои соображения - пишите. Чуть позже напишу продолжение об идентификации не-статичных данных.