### The Continuation Passing Transform and the Yoneda Embedding

#### Posted by John Baez

*Guest post by Mike Stay*

The Yoneda embedding is familiar in category theory. The continuation passing transform is familiar in computer programming.

They’re the same thing! Why doesn’t anyone ever say so?

Assume `A`

and `B`

are types; the continuation
passing transform takes a function (here I’m using C++ notation)

B f(A a);

and produces a function

<X> CPT_f(<X> (*k)(B), A a) { return k(f(a)); }

where `X`

is any type. In `CPT_f`

, instead of
returning the value `f(a)`

directly, it reads in a
continuation function `k`

and “passes” the result to it.
Many compilers use this transform to optimize
the memory usage of recursive functions; continuations are also
used for exception
handling, backtracking,
coroutines, and even
show up in
English.

The Yoneda embedding takes a category $C^{op}$ and produces a category $HOM(C, Set):$

$\array{CPT: & C^{op} & \to & HOM(C, Set) \\ & A & \mapsto & hom(A, -) \\ & f:B\leftarrow A & \mapsto & CPT(f): & hom(B, -) & \to & hom(A, -) \\ & & & & k & \mapsto & k \, \mathrm{o} \, f}$

We get the transformation above by uncurrying to get $CPT(f):hom(B, -) \times A \to -.$

In Java, a (cartesian closed) category $C$ is an interface `C`

with a bunch of internal interfaces and methods mapping between them. A functor $F:C \to Set$ is written

`class F implements C`

.

Then each internal interface `C.A`

gets instantiated as a set `F.A`

of values and each method `C.f()`

becomes instantiated as a function `F.f()`

between the sets.

The continuation passing transform can be seen as a parametrized functor $CPT\langle X\rangle:C \to Set$. We’d write

`class CPT<X> implements C`

.

Then each internal interface `C.A`

gets instantiated as a set `CPT<X>.A`

of methods mapping from `C.A`

to `X`

—i.e. continuations that accept an input of type `C.A`

—and each method `C.f`

maps to the continuized function `CPT<X>.f`

described above.

Then the Yoneda lemma says that for every model of $C$—that is, for every `class F`

implementing the `interface C`

—there’s a natural isomorphism between the set $F(A)$ andthe set of natural transformations $hom(hom(A, -), F).$

A natural transformation $\alpha$ between $F:C \to Set$ and $CPT:C \to Set$ is a way to cast the class `F`

to the class `CPT<X>`

such that for any method of `C`

, you can either

- invoke its implementation directly (as a method of
`F`

) and then continuize the result (using the type cast), or - continuize first (using the type cast) and then invoke the
continuized function (as a method of
`CPT<X>`

) on the result

and you’ll get the same answer. Because it’s a natural
*isomorphism*, the cast has an inverse.

The power of the Yoneda lemma is taking a continuized form (which apparently turns up in lots of places) and replacing it with the direct form. The trick to using it is recognizing a continuation when you see one.

## Re: The Continuation Passing Transform and the Yoneda Embedding

It seems to me that, by itself, the interface is more like a graph, and implementing the interface establishes a graph morphisms from that graph to the graph underlying the category of sets.

The reason is that the interface makes no specification about the result of composing any of the methods it declares.

Just recently I saw on some blog, but I forget where (yours maybe??), a discussion of how categories appear in Java and/or C++.

There I saw this point addressed: the author identified the composition operation in the category with a kind of consistency checking that some programming languages apparently have. I forget the programming language termininology. Something like “tests” or the like. You need to help me here.

The point being that, if you define an interface which specified one data type A and three methods $f,g,h : A \to A$ which each read in an $A$ and spit out an $A$, you want to be able to say things like $g \circ f = h \,.$

The interface alone does not do that.

And in fact that seems to be pretty hard to implement in a programming language. It should even be impossible, right? The compiler would have to check, whenever you instantiate an interface, if the methods in the class implementing the interface satisfy this composition property. But each method is a program in its own right. So checking this amounts to checking correctness of programs, right? Which is in general impossible, right?

(Stop me if I am spouting nonsense, I am not a computer science expert.)