March | 2012 | Category Theory in JavaScript

March 31, 2012

Categorical products

Here are a bunch of constructions that share a similar property:

The intersection of two sets is the largest set that’s a subset of both of them.
The minimum of two numbers is the largest number that’s less than or equal to both of them.
The greatest common divisor of two numbers is the largest number that divides both of them.
The proposition “A and B” is the one with the least assumptions needed to prove both A and B.

A partial order is a set equipped with a relation ≤ that is

transitive $(X \le Y \le Z \Rightarrow X \le Z),$
reflexive $(X \le X),$ and
antisymmetric $(X \le Y \mbox{ and } Y \le X \Rightarrow X = Y).$

All of these examples are extremes in a partial order, either the largest or smallest example of something. We say they satisfy a “universal property”.

Another definition of partial order is “a category where there’s at most one morphism between any two objects and the only cycles are identities”, so we have four categories:

The category whose objects are sets and whose morphisms are statements of the form “X ⊂ Y”.
The category whose objects are real numbers and whose morphisms are statements of the form “x ≤ y”.
The category whose objects are natural numbers and whose morphisms are statements of the form “x is a factor of y”.
The category whose objects are propositions and whose morphisms are statements of the form “X implies Y”.

In order to state more precisely what it means to be the most extreme example of this property, let’s look at the examples again:

Say we have a set X that we believe to be the intersection of A and B. It has to be the case that X ⊂ A and X ⊂ B. It should also be the largest such subset. We can frame this in terms of a duel between competitors: say Y is a set that also satisfies Y ⊂ A and Y ⊂ B. What is the relation between the real intersection and Y? Well, the intersection is the biggest one, so if X is the intersection, we’ve got to have Y ⊂ X for any choice of Y.
Say we have a number x that we believe to be the minimum of two numbers a and b. It has to be the case that x ≤ a and x ≤ b. It should also be the largest such number. We can frame this in terms of a duel between competitors: say y is a number that also satisfies y ≤ a and y ≤ b. What is the relation between the real minimum and y? Well, the minimum is the biggest one, so if x is the minimum, we’ve got to have y ≤ x for any choice of y.
Say we have a number x that we believe to be the GCD of two numbers a and b. It has to be the case that x is a factor of a and x is a factor of b. It should also be the largest such number. We can frame this in terms of a duel between competitors: say y is a number such that y is a factor of a and y is a factor of b. What is the relation between the real GCD and y? Well, the GCD is the biggest one, so if x is the GCD, it’s got to be true that y is a factor of x for any choice of y.
Say we have a proposition X that we believe to be the logical AND, or conjunction, of A and B. It has to be the case that X implies A and X implies B. It should also be the weakest such proposition. We can frame this in terms of a duel between competitors: say Y is a proposition that also satisfies Y implies A and Y implies B. What is the relation between the real conjunction and Y? Well, the conjunction is the weakest one, so if X is the conjunction, we’ve got to have Y implies X for any choice of Y.

Each of the examples above can be illustrated with a simple diagram, where an arrow denotes that the source is less than or equal to the target:

$\begin{array}{rcccl} & & Y & & \\ & \swarrow & \downarrow & \searrow \\ A & \leftarrow & X & \rightarrow & B \end{array}$

It turns out that we can generalize the product from partial orders to categories and get useful structures. In the category of sets and functions, we are no longer restricted to a single morphism between two objects, so we need labels on the diagram naming our functions; in order to have a “best” object, though, we want the arrow from Y to X to be unique:

$\begin{array}{rcccl} & & Y & & \\ & {\scriptstyle r} \swarrow & {\scriptscriptstyle \stackrel{\vdots}{\vee}}{\scriptstyle !} & \searrow {\scriptstyle s} \\ A & \xleftarrow[p]{} & X & \xrightarrow[q]{} & B \end{array}$

This says that X is an object with morphisms to A and B such that given any object Y with morphisms to A and B, there exists a unique morphism from Y to X making the diagram commute—that is, if we apply the morphism marked ! and then p, we get the same result as applying r; similarly, if we apply ! and then q, we get the same result as applying s.

In the category of sets and functions, the categorical product gives us the cartesian product of sets:

If instead of using two sets and two functions “first” and “second”, we use an arbitrary finite number of sets and index them with brackets and natural numbers, then we get tuples.

Posted in Uncategorized | 2 Comments »

March 30, 2012

Hom

Most statically-typed languages have you put all the typing information in the same place. So far, we’ve had to put the output contract at the end of the function in the return statement. We’ve seen that we can write a higher-order contract that guarantees a function will map strings to strings; here’s one that works for an arbitrary pair of contracts:

var hom = function (sourceArr, target) {
  var source = makeProduct(sourceArr);
  return function (f) {
    func(f);
    return function (varArgs) {
      return target(f.apply(this,
          source(toArray(arguments))));
    };
  };
};

We can use hom to give type information up front:

var repeat = hom([str, nat32], str)
  (function (s, n) {
    return Array(n+1).join(s);
  });

The name “hom” comes from category theory: given any two objects A and B in a category, there’s a set of morphisms between them called hom(A, B). The higher-order contract hom ensures that a function is an element of that set.

Posted in Uncategorized | 2 Comments »

March 30, 2012

Some more categories

Recall that a category consists of

a collection of objects, and
for any pair of objects A, B, a set of morphisms between them (if f is a morphism from A to B, we write f:A -> B)

such that

every object A has an identity morphism id_A:A -> A;
we can compose morphisms f, g if the target object of f matches the source object of g;
composition is associative; and
composing with the identity gives back the same morphism.

Here are some categories with just a single object.

The category with one object str and morphisms generated by applying makeConcat to strings:
```
var makeConcat = function (s) {
  str(s);
  return function (t) {
    return str(t) + s;
  };
};
```
The identity morphism is makeConcat('').
The category with one object nat32 and morphisms generated by applying makeAdd to natural numbers:
```
var makeAdd = function (s) {
  nat32(s);
  return function (t) {
    return nat32(t) + s;
  };
};
```
The identity morphism is makeAdd(0).
The category with one object nat32 and morphisms generated by applying makeMultiply to natural numbers:
```
var makeMultiply = function (s) {
  nat32(s);
  return function (t) {
    return nat32(t) * s;
  };
};
```
The identity morphism is makeMultiply(1).

The category with one object

// A higher-order contract
var str_to_str = function (f) {
  func(f);
  return function (s) {
    return str(f(str(s)));
  };
};

that insists that f:str -> str, and morphisms given by applying makeCompose to functions from str to str:

var makeCompose = function (f) {
  f = str_to_str(f);
  return function (g) {
    g = str_to_str(g);
    return function (s) {
      return g(f(s));
    };
  };
};

The identity is makeCompose(function (s) { return s; }).

A monoid is a category with one object. Any time you’re adding or multiplying values, you’re using a one-object category. Note that it’s not true for exponentiation! $a^{(b^c)}$ is not, in general, equal to $(a^b)^c.$

Here are three functions that share an interesting property:

// Tells whether the number of 1 bits
// in the binary expansion of n is
// even or odd.
var parity = function (n) {
  nat32(n);
  var p = 0;
  while (n > 0) {
    p = p ^ (n & 1);
    n = n >> 1;
  }
  return nat32(p);
};

// Returns the length of the string.
var length = function (s) {
  str(s);
  return nat32(s.length);
};

// Applies g to every element of an array.
var map = function (g) {
  func(g);
  return function (a) {
    arr(a);
    var result = [];
    for (var i = 0; i < a.length; ++i) {
      result[i] = g(a[i]);
    }
    return result;
  };
};

parity(n ^ m) = parity(n) ^ parity(m)
length(s + t) = length(s) + length(t)

for all arrays a,

map(function (x) { return g(f(x)); })(a);

is the same as

(function (x) { return map(g)(map(f)(x)); })(a);

A monoid homomorphism between monoids M and N is a function f that preserves composition and identity. That is, it maps the morphisms of M to the morphisms of N in such a way that given two morphisms m and m' of M, composing first and then applying f is the same as applying f to each and then composing the results in N:

f(m m') = f(m) f(m'), and
f(id_M) = id_N.

Here are some other useful categories.

The category whose objects are real numbers (the numbers themselves, not contracts), and where a single morphism exists between m and n if m <= n. Composition of morphisms is transitivity: for all m, n, p, we have m <= n <= p implies m <= p. The identity morphism for a number is reflexivity: for all m, m <= m.
The category whose objects are monoids and whose morphisms are monoid homomorphisms.
The category whose objects are natural numbers (the numbers themselves) and whose morphisms from m to n are n-by-m matrices of integers. Composition is matrix multiplication.
A directed multigraph consists of
- a set N of nodes,
- a set E of edges,
- a function source:E -> N, and
- a function target:E -> N.
This definition allows for parallel edges and self-directed edges.

Given any such directed multigraph, there is a category whose objects are the nodes and whose morphisms are the paths. (If there’s an edge from A to B and from B to C, there’s not necessarily an edge from A to C, but there is a path from A to C.) The identity morphism for an object is the “path of length zero” that starts and ends in the same place.

Categories show up all over the place.

Posted in Uncategorized | 12 Comments »

March 29, 2012

Subsets

Given a contract like nat32, we can define contracts that are more restrictive:

var positive32 = function (n) {
  nat32(n);
  if (n === 0) {
    throw new TypeError('Expected a ' +
        'strictly positive integer.');
  }
  return n;
}

The set of values that pass the positive32 contract is a subset of the values that pass the nat32 contract. A subcontract S of a contract C is a contract such that if a value v passes S, then it also passes C. The contract positive32 is therefore a subcontract of nat32.

For any contract C, there is a category whose objects are all the subcontracts of C and whose morphisms are injections. This is a subcategory (defined in the obvious way) of the category of all contracts and injections between them.

Posted in Uncategorized | 6 Comments »

March 29, 2012

Memoization and injections

A higher-order contract takes a function and returns a wrapped function obeying some input/output contract. If we want to trade memory for time, we can cache the results of a function so we don’t have to recompute them; a side-effect is that the result is guaranteed to be functional: it will always return the same value for a given input. For simplicity, assume the function takes a string as input.

// First-order contract
var func = function (f) {
  if (typeof f !== 'function') {
    throw new TypeError('Expected a function.');
  }
  return f;
};

// Higher-order contract
var memoize = function (f) {
  func(f);
  var memo = {};
  return function (s) {
    str(s);
    // The '$' prefix avoids issues with
    // magic properties like __proto__.
    var key = '$' + s;
    if (key in memo) {
      return memo[key];
    }
    return memo[key] = f(s);
  };
};

A variant of this technique lets us write a contract for injections—that is, functions where two inputs can never give the same output. Here, for simplicity, assume the function f outputs a string.

// Another higher-order contract
var injection = function (f) {
  func(f);
  var memo = {};
  return function (s) {
    var key = '$' + str(f(s));
    if (key in memo && s !== memo[key]) {
      throw new TypeError('Violated ' +
          'injection contract!');
    } else {
      memo[key] = s;
    }
    return f(s);
  };
};

Notice that f may not actually be an injection; we’ll only get an error if the wrapper realizes it’s not an injection.

There is a category whose objects are contracts and whose morphisms are injections between them. It is a very different category from the one whose objects are contracts and whose morphisms are functions between them. For example, suppose we have two contracts A, B that each allow only a finite set of values to satisfy them—say $a$ and $b$ elements, respectively. Then there are $b^a$ functions between them, but only ${b \choose a} = \frac{b!}{(b-a)!a!}$ injections because injections aren’t allowed to repeat outputs.

Posted in Uncategorized | 1 Comment »

March 29, 2012

Product and terminal contracts

In the last post, we saw a function from nat32 to str:

var spaces = function (n) {
  nat32(n);
  var result = new Array(n + 1).join(' ');
  return str(result);
};

This function is pretty specific: it only gives repetitions of the space character. What if we wanted to have lines of hyphens or asterisks or my name? We could write

var repeat = function (s, n) {
  str(s); nat32(n);
  var result = (new Array(n + 1)).join(s);
  return str(result);
};

and then say repeat('.oOo', 6) to get a nice scalloped edge: .oOo.oOo.oOo.oOo.oOo.oOo

If the type signature of spaces is spaces:nat32 -> str, what is the type signature of repeat? We have two contracts being applied, not just one. If we want to stick to the rule that we have one contract for input and one for output, we have to combine them somehow. Here, we want a function that will take a list of contracts and produce a single contract that we can apply to the list of arguments:

var arr = function (a) {
  if (!Array.isArray(a)) {
    throw new TypeError('Expected an array.');
  }
  return a;
};

// Takes an array-like object---one with a
// length property and numeric properties---
// and returns an actual array instance.
// This is necessary because the 'arguments'
// object only duck types as an array.
var toArray = function (a) {
  var result = [];
  for (var i = 0; i < a.length; ++i) {
    result[i] = a[i];
  }
  return arr(result);
};

var makeProduct = function (cs) {
  arr(cs);
  var len = cs.length;
  return function (args) {
    arr(args);
    if (args.length !== len) {
      throw new TypeError('Expected ' +
          len + ' arguments');
    }
    for (var i = 0; i < len; ++i) {
      // Apply each contract to the
      // corresponding argument.
      cs[i](args[i]);
    }
    return args;
  };
};

var str_x_nat32 = makeProduct([str, nat32]);

var repeat = function (s, n) {
  str_x_nat32(toArray(arguments));
  var result = (new Array(n + 1)).join(s);
  return str(result);
};

Now we can say repeat: str_x_nat32 -> str. I chose to use _x_ in the name to remind us that the set of values that pass this new contract is the cartesian product of the sets that pass str and nat32, respectively.

What about the empty list of contracts?

var terminal = makeProduct([]);

The name ‘terminal’ means that there’s a unique function from any contract c to terminal; the only acceptable output value is an empty array, so it just throws away its input.

var makeUnique = function (c) {
  return function (x) {
    c(x);
    return terminal([]);
  };
};

Posted in Uncategorized | 2 Comments »

March 28, 2012

Contracts

Can you spot the error in the following?

var raise = function (div) {
  div.style.setProperty('z-index',
      div.style.getProperty('z-index') + 1);
}

If the z-index of div was ‘4’, then calling raise(div) would set z-index to ’41’! The reason is that style properties are strings, and when one of the arguments to + is a string, it coerces the other to a string and concatenates the two.

Contracts can help avoid errors like the one above. A first-order contract is a function that either returns its input or throws an exception. Here are two first-order contracts:

var str = function (s) {
  if (typeof s !== 'string') {
    throw new TypeError('Expected a string.');
  }
  return s;
};

var nat32 = function (n) {
  if ((n | 0) !== n || n < 0) {
    throw new TypeError('Expected a 32-bit ' +
        'natural.');
  }
  return n;
};

Here are two functions from nat32 to str:

var itoa = function (n) {
  return str('' + nat32(n));
};

var spaces = function (n) {
  nat32(n);
  var result = new Array(n + 1).join(' ');
  return str(result);
};

I’ll denote the types of itoa and spaces as

itoa: nat32 -> str
spaces: nat32 -> str

Now for some math: a category consists of

a collection of objects, and
for any pair of objects A, B, a set of morphisms between them (if f is a morphism from A to B, we write f:A -> B)

such that

every object A has an identity morphism id_A:A -> A;
we can compose morphisms f, g if the target object of f matches the source object of g;
composition is associative; and
composing with the identity gives back the same morphism.

Contracts and the functions between them form a category. Given any two contracts, there’s a set of functions going between them. If we have two functions

f:A -> B g:B -> C,

we can compose them to get

gf: A -> C

by writing

var gf = function (a) {
  return g(f(a));
};

Also, given any contract A, there’s the identity function from A to itself:

var id_A = function (a) {
  return A(a);
};

This is obviously equivalent to the contract A, so we’ll always use A instead.

Had setProperty used the appropriate contract, raise would have caused an error the first time it was used, and we could have fixed it:

var raise = function (div) {
  div.style.setProperty('z-index',
      // The unary + coerces the
      // result to a number.
      +div.style.getProperty('z-index') + 1);
}

Posted in Uncategorized | 6 Comments »

March 28, 2012

Experiment #2

In my first experiment, I tried teaching some category theory from a programmer’s point of view over on Google+, but the platform wasn’t right for the content: posts got reordered whenever someone commented on them, and people didn’t have time or were too shy to engage at the rate I was hoping for. In this experiment, I’ll try it in a blog format and focus on the one programming language everyone on the internet has access to: JavaScript.

Since the category of computably enumerable sets and partial computable functions is—ahem—functional, choosing an imperative, dynamically-typed language might seem strange. Dynamic typing, though, can be seen as a tagged union of all possible types, so by using contracts we can split them up again. It also offers benefits like being able to say “the type of prime natural numbers” that we aren’t usually able to express statically.

As for the statefulness of JavaScript, I’ll start with the functional part and show how it avoids all kinds of problems with testing code—so you ought to be programming functionally anyway—and then (eventually) show how the standard object model JavaScript uses can be seen as a state monad on the functional part.

I’d like to do some videos as part of this, too: drawing commuting diagrams beautifully is still difficult on the web. (If you know otherwise, please tell me how!)

So, welcome! Please ask questions—it’s what keeps me motivated, and everyone else who doesn’t understand will thank you for it.

Posted in Uncategorized | 2 Comments »

M	T	W	T	F	S	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Category Theory in JavaScript

Recent Posts

Archives

Meta

Archive for March, 2012

Categorical products

Hom

Some more categories

Subsets

Memoization and injections

Product and terminal contracts

Contracts

Experiment #2

Tags

Calendar

Archives

Blogroll