Category: it

Category was added automatically. Read all entries about "it".

with Cat The Cat

Современное программирование.

В течении лет шести-семи в начале моей трудовой деятельности моим предпочтительным инструментом был ассемблер, конкретно, Turbo Assembler. Практически всё я писал на ассемблере и до сих пор горжусь выводом сжатых изображений с кодированием последовательностей (не)прозрачности для VGA - код не использовал переменные на стеке, даже сохранения регистров на стеке не было, да и данных надо было пересылать меньше.

Так вот.

Современные технологии недалеко ушли от моего любимого tasm.

Если там я следил за регистрами, то сейчас я слежу за другими эффектами - cudaMallocManaged((void**)некий_массив_объявленный_static, ...) из последнего приключения в субботу, в процессе перевода программы на Си в программу на CUDA.

До этого был язык Regent, где надо было понимать, что это такой код на Lua, а не декларативное описание решения задачи. До этого Legion на C++. До этого ANTLR4, который сваливался до скорости синтаксического разбора в 4 килобайта в секунду (!!!), если ему не нравилось то, как грамматика языка используется программистами. И C#, который не умел видеть сквозь функции высших порядков.

И так далее, и тому подобное.

В современном Хаскеле это тоже присутствует, только больше в инфраструктуре, чем в языке. Хотя и язык тоже добавляет радости: "Haskell is very pragmatic language. You have to startyour program with at least dozen of LANGUAGE pragmas". Вот зачем специально надо разрешать вывод любых реализаций для newtype? Чему мешает постоянное включение этой возможности?

Не то, чтобы я жаловался - это же часть приключения. Как расследование преступлений Джека Потрошителя обязательно должно включать в себя путешествие по лондонской канализации, так и программирование должно включать борьбу с эффектами разного рода, от проблем языков программирования до разбора FIX.

Просто наблюдение.
with Cat The Cat

Блокчейны

Вдогонку к предыдущему.

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

Исключение составляет bitcoin, одно из. Ну, он один из первых и довольно дубоват. Это понятно, поскольку до него никто ничего такого не делал.

Второе исключение - Avalanche. Этот интересен тем, что блокчейн-как-всё-на-свете у него вторичен (последний протокол из пачки), а консенсус достигается практически без использования шифрования.
with Cat The Cat

Блокчейны

Познакомили меня коллеги с системой Ergo: https://ergoplatform.org/en/

Общее описание вот тут.

Интересна она тем, что она основана на "доказательстве работы" и алгоритм использует секретный ключ (sk) добытчика для вычислений доказательства. Использование секретного ключа должно гарантировать невозможность создания кооперативов по выработке доказательств.

Внутри алгоритм выглядит вот так, примерно:

1. Создаём пару секретный-открытый ключи w и x (x - секретный)
2. Сперва просчитываем массив размером в N=226 элементов. Вычисляется он на основе открытого ключа добытчика pk и w.
3. Крутим цикл:
4.   вычисляем одноразовый номер
5.   на основе криптосуммы текущего блока и одноразового номера получаем k=32 индекса в массиве, вычисленном на шаге 2.
6.   считаем дельту d=(сумма по i=1..k (массив[i-й индекс в массиве] * x) - sk) mod q
7.   если дельта меньше порога b, возвращаем кортеж из (криптосумма блока, открытый ключ добытчика, w, одноразовый номер, дельта)
8.   продолжаем цикл

Мы можем представить вычисление выше, как отображение из списка одноразовых номеров в список элементов Maybe (кортеж результата). Далее обычный scanl позволяет получить результат.

Чем это ценно?

something `mappend` otherthing для значений из Maybe a, где a имеет фиксированный размер в битах (как в алгоритме выше) может быть представлено схемой - дополняем кортеж одним битом со смыслом "есть данные" и далее производим выбор варианта с данными с помощью функции выбора.

Чем ценно это?

Если мы можем представить вычисление (или часть его) в виде схемы, мы можем применять гомоморфное шифрование - побитовые операции над шифрованными данными.

В частности, в алгоритме выше надо гомоморфно шифровать шаги 6 и 7. Членам кооператива добытчиков надо раздать шифрованные x и sk, и предоставить константы 0 и 1 для представления на вход гомоморфных вычислений данных, вычисленных обычным способом (массив, индексы, результат выборки из массива).

Что это означает?

Это означает принципиальную возможность создания коллектива добытчиков. Мы раздаём членам коллектива шифрованные данные, и они производят вычисления по нескольким итерациям цикла и отдают результаты (свёрнутые с помощью mappend) владельцу кооператива. Последний расшифровывает данные и формирует доказательство, если оно было вычислено.

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

В общем описании системы про гомоморфное шифрование упоминаний нет.

Вдогонку - если использовать bit-sliced представление для выполнения гомоморфно-шифрованных вычислений, то просто на ровном месте можно получить ускорение в пару-пяток десятков раз. Это делает предложенный метод ещё более вероятным, не говоря уж про ASIC.
with Cat The Cat

Просуммирую опыт.

Современное состояние дел с программированием на Haskell чрезвычайно и требует скорейшего вмешательства высших сил.

Наличие cabal файлов и составление проектов из них, вкупе с текущей реализацией самого cabal, делает невозможным программирование с исследованием (exploratory programming). Потому, что вы, сделав cabal (new-)repl в текущем проекте, не можете простым образом загрузить файл из проекта, который использован в зависимостях вашего проекта.

В переводе на русский, если ваш проект содержит ссылку на проект abanamat с Control.Abanamat, который использует Funck.Russian из проекта funcking-i18n, то вы не можете выполнить ":m Funck.Russian" напрямую - надо переходить в другой проект. Таким образом, для понимания работы требуется больше движений, чем надо.

Так же, cabal местами чрезвычайно "последовательный". Из недавнего - я ждал порядка 15 минут окончания выполнения тестов happy, а ещё через некоторое время - окончание тестов alex, тоже заметные минуты. В это время ничего не собиралось. Ну, и даже на ноутбуке с 16Г памяти надо ограничивать параллельность оного кабала - иначе вы в обязательном порядке напоритесь на работу нескольких сборщиков (ld - он долгий!) одновременно, что вызовет откачку памяти и неработоспособность системы в целом. Приятная такая вишенка на торте.

Теперь перейдём к определению зависимостей внутри пакетов. На самом деле никого не интересует, какая версия у пакета. Интересна функциональность. Есть ли у функции sdL из пакета butic второй параметр с типом Zefirity, или нет? А что, если в версии 0.1 он был, потом, в версиях с 0.2.3 до 183.7.15.144 включительно его не было, а в версии 192.6 он снова появился? Надо ли мне ограничивать версии пакетов с помощью связей вида butic >= 192.6 || butic < 0.2.3? Или мне надо указать, что в sdL второй параметр должен иметь тип Zefirity? Или, вообще, "вот такой тест должен выполняться".

Я очень странно себя чувствую. Вроде бы, по всем ощущениям не Хаскель начала 2000-х, но, почему-то, я всё равно продуктивен. Но от ощущения "я мог бы и больше" избавиться не удаётся.
with Cat The Cat

Интересный опыт

Принял участи в телеграммном обсуждение под заголовком Haskell.

Покинул последнее по следующим причинам:

1. слишком часто отвлекался на обсуждение само по себе;
2. слишком часто принимал участие в обсуждении чего-то, что не могло принести пользу читателям;
3. мой комментарий со смыслом "используя Хаскель, как средство обучения, можно узнать много нового и, в результате, получать большую зарплату" был расценён некоторыми участниками обсуждения, как известный мем "сперва добейся" и даже появились призывы к бану.

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

Я думаю принести пользу как-то ещё.
with Cat The Cat

Поржать.

https://matloff.wordpress.com/2018/06/20/neural-networks-are-essentially-polynomial-regression/ - нейронки смело уподоблены полиномам, причём полиномы добиваются схожей точности при степени полинома 2. По мнению авторов, поскольку на каждом следующем слое степень полинома перемножаются, это приводит к переобучению.

https://arxiv.org/abs/1611.03530 - современные нейронки свободно учатся на случайных метках в тренировочных данных, достигая нулевой ошибки предсказания на них.
with Cat The Cat

Ещё пример.

Рассматривая инструмент (язык программирования), можно смотреть на квадрат "(не) позволяет (не) делать".

Позволяет ли инструмент делать полезное? Позволяет ли инструмент не делать вредное или бесполезное? С отрицанием перед глаголом "позволять" труднее, поэтому сменю вид вопроса. Инструмент не позволяет делать бесполезное или бесполезное - насколько это правда? Инструмент не позволяет не делать нужное и/или важное - насколько это правда?

Между "позволяет не делать" и "не позволяет делать" есть разница. Первое это вероятная экономия усилий, второе - прямой запрет. Первое это "позволяет не делать лишних движений, на которые тратится время". Второе это "не сможете потратить лишнее время".
with Cat The Cat

Эксперимент.

А что будет, если мы попробуем приблизить градиент случайными векторами?

(проверяю идеи)

Collapse )

Предел получается в районе обратного корня из 2. Это разумно ожидать. До косинуса, равного половине, мы добираемся за выборку, равную трети от размерности вектора. Четверть - где-то в районе 7%, пятая часть - 4,7%. Снижая скорость приближения, мы можем уменьшить количество вычислений.

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

Мне не нравится градиентный спуск, как его применяют сейчас. Он был придуман, в его современной форме, из-за ограниченности ресурсов (особенно learning rate) и уже довольно давно. У него есть проблемы со значениями и он плохо применим в новых системах (то самое обучение подкреплением). Поэтому я и пытаюсь получить что-то другое. Две вещи, которые мне очень не нравятся, это скорость обучения (learning rate) и обратное распространение ошибок (backpropagation). Обе они подозрительны мне из-за связанной с ними магии - для скорости обучения придумывают вычурные "расписания" (learning rate cosine schedule, например), обратное распространение ошибок требует хитрых приведений (batch normalization, ADAM и тп), чтобы оно обучало более-менее быстро на современных данных.
with Cat The Cat

Сложение-Вращение-ИсключающееИЛИ

или Add-Rotate-Xor - базовые блоки построения криптографических функций, от поточного шифрования до криптосумм (пример SipHash).

Я тут с этим экспериментирую, пока болею.

Пока вывод один - любая константа важна. Вроде бы, вращать на 17 позиций должно быть неважно, в какую сторону, однако практика показывает, что это не так.
with Cat The Cat

Случайный поиск.

https://thegradient.pub/why-rl-is-flawed/

Там про "обучение подкреплением", и в процессе рассматриваются методы, отличные от градиентного спуска. Вкратце, случайный поиск вполне себе сравним с градиентным спуском и даже превосходит его.