Russian Lambda Planet

22 июня 2016

Dee Mon journal

generic fourth-order Runge-Kutta method

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

type alias DiffVecSpace v = {
  timeDerivative : v -> v,
  mulByFloat : Float -> v -> v,
  add : v -> v -> v
}

evolveRK : DiffVecSpace v -> Float -> v -> v
evolveRK ops dt state = 
  let a = ops.timeDerivative state
      b = ops.add state (ops.mulByFloat (dt/2) a) |> ops.timeDerivative
      c = ops.add state (ops.mulByFloat (dt/2) b) |> ops.timeDerivative
      d = ops.add state (ops.mulByFloat dt c) |> ops.timeDerivative
  in List.foldl ops.add state [ops.mulByFloat (dt/6) a,
                               ops.mulByFloat (dt/3) b,
                               ops.mulByFloat (dt/3) c,
                               ops.mulByFloat (dt/6) d]


(тут на Elm'e)
Если выразить на языке с нормальными тайпклассами или ООЯ с определяемыми операторами, получится еще проще. С другой стороны, возможно операцию вычисления производной стоит не вносить в тайпкласс, а передавать явно. Тогда можно для одного типа состояния считать его эволюцию при разных внешних условиях (разных методах вычисления сил/ускорений/операторов/whatever), что у меня активно используется в программе.

22 июня 2016, 06:37

Elm 0.17

Elm - это хаскелеподобный чистый функциональный язык для всяких безобразий в браузере, т.е. "компилирующийся" в JavaScript. Знаменит прежде всего тем, что на нем написан визуализатор квантовой механики из предыдущего поста. :)
Три года назад я писал про тогдашний Elm, с тех пор он заметно изменился, а в последней на сегодня версии произошло существенное изменение в архитектуре, отчего большая часть старого кода и описаний перестала быть актуальной.
Изначально он появился как воплощение идей FRP, и thesis (дипломную работу?) автора Elm'a я могу всем рекомендовать как замечательное изложение идей и разных подходов к FRP, плавно переходящее в объяснение исходной архитектуры Elm'а (и без этого объяснения научиться тогдашнему Elm'у было трудно). Там вся динамика была построена на идее сигналов, когда есть обычные иммутабельные данные типов A,B,C... и есть отдельная категория типов A',B',C'... описывающих такие же данные, но меняющие свои значения со временем (навроде Time -> A'), и есть функтор Signal из первой категории во вторую. Пишешь чистый код, работающий с простыми иммутальными данными, потом этим функтором лифтишь свои чистые функции в мир динамически меняющихся значений. Есть набор внешних источников событий/данных, вроде координат мыши, т.е. уже живущих во второй категории, и нужно построить в ней функцию из нужных источников событий/данных в некое дерево контролов, элементов. А рантайм уже сам позаботится о том, чтобы все события и новые данные проходили как надо через все преобразования и получающееся на выходе дерево превращалось в DOM страницы. Ну и были во второй категории специальные комбинаторы для обращения с временнЫми потоками данных, вроде соединения, сворачивания и пр.
Потом в Elm'е появились Mailbox'ы и Elm Architecture, в которой программа описывалась двумя функциями view и update и начальным значением пользователького типа Model (содержащего все данные). update получала значение произвольного заданного пользователем типа Action (обычно это перечисление разных действий) и текущее значение модели, возвращала обновленное значение модели, а view отображала значение модели в дерево элементов, принимая одним из параметров "адрес" (значение специального типа Mailbox). Возвращаемые ф-ей view элементы в своих атрибутах могли иметь функции "что делать при нажатии/изменении", эти функции получали тот самый "адрес", чтобы слать свои оповещения туда. Так все оставалось иммутабельным и чистым, а рантайм заботился о доставке всех событий в форме пользовательского типа Action в функцию update, так осуществлялся круговорот событий-реакций в колесе сансары. Как видите, в явном виде сигналы уже не участвовали в Elm Architecture, но в разных API еще оставались.
В свежей версии 0.17 авторы сказали "прощай FRP" и выкинули все сигналы нафиг. И API для построения дерева элементов поменяли заодно. Зато добавили модный способ работы с первоклассными эффектами, как у взрослых. Осталась Elm Architecture, но уже другая. Теперь программа это
program : { init : (model, Cmd msg), 
         update : msg -> model -> (model, Cmd msg), 
         subscriptions : model -> Sub msg, 
         view : model -> Html msg }  -> Program Never

Т.е. описываешь свой тип Model с любыми нужными данными, описываешь свой тип сообщений (как Action раньше), и три функции: view, update и subscriptions. view тупо отображает модель в DOM HTML, но тип дерева элементов параметризован твоим типом сообщений, ибо в атрибутах элементов вставляются функции реакций на события, которые производят значения этого самого типа твоих сообщений. Им теперь не нужно знать ни про какие мэйлбоксы, не нужно туда ничего слать, просто произвести сообщение, рантайм сам знает куда его доставлять. Кроме того есть функция subscriptions, которая исходя из текущего состояния модели говорит, какие внешние события нам интересно слушать, и тип ее ответа тоже параметризован типом наших сообщений, т.к. внешние события приходят в рамках все того же потока сообщений, а когда подписываешься на внешнее событие, говоришь, как его завернуть в твой тип сообшений. Ну и ф-я update, которая получает все эти сообщения твоего типа и меняет модель, а заодно может произвести "команду" - указание рантайму произвести некоторый эффект, подобно значению типа IO Smthng в хаскеле. Выражение действий в виде данных обещает много бенефитов, но я в эту тему пока не вдавался.Вот такой теперь Elm, больше никаких сигналов, но по-прежнему все чисто функционально.
В версии 0.17 зачем-то изменился синтаксис описания модулей, там мелочь поменялась, но из-за нее некоторые библиотеки не собираются, надо одну строчку поменять в заголовке модуля.

А еще в Elm'e неожиданно оказалась встроенная поддержка WebGL: там не просто есть нужная библиотека, а компилятор умеет распарсить текст шейдеров на GLSL и проверить согласованность используемых типов между шейдерами и основной программой! Во-первых, сама библиотека для работы с WebGL более высокоуровневая и намного более удобная в обращении, чем то, что я видел в примерах про WebGL на JavaScript'e. В JS, похоже, просто копировали Си, там даже указатели есть, и приседаний на каждый чих нужно не меньше дюжины. В элмовском модуле WebGL все это безобразие спрятано, а выставлен довольно чистый и удобный API. Программа на Elm'e производит HTML дерево, соответственно конечная точка в WebGL это
toHtml : List (Attribute msg) -> List Renderable -> Html msg
и наша задача произвести список Renderable, которые получаются так:
render
    :  Shader attributes uniforms varyings
    -> Shader {} uniforms varyings
    -> Drawable attributes
    -> uniforms
    -> Renderable

где
type Drawable attributes
    = Triangle (List (attributes, attributes, attributes))
    | Lines (List (attributes, attributes))
    | LineStrip (List attributes)
    ...

Т.е. кусок графики (Renderable) получается из четырех вещей: двух шейдеров (вершин и пикселей), описания геометрии и общих данных для шейдеров. Причем и геометрия, и общие данные описываются пользовательскими типами - что хочешь, то туда и передавай. Например, набор треугольников представлен списком троек, но троек чего? Чего скажешь: хошь координат, хошь более сложных структур. Вертексный шейдер получит значения из этих списков в виде атрибутов - данных, меняющихся от вершины к вершине, а в качестве uniform данных (общих для всех вершин) получит то, что передашь, тут тоже твой тип, сам решаешь. А как в render передать шейдер? Это значение типа Shader attributes uniforms varyings (где все три типа-параметра - твои, какие скажешь), и описывается значение шейдера специальным синтаксисом с текстом шейдера на GLSL. Компилятор посмотрит, какие данные в тексте шейдера описаны как attribute, uniform и varying, и убедится, что они соответствуют полям твоих типов для attributes, uniforms и varyings, что переданы параметрами типу Shader. Тут происходит связь города и деревни, связь кода на Elm и кода на GLSL. Пример из моей программы:
sphVertSh : Shader { attr | position:Vec3, color:Vec3 } { unif | perspective:Mat4, pos:Vec3 } { v:Vec3 }
sphVertSh = [glsl| 

attribute vec3 position;
attribute vec3 color;
uniform mat4 perspective;
uniform vec3 pos;
varying vec3 v;

void main () {
    gl_Position = perspective * vec4(position*0.1 + pos, 1.0);
    v = position; 
}
|]

Такой вершинный шейдер будет вызван для каждой вершины сферы, он получит данные о вершине в виде attribute vec3 position и color, вычислит требуемое значение позиции и заодно запишет что нужно в выходное значение varying v, которое потом пиксельный шейдер получит проинтерполированным себе на вход и будет использовать для вычисления цвета пикселя. Поскольку оба вершинный и пиксельный шейдер передаются вместе в render, типы их uniforms и varyings обязаны совпадать, таким образом компилятор проверит не только то, что я в шейдеры правильные данные передаю, но и что вершинный шейдер производит именно такие данные, которые принимает пиксельный. При том, что тип этих данных я придумываю сам. Если сравните это с JS'ным WebGL или сишным OpenGL, увидите пропасть как в удобстве, так и в уровне статического контроля. Там все намного труднее делается и с минимумом проверок.

Другие впечатления после написания полтыщи строк. Близкий к хаскелю синтаксис и отличный вывод типов в сочетании с referential transparency от чистоты и иммутабельности позволяют очень легко массировать код: любой кусок можно элементарно превратить в функцию, перенести в другое место, параметризовать, при этом не порождается бойлерплейта и впечатления от процесса очень положительные. Компилятор очень шустрый (единственная быстрая программа на хаскеле из мне известных), сообщения об ошибках более чем подробные и ласковые, об этом авторы особенно заботились. В синтаксисе нет where, и это очень хорошо, на мой взгляд. По-прежнему есть что-то вроде встроенных тайпклассов (вроде number), но нельзя описывать свои тайпклассы или добавлять свои инстансы, когда работаешь с комлексными числами об этом сильно жалеешь. Можно описывать свои операторы, но только на самом внешнем уровне, т.е. определить оператор локально (чтобы было замыкание, задействовать значения из текущего скоупа) нельзя, это тоже обидно немножко.
Но общие впечатления очень положительные. Язык стал проще и одновременно удобнее. Компилятор стал стабильнее и вообще образцовый во многих отношениях. Есть очень классный менеджер пакетов и их репозиторий (причем они умеют гарантировать соблюдение логики semver, это отдельная тема). Есть удобная штука elm reactor, навроде debug mode в рельсах, когда поменял исходник, нажал в браузере F5 и все пересобралось и перезапустилось, благо компилируется мгновенно. А еще там удобные record'ы с row polymorphism'ом! О чем еще мечтать? :)

22 июня 2016, 06:09

17 июня 2016

Фонд Поддержки Функционального Программирования

Июньский конкурс по ФП в 2016 году закрывается

Июньский конкурс по ФП в 2016 году закрывается с этого момента. Итоги будут подведены, я надеюсь, в течение недели. Впрочем, победитель уже определён, мне надо просто написать отчёт. Этим и займусь.

написал Dark Magus (noreply@blogger.com) 17 июня 2016, 11:43

13 июня 2016

Евгений Охотников

[prog.flame] Любопытная заметка "Disadvantages of purely functional programming"

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

Имхо, статейка Disadvantages of purely functional programming как раз в эту же тему. Суть -- чистое ФП классная штука, конечно. Но тормозит. И, в принципе, в определенных местах не может не тормозить.

Отдельно отметил бы ссылочку, которая есть в этой статье: Naive parallelism with HLVM. Особенно мне понравились пути повышения производительности HLVM-программы: Disabling bounds checking provides a substantial 20% performance improvement. Disabling the shadow stack (and, therefore, disabling GC) provides another 25% performance improvement. With these two changes, HLVM is only 24% slower than C++. Ну, т.е., берем язык более высокого уровня, чем C++, и гораздо более безопасный, чем C++, а потом отключаем нафиг те фичи, которые как раз и делают его более высокоуровневым и более безопасным. И все только для того, чтобы не тормозить так сильно.

Ну и вообще, как мне кажется, в последние год-полтора прослеживается интересная тенденция: если раньше во главу угла ставилась скорость разработки и на передний план выходили безопасные языки программирования (причем даже не Java, а всякие Python-ы, Ruby, Erlang-и, Scala, Clojure и прочие OCaml-ы с Haskell-ями), то теперь просто скорости разработки мало. Нужно еще, чтобы результат работал быстро и/или жрал мало. Отсюда и интерес к тому же Go, который позволяет писать что-то так же быстро, как и на Python-е, но работает затем это что-то намного эффективнее, чем на Python-е. И возродившийся интерес к старой ламповой сишечке (а так же вспыхивающие вновь споры C vs C++). И пристальное внимание к Rust-у и Nim-у...

Объяснение сей тенденции я вижу в том, что делать быстро на Python-е (Ruby, Erlang, Scala, Clojure,...) теперь могут практически все. И одним из важнейших факторов становится снижение издержек на эксплуатацию. Для чего нужны не только быстро выходящие на рынок решения, но еще и эффективно работающие. А вот это умеют делать пока не только лишь все :)

PS. Кстати говоря, то, что все стараются друг другу что-то продать (кто-то "продает" Haskell, кто-то "продает" Clojure, я, например, "продаю" SObjectizer) -- это нормально. Правильно сделанная "покупка" сильно облегчает жизнь. Однако, важно понимать, что в процессе "продажи" мало кто будет на 100% откровенен и будет честно и по собственной воле рассказывать не только о достоинствах, но и недостатках. Так что никому нельзя верить. Мне можно ;)

PPS. Прошу воспринимать написанный выше текст с изрядной долей юмора и иронии.

написал Yauheni Akhotnikau (noreply@blogger.com) 13 июня 2016, 10:12

10 июня 2016

Фонд Поддержки Функционального Программирования

Июньский конкурс по ФП в 2016 году: плотная упаковка полимино

Сегодня мы запускаем очередной конкурс по функциональному программированию, который как обычно проходит под эгидой Фонда Поддержки Функционального Программирования ФП(ФП) и Научной лаборатории имени светителей Проца и Халикаарна. На этот раз мы займёмся плотной упаковкой полимино в коробки на плоскости.

Возьмите следующий файл с исходными данными:

ФАЙЛ

В этом файле 100 задач. Каждая задача представляет собой поле вида:
111000
111111
111111
011110
011100
011000
Здесь единицы обозначают те места на поле, которые должны быть заполнены фигурами. Фигуры же перечисляются после поля и представляют собой такие же матрицы. Необходимо так расположить фигуры на поле, чтобы они покрыли все единицы поля своими единицами, и ни одной непокрытой единицы не осталось (ну и нули поля не должны покрываться единицами, но это говорить излишне, так как фигуры подобраны так, чтобы при выполнении первого условия второе выполнялось автоматически).

Ваши ответы присылайте мне ссылками на файл с результатами, в котором должно быть 100 строк вида:
(0, 2), (0, 0), (1, 0)
И здесь каждая пара обозначает координаты верхнего левого угла фигуры (по порядку перечисления в файле с заданиями) относительно верхнего левого угла матрицы поля. Также присылайте ссылку на ваше решение (исходный код) и название использованного языка программирования.

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

написал Dark Magus (noreply@blogger.com) 10 июня 2016, 08:00

darkus

Июньский конкурс по ФП в 2016 году: плотная упаковка полимино

А вот вам конкурс по функциональному программированию, с пылу с жару. Сегодня мы делаем плотную упаковку полимино. Налетай, играй, выигрывай.

http://haskell98.blogspot.ru/2016/06/2016.html

10 июня 2016, 07:00

07 июня 2016

David Sorokins WebLog

Айвика как конструктор общецелевых библиотек имитационного моделирования

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

написал dsorokin (noreply@blogger.com) 07 июня 2016, 15:47

Фонд Поддержки Функционального Программирования

Скоро конкурс по ФП

Да, кстати, уведомляю всех причастных и просто сочувствующих. В следующую пятницу, то есть 10.06.2016, под эгидой Фонда Поддержки Функционального Программирования ФП(ФП) и Научной лаборатории имени светителей Проца и Халикаарна состоится очередной конкурс по функциональному программированию. Готовьтесь, будет интересно.

написал Dark Magus (noreply@blogger.com) 07 июня 2016, 12:24

darkus

Скоро конкурс по ФП

Да, кстати, уведомляю всех причастных и просто сочувствующих. В следующую пятницу, то есть 10.06.2016, под эгидой Фонда Поддержки Функционального Программирования ФП(ФП) и Научной лаборатории имени светителей Проца и Халикаарна состоится очередной конкурс по функциональному программированию. Готовьтесь, будет интересно.

07 июня 2016, 10:24

06 июня 2016

swizard

Вероятностные алгоритмы.

Введение.

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

Задание было придумано очень крутое. "Очень крутое" -- это, в моём понимании, такое задание, которое:

  1. Имеет практическую ценность.
  2. Не подразумевает одного единственного верного решения, до которого просто нужно додуматься в процессе конкурса.

Полностью условие можно почитать на офсайте, а вкратце оно звучит так:

  • Дан словарь из ~660k записей. Ориентировочно, это английские слова.
  • Надо написать функцию "test(word)", которая возвращает true, если заданное слово входит в словарь, и false, если нет.
  • Суммарный объём программы и файла с данными, которым она может пользоваться, не должен превышать 65536 байт.
  • Побеждает решение, которое даст максимальный процент правильных ответов на большом количестве тестов.

Чтобы было повеселее, в тестах используется специальный генератор слов, которые визуально (и грамматически) очень похожи на нормальные английские, но при этом в словаре их нет, например: "goldrunk". И, напротив, в заданном словаре есть весьма странные записи, в которых распознать английский язык очень сложно, например, "qwertys" или "rRNA".

Согласно комментариям участников в соответствующем треде на хабрахабре, основные идеи (успешных) решений были следующие:

  • Максимальное обрезание словаря, выделение значащих префиксов/суффиксов/нграмм, и последующее запихивание всего этого в фильтр Блума.
  • Машинное обучение. В основном, это разновидности деревьев решений.
  • Решения, воссоздающие словарь из тестовых данных в рантайме.

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

Немного теории.

В статье на русскоязычной википедии говорится, что: "Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью". Это не совсем так -- принципиально, к ГСЧ в вероятностных алгоритмах обращаться необязательно. В англоязычной версии этой статьи есть более корректное определение: "uniformly random bits". Опять же, экономия может достигаться не только во времени работы, а по памяти, например.

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

Соответственно, возможность такого рода компромисса в постановке задачи (значительный выигрыш по ресурсам взамен некоторой допустимой недостоверности ответа) может быть хорошим признаком того, что в решении имеет смысл использовать вероятностный алгоритм. Например, это конкурс про упаковку огромного словаря в 64Kb :)

Самое главное, что здесь нужно запомнить, это фразу: дискретно-равномерное распределение. "Равномерное распределение" на практике должно означать следующее: если случайная величина (ГСЧ, хэш-функция, значение сигнала) генерирует нам какое-то значение из интервала R, нужно, чтобы вероятность получения каждого значения из R была 1/R (или, хотя бы, очень близко к этому). При этом количество таких значений должно быть конечно (дискретно). Визуально, это выглядит следующим образом: допустим, мы взяли поле 10x10 и ткнули в рандомную точку. Получилось, например, как-то так:

А если мы воткнули их несколько тыщ, то должно получиться относительно равномерное покрытие, что-то типа такого:

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

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

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

Немного практики.

Из популярных практических алгоритмов для подобного рода задач я бы хотел отметить, например, такие:

  • Locality-sensitive hashing: подбирает для множества элементов хэш-функцию таким образом, что "схожие" элементы попадают в одну корзину (хеши дают коллизию ожидаемым образом). Таким образом достигается существенное уменьшение размерности данных, и используется, например, в задачах кластеризации.
  • MinHash: ускорение расчёта коэффициента Жаккара для вычисления степени схожести двух множеств. Широко используется, например, для задач выявления нечётких дубликатов среди большого количества документов.
  • Семплирование потока данных. В отличие от простой выборки каждого N-ого элемента из потока, хешируют некоторый составной ключ (например, "пользователь"/"запрос"/"таймстамп"), после чего берут N корзин, и отбрасывают все результаты, не попавшие в одну из них. Это позволяет семплировать поток по сложным условиям, избегая дорогостоящей группировки.
  • Flajolet–Martin algorithm, и его развитие в виде HyperLogLog. Алгоритмы используют достаточно изящный хак для быстрой аппроксимации количества уникальных элементов в заданном множестве. Я реально советую ознакомится с описанием, это, действительно, хитрый трюк :)

Конкурсная задача.

Вернёмся к задаче про словарь. Итак, уже в условии однозначно написано про компромисс "допустимая недостоверность в обмен на ограниченные ресурсы". Следовательно, задачу можно пробовать решать вероятностным алгоритмом.

Самый простой вероятностный алгоритм, который можно придумать, это подбрасывание монетки:

function test(word) {
    return Math.random() < 0.5;
}

Несложно догадаться, что он совершенно бесплатно даёт нам 50% правильных ответов, при этом даже не пользуясь своим аргументом :) Соответственно, это значение будет базисом, с которым можно сравнивать результативность других алгоритмов.

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

Но, если понимать как работают вероятностные алгоритмы в принципе, можно попробовать придумать что-нибудь чуть более оригинальное. Я позаимствовал некоторые идеи из MinHash, и получилось вот что.

В качестве источника случайных значений я взял множество рандомных хеш-функций, как это сделано в minhash. Для этого я выбрал fnv (просто потому, что она мне нравится), которому я на вход подаю сначала случайное число, а потом сам аргумент.
Соответственно, набор таких случайных чисел (seeds) будет однозначно определять множество хеш-функций, которое будет использовано в задаче.

Применив K таких случайных хеш-функций к одному и тому же аргументу (например, слову из словаря) мы получим K результатов, которые будут, опять же, случайно распределены по всему диапазону значений fnv. Я взял 32-х битную версию, соответственно, результаты хеширования будут в диапазоне 0 - 0xffffffff. Дальше надо как-то убедиться, что эти результаты имеют равномерное распределение. Этот факт явно каким-то образом должен доказываться, но я, к сожалению, не математик, поэтому тупо нарисовал график и посмотрел на него глазами. Выглядит как равномерное :) Это свойство в данном случае мне важно для того, чтобы можно было оценить вероятность того, что случайная хэш-функция даст конкретное значение. При равномерном распределении эта вероятность будет 1/R, где R = 232.

Дальше сделаем вот что: возьмём одну такую случайную хеш-функцию H, и прогоним через неё все N слов из словаря. Получим N чисел (хешей слов), которые как-то случайным образом будут раскиданы в интервале от 0 до 232 - 1. Теперь нам надо найти какое-то такое утверждение P, которое бы:

  1. Выполнялось бы для всех полученных чисел.
  2. Не выполнялось для как можно большего количества остальных чисел из [0, 232).

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

Допустим, к примеру, сложилось такая ситуация, что все хеши слов из словаря оказались чётными. Тогда все нечётные значения из интервала от 0 до 232 означали бы true negative. Вероятность этой ситуации (хеш проверяемого слова оказался нечётным) была бы почти 0.5 -- это очень крутой результат для одной только пробы. Ведь тогда нам для достоверности ответа "слова точно нет в словаре" в 99% достаточно log0.50.01 = ~7 проб, то есть, всего семь рандомных хеш-функций.

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

Конкретно под наш словарь можно попробовать делить всё множество значений хеш-функций не на две корзины (чётные и нечётные числа), а на большее количество: M > 2. Тогда нашей задачей будет подобрать для каждой используемой хеш-функции такое (в идеале, минимальное) количество корзин, чтобы при хешировании всех слов из словаря одна из корзин оказалась пустой.

Если значения хеш-функций имеют равномерное распределение (а они имеют в нашем случае), вероятность попадания хеша в одну из корзин будет равняться 1/M. Каким же должен быть M, чтобы, раскидав по этому такому количеству корзин 660 тысяч хешей, у нас бы осталась одна пустая корзина? Это как-то явно подсчитывается при помощи математики, но (если вы, подобно мне, ничерта не помите из тервера) можно немного схалтурить, и получить нужные цифры при помощи несложного программирования.

Проведём эксперимент: сгенерируем нужное количество 32-х битных случайных чисел, по одному на слово из словаря -- как будто, это результаты хеширования. Программный ГСЧ должен давать равномерное распределение, и хеш-функция тоже даёт равномерное распределение, так что это относительно равноценная замена. Далее тупо брутфорсом попробуем подобрать минимальное количество корзин так, чтобы в одну из них ни одно рандомное число не попало. Вот как это примерно может выглядеть на Common Lisp:

(defun get-minimum-buckets-count (words-count)
  (iter
    ;; generate pseudo hashes
    (with pseudo-hashes =
              (iter (repeat words-count)
                    (collect (random (ash 1 32)) result-type simple-vector)))
    (for buckets-count from 2)
    ;; make buckets with hit counters
    (for buckets-hits =
         (make-array buckets-count
                     :element-type 'fixnum
                     :initial-element 0))
    ;; collect hits
    (iter (for i from 0)
          (for hash in-sequence pseudo-hashes)
          (for bucket = (mod hash buckets-count))
          (incf (elt buckets-hits bucket)))
    ;; check whether an empty bucket exists
    (for empty-bucket = (position 0 buckets-hits))
    (when empty-bucket
      (return-from get-minimum-buckets-count
        (values buckets-count empty-bucket)))))        

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

Запустив эту функцию для 660000 слов, мы (через некоторое время) получим результат для M порядка ~33000. Разумеется, при каждом запуске он будет разный (так как псевдо-хеши генерируются каждый раз случайным образом), но это будут всегда приблизительно одинаковые значения с небольшим разбросом. На практике это означает, что мы можем получить с одной пробы вероятность 0.00003, что слово не входит в заданный словарь: для этого достаточно проверить, что хеш слова попал в пустую корзину. На первый взгляд совсем мизерный шанс, но давайте прикинем, что с этого можно получить.

Итак, мы можем взять одну рандомную хеш функцию H0, словарь, и найти для них два числа: M0 (минимальное количество корзин, раскидывая хеши по которым образуется одна пустая), и B0 (номер пустой корзины). Эти два числа описывают пробу P0, которая даёт шанс в 0.003%, что проверяемое слово точно не принадлежит словарю. Если же мы посчитаем таким же образом P1 для другой функции H1, мы сможем провести две независимые пробы, увеличив вероятность true negative до 0.00006 (вероятность не попасть в пустую корзину для одной пробы равняется 1.0 - 0.00003 = 0.99997, а для двух независимых проб вероятности умножаются). Аналогично, десять подобных проб дадут уже вероятность в 0.03%, сто в 0.3%, а десять тысяч, например, целых 26.1%. Продолжая этот ряд, можно подобрать число 153000 -- именно столько проб нужно выполнить, чтобы с вероятностью 99% определить true negative.

Одна проба однозначно задаётся двумя числами M и B, соответственно, для 150-ти тысяч проб нужно сохранить 300 тысяч чисел. Это явно больше того, что можно запихать в заданные задачей лимиты. Нетрудно прикинуть, что, если мы аллоцируем, ориентировочно 14 бит для M и 15 бит для B, в 64 Kb можно вместить всего порядка 18000 проб. А ведь там ещё должно остаться какое-то место для сценария на js! Соответственно, чуть более реалистичная цифра в 17000 проб даст вероятность определения true negative в ~40%.

Что это означает на практике? Это означает следующие вещи:

  • Если на вход функции test было подано слово из словаря, все пробы будут успешными (хеши не попадут в пустые корзины), и будет возвращена истина. Это true positive.
  • Если на вход функции test было подано слово не из словаря, то:
    1. с вероятностью 40% одна из проб даст неуспех (один из хешей попадёт в пустую корзину), и будет возвращена ложь. Это true negative.
    2. с вероятностью 60% все пробы, всё же, дадут успех, и будет возвращена истина. Это false positive.
  • Ситуация false negative в данной конфигурации невозможна, потому что мы, формируя множество проб, специально так подбирали числа M, чтобы для слов из словаря обязательно оставалась пустая корзина.

Итоговый процент верных ответов зависит от характера тестовых данных: в худшем случае он будет стремиться к 40% (если на вход подаются только слова не из словаря), в лучшем -- к 100% (если на входе только слова из словаря), а в случае половина тех, и половина других, это должно быть значение порядка 70%.

Эту цифру можно чуть-чуть улучшить, параллельно значительно упростив формат сериализованной пробы (что тоже немаловажно, ведь размер js-скрипта тоже имеет значение). Можно подбирать M специальным образом, чтобы пустая корзина оказывалась всегда, например, в нулевой позиции (B == 0, или H % M == 0). В этом случае для записи пробы нам достаточно только одного числа M. Эксперименты показывают, что это получаются значения из диапазона примерно 38000 - 91000: это означает, что соответствующие вероятности для проб будут меньше, но зато для их упаковки теперь достаточно 16 бит, следовательно количество проб можно увеличить до ~32000, и, главное, сильно упростить код для их упаковки/распаковки.

Конечно, полученная цифра в 70% верных ответов выглядит не очень впечатляюще. Но следует отметить две вещи про это решение:

  1. Удивительная простота алгоритма в целом, и элементарная масштабируемость: для достижения нужной точности нужно просто последовательно увеличивать количество проб.
  2. Это абсолютно "чистый" и "честный" результат: на нетронутых оригинальных входных данных, когда словарь взят полностью как есть. Всегда можно приложить некоторые усилия к препроцессингу: порезать слова, оканчивающиеся на "'s", разделить на префиксы/суффиксы, и т.п. Ребята в комментариях к задаче на хабрахабре писали, что они относительно безболезненно уменьшали словарь до 280000 записей. А 280 тысяч хешей в нашем алгоритме уже означают M ~ 13000, что, в свою очередь, даёт вероятность одной пробы 0.0076% и порядка 18000 проб в 64 Kb, выдающих, суммарно, почти 75% true negative! А это уже больше 87% верных ответов для случая 50/50 словарных и не словарных слов.

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

Полностью моё решение, вместе с расчитанными данными, можно взять в этом репо: сами хеши я породил из js (директория generator), а компилятор проб из них сделал на Rust (директория compiler).

06 июня 2016, 16:53

02 июня 2016

Egobrain

Erlang ORM. часть 3

Прошло уже очень много времени с момента как я писал про свои эксперименты с Erlang ORM.
И что я могу сказать?
Первое и самое, вероятно, печальное, подход оказался не жизнеспособным, Второе – несмотря на недостатки ORM ее использование помогло набраться опыта работы с postgresql из Erlang и получить представление о том как все действительно должно работать.

Где я допустил ошибки:
– Нельзя мешать в одной модели описание того как данные хранятся в базе и как будут отдаваться клиенту
– Не стоило мешать генерацию sql и непосредственную работу с БД в одном проекте
– Подход ActiveRecord – не самая лучшая идея для Erlang
– Слишком много parse_transform-a

За эти 2 года я очень часто сталкивался с генерацией sql в чужих проектах на Erlang и, к сожалению, единого, общепризнанного, да что там, хотя бы просто удобного решения нигде не встречал. Везде лишь ад из case блоков, сверток и iolist-ов. Что еще печальнее, коллеги все чаще стали поглядывать в сторону Elixir с его ecto. А уж совсем не хочется изучать, а тем более использовать в продакшене еще один язык.

Так на свет появился стек для работы с postgresql и моделями данных:
epgpool – простой пулл подключений к postgres. Очередной велосипед, если есть предложения чего-то получше – могу рассмотреть
dbschema – автоматические миграции наше все. Библиотек позволяет исполнять sql и erl up/down инструкции. Что убирает кучу работы по ручной раскладке и позволяет автоматизировать тестирование
emodel – библиотека для валидации входных данных. Та самая прослойка, которая должна отделять чистые, проверенные данные от мусора, который к нам прилетает. Отличается тем, что возвращает сразу все ошибки до которых может дотянуться.
equery – генерация sql, вдохновленная подходом Ecto
repo – одна из возможных реализаций CRUD библиотеки поверх equery и epgpool.

Сегодня я расскажу про repo и equery.

Equery

Какие проблемы с ручным написанием sql?
1. Как выразился один мой бывший коллега, основная проблема – смапить результат исполнения sql на внутреннюю структуру данных
2. Сложность композиции. (К примеру, как добавить еще один фильтр к уже имеющимся)
3. Необходимость модифицировать разрозненные запросы в случае добавления, удаления полей в таблице.

Как будем решать?

Итак, понадобится сущность, которая будет описывать структуру таблицы SQL (Благо в Erlang r17 появились мапы и с ними жизнь стала намного легче). Решение в лоб

1
2
3
4
5
6
7
Schema = #{
    fields => #{
       field_1 => Fields1Opts,
       field_2 => Fields2Opts,
    },
    table => <<"SomeTableName">>
}

FieldOpts – Набор дополнительной информации о колонках. Например:
– type – тип в бд ({varchar, 255}, decimal, int, text, bigint, …)
– required – аналог NOT NULL (boolean)
– readOnly – удобная опция, в случае если поле нельзя обновлять, например id, который генерируется через serial или timestamp через now()
– index – поле является индексом, или частью составного индекса (boolean)
– … – что угодно. Т.к. Opts – это map(), то можно добавлять свои опции по желанию.

К этому моменту у меня примерно прояснилась картина, как я хочу видеть код.

1
2
3
4
Query1 = from(Schema),
Query2 = filter(Query1),
...
Result = select(QueryN)

Скорее всего делать внутреннее представление SQL придется через какой-то промежуточный AST, но, у меня есть одно важное требование – легкое добавление SQL конструкций, которых еще нет в моей библиотеке. Делать полноценный AST который потом бы компилировался в SQL или во что-то еще я не хочу. У меня есть postgresql и это все что мне нужно на данный момент. При такой постановке вопроса проектировать решение становится заметно проще :) Я взял на вооружение подход из моей предыдущей ORM – добавить дополнительную разметку прямо в SQL

Возьмем пример:

1
select sum(o.sum), u.name from users as u join orders o on o.user_id = u.id where u.age > 18 group by u.name

Что понадобится?
Ключевые слова, операции, пробелы, запятые и прочее что должно быть встроено “как есть” назовем raw (в equery – {'$raw', iolist()} ).
Названия таблиц повторяются часто и не хотелось бы чтобы при объединении запросов были проблемы с одинаковыми псевдонимами поэтому есть 2 варианта:
1. генерировать уникальные псевдонимы по ходу построения запроса
2. генерировать их в самом конце – при генерации sql, а в ast использовать уникальную “ссылку”

Т.к. posgresql кэширует план запросов – то нужно чтобы один и тот же код каждый раз давал один и тот же результат.
Следовательно решение 1 отпадает и вводим дополнительную конструкцию {table, UniqueRef} там где нужно ссылаться на поля таблиц. (в equery – {'$table', ref()})
Чтобы как-то группировать несколько синтаксических конструкций в одну добавим выражение {exp, [Nodes]} (в equery – {'$exp', ref()})
Все остальное считаем данными и при генерации SQL будем их собирать в отдельном списке, а в SQL на этом месте проставлять ссылки на аргументы $1, $2, ...

В результате sql из примера превращается в AST:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
{exp, [
    {raw, "select "},
    {exp, [
        {raw, "sum("},
            {exp, [{table, Ref2},{raw, "."},{raw, "sum"}]},
        {raw, ")"}
    ]}
    {raw, ","},
    {exp, [{table, Ref1},{raw, "."},{raw, "name"}]},
    {raw, " from users as "}, {table, Ref1},
    {raw, " join orders as"}, {table, Ref2},
    {raw, " on "},
    {exp, [
        {exp, [{table, Ref2},{raw, "."},{raw, "user_id"}]},
        {raw, " = "},
        {exp, [{table, Ref1},{raw, "."},{raw, "id"}]},
    ]},
    {raw, " where "},
    {exp, [
        {exp, [{table, Ref1},{raw, "."},{raw, "age"}]},
        {raw, " = "},
        18
    ]},
    {raw, " group by"},
    {exp, [{table, Ref1},{raw, "."},{raw, "name"}]}
]}

Как преобразовать такое представление в SQL + Args, думаю вполне очевидно. А вот как строить его с помощью erlang?

Для начала нам понадобятся схемы для таблиц:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
UserSchema = #{
    fields => #{
        id => #{type => int, index => true, required => true, readOnly => true},
        name => #{type => {varchar, 255}, required => true},
        age => #{type => int}
    },
    table => <<"users">>
}.

OrderSchema = #{
    fields => #{
        id => #{type => int, index => true, required => true, readOnly => true},
        user_id => #{type => int, required => true},
        sum => #{type => number, required => true}
    },
    table => <<"orders">>
}

Начнем с того, что должна делать функция from(Schema)

1
Query1 = from(UserSchema).

В AST видны повторяющиеся конструкции для ссылок на поля {exp, [{table, Ref1},{raw, "."},{raw, "name"}]}. Следовательно, нужно сгенерировать Ref1 и для каждого поля из схемы построить такое AST выражение. Получится map, который я называю TableData:

1
2
3
4
5
6
Ref1 = make_ref(),
#{
    id   => {exp, [{table, Ref1},{raw, "."},{raw, "id"}]},
    name => {exp, [{table, Ref1},{raw, "."},{raw, "name"}]},
    age  => {exp, [{table, Ref1},{raw, "."},{raw, "age"}]},
}

теперь про функции. Для реализации текущего запроса нам нужны функции sum и =. Выглядят они очень просто:

1
2
3
4
5
sum(Field) ->
    {exp, [{raw, "sum("}, F, {raw, ")"}]}.

'=:='(A, B) ->
    {exp, [A, {raw, " = "}, B]}.

Как строить where? Я сделал функцию where(Fun, Query) принимающую Fun, в которую передается несколько TableData уже участвующих в запросе, а на выходе AST для where выражения. Результирующий AST добавляется через and к тому, который уже хранится в Query.

1
Query2 = where(fun([#{age := Age}]) -> '=:='(Age, 18) end, Query1).

С join поступим похожим образом,

1
Query3 = join(OrderSchema, fun([#{id := Id}, #{user_id := UserId}]) -> '=:='(Id, UserId) end, Query2).

для OrderSchema создается OrderTableData и вместе с UserTableData, которая уже есть в запросе передается в callback.

Что касается group by то функция тоже очень похожа на предыдущие только возвращает не AST, а массив в котором описано по каким полям группировать

1
Query4 = group_by(fun([#{name := Name}, _OrdersTableData]) -> [Name] end, Query3).

Осталось сделать select. Функция не будет исключением и работает по сходным правила

1
Query5 = select(fun([#{name := Name}, #{sum := OrderSum}]) -> #{name => Name, sum => sum(OrderSum)} end, Query4)

select callback возвращает описание результата – это может быть или map или одно поле (удобно для count).

Query готов. Осталось только на основе него сгенерировать итоговый Select AST и преобразовать его в SQL. Этим займемся чуть позже. А пока приведу код запроса полностью и попробуем сделать его чуть-чуть красивее.

1
2
3
4
5
Query1 = from(UserSchema),
Query2 = where(fun([#{age := Age}]) -> '=:='(Age, 18) end, Query1),
Query3 = join(OrderSchema, fun([#{id := Id}, #{user_id := UserId}]) -> '=:='(Id, UserId) end, Query2),
Query4 = group_by(fun([#{name := Name}, _OrdersTableData]) -> [Name] end, Query3),
Query5 = select(fun([#{name := Name}, #{sum := OrderSum}]) -> #{name => Name, sum => sum(OrderSum)} end, Query4)

Во-первых, давайте перенесем все функции, модифицирующие запрос в отдельный модуль. Для лаконичности q.erl Функции, которые генерирую postgresql AST для операций в другой модуль – pg_sql.erl

1
2
3
4
5
Query1 = q:from(UserSchema),
Query2 = q:where(fun([#{age := Age}]) -> pg_sql:'=:='(Age, 18) end, Query1),
Query3 = q:join(OrderSchema, fun([#{id := Id}, #{user_id := UserId}]) -> pg_sql:'=:='(Id, UserId) end, Query2),
Query4 = q:group_by(fun([#{name := Name}, _OrdersTableData]) -> [Name] end, Query3),
Query5 = q:select(fun([#{name := Name}, #{sum := OrderSum}]) -> #{name => Name, sum => pg_sql:sum(OrderSum)} end, Query4)

Во-вторых, передавать схему как map не совсем практично. В дальнейшем нам понадобится больше функционала для моделей. Поэтому перенесем каждую схему в свой модуль. Я использую префикс m_ и функцию schema/0.

m_user.erl
1
2
3
4
5
6
7
8
9
10
11
12
13
-module(m_user).
-export([schema/0]).

schema() ->
    #{
        fields => #{
            id => #{type => int, index => true, required => true, readOnly => true},
            name => #{type => {varchar, 255}, required => true},
            age => #{type => int}
        },
        table => <<"users">>
    }.

m_order.erl
1
2
3
4
5
6
7
8
9
10
11
12
-module(m_order).
-export([schema/0]).

schema() ->
    #{
        fields => #{
            id => #{type => int, index => true, required => true, readOnly => true},
            user_id => #{type => int, required => true},
            sum => #{type => number, required => true}
        },
        table => <<"orders">>
    }.

попутно обучим функции, которые принимали схему принимать модуль и дергать Module:schema() при этом.

Теперь возьмемся за то, что ломает глаза и бесит многих, кто приходит в erlang из других языков: повторы QueryN. Ну как решать эту проблему мы-то знаем ;) В elixir для этого существует pipe оператор |>, в erlang его нет, но можно сделать по-другому:

1
2
pipe(State, Funs) ->
    lists:foldl(fun(F, St) -> F(St) end, State, Funs).

а для каждой функции из q заведем каррированый аналог.

f(Fun, Query). => f(Fun) -> fun(Query) -> f(Fun, Query) end.

получилось:

1
2
3
4
5
6
q:pipe(q:from(m_user), [
    q:where(fun([#{age := Age}]) -> pg_sql:'=:='(Age, 18) end),
    q:join(m_order, fun([#{id := Id}, #{user_id := UserId}]) -> pg_sql:'=:='(Id, UserId) end),
    q:group_by(fun([#{name := Name}, _OrdersTableData]) -> [Name] end),
    q:select(fun([#{name := Name}, #{sum := OrderSum}]) -> #{name => Name, sum => pg_sql:sum(OrderSum)} end)
]).

теперь можно легко переставлять выражения (но порядок все-таки важен)

1
2
3
4
5
6
q:pipe(q:from(m_user), [
    q:join(m_order, fun([#{id := Id}, #{user_id := UserId}]) -> pg_sql:'=:='(Id, UserId) end),
    q:select(fun([#{name := Name}, #{sum := OrderSum}]) -> #{name => Name, sum => pg_sql:sum(OrderSum)} end),
    q:group_by(fun([#{name := Name}, _OrdersTableData]) -> [Name] end),
    q:where(fun([#{age := Age}]) -> pg_sql:'=:='(Age, 18) end)
]).

Получился вполне удобный язык запросов, который удовлетворяет всем требованиям которые я описал выше. Все это и немного больше находится в библиотеке equery и пока ее возможностей хватает чтобы покрыть 95% того что мне сейчас нужно (5% – это union, которых пока нет и выборка из нескольких таблиц select * from table1, table2, ... , но поддержка появится в скором будущем)

Маленький бонус. Для тех, кому как и мне, не совсем приятно и удобно читать выражения вида

1
2
3
4
pg_sql:'andalso'(
    pg_sql:'>=(Age, 18),
    pg_sql:'=<'(Age, 25)
)

я реализовал parse_transform, который в q callback-ах позволяет писать код в erlang стиле

1
Age >= 18 andalso Age =< 25

работает даже в repl !!! :)

с ним наш запрос будет выглядеть так:

1
2
3
4
5
6
7
8
-include_lib("equery/include/equery.hrl").

Query = q:pipe(q:from(m_user), [
    q:where(fun([#{age := Age}]) -> Age =:= 18 end),                                                %% Изменения тут
    q:join(m_order, fun([#{id := Id}, #{user_id := UserId}]) -> Id =:= UserId end),      %%  и тут
    q:group_by(fun([#{name := Name}, _OrdersTableData]) -> [Name] end),
    q:select(fun([#{name := Name}, #{sum := OrderSum}]) -> #{name => Name, sum => pg_sql:sum(OrderSum)} end)
]).

Чтобы получить AST для select запроса нужно вызвать qsql:select/1. А чтобы получить SQL qast:to_sql/1.

1
2
3
qast:to_sql(qsql:select(Query)).

{<<"select \"__table-0\".\"name\",sum(\"__table-1\".\"sum\") from \"users\" as \"__table-0\" inner join \"orders\" as \"__table-1\" on (\"__table-0\".\"id\" = \"__table-1\".\"user_id\") where (\"__table-0\".\"age\" = $1) group by \"__table-0\".\"name\"">>,  [18]}

REPO

Генерация запросов это хорошо, но хочется еще добавлять, изменять, удалять сущности из БД. Хочется исполнять запросы через pool, иметь хуки на сохранение и т.п. Для этого всего я реализовал библиотеку repo. Она построена поверх equery and epgpool

Select

С select запросами все совсем просто: пишешь запрос и он исполняется.

1
2
3
4
5
6
repo:all(m_user, [
    q:where(fun([#{age := Age}]) -> Age =:= 18 end),
    q:join(m_order, fun([#{id := Id}, #{user_id := UserId}]) -> Id =:= UserId end),
    q:group_by(fun([#{name := Name}, _OrdersTableData]) -> [Name] end),
    q:select(fun([#{name := Name}, #{sum := OrderSum}]) -> #{name => Name, sum => pg_sql:sum(OrderSum)} end)
]).

Довольно часто нужно выбрать сущности по какому-то полю или набору полей, например по id. Изначально для этого нужно писать where запрос

1
2
3
repo:all(m_user, [
    q:where(fun([#{id := Id}]) -> Id =:= 123 end)
]).

но, благодаря тому, что запросы легко строить динамически можно добавить немного сахара:

1
2
3
4
5
6
7
8
9
10
11
12
like(Map) ->
    q:where(fun([M|_]) ->
        maps:fold(
            fun(K, V, S) ->
                case maps:find(K, M) of
                    {ok, V2} -> S andalso V =:= V2;
                    error -> S
                end
            end, true, Map)
    end).

repo:all(m_user, [ like(#{id => 123} ]).

я пошел еще дальше и repo api принимает map на вход.

1
repo:all(m_user, #{id => 123}). %% просто, понятно, лаконично

для поиска единственного элемента есть функция get_one

1
{ok, User} = repo:get_one(m_user, #{id => 123}).

Если результат запроса слишком большой, но при этом его можно обрабатывать потоково (например вывод отчета с большим количеством полей) то желательно использовать потоковое api через zlist, что сильно уменьшает latency и потребление памяти, т.к. данные из БД подгружаются пачками по мере необходимости

1
2
3
repo:all(m_user, [q:where(fun([#{age := Age}]) -> Age > 18 end)], fun(ZList) ->
    zlist:foreach(fun(#{name := Name, age := Age}) -> io:format("User: ~p, ~p\n", [Name, Age]) end, Zlist)
end).

Чуть не забыл. С помощью repo_utils:preload/1 можно подгружать данные из зависимых таблиц (has_many, belongs_to). Например:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-module(m_user).
-export([schema/0]).

schema() ->
    #{
        fields => #{
            id => #{type => int, index => true, required => true, readOnly => true},
            name => #{type => {varchar, 255}, required => true},
            age => #{type => int}
        },
        links => #{
            orders => {has_many, m_order, #{id => user_id}}
        },
        table => <<"users">>
    }.

запрос

1
2
3
repo:all(m_user, [
    repo_utils:preload(orders)
]).

вернет подобную структуру

1
2
3
4
5
6
7
8
9
10
11
[#{
    id => UserId,
    name => UserName,
    age => UserAge,
    orders => [
         #{id => OrderId1,  user_id => UserId, sum => Sum1},
         #{id => OrderId2,  user_id => UserId, sum => Sum2},
         ...
 },
 ... Other users ...
].

и все это одним SQL запросом.

Insert/Update/Upsert

С insert/update все очень просто. API принимает один или несколько объектов и по-умолчанию возвращает их же (через sql returnging)

1
repo:insert(m_user, [#{name => <<"Alladin">>, age => 25}, ...]).
1
repo:update(m_user, [#{id = 238, name => <<"Masha">>, age => 18}, ...]).
1
repo:upsert(m_user, [#{id = 239, name => <<"Igor">>, age => 18}, ...]).

Хочется добавить, что для каждой модели можно, при необходимости, объявить before_save/2 и after_save/2 hook-и и, если хочется хранить сущности не в мапах, а, скажем, в record-ах, для этого есть from_db/1 и to_db/1 (для примера смотри common тесты)

Batch update

Можно обновлять сущности пачкой, а не по одному:

1
2
3
repo:set(m_user, [
   q:set(fun([#{age := Age}]) -> #{age => Age * 2 } end)
]).

Batch delete

Удаляются данные только пачкой.

1
2
3
repo:delete(m_user, [
   q:where(fun([#{age := Age}]) -> Age > 99 end)
]).

Резюме

На данный момент я не считаю что реализация repo идеальна и эталонна, но она решает большую часть повседневных задач стоящих в моих проектах и уже успешно используется в production. Нет ничего плохого в том, чтобы форкуть его и заменить, докрутить его части так как это необходимо именно вам, т.к. проект очень маленький и при этом ~100% покрыт тестами.

При этом проект позволил полностью избавиться от генерации SQL вручную (кроме миграций) и заметно сократить общий объем кодовой базы. Стоит, однако, понимать, что библиотека equery не контролирует ошибки генерации sql, зато дает больший контроль во взаимодействии с Postgresql т.к. вы можете самостоятельно реализовать почти любую синтаксическую конструкцию. Необходимо понимать что и как работает и где копать в случае проблем. Именно поэтому я привел достаточно подробное описание выше. Хорошо это или нет – решать вам.

Дальнейшие планы

Предстоит еще не мало работы:
– добавить unioun, multiple from в equery
– покрыть все спеками и dialyzer тестами
– написать документацию
– добавить больше common операций в equery pg_sql.erl
– реализовать dbschema-repo addon чтобы автоматически генерировать миграции для изменения схем

Основным недостатком (вероятно для некоторых) что проект ориентирован только на Posgresql и при том 9.5 версии (из-за upsert)

Буду рад комментариям и PR :)

02 июня 2016, 16:26

01 июня 2016

31 мая 2016

ruhaskell.org

Улучшение тестов для statistics, часть 1

Длинная история об отладке тестов для statistics и пакета math-functions

написал Денис Шевченко 31 мая 2016, 16:32

29 мая 2016

Anton Salikhmetov

Еще одно введение в веревочковедение

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

Сети взаимодействия (interaction nets) - это структуры, подобные графам, состоящие из агентов (agents) и дуг. Агент типа α

имеет арность ar(α) ≥ 0. Если ar(α) = n, то агент α имеет n дополнительных портов (auxiliary ports) x1,..., xn в дополнение к его главному порту (principle port) x0. Все типы агентов принадлежат множеству Σ, называемому сигнатурой (signature). К любому порту можно присоединить не более одной дуги. Порты, которые не соединены ни одной дугой, называются свободными (free ports). Совокупность всех свободных портов в сети называется ее интерфейсом. Разводка (wiring) ω

состоит исключительно из дуг. Индуктивно определяемые деревья (trees)

соответствуют термам t ::= α(t1,..., tn) | x в исчислении взаимодействия (interaction calculus), где x называется именем (name).

С помощью разводок и деревьев любая сеть может быть представлена следующим образом:

что в исчислении взаимодействия будет соответствовать конфигурации (configuration)
<t1,..., tm | v1 = w1,..., vn = wn>,
где ti, vi, wi - некоторые термы. Последовательность t1,..., tm называется интерфейсом (interface), остальное же представляет собой мультимножество уравнений (equations). Разводка ω транслируется в выбор имен, и каждое имя обязано иметь ровно два вхождения в конфигурации.

Как и λ-исчислении, в исчислении взаимодействия естественным образом определяются понятия α-конверсии и подстановки (substitution). Оба вхождения любого имени могут быть заменены на новое имя, если оно не участвует в данной конфигурации. Если терм t имеет ровно одно вхождение имени x, то подстановка t[x := u] определяется как результат замены имени x в терме t некоторым термом u.

Когда два агента соединены своими главными портами, они формируют активную пару (active pair). Для активных пар можно ввести правила взаимодействия (interaction rules), которые описывают, как активная пара будет заменена во время редукции сети взаимодействия. Графически любое правило взаимодействия можно преставить следующим образом:

где α, β ∈ Σ, а сеть N представлена с помощью разводок и деревьев в виде, пригодном для исчисления взаимодействия: в нотации Lafont это соответствует
a[v1,..., vm] >< β[w1,..., wn].
Говорят, что сеть без активных пар находится в нормальной форме (normal form). Сигнатура и множество правил взаимодействия вместе задают систему взаимодействия (interaction system).

Теперь рассмотрим пример для введенных конструкций, в котором участвуют часто использующиеся агенты ε и δ. В нотации Lafont правила взаимодействия для удаляющего (erasing) агента ε

записываются как ε >< α[ε,..., ε], а правила для дублирующего (duplicating) агента δ

выглядят следующим образом:
δ[α(x1,..., xn), α(y1,..., yn)] >< α[δ(x1, y1),..., δ(xn, yn)].
В качестве примера сети, в которой участвуют правила удаления и дублирования, возьмем простую сеть которая не имеет нормальной формы и редуцируется к самой себе:

В исчислении взаимодействия такая сеть соответствует конфигурации
<∅ | δ(ε, x) = γ(x, ε)> без интерфейса.

Редукция для конфигураций определяется более подробно, чем для сетей. Если
a[v1,..., vm] >< β[w1,..., wn], то следующая редукция:
<... | α(t1,..., tm) = β(u1,..., un), Δ> → <... | t1 = v1,..., tm = vm, u1 = w1,..., un = wn, Δ>
называется взаимодействием (interaction). Когда одно из уравнений имеет форму x = u, к конфигурации применимо разыменование (indirection), в результате которого другое вхождение имени x в некотором терме t будет заменено на терм u:
<...t... | x = u, Δ> → <...t[x := u]... | Δ> или <... | x = u, t = w, Δ> → <... | t[x := u] = w, Δ>.
Уравнение t = x называется тупиком (deadlock), если x имеет вхождение в t. Обычно рассматривают только сети, свободные от тупиков (deadlock-free). Вместе взаимодействие и разыменование задают отношение редукции на конфигурациях. Тот факт, что некоторая конфигурация c редуцируется к своей нормальной форме c', где мультимножество уравнений пусто, обозначают через c ↓ c'.

Если вернуться к примеру незавершающейся редукции сети, то бесконечная редукционная цепочка, начинающаяся с соответствующей конфигурации выглядит следующим образом:
<∅ | δ(ε, x) = γ(x, ε)> →
<∅ | ε = γ(x1, x2), x = γ(y1, y2), x = δ(x1, y1), ε = δ(x2, y2)> →*
<∅ | x1 = ε, x2 = ε, x = γ(y1, y2), x = δ(x1, y1), x2 = ε, y2 = ε> →*
<∅ | δ(ε, x) = γ(x, ε)> → ...

На нашем языке программирования, который подобен yacc(1)/lex(1) по структуре и лексически близок к LaTeX-нотации для исчисления взаимодействия, тот же самый пример можно записать следующим образом:
\epsilon {
        console.log("epsilon >< delta");
} \delta[\epsilon, \epsilon];

\epsilon {
        console.log("epsilon >< gamma");
} \gamma[\epsilon, \epsilon];

\delta[\gamma(x, y), \gamma(v, w)] {
        console.log("delta >< gamma");
} \gamma[\delta(x, v), \delta(y, w)];

$$

\delta(\epsilon, x) = \gamma(x, \epsilon);
Отметим, что наш язык программирования позволяет записывать побочные действия в императивном стиле, таким образом давая возможность исполнять произвольный код, включая ввод-вывод, а также условные множественные правила для пар вида αi >< βj в зависимости от значений i и j, которые могут быть произвольными данными, привязанными к агентам.

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

Сигнатура и арности агентов соответствующей системы взаимодействия автоматически выводятся при компиляции исходного кода программы на основе правил взаимодействия и начальной конфигурации. Правила взаимодействия вместе с их побочными действиями компилируются заранее, до начала редукции сети, при этом компилятор формирует таблицу для быстрого O(1)-поиска правил, соответствующих активным парам, во время последующего исполнения программы. После этого начальная конфигурация добавляется в FIFO-очередь уравнений, которая затем обрабатывается, пока она не станет пуста.

comment count unavailable comments

29 мая 2016, 15:32

26 мая 2016

nponeccop

Возрадуйтесь до плеши, злопыхатели!

https://github.com/commercialhaskell/stack-ide

Пилили проприетарную онлайн мега-иде и сдулись, всё заопенсорсили, проект заглох. И там ещё не академики, а Снойман.

После каждого слова можно говорить "Карл!"

26 мая 2016, 00:02

24 мая 2016

Scala@livejournal.com

Частичная явная передача implicit-параметров.

У меня есть функция с двумя implicit-параметрами. А в одном месте понадобилось один из параметров передать явно. Что-то вроде
scala> def f()(implicit a: String, b: Int) = b + a
f: ()(implicit a: String, implicit b: Int)String

scala> implicit val x = "ggg"
x: String = ggg

scala> implicit val y = 17
y: Int = 17

scala> f()
res0: String = 17ggg

scala> f()("ggg",56)
res1: String = 56ggg

scala> f()("gggg",56)
res2: String = 56gggg

scala> f()("gggg")
:14: error: not enough arguments for method f: (implicit a: String, implicit b: Int)String.
Unspecified value parameter b.
       f()("gggg")

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

написал Mike Potanin (mpotanin@gmail.com) 24 мая 2016, 14:54

Максим Сохацкий

Об универсальных языках программирования/моделирования 1

Ребята пишут про какой-то паттерн матчинг настоящий :-)
Про итеграцию и то, что это было в лиспах (ну не в лиспах, а в ACL2 — это все же не лисп). Ну и понятное дело все это пишут ебанаты, код которых так воняет по всему интернету что даже из гитхаба его удаляют :-) Невозможно понять как работает паттерн мачинг, если вы не поняли как раотает оператор J. Я написал за свою жизнь около 15 языков. И поверьте любые ваши попытки написать свой язык, в котором нет зависимых типов и бесконечного счетного количества вселенных — навсегда остануться костылями, которые никогда не будут восприниматься более-менее здоровыми психически людьми как нечно стоящее. Потратьте хотябы несколько лет в медитации, чтобы понять что А) мы (Групоид Инфинити) не занимается хуйней и Б) вы занимаетесь хуйней.

Originally posted by justy_tylor at Об универсальных языках программирования/моделирования 1
В начале века я ещё считал, что прогресс технологий работы с информацией сильно сдерживается существующими языками программирования, но достаточно заменить C++ чем-то более развитым по части функциональщины и метапрограммирования (но сохраняющим возможность генерации оптимального нативного кода), чтобы стало легко и удобно разрабатывать продукты любой сложности, уделяя внимание только проблемам предметной области, но не ограничениям предыдущего поколения инструментов. Был юный и тупой.

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

Можно сделать язык с полноценной реализацией pattern matching (а не как принято сейчас). С паттернами и комбинаторами в качестве первоклассных сущностей языка. И это уже польза. Однако.

Для определённых типов данных эффективнее создание индексов вместо полного перебора веток. Появляется выбор, либо через удобный pattern matching, либо через ручное решение с индексами. Ложный выбор. Средства метапрограммирования языка должны позволять создание подобных индексов в pattern matching, сочетая удобство написания и эффективность работы. И это ещё полезнее. Однако.

В реальном мире код работает не только с разными видами процессоров, памяти и периферии. Код работает с другим кодом. И существует множество информационных систем, где, например, выражения из паттернов/комбинаторов для регистрации на какие-то события указываются через XML-конфиг, а потом придумываются дублируемые идентификаторы, связывающие их с неким исполняемым кодом (часто тоже не нативным). И да, люди, создающие системы с ручным редактированием XML, достойны перерождения в виде жаб в Бангалоре. Но это не отменяет необходимости интеграции с такими системами. И здесь даже нет выбора. Только через конфиг. Хотя... Ведь и его можно сгенерировать. Ещё одна возможность трансляции pattern matching: что слева - в конфиг, что справа - в код.

То есть, язык, решающий проблемы разработки, должен решать проблемы интеграции. Поддерживать в процессе компиляции как пользовательские compile-time алгоритмы, так и описания таргетов из пользовательских библиотек. Здесь конфиг, там HTML, а кому-то вообще кусочек COBOL на мейнфрейм сгенерировать надо.

Но зачем тогда вообще писать что-то на COBOL (Java, C++, SQL, XML, bash, make, whatever...), если это можно сгенерировать из единой исполняемой спецификации, гарантируя отсутствие расхождений на стыках языков? Да, всё так, они оказываются лишь артефактами старых систем. Настоящий язык программирования должен быть универсальным, и заменить сразу все неуниверсальные. Что не значит, что он будет единственным (таким). Будут и другие универсальные, возможно (точнее: когда-то) лучше.

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

24 мая 2016, 12:56

22 мая 2016

nponeccop

Мега-СУБД: указатели, плотная упаковка и строки кеша

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

Массив с бинарным поиском - чуть меньший идиотизм, потому что всё равно отравляет кэш. Допустим, у вас 4-байтовые ключи и строка кэша 64 байта. Первое обращение к массиву вытянет 16 ключей (строку кеша, содержащую "серединный" ключ), из которых 15 будут бесполезны и занимать драгоценное место.

Проблема хорошо известна в алгоритмах внешнего поиска (B-tree и т п), и решения для дисков можно переносить на случай иерархии памяти. Там разные варианты есть. Например, в лоб сделать B-tree с 64-байтовыми страницами, и упаковать его в массив.

Далее, 8 байт на указатель - это непомерное расточительство памяти. Можно побить память на сегменты по 64к, и использовать короткие внутрисегментные указатели. И отказаться от указателей, и использовать вместо них индексы в массивах (или, эквивалентно, большое выравнивание). Первый подход позволяет не хранить "старшие" биты в указателях, а второй - младшие.

Условно, если есть 100 связных структур по 600 узлов одинакового размера - то можно узлы для всех них аллоцировать в одном массиве из 60к элементов, а вместо указателей использовать двухбайтовые индексы в этом массиве. Можно даже gc организовать локальный.

Мне кажется, что такая софтварная сегментация вполне может выстрелить в системах типа редиса. Потому что

а) длинных указателей мало
б) алиасинг под контролем - на большинство живых узлов ровно один указатель
в) системное ПО - можно один раз потрахаться, а потом 100500 раз хипсторам продать

22 мая 2016, 02:22

Мега-СУБД: интерфейс мапредьюса

Мне тут пришла в голову идея запилить узкоспециализированную СУБД под свои нужды. Это больше похоже на библиотеку ридонли-контейнеров с интерфейсом мапредьюса.

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

GET - это ночное окошко в аптеке. Клиент пришёл, сказал что ему нужно, продавец закрыл окошко и пошёл искать. Если пришло 2 клиента - то продавец не разговаривает со вторым, пока не отпустит первого.

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

Даже продавцы шаурмы догадываются, что такие стратегии работают плохо. И в супермаркетах с макдональдсами используют совершенно другие, более оптимальные стратегии обслуживания.

22 мая 2016, 01:02

20 мая 2016

nponeccop

Чем закончился хайп вокруг UML/Rational Rose?

Я так понимаю, SysML, BPMN и MBSE живее всех живых, но хипсторам неизвестны. Хипсторы предпочитают не заниматься такой ерундой, как проектирование и документирование дизайна, и используют вариации того, что древние именовали XP.

Что там вообще на ниве CMM происходит, что сейчас рекомендуется для достижения высокой мачурити? Куда читать, чем облачка с квадратиками соединять, какой бюрократией ни в чём не повинных девов облагать?

20 мая 2016, 19:15

Языки в тренде, согласно tiobe.com

Java, PHP, Ruby, Perl, Delphi/Object Pascal, Assembly language, Swift, Groovy, D

Это языки, чья доля заметно выросла с прошлого года. В принципе, начиная с 4-й позиции фейспалм можно не отпускать, и лишь чуть-чуть приопустить на D.

Уменьшилась доля у:

C, C++, C#, Javascript, VB.Net, Objective-C, R

Тут всё соответствует внутренним предрассудкам, кроме, может, проседаний шарпа.

Рейтинг (известных мне) около-ФЯ:

R, Matlab, Scheme, Lisp, Scala, Prolog, F#, Haskell, Erlang, Q

Ну тут тоже без сюрпризов:
- R, Matlab - для прикладных математиков
- Scheme, Lisp, Prolog - лигаси
- Scala, F# - выезжают на поддержке вендоров, инструментальной поддержке и интеграции с успешным рантаймом
- Haskell, Erlang, Q - наши друзья замыкают процессию

20 мая 2016, 16:23

Dee Mon journal

Покровы сорваны!

Группа ученых под руководством Дэниела Лебреро из Лаборатории Торговых Программных Интерфейсов британской компании IG Markets Ltd провела статистическое исследование о связи числа баг-репортов и языков программирования на базе информации об открытых проектах на сайте "Центр деятельности мерзавцев" (GitHub.com, организация разрешена в России, за исключением некоторых периодов, когда она запрещена). Выяснилось, что наличие статической типизации и продвинутой системы типов не помогает в уменьшении ошибок, а порой даже вредит, в то время как меньше всего ошибок получается в программах на максимально простых языках.

Плотность багов у проектов с 10 звездами и более:


Теперь научно доказано, что theiced был прав: типы не нужны, а писать надо на Кложури. А также Эрланге и Го. Адептам сложных языков и развитых систем типов надлежит раскаяться, одуматься и перестать уже своими надуманными неработающими идеями отвлекать благородных донов, занятых TDD.

20 мая 2016, 08:31

18 мая 2016

nponeccop

Ничего не напоминает?

New features proposed include concurrency and atomics, zero-copy binary data transfer, more number and math enhancements, syntactic integration with promises, observable streams, SIMD types, better metaprogramming with classes, class and instance properties, operator overloading, value types (first-class primitive-like objects), records and tuples, and traits

18 мая 2016, 06:16

17 мая 2016

rssh

Видео со #scalaua

Появились первые записи докладов. Плейлист - https://www.youtube.com/playlist?list=PL-RBtv_a80i6xwA_yGGXzEjScSYuuT-YF .

Вот индекс первого блока:


К сожалению, часть видео записано с провалами (должны же мы были что-то зафейлить :)
Будем надеяться что наибольшие повреждения пришлись на два моих доклада, но посмотрим.
Ну ничего, если следующий раз будет, то сделаем лучше ;)

17 мая 2016, 05:55

15 мая 2016

ru_declarative

Вопрос про Agda:

А никто не знает - на ней хоть какие-то более или менее реальные программы писали, не обязательно сложные - на крайний случай и Тетрис какой-нибудь сойдет, но именно реальные.

PS: И тот же вопрос про Idris, хотя тут менее интересно.

написал kouzdra 15 мая 2016, 03:41

14 мая 2016

nponeccop

ES6 style guide

https://github.com/airbnb/javascript

Впервые вижу руководство по стилю, призывающее использовать фичи. Чаще запрещают.

Вообще хорошо бы написать какое-нибудь абсурдное руководство по стилю для Хаскеля. Например, содержащее требование не использовать анонимные функции, $ и более чем одну аппликацию в строке.

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

14 мая 2016, 06:34

Автоподбор параметров

Пилим тут https://github.com/streamcode9/node-discrete-spsa

An implementation of the Discrete Simultaneous Perturbation Stochastic Aproximation algorithm.

See Stacy D. Hill, "Discrete Stochastic Approximation with Application to Resource Allocation", 2005 http://www.jhuapl.edu/SPSA/PDF-SPSA/Hill_TechDig05.pdf

Cам алгоритм на 5-й странице step1-5, прост как палка.

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

Это всё равно бесконечная игра с подбором learning rate, но наверное получше будет, чем наивный подход "просемплировать всё пространство состояний с заданным шагом, используя статистически значимые бенчмарки".

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

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

14 мая 2016, 05:17

12 мая 2016

nponeccop

Языки под задачи и хаскельный элитизм

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

Выбор языка определяется в основном не "задачей", а наличием команды. Задачи набираются под имеющиеся проверенные команды, команды набираются под имеющихся проверенных техлидов и освоенный ими (пока были джуниорами, миддлами и сеньорами-кодерами) и "испытанный" технологический стек. Под "испытанностью" подразумевается либо использование в пилотном проекте, либо использованием конкурентов. Если "соседи" по индустрии пишут игры на С++ - то один этот факт (при наличии С++ лида) может определить выбор С++ как языка.

Работать на одном стеке гораздо выгоднее, чем каждый раз его менять. Если предприятие начинает использовать какой-то стек по причинам выше (а не "исходя из задачи") - то дальше работает только на нём. Там же целый завод по выпуску ПО - отлаженные технологические процессы, построенные цеха, настроенная инфраструктура, сработавшиеся с друг другом специалисты разных профилей в рамках стека (админы-QA-девы-аналитики-эйчары-пмы и т п). Соответственно, выбора языка на уровне предприятия как такового нет.

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

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

В моём случае С++ я знал "со школы", а "заделами" являлось изучение Perl (это был 1998 год, PHP был относительно маргинальным, а Perl - проверенным решением) и Haskell.

Пилотным для Perl был проект сайта брачного агентства, который сделал одногруппник, а я мейнтейнил (т.е. заметьте, безрисково!). JS учил в проекте с одногруппником, который более-менее его знал. А Haskell я учил по сути все 15 лет последние, с пилотной обкаткой на опенсорсных хобби HNC и N2O.hs и небольших утилитках в продакшене.

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

А на текущей - брать сеньора в команду не по его специализации является моветоном. И наоборот - я как приличный сеньор всегда найду работу по специализации. А внезапных смен языка на текущем месте работы не бывает, см. выше.

Т.е. я намеренно, в течение 15 лет сменял специализацию. "Элитизм" тут проистекает из зарплат порядка 100 дол в час, достижимых на ниве хаскель кодерства.

По С++ для таких зарплат требуется уровень vit_r а то и выше - т.е. кодерством не заработать, нужно очень высококлассное ПМ-ство и техлидство, я это не потяну. А математика - запросто. Там спрос небольшой, но и предложение небольшое, математику без задротства не освоить, а задротов относительно мало в популяции.

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

Короче, "языки под задачи" - это для
а) джуниоров, берущихся за что попало;
б) начинающих контор, берущихся за что попало;
в) при поиске субподрядчика.

12 мая 2016, 16:02

11 мая 2016

nponeccop

Протокол однопоточного воркера

Художественная резьба по диаграммам дала частичный ответ на вопрос об оптимальности однопоточного протокола. Оказывается, если нет ненужных блокировок, разные реализации отличаются всего лишь последовательностью пакетов в половине TCP-соединения, направленной от воркера к гирману (обозначенной как send).

Send и Recv - половины TCP-соединения.
Source и Sink - половины гирмана. Сорс раздает работы, синк принимает результаты.
Grabber и CPU - половины воркера.

исходник

11 мая 2016, 22:28

10 мая 2016

nponeccop

Усиленная версия протокола

В общем случае воркер однопоточный и подключен по WAN, т.е. надо раздавать более 1-й работы (active) и заполнять "трубу" bandwidth x latency (queued). start() точка старта, говорим какие типы работ принимаем. grab - "подпрограмма", используемая в 2-х местах: по выходу из сна и по окончанию работы. run - по окончанию работы и по приходу новой
invariant active + grabbing + queued <= max_active + max_queued
invariant active < max_active && queued == 0
invariant active >= 0 && active <= max_active
invariant queued >=0 && queued <= max_queued
invariant grabbing >=0

max_active = ...
max_queued = ...
grabbing = 0
active = 0
queued = 0

run():
	dequeueJob()
	active++
	queued--
grab():
	<- GRAB_JOB
	grabbing++
start():
	<- CAN_DO test_tube
	<- PRE_SLEEP
-> NO_JOB:
	grabbing--
	if grabbing == 0
		<- PRE_SLEEP
-> NOOP:
	assert grabbing == 0
	while (active + grabbing + queued < max_active + max_queued)
		grab()
-> JOB_ASSIGN:
	grabbing--
	queueJob()
	queued++
	if active < max_active
		run()
-> workComplete:
	active--
	if (queued > 0)
		run()
		assert active == max_active
	grab()
	<- WORK_COMPLETE
-> workData:
	<- WORK_DATA
Основной вопрос - как убедиться, что спецификация корректна? И это всё ешё упрощённый протокол. Так как если в сети congestion - то надо говорить воркерам "горшочек, не вари". В апстриме этого не делается и получается жопа.

10 мая 2016, 20:34

Протокол Gearman

Gearman.org - это такой task queue server, один из вариантов request-response. Идея в том что есть "клиенты", раздающие работу, и "воркеры", выполняющие работу. Клиенты отправляют реквесты, получают респонсы. Воркеры - наоборот. Сервер форвардит.

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

Протокол между гирманом и воркером состоит из 8 сообщений, 4 из которых можно для целей дискуссии проигнорировать, так что остается 4:

<- GRAB_JOB
-> JOB_ASSIGN
<- WORK_COMPLETE
-> NO_JOB

В случае, если воркер у нас однопоточный, наивный обмен описывается грамматикой

GRAB_JOB (JOB_ASSIGN WORK_COMPLETE GRAB_JOB | NO_JOB GRAB_JOB) *

Однако, его можно "улучшить":

GRAB_JOB (JOB_ASSIGN GRAB_JOB WORK_COMPLETE | NO_JOB GRAB_JOB) *

Непонятно, как вообще формализовывать понятие "хорошести".

10 мая 2016, 17:40

Task queue курильщика

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

Сейчас я нашёл подходящий для этого строительный блок.

С его помощью задача 10к раз применить toUppercase() к строке "abc" занимает 700 секунд! Т.е. 70мс на каждый вызов.

Сделано вставкой в плёвую задачу кода индирекшона, который по всем понятиям (что курильщика, что здорового человека) должен занимать заведомо меньше 70мс.

Эти "abc" ставятся в task queue, и задействованы 3 процесса, соединенные через локалхост: клиент, сервер очереди сообщений типа request/response, и воркер.

Я так понимаю, внутри очереди есть какие-то квадратичные алгоритмы, не рассчитанные на 10к сообщений в очереди, причём, скорее всего во всех 3-х компонентах. Достоверно известно, что там точно всё написано по принципу наивного неконкурентного программирования - т.е. двойных буферизаций, учета bandwidth*latency и прочих трюков нет.

Интересно, где зарыта собака окажется.

Upd: сделал бенчмарк, с квартилями, нормализацией, усатыми графиками и шлюхами. Выяснилось, что исправление, которое умозрительно не может замедлять код, его таки замедляет, причём аж на 8%. Но замедляет только говнореализацию сервера на локалхосте. Нормальную реализацию которая на С++ - не замедляет, как и подсказывает нам голова. А сишную нормальную реализацию по WAN даже ускоряет, собственно ради WAN всё затевалось. Говнореализацию по WAN не тестил, но там думаю ускорение в 270% победит замедление в 8%.

10 мая 2016, 06:52

08 мая 2016

Максим Сохацкий

Немного Мадхьямики в MLTT сеттинге



В тибетской традиции есть такое понятие — Дхармадхату — пространтсво всех Дхарм. Это пространство всех мыслей которые существуют вне контекстов. Представить сложно — понятное дело. Но у нас есть MLTT теория которая поможет это представить.

Представьте себе пространство всех языков программирования — понятно дело все знают про лямбда исчисление. Но не многие же рубисты или ПХП программисты задумываются, что они пишут на языке пространства — которое с точностью до битов моделируется теорией типов Мартина Лефа (надо только вселенные правильно отконфигурировать, это научились делать в 2001 году, когда Coq все дружно писали). Конечно я сам в это по началу не верил, и думал что есть все-таки ограничения и что Данила Мастер, который вручную все сам делает вместо того чтобы экстрактить это из Инфинити Топоса делает ненапрасный труд. Мне пришлось написать прувер чтобы понять — таки да, каждый Данила Мастер, который считает себя инженером — производит временный и бесполезный труд, давая ярлыки феноменам не видя их сути.

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

У всех типов есть четкая логика заселения пространства бесконечного топоса, подобно тому как жители самсары заселяют шесть лок. Начинается все с нижнего дна ада — Bottom типа. И потом по кирпичику начиная с Unit (), потом A -> A, потом Nat, потом Stream, потом List, потом ... и так далее вплоть до инфинити-групоида, потом все начинает повторятся и узор начинает меняться. Где у этого узора дырки я пока не вижу, и какая у него структура, но как бы чувствую немного дыхание этой мандалы. Эта мандала доступна впринципе всем программистам, которые могут писать циклы, складывать числа, больше уровня не нужно. Всю эту математику можно переформулировать так, чтобы MLTT преподавать 11 летним детям — считайте, что эксперимент начат.

Не многие знают, что имя линии передачи, которую мы официально представляем в Киеве, называется Лонгчен Ньингтик. KLONG по тибетски — это пространство, пространство всех феноменов, KLONG CHEN NYING THIG обширное пространство сердечной сущности. Так же как Инфинити Топос — это пространство всех MLTT типов, которое объединяет континуум и дискретное, а также проглатывает всю математику со всеми ее логиками и теориями, так как все математики разговаривают уже давно на этом языке кванторов и бесконеченых вселенных.

Так вот, точно также как все языки рождены из этого пространства, так же и мысли все рождаются из одного пространства, и все они проименованы, точно также, как проименованы все типы во всех вселенных. Рождаются тут условно, так как List не рождается, его можно обнаружить понять, но он всегда присуствует в Топосе во всех уровнях вселенных. Все типы являются несозданными, пока их не объявит программист в виде аксиом MLTT. Но если их рассматривать через призму нечистого видения — нетипизированного лямбда исчисления, то рассмотреть их не получится или очень сложно (Алонсо Черч и Боем с Берардуччи не смогли этого сделать). Ну а аналогия просветления — это выход в эту мандалу, где видны все типы сразу, или куда не кинешь взор, видишь везде похожие паттерны. Послушай функциональный программистов — натуральные же шизофреники, видят какие-то катаморфизмы там, где обычный человек видит while или for; видят группы, там где обычный человек видит record; чему обычные инженеры дали уже тысячу ярлыков. Знаете есть такое в духовных практиках быть остраненным и не вешать ярлыки на феномены, потому что это бессмылсенно. Это тоже самое что List/Cons и Stream/Mk — миллионы програмистов дали разныне названия этим штукам, но штуки эти существуют сами по себе и увидеть их можно при индуктивном рассмотрениии заполнения пространства типами начиная с Unit, и сделать это можно начиная уже с третьего шага.

Вообщем аналогии настолько прочные, что я могу в священных тибетских текстах заменять Дхармадхату на "Инфинити Топос", SEMS или Ум на "правила вывода" (кстати один из переводов SEMS — это вычислитель) или на "компютешинал аксиомы", CHOS или DHARMA (Феномен) на Тип и ничего почти не изменится. Процесс мышления — это то как вы конструируете теоремы, как вы выстраиваете рекурсивные цепочки, т.е. как вы композируете мысли (рекурсия и индукция). Если у типа нет рекурсора, значит вы не можете пустить мысль по этому феномену. А пустить мысль по феномену означет его осознание т.е. освобождение в дхармакае, что впринципе соотвествует этимологии слова элиминатор.

Пора положить конец спорам различных школ Мадхьямики (модели сватантрик) и описать все эти логики в виде MLTT программ.

08 мая 2016, 02:03

07 мая 2016

Максим Сохацкий

Erlang Killer Apps

В Эрланг среде принятно считать, что RabbitMQ и Riak, или по крайней мере riak_core — являются киллер приложениями Erlang. Я сам помню на начале своей карьеры тоже поставил на эти продукты и еще на Nitrogen. С нитрогеном я разобрался быстро (он уже история — все используют N2O уже давно). Настала очередь Riak или RabbitMQ, не знал за что взяться. Взялся сразу за распределенную базу, но так быстро на распределенные алгоритмы не наскочишь, а тестами покрывать распределенные системы — это не в этой жизни, может в следующей, если плохо себя вести буду. Вообщем исследование Chain Replication завело меня в тупик зависимых типов и я начал пить™.

Расскажу какие мысли у меня были во-первых по Riak. Riak после всего что я видел до него поверг меня в шок стоимостью обслуживания продакшина. Я с легкостью строил кластера пока не понял что они мне совершенно не нужны. Из riak нужно реально только riak_kv, riak_core и riak_pipe. Причем я даже собирал Riak без bitcask полностью (он вшитый в ядро) и многие другие штуки делал типа порт Riak под Windows 8. Собственно KVS появился как штука чтобы не ебаться с голым riak. В Riak вы храните бинари, а в KVS типы-рекорды описаные в схемах. Это потом в KVS появились бекенды.

Паралельно у меня был кластер из трех RabbitMQ. Тогда уже я понял что производительность RabbitMQ высокая только если они работают в шардах (не кластер, потому что интерконнет хуйовый у эрланга). Т.е. реально RabbitMQ используют все просто как ETS с красивым дашбордом для админов. Забейте хуй на RabbitMQ, эта штука покрыта кольцами как и Riak. Счас есть гораздо емкостные MQ типа emqtt.io (gproc в качестве деливери, mnesia — для дюрабилити), тоже причем с красивыми дашбордами. У меня кстати есть заказ от Остинелли на порт emqtt.io с gproc на syn.

Но я не об этом.

Спросите себя почему MQ и KV сервера в вашем окружении (а они у вас все равно есть, какое бы вы приложение не писали) находятся в разных приложениях. Ведь в вашем приложении MQ обслуживает клиентов, и KV обслуживает клиентов. Поэтому тут работатет data locality, а значит можно посадить это на одни и теже воркеры vnode. Но почему у всех ПОГОЛОВНО MQ и KV сервера — это разные продукты? Почему так? Ответа не нашел. Продуктов нет (разве что redis). Поэтому я подумал написать (еще два года назад) MQ + KV сервер работающий на одном ядре. И ядро это KVS.

KVS отвечает за durability, MQ должен хранить сабскрипшин меш своих подписок а также все сообщения (если очередь скажем персистента или нужны ACK или нужна транзакционность). Вполне очевидно что это можно хранить в том же KVS. Уверен что все люди которые используют RabbitMQ (илии другие MQ продукты) дублируют и синхронизируют свой сабскрипшин меш приложения и состояние подписок в mnesia таблицах RabbitMQ. Нахуя? Незнаю, в моем MQ такого дублирования не будет.

Какие я могу обеспечить показатели MQ сервера на KVS:

1) ну я могу выжать из мнезии 40K RPS на данных которые помещаются в RAM, и 20K RPS на данных которые не ограничиваются ничем. async_dirty естественно.

2) Data Locality. И серверы очередей и серверы данных будут обслуживать на одних и тех же vnode (по 64 или 128 на ноду), т.е. вычислятся хешом по идентификатору пользователя, а значит исчезает необходимость в синхронизации, так как все сообщения от MQ и KV протокола будут помещены в одну и туже очередь пользователя (линеаризация во имя консистентности).

3) Благодаря KVS, и MQ сервер и KV сервер будут поддерживать все бекенды которые поддерживает KVS: mongoDB, SQL, Riak, mnesia, redis.

4) доступ к очередям можно получать напрямую читая их из базы, если нужно. Еще был план написать универсальный REST эндпойнт к KVS как в Riak и CouchDB, и чтобы этот же эндпойнт был API для MQ сервера.

Ну и этот конструктор не имеет ограничений. На KVS можно лепить уже более сложные API и системы. Пример CR хоть и заезженный, но рабочий.

Вообщем надо соединять MQ и KV сервера, мое мнение, а вы делайте как хотите :-)

07 мая 2016, 03:36

nponeccop

Poor man's IOmeter

Вот ещё задача. Есть файл более 4 гб и во много раз превышающий ОЗУ, состоящий из блоков фиксированного размера. Надо написать прогу, читающую из него в течение X минут блоки размера Y со случайным номером c конкурентностью Z.

Должно работать на линуксе i686 и винде x64 и поддерживать блоки размером от 64кб до 16 МБ (c большими блоками может быть минижопа). В виде бонуса - обеспечить чтобы прочитанные страницы не отравляли системный дисковый кэш.

Опять же - как бы делали и какие трудозатраты?

07 мая 2016, 00:00

06 мая 2016

nponeccop

Poor man's ZMQ_PAIR

http://api.zeromq.org/4-0:zmq-socket

В ZeroMQ есть тип соединения ZMQ_PAIR. Идея в следующем: пользователь библиотеки видит постоянно открытое виртуальное соединение между узлами. В него можно слать байтики и принимать байтики. Ошибок пользователь не видит никаких.

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

Как бы вы такое делали, на чём, и какие примерно трудозатраты чисто на сервер, придуряющийся единственным вечносоединённым двунаправленным сокетом?

Допустим, что секьюрити, message semantics/framing layer, application level keepalive и слежение за отсутствием дыр и дубликатов в данных не нужны.

06 мая 2016, 23:47

05 мая 2016

nponeccop

Как научиться хачить Om/Exe/HNC

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

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

Системы типов немного похожи на доказательства в школьной геометрии, а теория категорий - на тождества в школьной алгебре. Так что в первую очередь надо знать их :smile:

Дальше надо понимать, как устроено обобщение в математике. Я думаю, можно прочитать какую-то популярную книжку про группы.

Далее надо научиться писать на хаскеле. Там и алгебра, и геометрия, и группы на каждом шагу.

Пресловутые монады - это вариации на тему групп. А также моноиды и решётки. В HNC оптимизатор использует т.н. верхние полурешётки. Для эффективной работы на хаскеле нужна некоторая практика, чтобы видеть за кодом абстрактные интерфейсы, вроде того как за трансформером стрима в node.js видеть Duplex, а за ним Writable. Только интерфейсы там очень обобщённые, типа тех, что в теории групп.

После хаскеля можно начинать читать книжки по системам типов и системам перезаписи, например TAPL Пирса и Functional programming and parallel graph rewriting

После книжек можно пробовать языки с зависимыми типами - я бы рекомендовал Idris, Lean, Agda. Ну и более продвинутые книжки, вроде Programming in Dependent Type Theory

Ну это довольно полная программа по Type Theory

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

Я столько математики не знаю, и вот пока не придумал, как мне теорию категорий освоить. Но это как бы высший пилотаж. То, что делает zeit_raffer, со своим изобретённым способом выражать спецификациии - это передний край мировой математики. Аналог Маска с его посадкой ракеты на струю. Принципиально ничего нового Маск не сделал, но никто этого не делал раньше в таких масштабах. Так же и у нас, что в Om, что в HNC.

Но глубокое понимание требуется, только чтобы дизайнить Om или HNC. Для того, чтобы писать код, требуется только общее понимание технологий компиляторостроения. И то, это только в случае HNC, который достаточно высокотехнологичен. Ом же на коленках слеплен, там код простой как пробка.

В HNC я использую parser combinators, attribute grammars и уже упоминавшийся lattice dataflow analysis. Ну, и уже упоминавшиеся "абстрактные интерфейсы", вроде использования F-алгебры в качестве итератора по дереву. Оно всё реально код сокращает.

05 мая 2016, 18:20

Языки в проде

У меня 4 рабочих языка: С++, Perl, Javascript, Haskell. Для нового кода выбор невелик: либо Typescript, либо Haskell. В продакшене крутятся все 4.

nodejs достаточно качественно сделан. У того же хаскеля под Windows рантайм-библиотека (реализация ввода-вывода из зелёных потоков) весьма плохонькая, написанная людьми, незнакомыми с системным API.

Учитывая что JS я знал раньше, а нормальные зеленые потоки под Windows мне неизвестны, альтернатива писать event driven на ноде выглядит очень даже.

После хаскеля учить и использовать какой-нибудь C#, F# или Go желания никакого нет. Не говоря уже о незрелых маргинальных поделках, вроде ATS и Idris, у которых на винде совсем-совсем плохо. А в GHC можно будет патч отправить, там вроде почти всё на мази, даже зачатки IO Completion Ports вроде как есть (это высокопроизводительный API для ввода-вывода, аналог epoll)

05 мая 2016, 18:14

Dee Mon journal

все-таки можно!

Говорили, на ноль нельзя делить, а вот британские учоные научились! Берешь хаскель и делишь себе, получаешь конкретные числа:
Prelude> floor (1/0)
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216


Для 1, -1 и 0 ответы разные выходят.

05 мая 2016, 02:48

04 мая 2016

"Записки программиста"

Сборка проектов на Haskell при помощи Stack

Прошло некоторое время с тех пор, как я последний раз писал в этом блоге что-то про Haskell. И вот, мне стало интересно, что успело измениться в мире этого языка. Изменилось, насколько я понимаю, не так уж и много, но вот вместо Cabal для сборки своих проектов теперь все используют какой-то Stack. Давайте же попробуем разобраться, [...]

написал Eax 04 мая 2016, 07:00

03 мая 2016

Максим Сохацкий

Орнаменты

На меня снизошел очередной микро-инсайт-просветление и я сразу же спешу с вами ним поделиться. Абсоюлтно очевидная и прекрасная вещь. Признаюсь честно, что я в глаза формулировок не видел, но вот система сразу нарисовалась перед глазами. Кто читал МакБрайда поправит меня, я уверен.

Как вы знаете, все конструкторы (ко)-индуктивных типов могут состоять из параметров и типа результата конструктора. Последний может и не находиться во вселенной этого типа, а быть типом Path. Так вот параметры этого типа могут быть всего трех видов:

1) Unit, как в типе Lazy A: () -> A или ленивом Nil: () -> List A.
2) Fixed Type как в типе первого параметра коснтруктора Cons: A -> List A -> List A.
3) Recursive Type, как в типе второго параметра tail конструктора Cons, или второго поля tail рекорда коиндуктивного Stream (они равны в MLTT).

Это называется три орнамента. Они все задаются разными профункторами P_{1,2,3}, которые описаны у Паши в блоге. Из этих орнаментов мы конструируем тела термов в наших кодировках (всех их модификациях). Круто да? Это еще не все, суть орнаментов не в этом, а в том что вы можете транзакционно добавлять новые параметры в существующие конструкторы. В современных пруверах и в ООП в операции extend применимое к структурам или рекордам действует на уровне добавления новых конструкторов только, а не модификации (версионировании) существующих. Орнаменты же позволяют делать версионирование типовых интерфейсов и структур, и позволяют избежать случает когда приходится называть линковочные интерфейсы DirectDraw2. С помощью орнаментов вы можете добавлять аргументы в существующие конструкторы или менят их тип. Я привел только три орнамента, которых достаточно чтобы покрыть все существующие базовые библиотеки всех языков программирования :-) А представьте что орнаментов может быть больше!

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

Как вам такой "внутренний лисп" пространства типов?

_______________
[1]. https://personal.cis.strath.ac.uk/conor.mcbride/pub/OAAO/LitOrn.pdf

03 мая 2016, 20:53

Лев тоже вкурсе про то, что ядро должно быть компактным

Лев называет это принципом де Брейна, хотя я такое не встречал в литературе, если кто видел где, покажите, я буду цитировать. Того самого де Брейна, учителя Барендрехта, который первый в мире автоматический прувер сделал AUTOMATH 1967 — голандская школа логиков (они еще записывали самые известные 100 теорем математики для всех систем на то время — http://www.cs.ru.nl/~freek/100 ); HOL/LCF 1972 это второй большой проект — британская школа, который дал миру ML и Хаскель тоже по сути британская школа, как и Агда и Идрис; и первый из современных пруверов Coq (инфинити предикативные вселенные и одна импредикативная внизу aka pCIC) — французкая школа.

https://youtu.be/c_S_bAdv4A0?t=719

Наверно поэтому мы хотим к Барендрехту податься в качестве крыши, т.е. знаменитого эдвайзора (несмотря на то, что он не занимается больше лямбда исчислением), чтобы, во-первых отдать дань уваженя принципам его учителя, который говорил что ядро прувера должно быть компактным, ну а во-вторых Барендрехт буддист, поэтому у меня получится написать ему красивое письмо :-)

03 мая 2016, 11:04

nponeccop

Левая развёртка косписков, anyone?

Код ниже на современном (с arrow functions - это ES5?) джаваскрипте. У натуральных чисел и списков есть, кроме обычного катаморфизма, такая же "штука с алгеброй", но "хитрая", соответствующая левой свёртке:
natCata = (algebra, i) => {

        if (i == 0)
	{
		return algebra(null)
	}
	else
	{
		return algebra(natCata(algebra, i - 1))
	}
}

natCata2 = (algebra, i) => {

	var ret = algebra(null) 
	while (i-- > 0)
	{
		ret = algebra(ret)
	}
	return ret
}
Вот у меня 3 вопроса в связи с этим:
1. Какие ещё структуры обладают этим "левым катаморфизмом"? Должны быть линейными, а ля

data O a = O a (E a) | ONil
data E a = E a (O a) | ENil

и неизоморфными хитрым спискам. Например O a неизоморфен списку из data RR a = OO a | EE a

2. Выразимы ли эти "периодические верёвки" как фиксированные точки функторов? Как вообще выглядит всё это разнообразие верёвок, т.е. какие варианты возможны? вот один, выразимый фиксированной точкой: data XList a b = XCons a (Xlist a b) | XNil b

3. Есть ли дуально "хитрые штуки с коалгеброй", у каких структур данных, и чему они соответствуют.

03 мая 2016, 05:32

02 мая 2016

Максим Сохацкий

OM/EXE Подкаст. Выпуск #1

В будущем самый крутой подкаст про лямбду от Groupoid Infinity:
OM/EXE Подкаст. Выпуск #1:



https://soundcloud.com/maxim-sokhatsky/omexe-podcast

02 мая 2016, 22:33

Андрей Байер тоже за минимальные ядра

Вот тут Андрей Байер (может быть известный программистам по Programming Languages Zoo — сборнике имплементаций ML вариаций), в лекции посвященной элиминатору индукции и равенству выраженному в чистой лямбде, в секции ответов на вопросы, говорит, что критически важно иметь простое ядро прувера:

https://youtu.be/IlfQjWqrK6I?t=3690

02 мая 2016, 07:37

01 мая 2016

nponeccop

Новости HNC

В связи с тем, что в подкаст почти никакой информации об HNC не вошло, надо снова придумать введение.

1. Что такое HNC

HNC - это аналог PureScript для С++, оптимизирующий компилятор из промежуточного языка HN в человекочитаемый С++. На HN можно будет писать вручную, или использовать в качестве бэкенда для более высокоуровневого языка вроде Om.

Ключевые фичи:
1. Человекочитаемость и относительная идиоматичность выходного кода. Сравните выходной Javascript у PureScript и у тех же Elm/Fay/GHCJS.
2. Первоклассный интероп с С++, включая отсутствие чужеродных схем управления памятью (GC, особый аллокатор, подсчёт ссылок и пр)
3. Наличие серьёзного оптимизатора
4. Hackable кодобаза малого размера (до 6к строк).

Основная исследовательская задача - можно ли написать такой оптимизатор из ФЯ, выходной код С++ которого бы проходил ревью человеком, и если нет - насколько можно приблизиться.

С++ выбран как наиболее трудный таргет. Имея рабочую версию для С++, перенацелиться на какой-нибудь Javascript будет просто.

2. Зачем HNC

Борьба с лигаси-кодом на С++. Дописывание компонентов в системы на С++. Быстрое прототипирование для С++. В перспективе расширение идеи на другие языки.

3. Что позволит делать

По задумке, более компактно и с нулевым оверхедом по производительности описывать бизнес-логику в программах на С++. Оставив низкоуровневый код, перекладывающий байтики, на попечении С++ и чистого Си.

От функционального кода на С++ 1х отличается функциональной чистотой, другим синтаксисом и системой типов, а также более простым способом убедиться в отсутствии платы за абстрактность.

4. На чём написано

- Хаскель
- атрибутные грамматики UUAG (с атрибутами на хаскеле)
- библиотека HOOPL для написания оптимизаторов
- библиотеки парсинга и структурной унификации (последяя нужна в выводе типов)

5. В каком окружении работает

Компилятор работает везде, где есть GHC 7.10 (Win,Lin,Mac). Программы работают везде, где есть приличный компилятор С++ (MSVC считается приличным). Собственного рантайма и стандартной библиотеки нет. Прикручиваете по FFI нужные типы и функции и вперёд.

6. Писать работающие программы на нем будет можно? Опердени, высоконагруженные сайты с котиками, видеостримминговые серверы, что-нибуть еще?

В первом приближении - можно использовать в проектах, где в коде есть высокоуровневая часть, которую можно было бы написать на Lua, но нельзя, потому что он тормозит (или Lua не нравится, или религия не позволяет - у С++-ников найдется миллион причин разной степени объективности)

7. Какие платформы поддерживает (сможет поддерживать)?

Сможет практически всё. JavaScript, C#/Java, хоть Perl.

8. Какой интероп? Поддержка нативных типов платформы будет?

Пока можно вызывать функции в обе стороны (С++ <-> HN). Типы только нативные для платформы (в HN можно только функции писать - нельзя объявлять типы. Оверхед интеропа сводится к необходимости заворачивать методы в функции, но это ограничение текущей реализации, а не принципиальное.

Ccылки по теме:

https://github.com/nponeccop/HNC/wiki
https://github.com/nponeccop/HNC/wiki/PaperDraft
https://code.google.com/archive/p/inv/
https://code.google.com/archive/p/inv/wikis/Manifesto.wiki

01 мая 2016, 00:40

30 апреля 2016

Фонд Поддержки Функционального Программирования

Отчёт о мартовском конкурсе по ФП

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

Конкурс по ФП в марте 2016 года: взлом пропорционального шифра

Здесь: генетические алгоритмы, криптография, взлом пропорционального шифра. Налетай, читай, комментируй, критикуй, делись, шарь и социаль.

написал Dark Magus (noreply@blogger.com) 30 апреля 2016, 18:12

darkus

Отчёт о мартовском конкурсе по ФП

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


Конкурс по ФП в марте 2016 года: взлом пропорционального шифра


Здесь: генетические алгоритмы, криптография, взлом пропорционального шифра. Налетай, читай, комментируй, критикуй, делись, шарь и социаль.

30 апреля 2016, 16:11

29 апреля 2016

David Sorokins WebLog

Айвика для кластера и суперкомпьютера

В прошлую субботу выпустил первую версию [5] своей Айвики, которая позволяет создавать и обсчитывать параллельные распределенные дискретно-событийные модели на кластере и/или суперкомпьютере.

В общем, идея такая. 

У меня есть основная версия [2] обще-целевой библиотеки, о которой я много писал у себя в блоге. Она построена на основе стандартного вычисления IO. Самая быстрая версия. Можно автоматизировать вывод графиков и таблиц. Есть документация [1] в формате PDF. Много примеров.

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

Дальше идут приложения. Создаю частные случаи вычислений, удовлетворяющие требованиям обобщенной версии Айвики, но добавляющие те или иные желаемые свойства.

Так родилась версия [4] для вложенных имитаций. Это когда из «настоящего» мы можем относительно дешево и быстро заглядывать в «будущее» модели столько раз, сколько необходимо, а потом на основе полученной информации принимать решения уже в «настоящем». Конек в относительной дешевизне создания вложенных имитаций и в том, что это по-прежнему обще-целевая библиотека имитационного моделирования.

Теперь же воплотил в жизнь еще и версию [5] для параллельного распределенного имитационного моделирования. Тоже обще-целевая библиотека моделирования. Здесь независимые узлы могут обмениваться друг с другом асинхронными сообщениями, привязанными к временным меткам. Если на узле уже «будущее», а приходит сообщение в «прошлое», то происходит прозрачный откат до «прошлого» модели. Все сообщения, которые были посланы узлом и стали устаревшими, отменяются, и, соответственно, рассылаются так называемые «анти-сообщения». Короче, реализована оптимистичная стратегия с прозрачными, возможно, каскадными откатами на основе идей метода «деформации времени» (англ. «time warp»), датируемого началом 80-х.

В распределенной версии экспериментальная реализация механизма синхронизации времени. Есть разные параметры, которые можно настраивать. Правда, с документацией немного туговато, да и требуется хорошее знание Haskell, но там очень мало отличий от основной версии, для которой уже есть документация. Если есть желающие, то пробуйте в своих университетах! :)



написал dsorokin (noreply@blogger.com) 29 апреля 2016, 10:41

27 апреля 2016

Максим Сохацкий

Вопросы на Подкаст

Друзья, перед Первым Категорным Митапом (где Groupoid Infinity будет презентовать свой тайпчекер языка с зависимыми типами и базовой рантайм библиотекой, где все это компилируется в Эрланг) мы решили сделать разогревочный подкаст.

В подкасте планируются такие учасники:
0. Влад Кириллов (@darkproger) — Lagrange Inversion, модератор
1. zeit_raffer — Groupoid Infinity
2. maxim — Groupoid Infinity
3. nponeccop — HNC

1. Знакомство. Все обсуждают текущие свои проекты. Чем они занимались до этого. Я рассказываю про приватбанк, распределенные алгоритмы и их доказательства. Как я через CR пришел к EXE и нашел Пашу. Паша рассказывает про себя. Влад про себя, Процессор про себя.

2. Немного ввод в теорию. Тут каждый рассказывает свое понимание проблемы должно быть нематематично, а эмоционально — интроспекция духовных лямбда поисков. Но может и математично, например про парадоксы, как появились вселенные, про универсумы Гротендика, про HoTT и HIT.

3. Дальше мы обсуждаем архитектуру OM/EXE. Тут все рассказывают со своей стороны, Андрей рассказывает про HNC, мы рассказываем про кодировки, рассказываем про HIT, HoTT и обсуждаем тему божественности MLTT. Готовим людей к тому чтобы слушать доклад про кодировки.

4. Обсуждаем приложения OM/EXE: распределенные алгоритмы, как кафедральный прувер для лабораторных работ. Не забываем что основной задачей подкаста найти людей которые хотят хачить OM/EXE.

Если кто хочет перевести эту беседу или добавить ручайков в русло — пишите, или учавствуйте в подкасте. Или просто оставляйте вопросы к посту, на которые хотите услышать ответ.

27 апреля 2016, 13:01