Arrows to Arrows, Categories to Queries :: Reasonably Polymorphic

I’ve had a little time off of work as of late, and been spending it in characteristically unwise ways. In particular, I’ve written a little programming language that compiles to SQL. I call it catlang. That’s not to say that I’ve written a new query language. It’s a programming language, whose compiler spits out one giant SELECT statement. When you run that query in postgres, you get the output of your program. Why have I done this? Because I needed a funny compilation target to test out the actual features of the language, which is that its intermediary language is a bunch of abstract category theory nonsense. Which I’ll get to. But I’m sure you first want to see this bad boy in action. Behold, the function that returns 100 regardless of what input you give it. But it does it with the equivalent of a while loop: 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 If you’re familiar with arrow notation, you’ll notice the above looks kinda like one big proc block. This is not a coincidence (because nothing is a coincidence). I figured if I were to go through all of this work, we might as well get a working arrow desugarer out of the mix. But I digress; that’s a story for another time. Anyway, what’s going on here is we have an arrow count, which takes a single argument x. We then loop, starting from the value of x. Inside the loop, we now have a new variable i, which we do some voodoo on to compute n—the current value of the loop variable. Then we subtract 100 from n, and take the absolute value. The abs function here is a bit odd; it returns Left (abs x) if the input was negative, and Right x otherwise. Then we branch on the output of abs, where Left and Right have been renamed inl and inr respectively. If n - 100 was less than zero, we find ourselves in the inl case, where we add 1 to n and wrap the whole thing in inr—which the loop interprets as “loop again with this new value.” Otherwise, n - 100 was non-negative, and so we can return n directly. Is it roundabout? You bet! The obtuseness here is not directly a feature, I was just looking for conceptually simple things I could do which would be easy to desugar into category-theoretical stuff. Which brings us to the intermediary language. After desugaring the source syntax for count above, we’re left with this IL representation: 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₁ We’ll discuss all of this momentarily, but for now, just let your eyes glaze over the pretty unicode. The underlying idea here is that each of these remaining symbols has very simple and specific algebraic semantics. For example, A ⨟ B means “do A and pipe the result into B.” By giving a transformation from this categorical IL into other domains, it becomes trivial to compile catlang to all sorts of weird compilation targets. Like SQL. You’re probably wondering what the generated SQL looks like. Take a peek if you dare. Ungodly Compiled 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 _) 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,