Cat

Cat is a statically typed, stack-based, pure functional programming language created by Christopher Diggins. It has no variables. It has no argument lists, no let, no parameters, no names for values of any kind. A Cat program is a sequence of instructions, each of which takes one stack and returns another, and putting two instructions side by side means composing them. That is the whole model.

What makes Cat more than a Joy clone is that it is typed, and typed without asking the programmer for anything. Cat infers a type for every expression, where a type describes what a function does to the shape of a stack, and it rejects programs that would underflow the stack or leave incompatible values on the branches of a conditional - all before running a single instruction.

The language was never intended to be a general-purpose programming language for humans writing applications. Diggins designed it as an intermediate language: something a compiler could target, verify, and optimize on the way down to a real machine.

History and Origins

Cat first appears publicly in a post to Diggins’ Artima weblog dated May 13, 2006. The framing there is telling. Cat is introduced not as a language to learn but as a compilation target, one that happened to sit between Joy and Microsoft’s MSIL. The argument was that high-level functional optimizations are easy to apply to a composition-based program and nearly impossible to recover once the program has been lowered to assembly-level instructions - so a compiler should pass through something like Cat first.

The direct ancestor is Joy, Manfred von Thun’s concatenative language, which is itself a descendant of Forth by way of Backus’s FP. Joy showed that you could build a complete functional language out of stack manipulation and quotation, with no variables at all. What Joy did not have was static types; it checked at runtime. Cat’s contribution was to keep Joy’s semantics and add a type system, which is why Cat has been summarised as “Forth meets Haskell.”

The language reached a wider audience in May 2008, when Diggins published Cat: A Functional Stack-Based Language in Dr. Dobb’s Journal. That article is still the most complete introduction to Cat v1 - quotations, partial application, higher-order combinators, metadata comments in a YAML-flavoured syntax that doubled as automated tests, and worked examples including quicksort and a MapReduce implementation.

Then it stopped. The v1 implementation - written in C#, running only on Windows, hosted on Google Code - was frozen in 2008 at v1b4. An embedding of Cat in Scheme and an online JavaScript interpreter had also been released, but the project went quiet for eight years.

The v2 rewrite

In October 2016, Diggins opened a GitHub repository for Cat; the first commit is annotated as the first since the Google Code v1b4 of 2008. Real work began in December 2017, with a complete reimplementation in TypeScript, compiled to ES5-compliant JavaScript so it would run anywhere rather than only on Windows.

The rewrite was not just a port. The specification was simplified, and the type system - which Diggins described as having originally been “a playground for various ideas” - was formalized properly. His own account of the intervening decade is that interest in Cat had settled on two things: the simple semantics, and the “deceptively simple type algorithm,” which he says he only later recognised as a higher-rank polymorphic type system.

The type checker was extracted into its own package, cdiggins/type-inference, explicitly so it could be reused by other JavaScript- or TypeScript-targeting language projects. Development ran for roughly two weeks. The last commit is dated January 4, 2018.

Design Philosophy

Composition instead of application

The central claim of concatenative programming, and Cat’s inheritance from Joy, is that program construction should be function composition rather than function application. In a conventional language you write f(g(x)) - you apply functions to arguments. In Cat you write g f, and juxtaposition is composition. There is no x.

The consequence is that any contiguous chunk of a Cat program is itself a valid function, and can be factored out and given a name with no rewriting whatsoever. That property - refactoring by cutting on any boundary - is the thing concatenative programmers tend to point at first.

Everything is a function on stacks

Cat takes this further than it might sound. Literals are functions too: 1 is the function that takes a stack and returns that stack with 1 pushed on it. Quotations are functions that push functions. There is exactly one kind of thing in the language.

Optimization as the design goal

Because a Cat program is a composition, program transformations are algebraic rewrites over a sequence. There are no environments to reason about, no aliasing, no order-of-evaluation questions. Diggins’ pitch was that this makes inlining, partial evaluation and verification structurally easy - the v1 C# implementation shipped type checking, inference, inlining and partial evaluation as part of the toolchain.

Key Features

Eight primitives

Cat v2 defines a core set of eight general-purpose primitive instructions, each with its type written in Cat’s own notation:

apply   : (('S -> 'R) 'S -> 'R)
quote   : ('a 'S -> ('R -> 'a 'R) 'S)
compose : (('B -> 'C) ('A -> 'B) 'S -> ('A -> 'C) 'S)
dup     : ('a 'S -> 'a 'a 'S)
pop     : ('a 'S -> 'S)
swap    : ('a 'b 'S -> 'b 'a 'S)
cond    : (Bool 'a 'a 'S -> 'a 'S)
while   : (('S -> Bool 'R) ('R -> 'S) 'S -> 'S)

A trivial program, from the project’s own readme: 6 7 dup mul sub leaves the value 43 on top of the stack.

Quotations

A quotation is an expression in brackets - [1 add] - which pushes that expression onto the stack as a value to be executed later, with apply or dip. This is how Cat gets first-class functions without ever naming a parameter. Quotations can be built at runtime by composing other quotations, which is how papply implements partial application.

Row-polymorphic types

Cat’s type notation describes a transformation between stack configurations. The terms left and right of the arrow are the stack before and after. Crucially, the last term on each side stands for “the rest of the stack” - a type variable representing everything the function does not touch. That is row polymorphism, and it is what lets a function like dup be given one type that works no matter how deep the stack is beneath it.

Identifiers prefixed with an apostrophe are type variables, which may be bound to any type including polymorphic functions.

A standard library derived from the primitives

Cat’s stack-shuffling vocabulary is not built in; it is defined. From the v2 standard library:

dip      = { swap quote compose apply }
rcompose = { swap compose }
papply   = { quote rcompose }
dipd     = { swap [dip] dip }
popd     = { [pop] dip }
popop    = { pop pop }
dupd     = { [dup] dip }
swapd    = { [swap] dip }
rollup   = { swap swapd }
rolldown = { swapd swap }

Every one of these gets a type inferred automatically. papply, for example, infers as ('t0 ('t0 't1 -> 't2) 't3 -> ('t1 -> 't2) 't3) - it consumes a value and a function and hands back a function with that value already bound.

Notably, dip was a primitive early in the v2 rewrite and was removed on December 29, 2017, once it could be defined in terms of the basic forms.

Higher-rank polymorphism, fully inferred

Cat v2 supports higher-rank parametric polymorphism without recursive types, and infers all of it - no annotations required anywhere. The formal statement of the primitive types uses explicit quantifiers and nested pairs for stacks:

apply   : !R.(!S.((S -> R) S) -> R)
quote   : !S!a.((a S) -> (!R.(R -> (a R)) S))
compose : !A!C!S.(!B.((B -> C) ((A -> B) S)) -> ((A -> C) S))

This has a concrete consequence the project documents explicitly: Cat cannot be embedded in a language limited to rank-1 polymorphism, such as Haskell or ML, because those systems cannot infer the type of the expression quote dup.

Grammar

Cat’s syntax is small enough to state in one page. The v2 parser is written with the Myna TypeScript parsing library and recognises quotations, integers, booleans, identifiers, type expressions, define with an optional type signature, and extern declarations. That is the entire language.

Evolution

The most interesting thing about the two versions is what got thrown away. V1 accumulated features across several years of experimentation. V2 kept eight primitives and a type system, and dropped nearly everything else. It is a rare case of a language author returning after a decade and making the language decisively smaller.

Current Relevance

Cat is dormant. The repository has not been touched since January 2018, the wiki entry describing it was last revised in early 2020, and there is no package ecosystem, no community, and no production software written in it. Nobody should pick Cat for a project today.

What survives is the idea. The problem Cat set out to solve - how do you give static types to a language where every function silently consumes and produces an unbounded stack - has an answer that Cat states cleanly, and that answer is row polymorphism plus higher-rank inference. Typed concatenative languages designed since operate in territory Cat helped map; the row-variable notation in particular is now common vocabulary for the problem. The type-inference package was deliberately factored out to make that transfer easy.

The repository remains available under the MIT License and has accumulated roughly 285 GitHub stars as of 2026 - a reasonable measure of a language nobody uses but a fair number of people found worth reading.

Why It Matters

Cat is a good example of a language whose value is entirely in its argument rather than its adoption. Three things it did are worth keeping:

1. It made a case for concatenative languages as compiler infrastructure. Not “here is a nicer language,” but “here is a representation in which optimization is easy,” which is a claim about compilers, not about taste.
2. It typed Joy. Joy demonstrated that variable-free functional programming works; Cat demonstrated that it can be statically checked without giving up inference or annotating anything.
3. It shows how far a handful of primitives goes. Eight instructions, plus quotation, generate the entire stack-manipulation vocabulary - and every derived definition types itself.

For anyone interested in how programming languages get smaller rather than larger, Cat’s v1-to-v2 arc is an unusually clean case study: an author with ten years of hindsight, deleting most of his own language and keeping the part that turned out to be the idea.