I’ve had a small period off of activity as of late, and been spending it in characteristically unwise ways. In particular, I’ve written a little programming tongue 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 elephantine 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 comic compilation mark to test out the genuine features of the language, which is that its intermediary tongue is a bunch of theoretical category theory nonsense. Which I’ll get to. But I’m certain you archetypal desire to see this troublemaker in action.
Behold, the function that returns 100 despite of what input you provision it. But it does it alongside the equal of a during loop:
count : Int -> Int count = x -> iteration x i -> n <- associate id id -< i z <- abs . (-) -< (n, 100) case z of inl _ -> inr . (+) -< (n, 1) inr _ -> inl -< n
If you’re acquainted alongside arrow notation, you’ll notice the complete looks kinda akin 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 power as fine get a operating arrow desugarer out of the mix. But I digress; that’s a narrative for another time.
Anyway, what’s going on current is we have an arrow count, which takes a sole disagreement x. We afterward loop, starting from the value of x. Inside the loop, we now have a new changeable i, which we do several voodoo on to compute n—the current value of the iteration variable. Then we subtract 100 from n, and obtain the complete value. The abs function current 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, anywhere Left and Right have been renamed inl and inr respectively. If n - 100 was small than zero, we discover ourselves in the inl case, anywhere we add 1 to n and cover the entire item in inr—which the iteration interprets as “loop again alongside this new value.” Otherwise, n - 100 was non-negative, and so we can come back n directly.
Is it roundabout? You bet! The obtuseness current is not immediately a feature, I was fair looking for conceptually uncomplicated things I could do which would be uncomplicated to desugar into category-theoretical stuff. Which brings us to the intermediary language. After desugaring the origin syntax for figure above, we’re remaining alongside 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 conversation all of this momentarily, but for now, fair let your eyes glaze complete the beautiful unicode.
The underlying idea current is that all of these remaining symbols has extremely uncomplicated and particular algebraic semantics. For example, A ⨟ B method “do A and pipe the outcome into B.” By giving a transformation from this categorical IL into another domains, it becomes trivial to compile catlang to all sorts of weird compilation targets. Like SQL.
You’re likely wondering what the generated SQL looks like. Take a peek if you dare.
Ungodly Compiled SQLSELECT 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, 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 _) 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 stage 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 _) 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 _;
It’s not pretty, fairly amazingly, operating the complete query in postgres 17 volition in fact come back a sole row alongside a sole pillar whose value is 100. And you’d improved accept it does it by actually looping its way up to 100. If you don’t accept me, create the following change:
- SELECT * FROM recursion ORDER BY stage DESC LIMIT 1) + SELECT * FROM recursion ORDER BY stage DESC)
which volition alternatively come back a row for all stage of the iteration.
There are several apparent optimizations I could create to the generated SQL, but it didn’t appear value my time, since that’s not the engaging part of the project.
What the Hell Is Going On?
Let’s obtain several period to conversation the underlying category theory here. I am by no method an expert, but what I have learned following a decade of bashing my caput against this material is that a small goes a lengthy way.
For our intents and purposes, we have types, and arrows (functions) between types. We continually have the character “do nothing arrow” id:
and we can create arrows by lining up one end to another:1
(⨟) :: (a ~> b) -> (b ~> c) -> (a ~> c)Unlike Haskell (or really any programming language, for that matter), we DO NOT have the notion of function application. That is, there is no arrow:
-- doesn't exist! ($) :: (a ~> b) -> a -> b
You can lone create arrows, you can’t use them. That’s why we call these things “arrows” fairly than “functions.”
There are a bundle of arrows for operating alongside merchandise types. The two projection functions equivalent to fst and snd, taking idiosyncratic components out of pairs:
prj₁ :: (a, b) ~> a prj₂ :: (a, b) ~> b
How do we get things into pairs in the archetypal place? We can use the “fork” operation, which takes two arrows computing b and c, and generates a new arrow which generates a brace of (b, c):
(△) :: (a ~> b) -> (a ~> c) -> (a ~> (b, c))If you’re coming from a Haskell background, it’s tempting to think of this procedure merely as the (,) brace constructor. But you’ll notice from the category of the computation that there can be no data dependency between b and c, thus we are liberated to parallelize all flank of the pair.
In category theory, the difference between remaining and correct sides of an arrow is fairly arbitrary. This gives increase to a notion called duality anywhere we can flip the arrows around, and get chill new behavior. If we dualize all of our merchandise machinery, we get the coproduct machinery, anywhere a coproduct of a and b is “either a or b, but certainly not the two nor neither.”
Swapping the arrow direction of prj₁ and prj₂, and replacing (,) alongside Either gives us the following injections:
inl :: a ~> Either a b inr :: b ~> Either a b
and the following “join” procedure for eliminating coproducts:
(▽) :: (a ~> c) -> (b ~> c) -> (Either a b ~> c)Again, coming from Haskell this is fair the norm either function. It corresponds to a branch between one of two cases.
As you can see, alongside fair these eight operations, we already have a enormous amount of expressivity. We can province data requirements via ⨟ and branching via ▽. With △ we automatically encode opportunities for parallelism, and acquire the capability to build complex data structures, alongside prj₁ and prj₂ allowing us to get the data back out of the data structures.
You’ll notice in the IL that there are no changeable names anyplace to be found. The desugaring of the origin tongue builds a stack (via the item to allocate △ id pattern), and replaces consequent changeable lookups alongside a sequence of projections on the stack to discover the value again. On one hand, this makes the categorical IL fairly difficult to read, but it makes it extremely uncomplicated to re-target! Many domains do have a notion of grouping, but don’t have a native notion of naming.
For example, in an digital circuit, I can have a ribbon of 32 wires which represents an Int32. If I have another ribbon of 32 wires, I can trivially path the two wires into a 64-wire ribbon corresponding to a brace of (Int32, Int32).
By eliminating names before we get to the IL, it method no compiler backend always needs to agreement alongside names. They can fair activity on a stack representation, and are liberated to special-case optimize sequence of projections if they are capable to.
Of particular involvement to this conversation is how we desugar loops in catlang. The underlying primitive is cochoice:
cochoice :: (Either a c ~> Either b c) -> (a ~> b)which magically turns an arrow on Eithers into an arrow without the eithers. We evidently must run that arrow on eithers. If that function returns inl, afterward we’re blessed and we can fair output that. But if the function returns inr, we have no choice but to continue it rear in to the eithered arrow. In Haskell, cochoice is implemented as:
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)
which as you can see, volition iteration until f eventually returns a Left. What’s neat concerning this formulation of a iteration is that we can statically differentiate between our archetypal and consequent passes through the iteration body. The archetypal period through eac is Left, during for all another times it is Right. We don’t obtain advantage of it in the first figure program, but how many times have you written iteration code that needs to initialize item its archetypal period through?
Compiling to SQL
So that’s the underlying theory rearward the IL. How can we compile this to SQL now?
As alluded to before, we merely need to provision SQL implementations for all of the operations in the intermediary language. As a uncomplicated example, id compiles to SELECT * FROM {}, anywhere {} is the input of the arrow.
The hardest part current was operating out a data representation. It seems apparent to encode all component of a merchandise as a new column, but what do we do concerning coproducts? After much activity thought, I decided to flatten out the coproducts. So, for example, the type:
would be represented as three columns:
( f1 INT NOT NULL , f2 INT , f3 INT )
with the constraint that exactly one of f2 or f3 would be IS NOT NULL at any stated item in time.
With this hammered out, nearly everything alternatively is beautiful trivial. Composition corresponds to a nested query. Forks are CROSS JOINs which concatenate the columns of all sub-query. Joins are UNIONs, anywhere we add a WHERE site IS NOT NULL clause to enforce we’re looking at the accurate coproduct constructor.
Cochoice is the lone really tricky thing, but it corresponds to a recursive CTE. Generating a recursive CTE array for the computation isn’t too hard, but getting the final value out of it was amazingly tricky. The semantics of SQL tables is that they are multisets and arrive alongside an arbitrary top element. Which is to say, you need an pillar organized in a applicable way in command to query the final result. Due to several quirks in what postgres accepts, and in how I organized my queries, it was prohibitively difficult to insert a “how many times have I looped” pillar and command by that. So alternatively I cheated and added a clock_timestamp() as stage pillar which looks at the processor clock and ordered by that.
This is plainly a hack, and presumably volition logic problems if I always add several primitives which create additional than one row, but again, this is fair for fun and who cares. Send me a pull request if you’re offended by my chicanery!
Stupid Directions To Go In the Future
I’ve run out of holiday period to activity on this project, so I’m likely not going to get about to the meta-circular stupidity I was planning.
The compiler motionless needs a few string-crunching primitives (which are uncomplicated to add), but afterward it would be uncomplicated to compose a small brainfuck translator in catlang. Which I could afterward compile to SQL. Now we’ve got a brainfuck translator operating in postgres. Of course, this has been done by hand before, but to my knowledge, never via compilation.
There be C to brainfuck compilers. And postgres is written in C. So in a move that would create Xzibit proud, we could run postgres in postgres. And of course, it would be fun to run brainfuck in brainfuck. That’d be a chill catlang backend if person wanted to contribute specified a thing.
Notes and Due Diligence and What Have You
I am not the archetypal individual to do item akin this. The origin tongue of catlang is heavily inspired by Haskell’s arrow syntax, which in rotate is basically a desugaring algorithm for Arrows. Arrows are slightly the incorrect idea since they necessitate an procedure arr :: (a -> b) -> (a ~> b)—which requires you to be capable to embed Haskell functions in your category, item which is almost never possible.
Unfortunately, arrow syntax in Haskell desugars downward to arr for nearly everything it does, which in rotate makes arrow notation efficiently useless. In an ideal world, everything I described in this blog article would be a small tiny Haskell library, alongside arrow notation doing the dense lifting. But that is fair not the earth we live in.
Nor am I the archetypal individual to notice that there are categorical semantics rearward programming languages. I don’t really cognize whom to citation on this one, but it is well-established folklore that the lambda calculus corresponds to cartesian-closed categories. The “closed” part of “cartesian-closed” method we have an procedure eval :: (a ~> b, a) ~> b, but everyone and their dog has implemented the lambda calculus, so I idea it would be fun to see how far we can get without it. This is not a limitation on catlang’s turing completeness (since cochoice gives us everything we need.)
I’ve been thinking concerning penning a category-first programming tongue for the improved part of a decade, always since I peruse Compiling to Categories. That document takes Haskell and desugars it rear downward to categories. I stole many of the tricks current from that paper.
Anyway. All of the code is accessible on github if you’re curious in taking a look. The repo isn’t up to my customary coding standards, for which you have my apologies. Of note is the template-haskell backend which can spit out Haskell code; definition it wouldn’t be extremely difficult to create a quasiquoter to compile catlang into what Haskell’s arrow desugaring ought to be. If there’s adequate clamor for specified a thing, I’ll see concerning turning this part into a library.
