Язык catlang компилируется в один гигантский SQL-запрос

Автор блога reasonablypolymorphic.com рассказывает, что в свободное от работы время написал небольшой язык программирования catlang, который компилируется в SQL. Это не новый язык запросов: catlang, именно язык программирования, а его компилятор выдаёт один гигантский оператор SELECT. Если выполнить этот запрос в Postgres, получится результат работы программы.

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

В качестве демонстрации приведена функция count: она принимает аргумент x и, по словам автора, возвращает 100 при любом входе, но делает это через эквивалент цикла while. Исходный синтаксис похож на запись arrow notation (блок proc), автор хотел заодно получить рабочий преобразователь такой записи и обещает рассказать об этом отдельно. Внутри цикла из значения i вычисляется текущее значение переменной цикла n; затем из n вычитается 100 и берётся модуль. Функция abs здесь необычная: для отрицательного входа она возвращает Left (abs x), иначе Right x (Left и Right переименованы в inl и inr). Если n − 100 меньше нуля, срабатывает ветка inl: к n прибавляется 1, результат оборачивается в inr, и цикл воспринимает это как «повторить с новым значением». Иначе n − 100 неотрицательно, и n возвращается напрямую. Автор признаёт, что пример окольный: запутанность, не самоцель, а следствие поиска концептуально простых вещей, которые легко свести к категорной форме.

После такого преобразования count превращается в промежуточное представление из комбинаторов: id, △, ▽, cochoice, dist, undist, проекций prj₁ и prj₂ и операторов вроде ⨟ (по определению автора, «A ⨟ B» означает «выполнить A и передать результат в B»). Идея в том, что у каждого символа простая и точная алгебраическая семантика, поэтому достаточно описать преобразование из категорного IL в другую область, и компиляция в самые странные цели становится тривиальной, в том числе в SQL.

Затем показан сам сгенерированный SQL, в тексте он назван «чудовищным». Это глубоко вложенные подзапросы WITH, UNION и CROSS JOIN, а цикл реализован через рекурсивное общетабличное выражение WITH RECURSIVE; значения хранятся в столбцах f0, f1 и так далее, а недостающие ветви заполняются NULL::integer. Доступный фрагмент записи обрывается посреди этого SQL, поэтому дальнейшие разделы здесь не пересказаны.

Ключевые факты

Автор написал язык программирования catlang, компилятор которого выдаёт один гигантский SELECT; при запуске в Postgres запрос даёт результат программы.
SQL выбран как забавная цель компиляции для проверки главной идеи: промежуточный язык построен на абстрактных конструкциях теории категорий.
Пример count по словам автора возвращает 100 при любом входе, реализуя цикл через ветвление inl/inr и операцию loop.
Промежуточное представление состоит из комбинаторов (id, △, ▽, cochoice, dist, undist, prj₁, prj₂); ⨟ означает «выполнить A и передать результат в B».
Сгенерированный SQL использует WITH RECURSIVE, вложенные WITH, UNION и CROSS JOIN.

Почему это важно

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

Кому это важно

Тем, кто интересуется компиляторами, функциональным программированием, arrow notation и теорией категорий в приложении к практике, а также любителям необычных трюков с SQL и Postgres.

Как это применить

Прямого применения в доступном фрагменте записи нет: ссылки на репозиторий, лицензия и способ установки catlang в видимом тексте не указаны. Можно использовать пример как учебный: проследить, как цикл через loop и ветвление inl/inr превращается в комбинаторы, а затем в рекурсивный запрос WITH RECURSIVE.

Можно ли доверять

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

Риски и подводные камни

Автор сам называет пример окольным, а SQL, ужасающим: запрос получается огромным и вложенным. Про производительность, версию Postgres и поддержку других баз данных в видимом тексте ничего не сказано, поэтому судить о практической пригодности по записи нельзя. Основная часть рассуждений о категорном IL и преобразователе arrow notation в доступный фрагмент не вошла.

«Мне нужна была забавная цель компиляции, чтобы проверить настоящие возможности языка: его промежуточный язык, это куча абстрактной чепухи из теории категорий.»

— автор записи в блоге reasonablypolymorphic.com