flow

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

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

Фактически, у меня не компилятор "алгоритмов и структур данных", а компилятор произвольных пользовательских требований, где основной проход это requirement 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), и пока выглядит оптимально. Если у вас есть свои соображения - пишите. Чуть позже напишу продолжение об идентификации не-статичных данных.
flow

Забавное


A Talk Near the Future of Python

Содержание: опытный джедай на виду у юных падаванов пишет простейшую VM на Python. Потом лёгким движением руки превращает эту VM в полнофункциональную VM для WebAssembly, которая запускает геймкод скомпилированный из Rust, используя pygame вместо вызовов JS/canvas.

Хорошего пятничного просмотра.
flow

Исследования-дыбр

После некоторого перерыва (включавшего как летние танцы/приключения, так и дела) продолжаю с компилятором. Не секрет (уже мелькало в чатах), что разработка прототипа ведётся на C#. Лет 5 назад я бы сам удивился такому решению, но сейчас .NET это прямо из коробки открытая и кроссплатформенная экосистема, дающая желаемую скорость итераций в exploratory programming.

Параллельно всплыла ещё одна тема - динамический синтез единой конфигурации из разрозненных (и местами противоречивых) требований. Управление правами доступа (к сущностям в базе данных или файлам на диске), описание правил сборки ПО, интеграция каких-либо сервисов или приложений в операционную систему, интеграция плагинов в расширяемый программный продукт - всё это работа с фрагментами требований, авторы которых не могут предсказать содержимого фрагментов из других источников на целевой системе, намерений, с которыми они созданы, а также всего множества ситуаций, возникающих при взаимодействии двух и более фрагментов. Похоже, что мне удалось подобрать представление фактов и алгоритм вывода, работающий с такими фрагментами независимо от предметной области, и дающий интуитивно понятные (а также идеально воспроизводимые на тех же исходных данных) результаты интеграции конфигураций. Ещё в 2011 году, когда мы работали над .15926, vvagr задал мне вопрос, можно ли логикой (а не вставкой extension points и кода на Python) описывать расширения и кастомизацию UI продукта. Я ответил "наверное да, но настоящего решения пока нет, и его поиск может занять очень долгое время" (добавление интерпретатора Prolog или miniKanren создало бы лишь "иллюзию логики", не решая проблему фрагментарных описаний). А сейчас решение есть. Но на 8 лет позже. И хоть и может быть применено в компиляторе (про который в абзаце выше) в какой-то момент, но к разработке ядра компилятора отношения не имеет. В общем, хорошо что случилось, чуть жаль, что только "сейчас", а не "тогда".

Также, продолжил старую тему идентификации криптохэшами, начатую в https://justy-tylor.livejournal.com/252597.html Как по части 4D-идентификации ролей, так и по части идентификации данных для content-addressable storage. Но это заслуживает отдельного поста.
flow

Когда требуется больше времени

В 2013 году я "завершил" интеграционную часть своего исследования в области языков программирования и моделирования. 8 месяцев (при 6 планировавшихся) переосмысления и интеграции знаний, которые десятилетиями накапливались человечеством и годами собирались мной, когда-то как хобби, а затем и целенаправленно. Цель была: вывести набор решений для создания языка программирования следующего поколения и перейти к созданию прототипа.

Предпосылки к успешности данной затеи:
1. Более 30 лет появления новых знаний со времён тех идей, на которых базируется сегодняшнее поколение, а также более полная доступность (благодаря интернету) архивных материалов.
2. Моё желание воспользоваться всем этим опытом прошлого. Как, опять же, показывает история: создатели языков чаще концентрируются на создании "better X with Y", игнорируя большую часть опыта за пределами своей привычной ниши, чем и обуславливается "топтание на месте", а местами и деградация в этой области. Видеть целое это возможность цельно решать существующие проблемы, а не создавать локальные нишевые заплатки.

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

И тогда, в 2013, когда необходимая информация была выведена, я приступил к созданию прототипа компилятора. Началось бодро. Но что-то пошло не так. Я обнаружил, что пишу очередной гибридный язык, как Scala, Nemerle или сегодняшние Kotlin и Swift, но с уклоном в расширяемость. И что пишу очередной "компромисный" компилятор, где прибитые гвоздями фичи выглядят логично с точки зрения основного языка, но снижают потенциал развития. В то же время, накопленные за годы знания продолжали работать, приводя к удобным новым решениям, которые прекрасно подходили в виде EDSL-библиотечки на "допишу позже", но противоречили сложившимся дизайнам и коду прототипа уже сейчас.

Так проявилась моя ошибка. Недостаточно просто создать платформу, обеспечивающую бесшовные переходы между воплощениями "успешных идей прошлого" в виде EDSL. Интеграция старых идей порождает новые, лучше. Так разработка приостанавливается. Пишется следующий прототип, но в процессе требования опять меняются. Становится ясно, что разработка преждевременна.

С тех пор прошло 6 лет, из которых многие сотни часов были затрачены на новое исследование. Не совмещение старых успешных подходов в одном языке, а синтез новых, заменяющих как старые, так и "белые пятна" между ними. Более того, полученные таким образом дизайны также сменялись множество раз. Как и дизайн компилятора, который поначалу никак не дотягивал до желаемой системы обработки независимых правил.

Прошлым летом дизайны ещё раз изменились кардинально, но с тех пор скорее дополнялись. Модель компиляции в части совмещения независимых правил и решения противоречий OWA и CWA (open world assumption и closed world assumption) выглядит оптимально. Время действовать.

На этой неделе я начал работать над прототипом нового компилятора. С обновлёнными силами и навыками.

Планировалость одно исследование на 6 месяцев. Получилось другое на 6 лет. 6M6Y. В чём-то как 3D2Y в One Piece.
Luffy_Pays_His_Respects.png
flow

Чтение 2018

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

В прочитанной же публицистике особенно зацепили две книги:

1. Yuval Noah Harari "Homo Deus: A Brief History of Tomorrow" (Юваль Ной Харари "Homo Deus: Краткая история завтрашнего дня"). Футурология - жанр на грани между фантастикой и реальностью, требующий от автора как хорошего понимания "здесь и сейчас", так и достаточного полёта фантазии в вариативности "завтра" (не повторения чего-то вроде "на дискету поместится библиотека"). Так что достойных книг в нём почти нет. Эта - редчайшее приятное исключение, хотя и менее крута, чем "Сумма технологии" Лема.

2. Jordan Ellenberg "How Not to Be Wrong: The Power of Mathematical Thinking" (Джордан Элленберг "Как не ошибаться. Сила математического мышления"). Несмотря на название, книгу с которым в магазине сразу поставят в раздел "популяризация науки", данное произведение не имеет ничего общего с работами клоунов вроде Гладуэлла. Это крепкая прикладная литература, в которой примеры и случаи из реального мира представлены не для удивления читателя, а в качестве моделей для применения математического аппарата, и историй его развития. Книга, способная не только наделить обычного человека знакомством с определёнными разделами математики и логики, но и улучшить связь математика с реальностью.
flow

Немного эволюции в визуальщине

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

Antimony CAD. Это практически неизвестный широкой публике хобби-продукт под Linux/macOs, но в сети можно найти пару демонстрационных видео:
https://vimeo.com/125111378
https://www.youtube.com/watch?v=uigjofZ_3HM

И так, ключевые преимущества:
1. Входные и выходные порты в одной колонке.
2. Входные порты также являются и выходными, в большинстве случаев.

Пункт [1] просто улучшает читаемость. Что же даёт [2]? При использовании визуальных средств "с портами", как правило, ваши намерения и спецификации могут быть воплощены лишь с потерями. Вы не можете заявить "Node1.N = что-то" и "Node2.N = Node1.N". Вам придётся вводить сторонние общие ноды с "ёжиками" связей. И это не только ухудшает читаемость схемы, но и отдаляет имплементацию от спецификации. В Antimony же эта проблема решена.

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

Селфи, безопасность и децентрализация репутаций

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

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

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

Исключение ботов является задачей любого честного скоринга. С прочими посторонними людьми чуть хитрее. Чьё мнение важно для меня в какой-то ситуации? Зависит и от моих личных приоритетов, и от специфики ситуации. Это требует как персонификации скоринга под использование конкретным человеком, так и включения в систему оценок людьми других людей как экспертов в какой-либо области. Да, пока один настоящий эксперт подтверждает квалификацию другого, где-то рядом происходит классическое "За что же, не боясь греха, Кукушка хвалит Петуха? За то, что хвалит он Кукушку". Однако, такие оценки концентрируются в острова связей, и имея априорное знание о некоторых экспертах можно отличить соответствующие острова экспертов от островов "кукушек".

В любой своей цифровой активности человек может быть представлен сертификатом с открытым ключём. Для децентрализованного подтверждения такого сертификата (да, ключ "nn nn ..." принадлежит такому-то Иванову Ивану Ивановичу) существует Web of Trust. А экспертные оценки могут быть подписаны уже подтверждёнными ключами. Уже сейчас это можно делать. Но достаточно ли надёжно? Нет. Web of Trust создавалась для определённой гик-тусовки, не для массового использования. Если подписанный сертификат не только используется для сетевого общения, а хоть где-то может быть учтён как отдельный голос и повлиять на скоринг, то среда сертификатов будет наводнена ботами, подписывающими друг друга. Для избежания этого требуются дополнительные меры.

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

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

3. Для исключения операций "задним числом" (а также сохранения возможности доверять подписям в старых документах, если достоверно известно, что ключ был украден и применён злоумышленниками не ранее определённой даты) можно использовать блокчейн. Здесь тоже есть своя специфика. Если консенсус базируется на proof of work или proof of stake, то организаторы премайна и (что хуже) "мошенники с электростанцией" получают серьёзные преимущества в контроле над системой и могут нарушить децентрализацию. Более устойчивым может быть вариант, опирающийся на индивидуальное доверие участников сети к неким ключевым нодам. Ведь даже в случае раскола сети вполне можно одновременно пользоваться двумя образовавшимися ветками (с разными критериями скоринга), или просто проигнорировать одну из них как ботоводческую.

Создают ли эти усовершенствования, в частности, использования фотографий, новые риски безопасности? Нет. Но подвержены старым рискам, сопровождающим любого пользователя социальных сетей. Информация о ваших связях, встречах и прочей активности становится доступна широкому кругу акторов с не самыми благими намерениями. Если в каких-то аспектах жизни это не устраивает - следует использовать там другие ключи и самоидентификации.

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