Arrows to arrows, categories to queries (2025)
Arrows to arrows, categories to queries (2025) (reasonablypolymorphic.com)
要約
著者は、カテゴリ理論の抽象概念を中間言語として利用し、SQLにコンパイルされるプログラミング言語 `catlang` を開発しました。この言語は、関数適用ではなく矢印（arrows）の合成に焦点を当てており、積（product）や余積（coproduct）といった概念をSQLのクエリに変換します。特に、ループ処理は再帰CTE（Common Table Expression）を用いて実装されており、その生成されるSQLコードの複雑さと動作原理が解説されています。
全文翻訳
Arrows to arrows, categories to queries
最近、少し仕事から離れる時間があったので、いつものように賢明とは言えない方法で過ごしていました。特に、SQLにコンパイルされる小さなプログラミング言語 を書きました。私はそれを catlang と呼んでいます。新しいクエリ言語を書いたということではありません。これはプログラミング言語であり、そのコンパイラは巨大な SELECT 文を出力します。そのクエリをPostgresで実行すると、プログラムの出力が得られます。
なぜこんなことをしたのか？それは、言語の実際の機能、つまり中間言語が抽象的なカテゴリ理論のナンセンスの集まりであることをテストするための、面白いコンパイルターゲットが必要だったからです。それについては後述します。しかし、まずこのすごいものを実際に動いているところを見たいと思うでしょう。
どんな入力が与えられても100を返す関数をご覧ください。しかし、それはwhileループに相当する方法で行われます。
count : Int -> Int
count =
x ->
loop x
i ->
n <- join id id -< i
z <- abs . (-) -< (n, 100)
case z of
inl _ -> inr . (+) -< (n, 1)
inr _ -> inl -< n
もしarrow notation に慣れているなら、上記が一つの大きな proc ブロックのように見えることに気づくでしょう。これは偶然ではありません（何も偶然ではないからです）。この作業をすべて行うのであれば、アローのデシュガー（desugarer）も一緒に手に入れれば良いと考えました。しかし、話が逸れました。それはまた別の機会の話です。
さて、ここで何が起こっているかというと、count というアローがあり、単一の引数 x を取ります。次に、x の値からループを開始します。ループの中では、n（ループ変数の現在の値）を計算するために、いくつかのマジックを行います。そして、n から100を引いて絶対値を取ります。ここでの abs 関数は少し奇妙です。入力が負の場合 Left (abs x) を返し、そうでなければ Right x を返します。次に、abs の出力に基づいて分岐します。ここで Left と Right はそれぞれ inl と inr にリネームされています。もし n - 100 がゼロ未満であれば、inl ケースに入り、n に1を加えて全体を inr でラップします。これはループによって「この新しい値でループを続ける」と解釈されます。そうでなければ、n - 100 は非負であり、n を直接返すことができます。
回りくどいですか？もちろんです！この分かりにくさは直接的な特徴ではありません。カテゴリ理論的なものに簡単にデシュガーできる、概念的に単純なことをやりたかっただけです。そこで中間言語の話になります。上記の count のソース構文をデシュガーした後、IL表現は以下のようになります。
id △ id
⨟ cochoice
( undist
⨟ ( (prj₁ ⨟ id ▽ id) △ id
⨟ ( prj₁ △ 100
⨟ (-)
⨟ abs
)
△ id
⨟ prj₁ △ id
⨟ dist
⨟ ( (prj₂ ⨟ prj₂ ⨟ prj₁) △ 1
⨟ (+)
⨟ inr
)
▽ ( prj₂
⨟ prj₂
⨟ prj₁
⨟ inl
)
)
△ prj₂
⨟ dist
)
⨟ prj₁
これらすべてについて後で議論しますが、今は美しいUnicodeを眺めてください。
ここでの基本的な考え方は、これらの残りのシンボルがそれぞれ非常にシンプルで特定の代数的意味論を持っているということです。例えば、A ⨟ B は「A を実行し、その結果を B にパイプする」ことを意味します。このカテゴリ理論的なILから他のドメインへの変換を与えることで、catlang をさまざまな奇妙なコンパイルターゲットにコンパイルすることが容易になります。SQLのように。
生成されるSQLがどのようなものか疑問に思っているでしょう。もし勇気があれば覗いてみてください。
冒涜的なコンパイル済みSQL
SELECT
f0 AS f0
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(SELECT *
FROM
(WITH t0 AS
(SELECT *
FROM
(WITH RECURSIVE recursion AS
(SELECT
clock_timestamp() as step
, *
FROM
(WITH t1 AS
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1, NULL::integer AS f2, NULL::integer AS f3
FROM
(WITH t2 AS
(SELECT * FROM (SELECT 0 as f0) AS _)
SELECT *
FROM
(SELECT * FROM (SELECT f0 AS f0 FROM t2 AS _) AS _
CROSS JOIN
(SELECT f0 AS f1 FROM t2 AS _))
AS _)
AS _)
AS _)
SELECT *
FROM
(WITH t3 AS
(SELECT *
FROM
(-- undist
SELECT *
FROM
(SELECT
f0 AS f0, NULL::integer AS f1, f1 AS f2
FROM
(-- undist1
SELECT * FROM t1 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
NULL::integer AS f0, f2 AS f1, f3 AS f2
FROM
(-- dist2
SELECT * FROM t1 AS _ WHERE "f2" IS NOT NULL)
AS _)
AS _)
AS _)
SELECT *
FROM
(WITH t4 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(WITH t5 AS
(SELECT * FROM t3 AS _)
SELECT *
FROM
(WITH t6 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0
FROM
(WITH t7 AS
(SELECT * FROM (SELECT f0 AS f0, f1 AS f1 FROM t5 AS _) AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0
FROM
(-- join1
SELECT * FROM t7 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
f1 AS f0
FROM
(-- join2
SELECT * FROM t7 AS _ WHERE "f1" IS NOT NULL)
AS _)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f1, f1 AS f2, f2 AS f3 FROM t5 AS _))
AS _)
SELECT *
FROM
(WITH t8 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(WITH t9 AS
(SELECT *
FROM
(SELECT
f0 - f1 AS f0
FROM
(WITH t10 AS
(SELECT * FROM t6 AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT f0 AS f0 FROM (SELECT f0 AS f0 FROM t10 AS _) AS _)
AS _
CROSS JOIN
(SELECT f0 AS f1 FROM (SELECT 100 as f0 FROM t10 AS _) AS _))
AS _)
AS _)
AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
abs(f0) as f0, NULL::integer as f1
FROM
t9
AS _
WHERE
f0 < 0)
AS _
UNION
SELECT *
FROM
(SELECT NULL::integer as f0, f0 as f1 FROM t9 AS _ WHERE f0 >= 0)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f2, f1 AS f3, f2 AS f4, f3 AS f5 FROM t6 AS _))
AS _)
SELECT *
FROM
(WITH t11 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(SELECT f0 AS f0, f1 AS f1 FROM t8 AS _)
AS _)
AS _
CROSS JOIN
(SELECT
f0 AS f2, f1 AS f3, f2 AS f4, f3 AS f5, f4 AS f6, f5 AS f7
FROM
t8
AS _))
AS _)
SELECT *
FROM
(WITH t12 AS
(SELECT *
FROM
(-- dist
SELECT *
FROM
(SELECT
f0 AS f0, f2 AS f1, NULL::integer AS f10, NULL::integer AS f11, NULL::integer AS f12, NULL::integer AS f13, f3 AS f2, f4 AS f3, f5 AS f4, f6 AS f5, f7 AS f6, NULL::integer AS f7, NULL::integer AS f8, NULL::integer AS f9
FROM
(-- dist1
SELECT * FROM t11 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
NULL::integer AS f0, NULL::integer AS f1, f4 AS f10, f5 AS f11, f6 AS f12, f7 AS f13, NULL::integer AS f2, NULL::integer AS f3, NULL::integer AS f4, NULL::integer AS f5, NULL::integer AS f6, f1 AS f7, f2 AS f8, f3 AS f9
FROM
(-- dist2
SELECT * FROM t11 AS _ WHERE "f1" IS NOT NULL)
AS _)
AS _)
AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
NULL::integer AS f0, f0 AS f1
FROM
(SELECT
f0 + f1 AS f0
FROM
(WITH t13 AS
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1, f2 AS f2, f3 AS f3, f4 AS f4, f5 AS f5, f6 AS f6
FROM
(-- join1
SELECT * FROM t12 AS _
WHERE
("f0" IS NOT NULL) AND ((("f1" IS NOT NULL) OR ("f2" IS NOT NULL)) AND (("f3" IS NOT NULL) AND ((("f4" IS NOT NULL) OR ("f5" IS NOT NULL)) AND ("f6" IS NOT NULL)))))
AS _)
AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0
FROM
(SELECT
f0 AS f0
FROM
(SELECT
f2 AS f0, f3 AS f1, f4 AS f2, f5 AS f3
FROM
(SELECT
f1 AS f0, f2 AS f1, f3 AS f2, f4 AS f3, f5 AS f4, f6 AS f5
FROM
t13
AS _)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f1 FROM (SELECT 1 as f0 FROM t13 AS _) AS _))
AS _)
AS _)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
f0 AS f0, NULL::integer AS f1
FROM
(SELECT
f0 AS f0
FROM
(SELECT
f2 AS f0, f3 AS f1, f4 AS f2, f5 AS f3
FROM
(SELECT
f1 AS f0, f2 AS f1, f3 AS f2, f4 AS f3, f5 AS f4, f6 AS f5
FROM
(SELECT
f7 AS f0, f8 AS f1, f9 AS f2, f10 AS f3, f11 AS f4, f12 AS f5, f13 AS f6
FROM
(-- join2
SELECT * FROM t12 AS _
WHERE
("f7" IS NOT NULL) AND ((("f8" IS NOT NULL) OR ("f9" IS NOT NULL)) AND (("f10" IS NOT NULL) AND ((("f11" IS NOT NULL) OR ("f12" IS NOT NULL)) AND ("f13" IS NOT NULL)))))
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f2 FROM (SELECT f2 AS f0 FROM t3 AS _) AS _))
AS _)
SELECT *
FROM
(-- dist
SELECT *
FROM
(SELECT
f0 AS f0, f2 AS f1, NULL::integer AS f2, NULL::integer AS f3
FROM
(-- dist1
SELECT * FROM t4 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
NULL::integer AS f0, NULL::integer AS f1, f1 AS f2, f2 AS f3
FROM
(-- dist2
SELECT * FROM t4 AS _ WHERE "f1" IS NOT NULL)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _
UNION ALL
SELECT
clock_timestamp() as step
, *
FROM
(SELECT *
FROM
(WITH t14 AS
(SELECT * FROM recursion AS _)
SELECT *
FROM
(WITH t15 AS
(SELECT *
FROM
(-- undist
SELECT *
FROM
(SELECT
f0 AS f0, NULL::integer AS f1, f1 AS f2
FROM
(-- undist1
SELECT * FROM t14 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
NULL::integer AS f0, f2 AS f1, f3 AS f2
FROM
(-- dist2
SELECT * FROM t14 AS _ WHERE "f2" IS NOT NULL)
AS _)
AS _)
AS _)
SELECT *
FROM
(WITH t16 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(WITH t17 AS
(SELECT * FROM t15 AS _)
SELECT *
FROM
(WITH t18 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0
FROM
(WITH t19 AS
(SELECT * FROM (SELECT f0 AS f0, f1 AS f1 FROM t17 AS _) AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0
FROM
(-- join1
SELECT * FROM t19 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
f1 AS f0
FROM
(-- join2
SELECT * FROM t19 AS _ WHERE "f1" IS NOT NULL)
AS _)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f1, f1 AS f2, f2 AS f3 FROM t17 AS _))
AS _)
SELECT *
FROM
(WITH t20 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(WITH t21 AS
(SELECT *
FROM
(SELECT
f0 - f1 AS f0
FROM
(WITH t22 AS
(SELECT * FROM t18 AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT f0 AS f0 FROM (SELECT f0 AS f0 FROM t22 AS _) AS _)
AS _
CROSS JOIN
(SELECT f0 AS f1 FROM (SELECT 100 as f0 FROM t22 AS _) AS _))
AS _)
AS _)
AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
abs(f0) as f0, NULL::integer as f1
FROM
t21
AS _
WHERE
f0 < 0)
AS _
UNION
SELECT *
FROM
(SELECT NULL::integer as f0, f0 as f1 FROM t21 AS _ WHERE f0 >= 0)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f2, f1 AS f3, f2 AS f4, f3 AS f5 FROM t18 AS _))
AS _)
SELECT *
FROM
(WITH t23 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(SELECT f0 AS f0, f1 AS f1 FROM t20 AS _)
AS _)
AS _
CROSS JOIN
(SELECT
f0 AS f2, f1 AS f3, f2 AS f4, f3 AS f5, f4 AS f6, f5 AS f7
FROM
t20
AS _))
AS _)
SELECT *
FROM
(WITH t24 AS
(SELECT *
FROM
(-- dist
SELECT *
FROM
(SELECT
f0 AS f0, f2 AS f1, NULL::integer AS f10, NULL::integer AS f11, NULL::integer AS f12, NULL::integer AS f13, f3 AS f2, f4 AS f3, f5 AS f4, f6 AS f5, f7 AS f6, NULL::integer AS f7, NULL::integer AS f8, NULL::integer AS f9
FROM
(-- dist1
SELECT * FROM t23 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
NULL::integer AS f0, NULL::integer AS f1, f4 AS f10, f5 AS f11, f6 AS f12, f7 AS f13, NULL::integer AS f2, NULL::integer AS f3, NULL::integer AS f4, NULL::integer AS f5, NULL::integer AS f6, f1 AS f7, f2 AS f8, f3 AS f9
FROM
(-- dist2
SELECT * FROM t23 AS _ WHERE "f1" IS NOT NULL)
AS _)
AS _)
AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
NULL::integer AS f0, f0 AS f1
FROM
(SELECT
f0 + f1 AS f0
FROM
(WITH t25 AS
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1, f2 AS f2, f3 AS f3, f4 AS f4, f5 AS f5, f6 AS f6
FROM
(-- join1
SELECT * FROM t24 AS _
WHERE
("f0" IS NOT NULL) AND ((("f1" IS NOT NULL) OR ("f2" IS NOT NULL)) AND (("f3" IS NOT NULL) AND ((("f4" IS NOT NULL) OR ("f5" IS NOT NULL)) AND ("f6" IS NOT NULL)))))
AS _)
AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0
FROM
(SELECT
f0 AS f0
FROM
(SELECT
f2 AS f0, f3 AS f1, f4 AS f2, f5 AS f3
FROM
(SELECT
f1 AS f0, f2 AS f1, f3 AS f2, f4 AS f3, f5 AS f4, f6 AS f5
FROM
t25
AS _)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f1 FROM (SELECT 1 as f0 FROM t25 AS _) AS _))
AS _)
AS _)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
f0 AS f0, NULL::integer AS f1
FROM
(SELECT
f0 AS f0
FROM
(SELECT
f2 AS f0, f3 AS f1, f4 AS f2, f5 AS f3
FROM
(SELECT
f1 AS f0, f2 AS f1, f3 AS f2, f4 AS f3, f5 AS f4, f6 AS f5
FROM
(SELECT
f7 AS f0, f8 AS f1, f9 AS f2, f10 AS f3, f11 AS f4, f12 AS f5, f13 AS f6
FROM
(-- join2
SELECT * FROM t24 AS _
WHERE
("f7" IS NOT NULL) AND ((("f8" IS NOT NULL) OR ("f9" IS NOT NULL)) AND (("f10" IS NOT NULL) AND ((("f11" IS NOT NULL) OR ("f12" IS NOT NULL)) AND ("f13" IS NOT NULL)))))
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f2 FROM (SELECT f2 AS f0 FROM t15 AS _) AS _))
AS _)
SELECT *
FROM
(-- dist
SELECT *
FROM
(SELECT
f0 AS f0, f2 AS f1, NULL::integer AS f2, NULL::integer AS f3
FROM
(-- dist1
SELECT * FROM t16 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
NULL::integer AS f0, NULL::integer AS f1, f1 AS f2, f2 AS f3
FROM
(-- dist2
SELECT * FROM t16 AS _ WHERE "f1" IS NOT NULL)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _
WHERE
("f2" IS NOT NULL) AND ("f3" IS NOT NULL))
AS _)
SELECT * FROM recursion ORDER BY step DESC LIMIT 1)
AS _)
SELECT *
FROM
(WITH t26 AS
(SELECT *
FROM
(-- undist
SELECT *
FROM
(SELECT
f0 AS f0, NULL::integer AS f1, f1 AS f2
FROM
(-- undist1
SELECT * FROM t0 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
NULL::integer AS f0, f2 AS f1, f3 AS f2
FROM
(-- dist2
SELECT * FROM t0 AS _ WHERE "f2" IS NOT NULL)
AS _)
AS _)
AS _)
SELECT *
FROM
(WITH t27 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(WITH t28 AS
(SELECT * FROM t26 AS _)
SELECT *
FROM
(WITH t29 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0
FROM
(WITH t30 AS
(SELECT * FROM (SELECT f0 AS f0, f1 AS f1 FROM t28 AS _) AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0
FROM
(-- join1
SELECT * FROM t30 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
f1 AS f0
FROM
(-- join2
SELECT * FROM t30 AS _ WHERE "f1" IS NOT NULL)
AS _)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f1, f1 AS f2, f2 AS f3 FROM t28 AS _))
AS _)
SELECT *
FROM
(WITH t31 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(WITH t32 AS
(SELECT *
FROM
(SELECT
f0 - f1 AS f0
FROM
(WITH t33 AS
(SELECT * FROM t29 AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT f0 AS f0 FROM (SELECT f0 AS f0 FROM t33 AS _) AS _)
AS _
CROSS JOIN
(SELECT f0 AS f1 FROM (SELECT 100 as f0 FROM t33 AS _) AS _))
AS _)
AS _)
AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
abs(f0) as f0, NULL::integer as f1
FROM
t32
AS _
WHERE
f0 < 0)
AS _
UNION
SELECT *
FROM
(SELECT NULL::integer as f0, f0 as f1 FROM t32 AS _ WHERE f0 >= 0)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f2, f1 AS f3, f2 AS f4, f3 AS f5 FROM t29 AS _))
AS _)
SELECT *
FROM
(WITH t34 AS
(SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1
FROM
(SELECT f0 AS f0, f1 AS f1 FROM t31 AS _)
AS _)
AS _
CROSS JOIN
(SELECT
f0 AS f2, f1 AS f3, f2 AS f4, f3 AS f5, f4 AS f6, f5 AS f7
FROM
t31
AS _))
AS _)
SELECT *
FROM
(WITH t35 AS
(SELECT *
FROM
(-- dist
SELECT *
FROM
(SELECT
f0 AS f0, f2 AS f1, NULL::integer AS f10, NULL::integer AS f11, NULL::integer AS f12, NULL::integer AS f13, f3 AS f2, f4 AS f3, f5 AS f4, f6 AS f5, f7 AS f6, NULL::integer AS f7, NULL::integer AS f8, NULL::integer AS f9
FROM
(-- dist1
SELECT * FROM t34 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
NULL::integer AS f0, NULL::integer AS f1, f4 AS f10, f5 AS f11, f6 AS f12, f7 AS f13, NULL::integer AS f2, NULL::integer AS f3, NULL::integer AS f4, NULL::integer AS f5, NULL::integer AS f6, f1 AS f7, f2 AS f8, f3 AS f9
FROM
(-- dist2
SELECT * FROM t34 AS _ WHERE "f1" IS NOT NULL)
AS _)
AS _)
AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
NULL::integer AS f0, f0 AS f1
FROM
(SELECT
f0 + f1 AS f0
FROM
(WITH t36 AS
(SELECT *
FROM
(SELECT
f0 AS f0, f1 AS f1, f2 AS f2, f3 AS f3, f4 AS f4, f5 AS f5, f6 AS f6
FROM
(-- join1
SELECT * FROM t35 AS _
WHERE
("f0" IS NOT NULL) AND ((("f1" IS NOT NULL) OR ("f2" IS NOT NULL)) AND (("f3" IS NOT NULL) AND ((("f4" IS NOT NULL) OR ("f5" IS NOT NULL)) AND ("f6" IS NOT NULL)))))
AS _)
AS _)
SELECT *
FROM
(SELECT *
FROM
(SELECT
f0 AS f0
FROM
(SELECT
f0 AS f0
FROM
(SELECT
f2 AS f0, f3 AS f1, f4 AS f2, f5 AS f3
FROM
(SELECT
f1 AS f0, f2 AS f1, f3 AS f2, f4 AS f3, f5 AS f4, f6 AS f5
FROM
t36
AS _)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f1 FROM (SELECT 1 as f0 FROM t36 AS _) AS _))
AS _)
AS _)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
f0 AS f0, NULL::integer AS f1
FROM
(SELECT
f0 AS f0
FROM
(SELECT
f2 AS f0, f3 AS f1, f4 AS f2, f5 AS f3
FROM
(SELECT
f1 AS f0, f2 AS f1, f3 AS f2, f4 AS f3, f5 AS f4, f6 AS f5
FROM
(SELECT
f7 AS f0, f8 AS f1, f9 AS f2, f10 AS f3, f11 AS f4, f12 AS f5, f13 AS f6
FROM
(-- join2
SELECT * FROM t35 AS _
WHERE
("f7" IS NOT NULL) AND ((("f8" IS NOT NULL) OR ("f9" IS NOT NULL)) AND (("f10" IS NOT NULL) AND ((("f11" IS NOT NULL) OR ("f12" IS NOT NULL)) AND ("f13" IS NOT NULL)))))
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _
CROSS JOIN
(SELECT f0 AS f2 FROM (SELECT f2 AS f0 FROM t26 AS _) AS _))
AS _)
SELECT *
FROM
(-- dist
SELECT *
FROM
(SELECT
f0 AS f0, f2 AS f1, NULL::integer AS f2, NULL::integer AS f3
FROM
(-- dist1
SELECT * FROM t27 AS _ WHERE "f0" IS NOT NULL)
AS _)
AS _
UNION
SELECT *
FROM
(SELECT
NULL::integer AS f0, NULL::integer AS f1, f1 AS f2, f2 AS f3
FROM
(-- dist2
SELECT * FROM t27 AS _ WHERE "f1" IS NOT NULL)
AS _)
AS _)
AS _)
AS _)
AS _)
AS _
WHERE
("f0" IS NOT NULL) AND ("f1" IS NOT NULL))
AS _)
AS _;
Postgres 17で上記のクエリを実行すると、値が100の単一の列を持つ単一行が返されます。そして、実際に100までループしてそれを達成していると信じてください。信じられないなら、以下の変更を加えてください。
- SELECT * FROM recursion ORDER BY step DESC LIMIT 1)
+ SELECT * FROM recursion ORDER BY step DESC)
これにより、代わりに各イテレーションのステップごとに1行が返されます。
生成されたSQLには明らかな最適化の余地がありますが、プロジェクトの面白い部分ではないので、私の時間を使う価値はないと思いました。
一体何が起こっているのか？
ここで、この背後にあるカテゴリ理論について時間をかけて議論しましょう。私は決して専門家ではありませんが、この分野で10年間頭をぶつけてきて学んだことは、少しでも進めば大きな違いを生むということです。
私たちの目的のために、型と、型間の矢印（関数）があります。常に恒等的な「何もしない矢印」id があります。
id :: a ~> a
そして、一方の端をもう一方に繋げることで矢印を合成できます。
(⨟) :: (a ~> b) -> (b ~> c) -> (a ~> c)
Haskell（あるいは実際にはどんなプログラミング言語でも）とは異なり、関数適用という概念はありません。つまり、矢印はありません。
-- 存在しない！
($) :: (a ~> b) -> a -> b
矢印を合成することしかできず、適用することはできません。だから、これらを「関数」ではなく「矢印」と呼ぶのです。
積型（product types）を扱うための矢印がいくつかあります。2つの射影関数は fst と snd に対応し、ペアから個々の要素を取り出します。
prj₁ :: (a, b) ~> a
prj₂ :: (a, b) ~> b
そもそもペアをどのように作るのでしょうか？2つの矢印を実行して b と c を計算し、新しい矢印を生成して (b, c) のペアを生成する「フォーク」操作を使用できます。
(△) :: (a ~> b) -> (a ~> c) -> (a ~> (b, c))
Haskellの経験がある場合、この操作を単に (,) ペアコンストラクタと考える誘惑に駆られるかもしれません。しかし、計算の型から、b と c の間にデータ依存関係がないことがわかります。そのため、ペアの各側を並列化することができます。
カテゴリ理論では、矢印の左右の区別はかなり任意です。これは双対性という概念につながり、矢印を反転させることでクールな新しい動作を得ることができます。積の仕組みをすべて双対化すると、余積（coproduct）の仕組みが得られます。a と b の余積は「a または b のどちらかだが、両方でもどちらでもない」ものです。
prj₁ と prj₂ の矢印の方向を入れ替え、(,) を Either に置き換えると、以下の注入が得られます。
inl :: a ~> Either a b
inr :: b ~> Either a b
そして、余積を削除するための「結合」操作が以下になります。
(▽) :: (a ~> c) -> (b ~> c) -> (Either a b ~> c)
ここでも、Haskellから来ると、これは単なる標準の either 関数です。これは2つのケースのいずれかへの分岐に対応します。
これら8つの操作だけで、すでに計り知れない表現力があることがわかります。⨟ を使ってデータ依存関係を、▽ を使って分岐を表現できます。△ を使うと並列化の機会が自動的にエンコードされ、複雑なデータ構造を構築する能力が得られ、prj₁ と prj₂ を使うとデータ構造から情報を取り出すことができます。
ILには変数名が一切見当たらないことに気づくでしょう。ソース言語のデシュガーはスタック（something to allocate △ id パターン経由）を構築し、後続の変数ルックアップをスタック上の射影のシーケンスに置き換えて値を再度見つけます。一方では、これはカテゴリ理論的なILを読みにくくしますが、リターゲットを非常に容易にします。多くのドメインにはグループ化の概念がありますが、ネイティブな命名の概念はありません。
例えば、電子回路では、Int32 を表す32本のワイヤのリボンを持つことができます。別の32本のワイヤのリボンがある場合、両方のワイヤを (Int32, Int32) のペアに対応する64本のワイヤのリボンに簡単にルーティングできます。
名前をILに到達する前に削除することで、コンパイラのバックエンドが名前を扱う必要がなくなります。スタック表現で作業するだけで、可能であれば射影のシーケンスを特別に最適化することができます。
この議論で特に興味深いのは、ループをどのようにデシュガーするかです。基本的なプリミティブは cochoice です。
cochoice :: (Either a c ~> Either b c) -> (a ~> b)
これは、Either 上の矢印を、Either のない矢印に魔法のように変換します。もちろん、その矢印を Either で実行する必要があります。その関数が inl を返した場合、私たちは満足し、それをそのまま出力できます。しかし、関数が inr を返した場合、それを Either 化された矢印に再度渡すしかありません。Haskellでは、cochoice は以下のように実装されます。
cochoiceHask :: (Either a c -> Either b c) -> a -> c
cochoiceHask f = go . Left
where
go :: Either a c -> b
go eac =
case f eac of
Left b -> b
Right c -> go (Right c)
ご覧のとおり、これは f が Left を返すまでループします。このループの定式化の素晴らしい点は、ループ本体を最初に通過したときとそれ以降の通過を静的に区別できることです。最初に eac は Left ですが、それ以外のすべての回では Right です。元の count プログラムではこれを利用していませんが、ループコードで最初の通過時に何かを初期化する必要があったことは何度ありますか？
SQLへのコンパイル
これがILの背後にある理論です。これをSQLにコンパイルするにはどうすればよいでしょうか？
前述したように、中間言語の各操作にSQL実装を与えるだけで済みます。簡単な例として、id は {} を SELECT * FROM {} にコンパイルします。ここで {} は矢印の入力です。
ここでの最も難しい部分は、データ表現を考案することでした。積の各要素を新しい列としてエンコードするのは明白に思えますが、余積についてはどうすればよいでしょうか？多くの試行錯誤の結果、余積をフラット化することにしました。例えば、型：
(Int, Either Int Int)
は3つの列として表現されます。
( f1 INT NOT NULL
, f2 INT
, f3 INT
)
ただし、f2 または f3 のどちらか一方のみが常に IS NOT NULL であるという制約があります。
これを確立すると、ほとんどすべてが些細なことになります。合成はネストされたクエリに対応します。フォークは CROSS JOIN で、各サブクエリの列を連結します。結合は UNION で、正しい余積コンストラクタを見ていることを保証するために WHERE field IS NOT NULL 句を追加します。
cochoice は唯一本当にトリッキーな部分ですが、これは再帰CTEに対応します。計算のために再帰CTEテーブルを生成するのは難しくありませんが、そこから最終値を取得するのは驚くほど困難でした。SQLテーブルのセマンティクスは、それらがマルチセットであり、任意の最大要素を持つということです。つまり、最終結果をクエリするには、関連する方法で構造化された列が必要です。Postgresが受け入れるものと、クエリの構造化方法のいくつかの癖のために、「ループした回数」列を挿入してそれに並べ替えることは、法外に困難でした。そのため、clock_timestamp() as step 列を追加してプロセッサクロックを参照し、それで並べ替えるというハックを使いました。
これは明らかにハックであり、もし私が1行以上の行を生成するプリミティブを追加した場合に問題を引き起こす可能性が高いですが、これもただの楽しみであり、誰が気にするでしょうか。私の詐欺行為に気分を害された場合は、プルリクエストを送ってください！
将来の愚かな方向性
このプロジェクトに取り組むための休暇時間がなくなってしまったので、計画していたメタサーキュラーな愚かさにはおそらく手が届かないでしょう。
コンパイラにはまだいくつかの文字列処理プリミティブ（追加は簡単）が必要ですが、その後、catlangで小さなBrainfuckインタプリタを書くのは簡単でしょう。それをSQLにコンパイルできます。これで、PostgresでBrainfuckインタプリタが実行されることになります。もちろん、これは以前にも手作業で行われてきましたが、私の知る限り、コンパイル経由では初めてです。
CからBrainfuckへのコンパイラが存在します。そしてPostgresはCで書かれています。Xzibitを喜ばせるような動きで、PostgresをPostgresで実行できます。そしてもちろん、BrainfuckをBrainfuckで実行するのは楽しいでしょう。誰かがそのようなものに貢献したい場合、それはクールなcatlangバックエンドになるでしょう。
ノートとデューデリジェンスなど
私がこのようなことをしたのは初めてではありません。catlangのソース言語は、Haskellのarrow syntaxに強く触発されており、それは結局Arrowsのデシュガーアルゴリズムに他なりません。Arrowsは、arr :: (a -> b) -> (a ~> b) という操作を必要とするため、少し間違った抽象化です。これは、Haskell関数をカテゴリに埋め込むことができる必要があることを意味しますが、これはほとんど不可能です。
残念ながら、Haskellのarrow構文はほとんどすべての操作を arr にデシュガーするため、arrow表記は事実上無用になります。理想的な世界では、このブログ記事で説明したすべてが小さなHaskellライブラリになり、arrow表記が重い作業を行うでしょう。しかし、私たちが生きている世界はそうではありません。
また、プログラミング言語の背後にあるカテゴリ理論的な意味論に気づいたのも初めてではありません。これについては誰を引用すべきか実際にはわかりませんが、ラムダ計算がデカルト閉カテゴリに対応することはよく知られた伝承です。「閉」という言葉は、eval :: (a ~> b, a) ~> b という操作があることを意味しますが、誰もがラムダ計算を実装しているので、それなしでどこまで進めるかを見るのは楽しいだろうと思いました。これはcatlangのチューリング完全性に対する制限ではありません（cochoice がすべてを提供してくれるため）。
私は、Compiling to Categoriesという論文を読んで以来、10年近く「カテゴリ優先」のプログラミング言語を書くことを考えてきました。その論文はHaskellを取り上げ、それをカテゴリにデシュガーし直します。私はここで多くのトリックをその論文から盗みました。
とにかく。コードはすべてgithubで利用可能です。リポジトリは私の通常のコーディング基準には達していませんが、お詫び申し上げます。注目すべきは、Haskellコードを出力できるテンプレートハスケルバックエンドです。つまり、catlangをHaskellのarrowデシュガーがあるべき姿にコンパイルするクォーター（quasiquoter）を作成するのはそれほど難しくないでしょう。もしそのようなものへの需要が十分にあれば、この部分をライブラリにすることを検討します。
- このエッセイで矢印の型を見るとき、
~>はcatlangで書ける矢印であり、->はメタ理論に存在する矢印であるという区別をします。↩︎