Skip to content

Composition pearls

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

В этом посте я собрал заметные, по моему мнению, примеры композиции в программировании. Тут не будет ничего про docker compose, Jetpack compose, composition api, reusable components, object orientation и подобное, поскольку ничего из этого не имеет ничего общего с понятием композиции. Надеюсь, к концу этого поста, будет понятно, что я имею ввиду под понятием композиции, и почему это хорошо.

Deconstructing composition

Эта часть - общие рассуждения про то, что есть композиция. Можно пропустить это, если не хочется душиться. Для желающих разораться глубже, можно читать дальше.

В одном (буквально) видосе я встретил следующее определение:

Composition := Congruence + Transitivity

Я бы добавил и раскрыл определения, получив следующее:

Composition := Equivalence + Congruence
Equivalence := Transitivity + Reflexivity + Symmetry
Reflexivity := x == x
Symmetry := x == y => y == x
Transitivity := x == y && y == z => x == z
Congruence := x == y => f(x) == f(y)

Для тех, кто не знает уже эти определения: - Equivalence - отношение эквивалентности, т.е. то, что мы считаем "неотличимым", например выражение 2+2 и 4 эквивалентны. Отношение эквивалентности требует три свойства: - Рефлексивность: любая "штука" эквивалентна сама себе: x == x - Симметрия: порядок не имеет значения, если x == y, то y == x - Транзитивность: эквивалентные "штуки" все связаны друг между другом, если x == y и y == z, то x == z - Congruence - возможность заменять эквивалентные "штуки" внутри функции, не меняя значение этой функции. Например 2+2 можно заменить на 4 в любом математическом выражении, как и наоборот, заменить 4 на 2+2.

Вместе, это дает нам композицию. Есть эквивалентность частей, и есть возможность заменять эквивалентные части, не меняя значение целого.

Рассмотрим простой пример: структурное программирование. Далее мы рассмотрим его подробнее. В структурном программировании есть четыре способа строить из малого бОльшее: 

P;Q             // последовательность
if b {P} else {Q} // if-else
while b {P}       // цикл
def f {P} Q     // функция

Мы знаем, что имея эквивалентные программы P и P', т.е. делающие одно и то же, мы можем утверждать, что эквивалентны 

P;Q == P';Q
Q;P == Q;P'
if b {P} else {Q} == if b {P'} else {Q}
if b {Q} else {P} == if b {Q} else {P'}
while b {P} == while b {P'}
def f {P} Q == def f {P'} Q
def f {Q} P == def f {Q} P'

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

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

По построению, x == y => f(x) == f(y) конгруэнтно. Под f можно понимать "отображение семантики", т.е. вложение синтаксиса в семантическое значение: функцию или смысл, в котором смысл композиции известен. В контексте f тогда определяется композируемость исходных "штук". Для примера с структурным программированием, f - будет "семантикой программы", т.е. буквально тем, "как программа выполняется". Именно в этом контексте программы считаются "эквивалентными" и "композируемыми". Если рассматривать другие отображения, например длину кода, то в этих контекстах эквивалентность и соответственно композиция будут другими.

Далее перейдем к практическим примерам.

Структурное программирование

Первый пример, известный всем со времен Дейкстры - структурное программирование. Вместо использования лапши из GOTO, из-за которой сложно понимать, как выполняется программа, предлагается разделить программу на переиспользуемые "блоки":
примитивные блоки обьявление переменной, присваивание, вычисление
sequence выполнить один блок, затем второй
if выполнить либо один блок, либо второй
while выполнять блок, пока условие истинно
function call отдать управление в блок функции, после чего вернуть управление обратно

Все эти примеры имеют одно свойство, позволяющее композировать их: есть ровно одна точка входа и ровно одна точка выхода. Мы точно знаем, что control flow не выйдет за пределы блока, поэтому можем рассуждать о программе, как о композиции частей. Есть даже расширения, позволяющие дополнить эти блоки параллельным примитивом: "блок структурного параллелизма" aka fork-join.
structured concurrency выполнить несколько блоков параллельно/асинхронно, после чего дождаться их завершения

В такой парадигме тривиально писать еще и параллельный код, см. парадигмы map/reduce, которые тривиально параллелятся и композируются.

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

type PrimitiveBlock = ...
type PredicateExpression = ...
enum Block(
  Primitive(PrimitiveBlock),
  Sequence(Block, Block),
  If(PredicateExpression, Block, Block),
  While(PredicateExpression, Block),
  FunctionCall(Block),
)

Видно, что нам достаточно одного фундаментального типа, и пару вспомогательный. Сам тип блока рекурсивный и использует свой тип в своем же определении. Это и определяет возможность композиции и будет встречаться дальше. Эта структура с доработками, известна и называется AST - Abstract Syntax Tree.

Неструктурное программирование

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

Мутабельность мешает композиции поскольку, если P и P' "делают" одно и то же, но меняют наблюдаемые из дальнейших стейтментов переменные, то их нельзя менять друг на друга. Если же из дальнейшего стейтмента изменяемые переменные не наблюдаемы, P и P' взаимозаменяемы. Условно: 

{ // P
  int x = 1;
  print(x);
}
Q;
// эквивалентно
print(1); // P'
Q;
P и P' взаимозаменяемы, поскольку x невозможно наблюдать из Q. Однако 
{ // P
  x = 1;
  print(x);
}
Q;
// не эквивалентно
print(1); // P'
Q;
т.к. в Q можно пронаблюдать x и получить разные результаты в первом и во втором случае.

С исключениями еще хуже (имхо). Использование функции, бросающей исключение, ломает весь control flow вплоть до хендлера try-catch. Поэтому про код, использующий исключения, можно рассуждать, только рассматривая весь набор стейтментов внутри хендлера: если вылетит исключение, оно дойдет до хендлера. Рассуждения же про лишь часть хендлера, будут допускать исключения и переход control-flow вовне рассматриваемой части кода (все еще в тот самый хендлер).

Выражения

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

  • сумма/разница/произведение/деление/остаток от деления/возведение в степень/etc: любой бинарный оператор, из двух значений вычисляет одно, сюда входит неограниченное число любых бинарных операторов
  • унарные операторы: из известных логическое/битовое отрицание и унарный минус, из одного значения делают другое значение
  • константы: значения, которые ничего для себя не требуют и сами являются значениями, также их называют литералами
  • тернарные операторы: по названию и по аналогии, из трех вычислений вычисляют одно, из известных примеров, тернарный оператор(хотя он не единственный) a ? b : c вычисляется в b или в c в зависимости от a, аналог блока if.
  • вычисление функции: по сути обобщение всего выше, т.к. функции могут иметь от 0 до скольки угодно аргументов.
  • переменная: не совсем способ строить выражения, скорее для удобства человека, let x = a in b позволяет не писать выражение a несколько раз, а просто ссылаться на его значение несколько раз по имени переменной x, в выражении b.
  • лямбды: для определения функций, нужен тоже примитив, плюс функции вполне себе являются значениями. Для этого придумали конструкцию лямбда выражения, хотя везде это пишут по разному: lambda/function/func/def/fn/procedure/proc. Суть одна и та же: lambda x: E это функция, которая при применении, вычисляет E, заменяя переменную x на значение аргумента.
  • переменная: несколько раз мы уже их использовали в выражениях, но не сказали, что переменные сами являются выражениями. Так вот, они тоже являются выражениями. Хоть и имеющими смысл только внутри лямбд или после определения.

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

enum Expression(
  Literal(Literal),
  Variable(String),
  FunctionCall(Expression, Expression...),
  Let(String, Expression, Expression),
  Lambda(String, Expression),
)
type UnaryOperator = ...
fn Unary(UnaryOperator, Expression) => Expression.FunctionCall(...)
type BinaryOperator = ...
fn Binary(BinaryOperator, Expression, Expression) => Expression.FunctionCall(...)
fn Ternary(Expression, Expression, Expression) => Expression.FunctionCall(...)

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

Типы данных

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

  • примитивные типы: int, float, char, bool, string суть есть литералы, уже известные типы, определенные в языке
  • списки: List<T>/T[]/[]T/*T - "унарный оператор", который из одного типа делает другой тип
  • другие примеры унарных операторов включают: Maybe(T)/Optional(T) - опциональное значение, () -> T - reader, <R>(T -> R) -> T -> R - continuation, Parser<T> - парсер, возвращающий значение, в принципе любой монадический или тип высшего порядка с одним параметром это унарный оператор над типом
  • аналогично, высшие типы, параметризованые несколькими параметрами/дженериками суть есть n-арные операторы, если угодно, функции, e.g. Either(L, R) - либо L, либо R, Pair(A, B) - пара из A и B
  • тип-произведение/таплы/кортежи/структуры/records: отдельно остановимся на примере с Pair(A, B), мы в принципе можем композировать типы, составляя из них тип, в значении которого есть значения всех исходных типов, это называется кортеж или тапл или структура, в общем имеющаяся в любом языке вещь. Не ограничена по количеству исходных типов, разве что отдельно стоит упомянуть произведение одного типа - это сам этот тип(либо одноэлементный тапл, что в сущности не дает ничего нового). А также произведение нуля типов - это единичный тип unit/void/() с одним значением. Почему именно он, потому что 1 * T = Pair(1, T) кортеж из 1 и T, а т.к. элемент 1 не дает никакой информации, это суть тот же тип T.
  • тип-сумма/enum/union/tagged-union: более экзотическая вещь, обобщение Either(L, R). Аналогично произведению, но содержит значение лишь одного из исходных типов. Нулевой суммой является пустой тип void/unreachable/0/never у которого нет значений.
  • тип-экспонента/возведение в степень: A -> B - по сути n-арный комбинатор (n минимум 2), тип лямбда выражений(функций).
  • массив: [n]T - тип, который параметризован интом и некоторым типом, по сути оператор (int, Type) -> Type, что необычно, т.к. мы используем значение, чтобы сконструировать новый тип. Более общее раскрытие этой идеи существует но несколько сложно, поэтому описывать его здесь не буду. Только упомяну, что все примеры выше это частные случаи зависимых типов. А также "лямбды над типами" суть есть зависимые типы(но не совсем).
  • рекурсивные типы: возможность строить тип, включая в его определение самого себя, e.g. List(T) = 1 + T * List(T). Сюда входят все возможные виды списков и деревьев и рекурсивных структур данных.

В виде типа (для описания структуры типов), это будет как-то так: 

type PrimitiveType = ...
enum Type(
  Primitive(PrimitiveType),
  TypeParameter(String),
  Product(Type...),
  Sum(Type...),
  Exponent(Type..., Type),
  Array(Int, Type),
  Recursive(String -> Type), // e.g. $List => Sum(Unit, Product(T, $List))
)
let Unit = Type.Product()
let Void = Type.Sum()

JSON

Спустимся с облаков абстракций и кратко вспомним что есть JSON: 

enum JSON(
  Null,
  Boolean(bool),
  Number(f64),
  String(String),
  Array(Vec<JSON>),
  Object(Map<String, JSON>),
)

Часть json-а есть json. json состоит из json.

Можно разве что добавить, что последовательность json значений тоже есть json значение, но это все таки чуть другое. Имеется ввиду не JSON.Array, а скорее jsonstream. Тогда 

enum JSON(
  Null,
  Boolean(bool),
  Number(f64),
  String(String),
  Array(Vec<JSON>),
  Object(Map<String, JSON>),
  Stream(Stream<JSON>),
)
fn to_stream(Vec<JSON>) -> Stream<JSON>

Разница между Array и Stream в том, что Array суть есть ограниченный набор значений, у которого например есть длина и имеет смысла понятия над несколькими значениями, например сумма значений массива. Stream же это же возможно неограниченный поток значений, у которого нет длины, и сумму которого нельзя посчитать в общем случае, а также значения обрабатываются независимо друг от друга. Array можно привести к Stream, забыв про длину и ограниченность списка. Зачем все это нужно станет понятно далее.

JQ

Ультимативный, на мой взгляд, пример композиции. Ничего более полного и композиционного человечество как будто еще не придумало. jq суть есть язык запросов над json, т.е. описывает некоторое подмножество функций вида JSON -> JSON. Эти запросы называются фильтрами, поэтому далее будем их так называть. Не буду повторять тут всю функциональность, приведу несколько важных примеров, которые можно проверить в playground:

  • . - identity фильтр, что пришло на входе, то отдает на выходе
  • <json> - фильтр, игнорирующий входное значение, и отдающий литерал json
  • f | g - фильтр, который применяет фильтр g к результату фильтра f. В простонародье, оператор композиции, хотя сам символ обычно называют pipe.
  • .key - по обьекту отдает значение по указанному ключу: {a: 1, b: null} | .a = 1
  • .[1] - аналогично, для получения элемента списка: [1, 2, 3] | .[1] = 2
  • f + g - и другие бинарные операторы, просто вычисляют значение оператора над результатами искомых фильтров, e.g. . + 2 прибавляет 2 к входному числу, . * (. + 1) вычисляет x * (x + 1) для каждого x из входного стрима. Заметим, что f, g это фильтры, и здесь сумма - есть "сумма" фильтров, т.е. функция JSON -> JSON, а не некий конечный результат.
  • .[] - фильтр, преобразующий массив в стрим, каждый фильтр хоть и действует на одно JSON значение, по факту они тривиально расширяются до Stream<JSON> -> Stream<JSON> отдавая стрим из примененных фильтров к значениям исходного стрима. Стримы конкатенируются, поэтому [[1, 2, 3], [4, 5]] | .[][] это стрим 1, 2, 3, 4, 5. Запись через запятую опциональна, обычно используется для вложенных стримов. На верхнем уровне, элементы стрима обычно разделяются переносом строки (хотя это тоже опционально). Таким образом
  • , - создает стрим из двух значений: 1, 2 = 1, 2(wow). Стримы все так же конкатенируются(стрима из стримов не бывает), поэтому ([1, 2, 3][]), ([4, 5][]) = 1, 2, 3, 4, 5
  • map(f) - применяет фильтр f ко всем элементам массива, e.g. [1, 2, 3] | map(. + 1) = [2, 3, 4]
  • select(f) - возвращает исходный элемент, если f от него истинен, иначе возвращает пустой стрим. Позволяет реализовать фильтр, без специальной для этого функции: [1, 2, 3] | map(select(. % 2 == 1)) = [1, 3]. Вообще говоря, это расширяет наше понимание понятия фильтров jq, т.к. можно думать о них как о JSON -> Stream<JSON>, и этот стрим может иметь как 0 или 1 элемент (select), так и 1 элемент (map/преобразование/transform), так и более 1 элемента(аля flatmap).
  • [stream] - стрим, полученный внутри квадратных скобок преобразует стрим в список: [[1, 2, 3][] | . + 1] = [2, 3, 4]. В сущности, это просто конструктор json массива, который принимает стрим. Также, теперь мы можем понять, почему map($f) это синтаксический сахар для [.[] | $f] - фильтр, который преобразует массив в стрим, затем применяет фильтр к каждому элементу, затем конструирует список из стрима. То есть, даже map не является примитивом.
  • from_entries/to_entries/with_entries - имея мощные возможности для работы с списками/стримами выше, ожидается что будет "параллельные" операторы для работы с словарями(обьектами). В этом нет необходимости, поскольку: 
    $ {a: 1, b: "B"} | to_entries
[
  {
    "key": "a",
    "value": 1
  },
  {
    "key": "b",
    "value": "B"
  }
]

$ [{"key": "a", "value": 1}, {"key": "b", "value": "B"}] | from_entries
{
  "a": 1,
  "b": "B"
}
    И, наконец, with_entries(f) = to_entries | map(f) | from_entries, по сути удобный alias.

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

  • f | g - "последовательная композиция"
  • map($f) - преобразование фильтра $f: JSON -> JSON в map($f): Array(JSON) -> Array(JSON)
  • to_entries | map($f) - преобразование фильтра $f: {key: JSON, value: JSON} -> JSON в to_entries($f): Object -> Array(JSON)
  • map($f) | from_entries - преобразование фильтра $f: JSON -> {key: JSON, value: JSON} в from_entries($f): Array({key: JSON, value: JSON}) -> Object
  • with_entries($f) - преобразование фильтра $f: {key: JSON, value: JSON} -> {key: JSON, value: JSON} в with_entries($f): Object -> Object
  • $f + $g - преобразование фильтров $f, $g: JSON -> JSON в $f + $g: JSON -> JSON

jq фильтр состоит из jq фильтров и jq фильтры в композиции образуют jq фильтр.

Composable SQL

Хотя существуют попытки интеграции jq в sql, здесь мы рассмотрим композиции запросов над реляционными данными безотносительно базовой модели в виде json-а. Мы знаем, что основой SQL является реляционная модель, а именно реляционная алгебра. И запросы суть есть реляционные операторы. Что есть реляционный данные? Для нас достаточно представления, что реляция(relation/table) это таблица из данных одного вида: []{column1: datatype1, column2: datatype2, ...}. Реляционные операторы же, это функции над подобными данными, общие, чтобы не зависеть от конкретной схемы(схемой называют тип конкретной таблицы). Приведем несколько примеров, чтобы перейти от абстрактных определений на практическую землю:

  • унарные
    • проекция(π): select column1, column3 преобразует таблицу, выделяя только заданные столбцы: []{column1, column2, column3, ...} -> []{column1, column3}
    • фильтрация(σ): where E оставляет только те элементы, которые удовлетворяют предикату, т.е. E может содержать только столбцы из исходной таблицы и литералы, а сам оператор преобразет таблицу в таблицу с той же схемой.
    • переименование(ρ): rename column1 as columnX переименовывает один столбец: []{column1, column2, ...} -> []{columnX, column2, ...}
    • в принципе, это можно выразить через другие операторы, но для простоты оператор select также позволяет добавить вычисленные столбцы: select E: []schema1 -> []schema2, где E - выражение над столбцами из schema1, который дает набор столбцов schema2.
    • сортировка: order by E - сортирует таблицу по выражению E: []schema -> []schema
    • limit/offset: limit/offset N оставляет только часть строк таблицы: []schema -> []schema
  • бинарные
    • обьединение(∪): t1 union t2 - обьединяет две таблицы в одну, при этом у исходных таблиц должна быть одинаковая схема, эта же схема будет у результирующей таблицы: ([]schema, []schema) -> []schema
    • пересечение(∩): t1 intersect t2 - оставляет только те элементы, которые есть в обеих исходных таблицах: ([]schema, []schema) -> []schema
    • exclude(-): t1 - t2 - оставляет только те элементы из t1, которых нет в t2: ([]schema, []schema) -> []schema
    • произведение(×): t1 cross join t2 - делает таблицу, в которой строки - всевозможные пары строк из исходных таблиц, при этом исходные схемы не должны иметь столбцы с одинаковыми названиями: cross: ([]schema1, []schema2) -> []{...schema1, ...schema2}
    • join(⋈): t1 join t2 on E - по сути alias для t1 cross join t2 | where E: join: ([]schema1, []schema2) -> []{...schema1, ...schema2}
  • изысканые операторы
    • pivot: (хз какой у нее синтаксис, я так его и не осилил, но суть такая) t pivot $Q by E: []schema -> []E(schema) вычисляет $Q от каждой набора строк, которые вычисляются по E, делая в результате схему по E. Например, исходная таблица t = []{weekday: monday|tuesday|..., count: integer}, тогда t pivot sum(count) by weekday вычислит таблицу []{monday: integer, tuesday: integer, ...} с суммой count по каждому дню недели. Другими словами, это способ "повернуть" таблицу на бок. Очень сложная операция по синтаксису и семантике, поэтому редко используется, хотя иногда бывает полезна.
    • window: t window $Q by E - вычисляет "окна" строк по E, вычисляя $Q над каждым набором строк в каждом окне. Окнами могут быть наборы подряд идущих значений, или значения "на 3 вперед на 2 назад", или только с определенными значениями в столбце и тд. Итоговый тип window: []schema -> []Q(schema) с результатами по каждому "окну".
    • group by: частным случаем window(но это не точно) является группировка, в которой все окна не пересекаются. t group $Q by E (синтаксис выдуман) вычисляет $Q по каждой группе строк с одним и тем же значением E. groupby: []schema -> []Q(schema) аналогично window.

Мы уже видим, что некоторые операторы повторяются: join = cross + where, group = window, плюс SQL включает возможность фильтровать по группам через HAVING, что ничем в конечном счете не отличается от where после группировки. Вся эта сложность и избыточность идет из того, что язык SQL имеет фиксированную схему и все эти базовые операторы упаковывает в один большой оператор вида 

SELECT [ ALL | DISTINCT [ ON ( expression [, ...] ) ] ]
    [ { * | expression [ [ AS ] output_name ] } [, ...] ]
    [ FROM from_item [, ...] ]
    [ WHERE condition ]
    [ GROUP BY [ ALL | DISTINCT ] grouping_element [, ...] ]
    [ HAVING condition ]
    [ WINDOW window_name AS ( window_definition ) [, ...] ]
    [ { UNION | INTERSECT | EXCEPT } [ ALL | DISTINCT ] select ]
    [ ORDER BY expression [ ASC | DESC | USING operator ] [ NULLS { FIRST | LAST } ] [, ...] ]
    [ LIMIT { count | ALL } ]
    [ OFFSET start [ ROW | ROWS ] ]

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

WITH
    t1 AS $Q1,
    t2 AS $Q2
$Q

"Оператор" with аналогичен let t1 = $Q1 in $Q, т.е. действительно способствует композиции. Но из-за грамматики SELECT запросов, вместо 

WITH
    t1 AS SELECT ... GROUP BY A
SELECT * FROM t1 WHERE B
предпочтительней делать 
SELECT * FROM ... GROUP BY A HAVING B

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

from invoices
filter invoice_date >= @1970-01-16
derive {
  transaction_fees = 0.8,
  income = total - transaction_fees
}
filter income > 1
group customer_id (
  aggregate {
    average total,
    sum_income = sum income,
    ct = count total,
  }
)
sort {-sum_income}
take 10
join c=customers (==customer_id)
derive name = f"{c.last_name}, {c.first_name}"
select {
  c.customer_id, name, sum_income
}
derive db_version = s"version()"

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

  • from - берет исходную таблицу
  • filter - фильтрует строки по условию
  • derive - добавляет новые столбцы
  • group - группирует строки, причем содержит блок с подзапросом над группой
  • sort - сортирует строки
  • take - берет первые N строк
  • join - "джойнит" таблицы, давая обьединенную таблицу на выходе
  • select - берет нужные столбцы

Т.е. композиция достигается через последовательность элементарных операторов (поэтому язык называется pipelined), а также через переиспользование запросов в group блоках. Другие примеры использования подзапросов включают в себя рекурсивные запросы, window и алиасы таблиц. Все это возможно сделать и в SQL, но для каждого из этих случаев выделен отдельный кусок грамматики внутри общего оператора SELECT. Никакого переиспользования и композиции запросов при этом нет, в отличие от prql.

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

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

Parser combinators

Функции из строк/байтов/стрима токенов в некоторую структуру называют парсерами. В частности, парсеры языков или форматов файлов тоже являются парсерами в этом смысле: они берут исходный файл и по нему создают некую структуру этого файла: AST для языков программирования, DOM дерево для HTML, список структур для csv, JSON для .json и тд и тп. Для подобных парсеров известны способы их комбинирования, они и называются парсер комбинаторами. Сначала примеры примитивных парсеров, из которых строятся более сложные:

  • парсер одного символа(anychar): берет символ, какой бы он ни был, и пропускает его в последовательности, результат - этот символ
  • парсер одного определенного символа(char(c)): берет символ, если он совпадает с данным, отдает его, иначе отдает ошибку парсинга аля expected ) but found ], также для простоты, в конец файла иногда "вставляют" символ EOF, поэтому ошибка парсинга может выглядеть как expected , but found EOF.
  • парсер заданной строки(string(s)): берет символы, пока они соответствуют заданной строке, иначе отдает ошибку парсинга. Полезно для известных элементов синтаксиса и ключевых слов, тоже отдают ошибку вида expected e, but found a, но могут быть и более подробными: expected false, but found falsa.

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

  • парсер последовательности(seq(p, q)): применяет парсер p, в случае удачи применяет парсер q, возвращает в качестве результата пару из обоих результатов. e.g. парсер json-строки это seq(char("), string_char, char("))
  • парсер альтернативы(alt(p, q)) - применяет парсер p, в случае неудачи применяет парсер q, результат - Either от результата p либо q. Используется для решения, что сейчас парсится, например можно представить alt(string("null"), json_bool, json_number, json_string, json_list, json_object) как парсер произвольного json значения.
  • парсер повторения(many(p)/many1(p)/star(p)): парсит p, пока не упрется в ошибку, возвращает список полученых результатов, при этом может проверить, что распарсилось минимум N элементов. Может использоваться, например, для парсинга структуры исходного кода, как последовательности функций, или блока кода, который является последовательностью statement-ов и тд.
  • парсер повторения с разделителями(intersperse(p, delim)) - парсит p, и парсит delim между ними, возвращает список результатов парсера p. Полезно для парсинга comma-delimited списков.
  • парсер опциональности(opt(p)) - парсит p, возвращает Some в случае успеха, None в случае ошибки. Т.е. всегда успешен и никогда не возвращает ошибку.

Собственно, все видно и так, весь парсер строится из комбинации других парсеров, поэтому и называются парсер комбинаторы.

На самом деле парсеры это пример монады, кроме указаного выше, для них определен bind: (Parser(T), T -> Parser(R)) -> Parser(R), т.е. парсер, которые применяет другой парсер, в зависимости от распаршеного значения. Аналогично можно описать любую другую монаду, для которых определены общие операции: 

return: T -> M(T)
map: (M(T), T -> R) -> M(R)
bind: (M(T), T -> M(R)) -> M(R)
так и операции и конструкторы с специфическими монадами. Мы не будем их все разбирать.

Файловая система

Сразу пара примеров реализаций, а также virtual file system в самом ядре линукса. В чем идея: есть базовый интерфейс для работы с файлами, аля 

type Permission ...
type File ...
type Stat ...
interface FS {
  Open(String, Permission) Result<File>
  Stat(String) Result<Stat>
  Remove(String) Result<()>
  Cd(String) Result<FS>
  Mkdir(String) Result<()>
  Mount(String, FS) Result<()>
}

И этот интерфейс может быть реализован поверх чего угодно:

  • поверх разных файловых систем на диске
  • в оперативной памяти(memfs/tmpfs)
  • над s3 хранилищем
  • удаленные(remote) файловые системы: sshfs, FTP
  • цифры числа пи
  • HTTP как файловая система
  • в качестве файловой системы использовать состояние какой-то программы или внутреннего состояния системы, т.е. когда по факту никаких файлов нигде нет.
  • и так далее

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

  • Cd отдает файловую систему, ограниченную заданной директорией внутри исходной файловой системы
  • можно сделать шифрование, чтобы в исходной файловой системе все было зашифровано, а для пользователя выглядело расшифрованым
  • можно ограничить права пользователя, чтобы он не видел "спрятанные" файлы, или не мог, например, их перезаписать(аля rofs)
  • Mount позволяет "подключить" одну файловую систему как директорию внутри другой файловой системы. Это позволяет работать с любыми типами файловых систем внутри одной глобальной. Также это позволяет работать с несколькими физическими дисками на одном компьютере, просто эти диски будут разными "директориями".
  • Само оперирование с файловыми системами при наличии нескольких файловых систем в одной, дает возможности, например, скачать файл из s3 в локальную файловую систему или наоборот загрузить его. При этом пользователь использует базовые операции файловой системы, а вся реализация протокола, буфферинга, авторизации и тд и тп будет на стороне файловой системы.

Composable database

Идея исключительно основана на одной статье, но тем не менее я считаю достойна упоминания. Аналогично файловой системе, база данных это интерфейс для получения данных, но в отличие от файловой системы не иерархичный. Здесь под базой данных мы понимаем некоторый key-value storage аля mongodb или redis или что угодно. Каждая запись по ключу это просто набор байт в конечном счете, возможно с метаданными, типо id или время изменения и тд. 

type Record = ...
interface DB {
  Get(String) Record
  Put(String, Record)
  Delete(String) Option<Record>
  List() Vec<String>
  Watch(String) Stream<Record>
}

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

  • union: из двух баз данных можно получить одну, в которой пространство ключей будет обьединением исходных, доступ по ключу в новой базе данных будет внутри идти в нужную исходную базу данных
  • аналогично хранению директорий в s3(s3 на самом деле key-value, поэтому можно использовать DB как FS и наоборот) можно разграничивать пространства ключей через разделители аля /, это позволит нам
    • mount-ить базы данных, и чтобы они не пересекались указывать префикс, аля db := mount("/users/", users_db, "/posts/", posts_db), тогда db.Get("/users/123") вернет пользователя users_db.Get("123"), а db.Get("/posts/123") вернет пост posts_db.Get("123")
    • ограничивать доступ только к определенному подпространству ключей, db := Filter(users_db, id => id == my_id) ограничивает базу данных до доступа только к своему пользователю, аналогично можно ограничивать подпространства ключей, например посты только своего пользователя
    • можно ограничить запись, сделав базу данных доступной только для чтения
    • продолжая идею, можно сделать базу данных доступной только для чтения, еще и в красивом виде, аля html страниц или чего либо еще. По сути это map над значениями базы данных. Также это позволяет делать представление по одному пути, аля /postHTML, тогда запись в /post/123 приведет к изменению /postHTML/123
  • можно добавить валидацию на ключи и значения, ограничивая запись
  • подключиться к удаленным базам данных
  • http as kv db

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

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

Линзы

Продолжая тему композиционного доступа к данным, предположим, что у нас есть структура, которая ни реляционная база данных, ни key-value storage, и даже не json. А просто что-то, к чему есть какой то доступ и которую как то хочется мутировать. Звучит максимально абстрактно, потому что так и есть:

interface Lens<S, A> {
  Get(S) A
  Put(S, A) S
}

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

Идея в том, что Lens<S, A> это интерфейс, который позволяет делать две вещи:

  • по "целому" S, получить "часть" A
  • по части A, и "целому" S, заменить "часть" A на указанное значение

Как примеры:

  • линза по спискам: lens_index(i) := {get(xs) => xs[i], set(xs, x) => [...xs, i: x]}
  • линза по словарям: lens_key(k) := {get(m) => m[k], set(m, x) => {...m, k: x}}
  • что то более абстрактное

Можно уже увидеть, что композицию можно строить вдоль "часть части": 

function LensCompose<S, A, B>(l1 Lens[S, A], l2 Lens[A, B]) Lens[S, B] {
  return {
    Get: (s: S): B => l2.Get(l1.Get(s)),
    Put: (s: S, b: B): S {
      a := l1.Get(s)
      return l1.Put(s, l2.Put(a, b))
    },
  }
}

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

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

function Over<S, A>(l Lens[S, A], f func(A) A) S {
    return l.Put(s, f(l.Get(s)))
}

Также можем сделать A не частью S, а другим "представлением" S, например шкалой фаренгейта вместо цельсия, или битсет, вместо списка булов и тд. Тогда Lens[S, A] это пара функций, которая сводится к: 

interface Iso<A, B> {
    To(A) B
    From(B) A
}

И является изоморфизмом между типами. Композируется так же, как и линзы, с доп. гарантией, что композиция Iso это Iso.

По факту не очень полезный на практике пример (нужен больше в haskell, где сложно менять часть сложной структуры), но тем не менее интересен как пример композиции нетривиальной пары функций getter/setter.

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

SC

Еще один, вдохновивший меня, пример. На этот раз одна конкретная cli тулза на zsh-е, в которой реализована одна идея, которая, как мне кажется, была бы полезна много где. Тулза называется sc. Она древняя, и на zsh, и не работает, и я не помню как ее нашел. Но как то сохранил и недавно переписал форк на го, чтобы более менее работало (UPD: оно снова не работает, мне впадлу чинить реверснутое кривое апи этого ебаного сервиса). В описании не сказано ничего про композицию 

A lightweight soundcloud client, conforming to unix philosophy.
но сказано про unix philosophy, суть которой в том, чтобы "писать программы, которые могут работать вместе". Как по мне это хорошая цель, но плохая идея в свете "текст это универсальный интерфейс". Из за этого 50%(цифра взята с потолка) скриптов это чистка и парсинг данных из одной утилиты для другой. Напоминает helm темплейтинг, в котором нужно каждый отступ и каждый ескейп сделать правильно, чтобы дай бог ничего не развалилось. Вместо этого всего, более жизнеспособными альтернативами видится использование json-а или даже вообще типизированных представлений.

В любом случае, это про композицию между разными программами. Также программа сама часто запускается, переиспользуя свои собственные данные. И ключевая идея в sc в том, что ее команды могут брать вывод самой команды sc, предоставляя "композиционное апи" над разными сущностями. Чтобы было понятнее, как это происходит, сначала разберем, какими базовыми сущностями оперирует sc. sc - это клиент к soundcloud, поэтому (сокращено для краткости): 

struct Track {
    ID            uint64
    UserID        uint64
    Plays         int
    Favoritings   int
    Comments      int
    Title         string
    Desc          string
    Last_modified time.Time
    Downloadable  bool
    Dur           time.Duration
}

type User struct {
    ID           uint64
    Username     string
    Plan         Free | Pro | Premium
    Followers    int
    Desc         string
    Tracks       int
    Img          string
    LastModified time.Time
}

Всего две сущности: пользователь и трек. На самом деле есть еще сущность запроса(Query), но я неоч понял, зачем она. Что же с этими сущностями можно сделать? Ну, как минимум получить:

  • sc user id/username - получает пользователя по id или логину
  • sc track id/title - получает трек по id или названию
  • sc resolve id/username/title - получает пользователя или трек id, логину или названию, что найдется

Отлично, мы получили пользователя и/или трек. Что с ними делать? Как получить треки пользователя? Как получить друзей пользователя? Как получить автора трека? Для всего этого есть подкоманды, которые на вход принимают соответствующую сущность:

  • sc resolve user | sc tracks - получить треки пользователя
  • sc resolve user | sc followers - получить подписчиков пользователя
  • sc resolve user | sc followings - получить, на кого пользователь подписан
  • sc resolve track | sc user - получить автора трека, здесь команда sc user не требует id/username, т.к. достает его из входного трека

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

sc user satont | sc followers | sc tracks

Как это работает, как было упомянуто выше, для промежуточного представления используется json. Но если просто принтить всегда json в консоль, то это будет нечитаемый minified json либо огромная структура, из которой куча строк занимают скобочки. Вместо этого sc умудряется печатать красивый человекочитаемый вывод. Для этого, sc проверяет перед выводом, является ли stdout терминалом или чем то другим (пайпом). В зависимости от этого можно печатать красиво или стандартизированную json-ину, для каждой базовой сущности со своей схемой. Это же позволяет композировать вызовы sc с jq, например, чтобы получить id пользователя: 

sc user satont | jq .ID

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

sc resolve user | sc followers | jq 'select(.Plan == "Premium")'

Кроме базовых сущностей, можно получать "побочные", например получить аватарку пользователю, или обложку трека, или вообще включить трек: 

sc user freddiedredd | sc art
sc track thecometiscoming/blood-of-the-past-feat-kate | sc art
sc track id | sc play

Возможности ограничены только фантазией. В качестве "клея" для програм, выдающих json, очевидно, достаточно только jq. Ну или как минимум избавит баш скрипты от тонны head, tail, sort, cut, tr, awk, sed и т.д. что уже сделает мир чуть лучше.

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

Картинки

Абстрактно, картинка это 

struct Image {
    Width, Height int
    At(x, y int) Color
}

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

  • одноцветные, At всегда возвращает константу
  • любые градиенты и текстуры, зависящие от координат, могут вычисляться в At

И бесконечные возможности для композиции:

  • картинка с измененным размером, At делает внутри мапинг и идет в исходную картинку
  • обрезание(crop) картинки, уменьшение размера и поход в At к "части" исходной картинки
  • маска(mask(m, im)), при которой At отдает фул прозрачность, если попали в маску m(в белый цвет, когда все цвета там либо белый либо черный), или im.At в противном случае
  • склеивание картинок(merge(im1, im2)), при котором At отдает im1.At в области im1, и im2.At в области im2. Области, в которых располагают картинки могут быть произвольные, хоть по вертикали, хоть по горизонтали, хоть куда угодно и с ресайзом.
  • эффекты, накрученные поверх картинки, это включает фильтр, шейдеры, перекрашивание и изменение цветов, whirl искажения, морфы, прозрачность и тд и тп
  • наложение двух картинок друг на друга с смешиванием(blend), кто использовал слои в фотошопе, тот поймет
  • отражения, повороты и трансформации картинок осуществляются все так же через замену координат внутри At
  • добавление текста или геометрических фигур поверх картинки, в принципе текст можно сам по себе сделать картинкой, параметризованой размером шрифта, шрифтом, текстом и цветом. А затем наложить ее поверх другой. Аналогично с геометрическими фигурами, которые можно сделать маской, а затем через наложение маски, покрасить их.
  • нереальные эффекты и анимации, если параметризовать функцию At временем, в этом случае мы почти получим видео(почти - потому что без звука), и с ним можно работать еще и вдоль временной плоскости: ускорять, замедлять, разворачивать, нарезать
  • чтобы поставить один пиксель, можно взять картинку "с одним пикселем" и наложить ее поверх исходной, поэтому возможен pixel perfect

В общем возможности ограничены только фантазией, а так весь фотошоп можно в теории уместить в библиотеку с минималистичным и композиционным интерфейсом.

ffmpeg

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

ffz emotes

Пропуская историю про "конкатенативные языки", где "конкатенативные" - означает буквально "композируемые", вспомним про смайлы 7tv/ffz/bttv:

cannyCat

Показывает один эмоут.

К этому можно добавить модификаторы: ffzX, ffzW, ffzCursed, etc.

cannyCat ffzCursed

Показывает тот же эмоут с эффектом затемнения.

В этом в принципе вся идея. У тсодинга есть похожий проект.

Идея мне настолько понравилась, что я придумал, но не реализовал (потому что это фронтенд и потому что libwebp кривая хуйня) проект/язык с стековой композицией эмоутов. Идея в том, чтобы добавить всякие разные модификаторы, в том числе zero-width эмоуты, композицию нескольких эмоутов и делать длмнные сложные выражения в виде эмоутов:

Watching dup stackx Ceiling stackx Resting vahui Ceiling stackx stackx Resting WatchingR dup stackx stackx stacky stacky

или попроще:

DIESOFCRINGE DIESOFCRINGE revt stackt

По сути получился стековый язык над смайликами. Композируемый так же, как и другие конкатенативные языки.

Noita wand building

Есть такая игра Noita. Очень кратко - суть в том, чтобы собирать спелы и собирать из них более мощные спелы.

  • базовые спелы(projectile) - просто создают снаряд, который летит и наносит урон
  • модификаторы(modifier) - берут следующий спел и меняют его параметры
  • мультикаст(multicast) - берут несколько следующих спелов и кастуют их одновременно
  • особые(other) - копируют спелы, меняют порядок каста и тд

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