Generics / templates

Java has generics and C++ has templates. These language features are only half of a functor, since they only act on types, not functions. In JavaScript we can do better.

// Stack interface
var stackOf = function (t, u) {
  u = u || t;
  func(t); func(u);
  return makeInterface({
    push: hom(t, id),
    // pop returns either [0, []] or [1, value]
    pop: hom([], makeCoproduct([terminal, u])), 
    size: hom([], nat32)
  });
};

// Stack implementation
var makeStack = function (t, u) {
  var state = [];
  return stackOf(t, u)({
    push: function (val) {
      state.push(val);
    },
    pop: function () {
      return state.length ?
          [1, state.pop()] :
          [0, []];
    },
    size: function () {
      return state.length;
    }
  };
};

// Create a stack of strings.
var myStack = makeStack(str);

This definition of stack is a little odd because it has the option of taking two contracts instead of just one. A functor like arrOf is both a contract and the map function. If we think of stackOf as a kind of map, then what does it do?

In arrOf, the contract or function gets applied to each element of the array. In stackOf, one contract or function gets applied before pushing and the other gets applied after popping. Given an associative array obj and a stackOf(str) object myStack, we could write

var myLookupStack = stackOf(
    id, 
    function (s) { return obj[s]; })(myStack);

and get a stack object where you push strings but pop values of obj.

A stack homomorphism from an implementation stackOf(t)(x) to stackOf(u)(y) is a function f: t -> u such that stack(f, u)(y) gives the same result as stack(t, f)(x). This notion of a stack homomorphism hasn’t appeared in the literature (at least not under the name “stack homomorphism”) even though it’s very natural from a category theory perspective. I believe Java and C++ developers didn’t come up with it just because generics and templates deal only with types rather than both types and functions between them.

Functors again

We’ve seen several different functors:

arrOf: C -> C
makeProduct: C* -> C
makeInterface: C* -> C
hom: Cᵒᵖ × C -> C
makeCoproduct: C* -> C

• The functor arrOf takes a contract and produces one contract that accepts an empty list, or a 1-item list, or a 2-item list, and so on up to a (2³¹ – 1)-item list. It can also take an arbitrary function and iterate over an array.
• The functor makeProduct takes an array of contracts and produces one that accepts tuples of values whose individual entries pass the corresponding contracts. It can also take an array of functions to apply in parallel.
• The functor makeInterface is the same as makeProduct, but with string indices instead of numeric indices.
• The functor hom takes two contracts and produces one contract that accepts functions whose input passes the first contract and whose output passes the second. It can also take two functions and apply them serially, doing one function before and one after.
• The functor makeCoproduct takes an array of contracts and produces one that accepts values that pass one of the contracts. It can also take an array of functions and apply one of them depending on the tag.

In each case, the functor takes some contracts and produces a single new contract, and each one encapsulates some control structure of the language in the way you take apart the values that pass the new contract.

Lists

Products are what a Python programmer might call a tuple, a list of a fixed length. Let c be a contract; a list of c‘s of arbitrary length (well, up to length 2³¹ – 1) is the contract

arrOf(c) ≅ makeCoproduct([
  makeProduct([]),
  makeProduct([c]),
  makeProduct([c, c]),
  makeProduct([c, c, c]),
  ...,
  makeProduct([c, ..., c]) // (1 << 31) - 1 copies
]);

That is, it’s either an empty list, or a one-item list, or a two-item list, and so on up to a (2³¹ – 1)-item list. The length member of the array says which of these it is.

Coproducts

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

• The union of two sets is the smallest set that contains both of them.
• The maximum of two numbers is the smallest number that’s greater than or equal to both of them.
• The least common multiple of two numbers is the smallest number that’s a multiple of both them.
• The proposition “A or B” is the one with the least assumptions needed to prove either A or B.

We can get all these concepts by reversing all the arrows in the categorical product diagram for posets; recall that an arrow indicates that the source is less than or equal to the target:

\begin{tikzpicture}
\begin{scope}[scale = 3]
\node (A) at (0,0) {$A$};
\node (B) at (2,0) {$B$};
\node (X) at (1,0) {$X$}
edge [<-] (A)
edge [<-] (B);
\node (Y) at (1,-1) {$Y$}
edge [<-] (A)
edge [<-] (B)
edge [<-, dashed] (X);
\end{scope}
\end{tikzpicture}

Just as with the product, we can also generalize the coproduct from partial orders to categories and get useful structures.

\begin{tikzpicture}
\begin{scope}[scale = 3]
\node (A) at (0,0) {$A$};
\node (B) at (2,0) {$B$};
\node (X) at (1,0) {$X$}
edge [<-] node [above,l] {$p$} (A)
edge [<-] node [above,l] {$q$} (B);
\node (Y) at (1,-1) {$Y$}
edge [<-] node [below left,l] {$r$} (A)
edge [<-] node [below right,l] {$s$} (B)
edge [<-, dashed] node [right,l] {$!$} (X);
\end{scope}
\end{tikzpicture}

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

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

An element of A+B is either an element of A or an element of B. In JavaScript, variables have a type that’s a sum over every possible type: it can be an int or a string or a Date object or a function or whatever we want.

We can write a contract for the coproduct of n contracts, where the coproduct of 0 contracts is a contract for the empty set: no item passes the contract. The contract makeCoproduct([str, nat32]) will accept values of the form [0, s] where s is a string or [1, n] where n is a natural number.

var makeCoproduct = function (cs) {
  arrOf(func)(cs);
  return function (x) {
    makeProduct([nat32, id])(x);
    if (x[0] >= cs.length) {
      throw new TypeError('Expected a tag less than ' + cs.length);
    }
    return cs[x[0]](x[1]);
  };
};

					

makeProduct as a functor

When I defined makeProduct, we hadn’t talked about higher-order contracts yet, so it doesn’t work quite right around hom. To fix it, we return a new array whose elements are the results of the contracts given to makeProduct.

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

Written like this, it’s a variant of map where instead of applying the same function to all the members, it applies a list of functions to each respective member. As such, it’s also a functor: you can supply it with either contracts or functions between them.

This

JavaScript functions always get a reference to an object called this. If you just invoke a function f(), then this is bound to the global scope object in older browsers and to undefined in newer ones.

Method invocation is a special form in JavaScript: if you invoke a property of an object o.f(), then this is bound to the object o. If you don’t want this bound to o, then you have to break up that special form. You can either assign the function to a variable and invoke that:

var g = o.f;
g();

or you can make a reference to o be the result of a subexpression and then invoke the f property on that:

(1,o).f()

In the example of the person interface, the print function took a name and an age as explicit parameters. The OOP way of doing it, of course, would be to use this.name and this.age:

var person = makeInterface({
  name: str,
  age: nat32
});

var print = function () {
  person(this);
  return str(this.name) + ' is ' + 
      nat32(this.age) + ' year' +
      ((this.age === 1) ? '' : 's') + 
      ' old.';
};

var joe = person({
  name: 'Joe Brown',
  age: 35,
  print: print
});

joe.print();

This is a lot better, but we’d still like to be able to use hom to express typing decisions. Instead of trying to shoehorn this into hom, we can write a function for labeling functions that should be called as methods on an object satisfying the interface.

// Captures the hom contract instance
var method = function (homDecl) {
  // Returns a higher-order contract that
  // gets applied when the interface contract
  // is applied to the object
  return function (f) {
    // Binds to the interface contract
    var intr = this;
    var g = homDecl(f);
    // Returns a function that behaves like f
    return function (varArgs) {
      return g.apply(intr(this),
        toArray(arguments));
    };
  };
};

var person = makeInterface({
  print: method(hom([], str)),
  name: str,
  age: nat32
});

var joe = person({
  name: 'Joe Brown',
  age: 35,
  print: function () {
    return name + ' is ' +
        this.age + ' year' +
        ((this.age === 1) ? '' : 's') +
        ' old';
  }
});

Interfaces

JavaScript’s objects (in the OOP sense) are all associative arrays; the Array class just has a magical length property that updates when you assign to indices that satisfy the nat32 contract. From a category theory point of view, they’re also products. From a programmer’s point of view, though, they give a nice way of writing an interface.

var obj = function (o) {
  if (typeof o !== 'object' || o === null) {
    throw new TypeError(
        'Expected an object.');
  }
  return o;
}

var makeInterface = function (intr) {
  obj(intr);
  for (var i in intr) {
    func(intr[i]);
  }
  return function (x) {
    obj(x);
    var result = Object.create(
        Object.getPrototypeOf(x));
    for (var i in intr) {
      result[i] = intr[i](x[i]);
    }
    return result;
  };
};

var person = makeInterface({
  name: str,
  age: nat32,
  print: hom(makeProduct([str, nat32]), str)
});

var joe = person({
  name: 'Joe Brown',
  age: 35,
  print: function (name, age) {
    return name + ' is ' + age + 'year' +
        ((age === 1) ? '' : 's') + ' old';
  }
});

Functors

Here’s a contract that checks if the input is an array of natural numbers.

var arrOfNat32 = function (a) {
  arr(a);
  return a.map(nat32);
};

First it checks to see that a is an array; next it applies nat32 to each element of the array.

Here’s a higher-order contract that takes a contract c and returns a contract that checks if the input is an array of values passing c.

var arrOf = function (c) {
  func(c);
  return function (a) {
    arr(a);
    return a.map(c);
  };
};

Now we can write things like

var arrOfNat32 = arrOf(nat32);
var arrOfStr_to_str = arrOf(hom(str, str));

Note that the function arrOf is a currying of the map method; JavaScript defines Function.prototype.bind for currying, so we could also have written it as

var arrOf = hom([func], hom([arr], id))
    (Function.prototype.bind.bind([].map));

The function arrOf acts both on contracts and on the functions between them. For example, the function atoi has the type signature nat32 -> str, while arrOf(atoi) has the type signature arrOf(nat32) -> arrOf(str).

A functor F from a category C to a category D

• assigns to every object c in C an object F(c) in D
• assigns to every morphism m:c -> c' in C a morphism F(m):F(c) -> F(c') in D

such that composition and identities are preserved—that is,

• F(function (x) { return m(n(x)); })
= function (x) { return F(m)(F(n)(x)); }, and
• F(id_c) = id_Fc.

The function arrOf is a functor from the category of contracts and functions between them to itself. It maps each contract c to a new contract arrOf(c), and each function f:c -> c' to a new function arrOf(f):arrOf(c) -> arrOf(c').

Optimizing compilers use properties of functors like arrOf or map to make code faster. If a is an array, then

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

The right-hand version only iterates over the array once, saving a lot of time; this technique is called “map fusion”.