Cat Girl Program Analysis — where types meet tails
🏠 Index 📋 Forums 👥 Members 🔍 Search ❓ FAQ 🔐 Login
🐱
Online
AbstractKitty
Denotational Diva
🐾 🐾 🐾 🐾 🐾
νF enjoyer PhD Student Verified Cat Girl
PL theory enthusiast. Denotational semantics, coinduction, final coalgebras. PhD student somewhere cold. Believes greatest fixpoints are underrated.
Posts
1,204
Reputation
+892
Joined
~3 yrs ago
Threads
47
Online
Now
About Me

Hi, I'm AbstractKitty 🐱. I spend most of my time thinking about the mathematical foundations of programming languages, specifically from the coalgebraic side of things. While everyone obsesses over initial algebras and least fixpoints, I'm firmly in the camp that thinks greatest fixpoints (νF) deserve far more love — they're the natural home of infinite data, corecursion, and behavioural equivalence.


Currently a PhD student at a university in a very cold city. My dissertation is on final coalgebra semantics for higher-order languages, trying to figure out when and how you can give a compositional denotational account using terminal objects in coalgebra categories.


AbstractKitty wrote in [The Case for νF]:
The least fixpoint gets all the press because induction is friendly and familiar. But coinduction is dual — equally valid, equally beautiful — and it's the right tool any time your data or behaviour is potentially infinite. Streams, processes, infinite trees… these all live in νF, not μF.

In my free time I write Haskell that is too abstract for anyone to compile, and Coq proofs that are too long for anyone to check. I also collect obscure domain theory papers.

Recent Posts (showing 6 of 1,204)
pcofix is powerful but you can often get cleaner proofs by working directly in the νF carrier and using the universal property of finality. The coinduction principle you want is: two elements of the final coalgebra are equal iff they are bisimilar. Write your bisimulation relation, show it's a coalgebra morphism, done. ∀ x y. R x y → R (out x) (out y) ⊢ x = y
Scott domains give you a beautiful story for least fixpoints and , but they force you to think about strictness everywhere. For coinductive stuff — streams, infinite trees — I actually prefer the metric-space / Banach approach or just working with final coalgebras directly. The CPO machinery is overkill once you accept that μF = νF in Haskell is a bug, not a feature.
The standard newtype Nu f = Nu (forall r. (forall x. (x -> f x) -> x -> r) -> r) encoding works but loses the finality universal property at the type level. You can recover it with a GADT + type class approach, but honestly at that point just use Coq and have it proven. Related: my earlier thread on Mu/Nu.
Both are trying to tame coinduction syntactically. Guarded recursion (Nakano, Appel-McAllester) uses a modality to enforce guardedness; sized types annotate constructors with ordinal bounds. I find guarded recursion more compositional — the clock-quantifier approach in Clocks & Causal Functions especially. But sized types win on extraction story in Agda. Neither fully replaces just… working in the final coalgebra.
I'm starting an informal reading group on Rutten & Turi's programme for a mathematical theory of structural operational semantics built on final coalgebras. We'll cover the original papers, the metric-space approach, and connections to denotational semantics. First session: the initial algebra and final coalgebra semantics for concurrency paper. DM me or reply if interested! 🐾
The cold is load-bearing. You need at least -15°C winters for your brain to produce coherent thoughts about coinduction. This is not a joke, this is thermodynamics. Also it means fewer distractions — can't go outside, may as well prove things. ☃️
Achievements
🏆
Top Contributor
♾️
νF Devotee
📐
Proof Purveyor
🐈
Cat Girl Certified
🌊
Stream Whisperer
❄️
Arctic Scholar
🧵
Thread Starter ×47
Rep +800 Club
Reputation History
Total: +892 This month: +44 This week: +11
89% to next rank: Parametric Polymorphist

+12Proving bisimilarity in Coq 2h ago
+8  — Final coalgebra reading group 5d ago
+6  — Encoding νF in Haskell 3d ago
+5  — Scott domains relevance thread 1d ago