Функциональное программирование

Распределенный API: по 22 сервера в 2-х датацентрах (Америка, Европа).
Разнообразные клиентские приложения: 40 desktop и web приложений.
Датацентр обрабатывает 12 000 запросов в минуту.
Ресурсоёмкие запросы и пакетные запросы.
Немного о проекте

Возникла необходимость добавить новый источник данных HBase.
С чего все началось?

NoSql – <ключ значение>;
написана на Java;
аналог Google Big table;
не является заменой SQL;
интерфейсы взаимодействия: REST, Java API, Apache THRIFT.
Что такое HBase?

Apache Avro — система сериализации данных.
Система использует JSON для определения структуры данных (схемы), которые сериализуются в компактный бинарный формат.
AVRO

AVRO – схема

HBase + Thrift-AVRO + .NET = ?
AVRO
AVRO
TCP Socket
TCP Socket

Workflow

META-DRIVEN;
результат – простая таблица;
возможность выполнять Map/Reduce;
сохранить отношения данных;
Требования

Проблемы
большие вложенные AVRO схемы до 1 000 000 строк;
AVRO не дружит с .NET;
после десериализации AVRO Dictionary
.

Что делать?
А давайте напишем свой DSL!

Разработка синтаксиса

А давай еще Join’s

А как быстро написать парсер?

Парсинг(синтаксический анализ текста)
ОБЩИЙ ПОДХОД

Парсер генератор на основе формальных языков (ANTLR).
Подключаемая библиотека комбинаторных парсеров (Sprache, SuperPower).
...
Выбор

Написать руками

ANTLR (Another Tool for Language Recognition)
Расширенная форма Бэкуса — Наура
Генератор на основе формальных языков

декларативный синтаксис;
строгое соблюдение грамматики;
не нужно думать о performance;
не нужно писать документацию.
Генератор на основе формальных языков
строгие грамматики;
интеграция с системой сборки;
тяжело отлаживать;
кастомные ошибки;
медленные парсеры;
проблемы с кодировками;
проблемы переносимости.
Плюсы
Недостатки

реализован как библиотека языка;
модульный и поддерживаемый;
полуавтоматическая генерация сообщений об ошибках;
backtracking и look ahead;
возможности в runtime;
не требует предварительной токенизации(лексера).
Комбинаторные парсеры (Sprache и т.д.)
компромисс между декларативностью производительностью;
проблемы с левой рекурсией;
придется учить API;
только для вашего языка.
может не иметь предварительной токенизации.
Плюсы
Недостатки

никакого внешнего кода;
поддается к индивидуальным требованиям;
потенциально быстр, как только это возможно.
Рукописные парсеры
все писать с 0;
создание быстрых парсеров требует опыта;
выражения с инфиксными операторами(приоритеты).
Плюсы
Недостатки

Причем тут функциональное прог-ие?
Основные концепции:
неизменяемые структуры данных;
чистые функции;
функции высших порядков;
рекурсия.

Императивное vs Функциональное

Написать примитивные парсеры(функции).
Написать функции для комбинирования.
Скомбинировать простые парсеры в более сложные.
PROFIT!
Don’t panic it’s monadic!

type Parser = String -> Tree
type Parser = String -> (String, Tree)
type Parser
= String -> (String, T)
type Parser
= TInput -> (TInput, T)
Сигнатура нашего парсера

Пишем простой комбинаторный парсер
Выражение : “42 + 5”
42 + 5
expression
+
42 5
Left operand
right operand
operator

Парсим простое выражение : “42 + 5”
Railroad - диаграмма
Грамматика в БНФ

Библиотеки с готовым набором комбинаторных парсеров для С#
небольшая библиотека, совместима .NET Core;
простой, но богатый API;
много используется в “боевых проектах”: R#, Octostache, EasyNetQ, Seq.
форк Sprache с блэк джеком и …;
использует токинезатор;
парсит потоки токенов, а не поток символов;
хорошие сообщения об ошибках, легко кастомизируются;
работает быстрее.
https://github.com/sprache/Sprache
https://github.com/datalust/superpower
Sprache

Готовый код парсера для “42 + 5”

Ну, а как же без TDD?

Давайте усложним : “42 + 5 - 7”
Railroad - диаграмма
Грамматика в БНФ

Парсер на Sprache “42 + 5 - 7”

DSL (Domain-specific language) Пример: XPath, SQL;
использование NoSQL;
не хватает всей “Мощи” XML;
разработка IDE или плагинов к ним;
клиентские приложения, например, поиск;
анализ документов.
Когда и зачем писать свои парсеры?

Что внутри?

Тип Result

Тип Input (обертка над string)

Начнем с простых парсеров

Пишем первый комбинирующий парсер
Parser
Parser
Then

Строим путь к LINQ’s query синтаксису

Комбинируем

Полный код на GitHub

Фрагмент из клипа Thrift shop ☺
HASL – HBase Avro Snapshot Language

прототип был написан за 1 вечер на Sprache;
был переписан на Superpower;
в дальнейшем все изменения занимали 1-2 часа.
Разработка

Что получилось достичь за 1 день?

Транформирует объекты в таблицу.
Ориентирован на AVRO-схему.
Селекторы для всех типов: object, type[], примитивы.
Фильтры для [].
API функций для сложных вычислений и фильтраций.
Поддержка Join’ов.
Особенности HASL

Перформанс HASL - Основа
Core-I7 6700 3.40 GHz.
Windows server 2010.
x64.

3 424 знаков.
120 строк.
3 Join’а.
102 селектора.
25 с фильтрами.
Полностью отформатирован.
Перформанс HASL – Тестовые данные

Перформанс HASL - Результаты

Схема

Пример запроса

Результат

Спасибо за внимание!