reperiendi

Category Theory for the Java Programmer

Posted in Category theory, Math, Programming by Mike Stay on 2007 November 3

[Edit May 11, 2012: I’ve got a whole blog on Category Theory in JavaScript.]

There are several good introductions to category theory, each written for a different audience. However, I have never seen one aimed at someone trained as a programmer rather than as a computer scientist or as a mathematician. There are programming languages that have been designed with category theory in mind, such as Haskell, OCaml, and others; however, they are not typically taught in undergraduate programming courses. Java, on the other hand, is often used as an introductory language; while it was not designed with category theory in mind, there is a lot of category theory that passes over directly.

I’ll start with a sentence that says exactly what the relation is of category theory to Java programming; however, it’s loaded with category theory jargon, so I’ll need to explain each part.

A collection of Java interfaces is the free3 cartesian4 category2 with equalizers5 on the interface6 objects1 and the built-in7 objects.

1. Objects

Both in Java and in category theory, objects are members of a collection. In Java, it is the collection of values associated to a class. For example, the class Integer may take values from -2^{63} up to 2^{63}-1. The class

enum Seasons { Spring, Summer, Fall, Winter }

has four possible values.

In category theory, the collection of objects is “half” of a category. The other part of the category is a collection of processes, called “morphisms,” that go between values; morphisms are the possible ways to get from one value to another. The important thing about morphisms is that they can be composed: we can follow a process from an initial value to an intermediate value, and then follow a second process to a final value, and consider the two processes together as a single composite process.

2. Categories

Formally, a category is

  • a collection of objects, and
  • for each pair of objects A, B, a set {\rm hom}(A, B) of morphisms between them

such that

  • for each object X the set {\rm hom}(X, X) contains an identity morphism 1_X,
  • for each triple of objects X, Y, Z and pair of morphisms f \in {\rm hom}(X, Y) and g \in {\rm hom}(Y, Z), there is a composite morphism (g \circ f) \in {\rm hom}(X, Z),
  • for each pair of objects X, Y and morphism f\in {\rm hom}(X, Y), the identitiy morphisms are left and right units for composition: 1_Y \circ f = f = f \circ 1_X, and
  • for each 4-tuple of objects X, Y, Z, W and triple of morphisms f \in {\rm hom}(X, Y), g \in {\rm hom}(Y, Z), h \in {\rm hom}(Z, W) composition is associative: h\circ (g \circ f) = (h \circ g)\circ f.

If a morphism f \in {\rm hom}(A,B), category theorists write f:A\to B.

We can also define a category in Java. A category is any implementation of the following interface:

interface Category {
  interface Object {}
  interface Morphism {}
  class IllegalCompositionError extends Error;

  Object source(Morphism);
  Object target(Morphism);
  Morphism identity(Object);
  Morphism compose(Morphism, Morphism)
    throws IllegalCompositionError;
};

that passes the following tests on all inputs:

void testComposition(Morphism g, Morphism f) {
  if (target(f) != source(g)) {
    assertRaises(compose(g, f),
                 IllegalCompositionError);
  } else {
    assertEqual(source(compose(g, f)), source(f));
    assertEqual(target(compose(g, f)), target(g));
  }
}
void testAssociativity(Morphism h,
                       Morphism g,
                       Morphism f) {
  assertEqual(compose(h, compose(g, f)),
              compose(compose(h, g), f));
}
void testIdentity(Object x) {
  assertEqual(source(identity(x)), x);
  assertEqual(target(identity(x)), x);
}
void testUnits(Morphism f) {
  assertEqual(f, compose(identity(target(f)), f));
  assertEqual(f, compose(f, identity(source(f))));
}

One kind of category that programmers use every day is a monoid. Monoids are sets equipped with a multiplication table that’s associative and has left- and right units. Monoids include everything that’s typically called addition, multiplication, or concatenation. Adding integers, multiplying matrices, concatenating strings, and composing functions from a set to itself are all examples of monoids.

In the language of category theory, a monoid is a one-object category (monos is Greek for “one”). The set of elements you can “multiply” is the set of morphisms from that object to itself.

In Java, a monoid is any implementation of the Category interface that also passes this test on all inputs:

void testOneObject(Morphism f, Object x) {
  assertEqual(source(f), x);
}

The testOneObject test says that given any morphism f and any object x, the source of the morphism has to be that object: given another object y, the test says that source(f) == x and source(f) == y, so x == y. Therefore, if the category passes this test, it has only one object.

For example, consider the monoid of XORing bits together, also known as addition modulo 2. Adding zero is the identity morphism for the unique object; we need a different morphism to add 1:

interface Parity implements Category {
  Morphism PlusOne();
}

The existence of the PlusOne method says that there has to be a distinguished morphism, which could potentially be different from the identity morphism. The interface itself can’t say how that morphism should behave, however. We need tests for that. The testPlusOne test says that (1 + 1) % 2 == 0. The testOneIsNotZero test makes sure that we don’t just set 1 == 0: since (0 + 0) % 2 == 0, the first test isn’t enough to catch this case.

void testOnePlusOne(Object x) {
  assertEqual(compose(PlusOne(), PlusOne()),
              identity(x));
}

void testOneIsNotZero(Object x) {
  assertNotEqual(PlusOne(), identity(x));
}

Here’s one implementation of the Parity interface that passes all of the tests for Category, testOneObject, and the two Parity tests:

class ParityImpl implements Parity {
  enum ObjectImpl implements Object { N };
  enum MorphismImpl implements Morphism {
    PlusZero,
    PlusOne
  };
  Object source(Morphism) { return N; }
  Object target(Morphism) { return N; }
  Morphism identity(Object) { return PlusZero; }
  Morphism compose(Morphism f, Morphism g) {
    if (f == PlusZero) return g;  // 0 + g = g
    if (g == PlusZero) return f;  // f + 0 = f
    return PlusZero;              // 1 + 1 = 0
  }
  Morphism PlusOne() { return PlusOne; }
}

3. Free

Java tests are a kind of “blacklisting” approach to governing implementations. Had we not added testOneIsNotZero, we could have returned PlusZero and the compiler would have been happy. In a free category, relations are “whitelisted:” an implementation must not have relations (constraints) other than the ones that are implied by the definitions.

  • “The free category” has no objects and no morphisms, because there aren’t any specified.
  • “The free category on one object N” has one object and one morphism, the identity 1_N. The morphism has to be there, because the definition of category says that every object has to have an identity morphism, but we can’t put in any other morphisms.
  • “The free category on the directed graph G
     
                         A -f-> B
                         |    /
                     G = h   g
                         |  /
                         V L
                         C

    has

    • three objects A, B, C and
    • seven morphisms:
      • 1_A:A \to A,
      • 1_B:B \to B,
      • 1_C:C \to C,
      • f:A \to B,
      • g:B \to C,
      • h:A \to C, and
      • (g \circ f):A \to C.

    The three vertices and the three edges become objects and morphisms, respectively. The three identity morphisms and (g \circ f) are required to be there because of the definition of a category. And because the category is free, we know that (g \circ f) \ne h.

    For abritrary directed graphs, the free category on the graph has the vertices of the graph as objects and the paths in the graph as morphisms.

  • The parity monoid is completely defined by “the free category on one object N, one morphism \mbox{PlusOne}:N\to N, and one relation \mbox{PlusOne} \circ \mbox{PlusOne} = 1_{N}.
  • If we leave out the relation and consider “the free category on one object N and one morphism \mbox{PlusOne}:N\to N,” then we get the natural numbers under addition: since we didn’t specify a point at which repeated applications of PlusOne“wrap around” back to zero, the free category has no such constraint. To add the number n, we form

    \underbrace{\mbox{PlusOne} \circ \mbox{PlusOne} \circ \cdots \circ \mbox{PlusOne}}_{n \mbox{ copies}}.

  • Exercise: what is the common name for “the free category on one object N and two morphisms \mbox{ConcatenateZero}:N\to N, \mbox{ConcatenateOne}:N\to N?” What should the identity morphism be named?

4. Cartesian

A cartesian category has lists as its objects. It has a way to put objects together into ordered pairs, a way to copy objects, and an object that’s “the empty” object.

It’s time to do the magic! Recall the interface Category:

interface Category {
  interface Object {}
  interface Morphism {}
  class IllegalCompositionError extends Error;

  Object source(Morphism);
  Object target(Morphism);
  Morphism identity(Object);
  Morphism compose(Morphism, Morphism)
    throws IllegalCompositionError;
};

Now let’s change some names:

interface Interface {
 interface InternalInterfaceList {}
 interface ComposableMethodList {}
 class IllegalCompositionError extends Error;

 InternalInterfaceList source(ComposableMethodList);
 InternalInterfaceList target(ComposableMethodList);
 ComposableMethodList identity(InternalInterfaceList);
 ComposableMethodList compose(ComposableMethodList,
                              ComposableMethodList)
   throws IllegalCompositionError;
}

Category theory uses cartesian categories to describe structure; Java uses interfaces. Whenever you see “cartesian category,” you can think “interface.” They’re pretty much the same thing. Practically, that means that a lot of the drudgery of implementing the Category interface is taken care of by the Java compiler.

For example, recall the directed graph G above. We can get effectively the same implementation of the graph by using this interface:

interface G {
  interface A;
  interface B;
  interface C;
  B f(A);
  C g(B);
  C h(A);
}

That’s it! We’re considering the free category on G, so there are no tests. We can compose lists of methods: g(f(a)). The compiler will give us an error if we try to compose methods whose source and target don’t match: h(g(b)) doesn’t work.

Because the objects of the cartesian category Interface are lists, we can define methods in our interfaces that have multiple inputs.

interface Monoid {
  interface M;
  M x(M, M);
  M e();
}
void testX(M a, M b, Mc) {
  assertEqual(x(a, x(b, c)),
              x(x(a, b), c));
}
void testE(M a) {
  assertEqual(a, x(a, e()));
  assertEqual(a, x(e(), a));
}

Here, the method x takes a two-element list as input, while e takes an empty list.

Exercise: figure out how this definition of a monoid relates to the one I gave earlier.

Implementation as a functor

Cartesian categories (interfaces) provide the syntax for defining data structures. The meaning, or semantics, of Java syntax comes from implementing an interface.

In category theory, functors give meaning to syntax. Functors go between categories like functions go between sets. A functor F:C \to D

  • maps objects of C to objects of D and
  • maps morphisms of C to morphisms of D such that
  • identities and composition are preserved.

There are several layers of functors involved in implementing a typical Java program. First there’s the implementation of the interface in Java as a class that defines everything in terms of the built-in classes and their methods; next, there’s the implementation of the built-in methods in the Java VM, then implementation of the bytecodes as native code on the machine, and finally, physical implementation of the machine in silicon and electrons. The composite of all these functors is supposed to behave like a single functor into {\rm Set}, the category whose objects are sets and whose morphisms are functions between sets. We end up approximating many of these sets: instead of integers, we use ints and hope that they don’t overflow. Instead of real numbers, we use doubles and are surprised when we lose precision. In category theory, we ignore this and say that in any practical application, we’ll use datatypes that are “big enough.”

The upshot of all this is that a Java class F implementing an interface X can be thought of as a functor F:X \to {\rm Set}. The class definition assigns to each inner interface a set of values and to each method a function mapping between those sets.

Here’s an example of three different classes that implement the Monoid interface from the last subsection. Recall that a monoid is a set of things that we can combine; we can add two integers to get an integer, multiply two doubles to get a double, or concatenate two strings to get a string. The combining operation is associative and there’s a special element that has no effect when you combine it with something else: adding zero, multiplying by 1.0, or concatenating the empty string all do nothing.

So, for example,

class AddBits implements Monoid {
  enum Bit implements M { Zero, One }
  M x(M f, M g) {
    if (f == e()) return g;  // 0+g=g
    if (g == e()) return f;  // f+0=f
    return Zero;             // 1+1=0
  }
  M e() { return Zero; }
}

Here, the functor {\rm AddBits}:{\rm Monoid} \to {\rm Set} assigned the set \{0, 1\} to the object M, assigned the function XOR to the morphism x, and assigned the constant function returning {0} to the morphism e.

class MultiplyBits implements Monoid {
  enum Bit implements M { Zero, One }
  M x(M f, M g) {
    if (f == e()) return g;   // 1*g=g
    if (g == e()) return f;   // f*1=f
    return Zero;              // 0*0=0
  }
  M e() { return One; }
}

Here, the functor {\rm MultiplyBits}:{\rm Monoid} \to {\rm Set} assigned to M the same set as before, \{0, 1\}, but assigned the function AND to the morphism x and the constant function returning 1 to the morphism e.

class Concatenate implements Monoid {
  class ConcatString implements M {
    ConcatString(String x) {
      this.x = x;
    }
    String x;
  }
  M x(M f, M g) {
    return new ConcatString(
        f.x + g.x);
  }
  M e() {
    return new ConcatString("");
  }
}

Here, the functor {\rm Concatenate}:{\rm Monoid} \to {\rm Set} assigned the set of strings to M, assigned the string concatenation function to the morphism x and the constant function returning the empty string to the morphism e.

5. Equalizers

An equalizer of two functions f:A \to C and g:B \to C picks out the set A {{}_f\times_g} B= \{\mbox{pairs of elements } (a,b) \mbox{ such that } f(a) = g(b)\}. This gets used in the definition of a category: we let A = B = the set of morphisms in our category, and let C be the set of objects. We let f, g be the source and target maps, repsectively. Then A {{}_f\times_g} B is the set of composable pairs of morphisms.

In Java, this means that we can throw an exception if the pair isn’t composable.

6, 7. Interface objects and built-in objects

The objects of the free category in question are java interfaces, whether defined by the programmer or built-in. Because it’s cartesian, we can combine interfaces into new interfaces:

interface XYPair { interface X; interface Y; }

The built-in objects have some relations between them–we can cast an integer into a double, for instance, or turn an integer into a string–so these relations exist between combinations of arbitrary interfaces with built-in ones. But there are no automatic cast relationships between user-defined interfaces, so the category is free.

Next time

This post was about how to translate between Java ideas and category-theory ideas. Next time, I’ll show what category theory has to offer to the Java programmer.

About these ads

13 Responses

Subscribe to comments with RSS.

  1. Science After Sunclipse said, on 2007 November 4 at 5:29 am

    Category Theory for Java Programmers

    Mike Stay has just posted “Category Theory for the Java Programmer,” an introduction to the subject intended for people with practical programming experience. This is the latest, but hopefully not the last, in a series of introductory arti…

  2. reperiendi said, on 2007 November 4 at 10:17 pm

    Someone linked to this article on reddit and it spawned a decent thread.

    http://programming.reddit.com/info/5zshz/comments/

    One common sentiment was, “Why do I need category theory to be a programmer?” You don’t, of course: my intended audience is the programmer who’s heard about category theory and wants an accessible introduction.

    Another was the question “why a whole set of morphisms between two objects? Shouldn’t there just be one, where f(a) = b?” It was suggested that in Haskell, Int is an object; the same is true in Java. It’s not widely known among any but the most advanced Java programmers, but all Java classes are instances of the class “Class.”

  3. summerstay said, on 2007 November 5 at 2:08 pm

    This was a lot clearer! I’m still a little confused about “monoid.” What is there only one of in a monoid?

  4. reperiendi said, on 2007 November 5 at 5:02 pm

    > I’m still a little confused about “monoid.” What is there only one of in a monoid?

    Essentially, only one set of elements.

    Remember, a monoid is usually defined to be a set M with an associative multiplication table and a unit element, satisfying the left- and right-unit equations. For every element x of M there’s a corresponding function

    f_x(Z) = x * Z

    that multiplies on the left by x. Then composition is “the same as” multiplication:

    f_x( f_y( Z ) ) = x * y * Z = f_{x*y}(Z)

    More concisely,

    f_x o f_y = f_{x*y}

    where o means compose.

    Since composition is a built-in operation on morphisms in category theory, we can take M as our one object and let

    hom(M, M) = {f_x: M->M such that x is an element of M}.

  5. mikaelstaldal said, on 2007 November 6 at 7:04 am

    It is quite confusing that what you call “object” is what is called “class” in Java, while “object” in Java is the values which are members of the classes.

  6. reperiendi said, on 2007 November 6 at 9:47 am

    > It is quite confusing that what you call “object” is what is called “class” in Java, while
    > “object” in Java is the values which are members of the classes.

    Only sometimes. Reread the first paragraph in section 1: the collection of objects is the set of values associated to a class, just as you said. In the “Category” interface, the objects are the members of the internal interface “Object.”

    In Java, there’s a class “Class” whose objects are classes. So I can say internal interfaces are objects, since they’re instances of Class. This is closer to the way category theory is used, since we often want the objects of our categories to be collections themselves.

  7. mattdr said, on 2007 November 6 at 10:47 am

    Interesting read (and, just to be a nitpicking git, doesn’t Integer support values between -2^31 and 2^31 – 1, as opposed to Long?) I look forward to the next article.

  8. reperiendi said, on 2007 November 6 at 11:11 am

    > just to be a nitpicking git, doesn’t Integer support values between -2^31
    > and 2^31 – 1, as opposed to Long?

    :) Probably! Unfortunately, WordPress’ editor isn’t idempotent; I think it doesn’t support the <pre> tag properly. So I had to compose this in a text editor and then paste it in. Unfortunately, I deleted the file, so it’s hard to make corrections.

  9. […] some introductions to theory of categories (a very good introduction to the theory, or this one more programmer oriented). As I also stumble upon this thread, I discover a new concept: “hylomorphism is a composite […]

  10. -= Linkage: 2007.11.05 =- said, on 2009 January 26 at 8:41 am

    […] JCategory-theory<br/> […]

  11. Vitomir said, on 2012 January 8 at 6:49 pm

    the source code for the Category interface is not valid. the names of the arguments are missing and the inheritance is not specified correctly.

    it should be

    interface Category {

    interface Object {}

    interface Morphism {}

    class IllegalCompositionError extends Error {}

    Object source(Morphism m);

    Object target(Morphism m);

    Morphism identity(Object o);

    Morphism compose(Morphism m1, Morphism m2) throws IllegalCompositionError;
    };

  12. dobesv said, on 2012 October 7 at 12:11 pm

    I do find it confusing that arithmetic and the bit operations are defined using a morphism from N to itself yet in the directed graph the morphisms have a distinct object for each node. Isn’t a directed graph a category of two objects Edge and Node?

    Or could we define a category where zero and one were separate objects?

    • Mike Stay said, on 2012 November 12 at 1:53 pm

      You certainly could define a category where 0 and 1 are separate objects. For example, we can form a category where the objects are integers and there’s a morphism from m to n if m ≤ n.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 26 other followers

%d bloggers like this: