Category Theory in JavaScript

December 17, 2021

Löb with Promises

Javascript is an imperative, eager language with mutable data structures, so things like circularly linked lists are easy to create. What an eager language can’t do well is infinite data structures; instead one has to fake laziness using some other technique. The traditional one is to use closures: instead of manipulating values, you manipulate functions that take no parameters and return values. I wrote an article on that approach back in 2012.

There’s a fun connection between Löb’s theorem and type theory that results in a “spreadsheet functor“. Unfortunately, in Javascript that approach has the downside that following links creates new objects. You expect this for infinite data structures, but not for circular ones. It also has terrible performance, recomputing all the values a cell depends on for each cell. Surprisingly, these bugs can even crop up in Haskell; Haskell’s lazy, but you have to use it properly.

Promises are a different approach to deferring execution of code until later. Here’s an implementation of the spreadsheet functor that uses Promises and both gets allocation right as well as cacheing the results of computations so they can be reused later.

const r = Promise.resolve().bind(Promise);
const s = r();
const defer = s.then.bind(s);
const ploeb=(formulas) => {
  var results = formulas.map(
    (formula) => defer(() => formula(results))
  ); 
  return results;
}; 
const q=ploeb([
  (c) => r({val:0, next:c[1]}),
  (c) => r({val:1, next:c[0]})
]); 
let x = await q[0];
console.log(x.val); // 0
console.log(x.next === q[1]); // true
x = await x.next;
console.log(x.val); // 1
console.log(x.next === q[0]); // true
x = await x.next;
console.log(x.val); // 0
x = await x.next;
console.log(x.val); // 1

Posted in Uncategorized | Leave a Comment »

February 20, 2016

Categories in ES6

Preliminaries

Assuming contracts from jscategory sourcecode.

log = console.log.bind(console);
logtry = (f) => {
  try { log(f()) } catch (e) { log(e); }
};
undef = typeOf('undefined');
inheritsFrom = (clazz) => (c) => {
  func(c);
  instanceOf(clazz)(c.prototype);
  return c;
};

Functors

Functor = class Functor {
  constructor() {
    let t=new.target;
    if (t === Functor) {
      throw new TypeError('Abstract');
    }
    inheritsFrom(Category)(t.src);
    inheritsFrom(Category)(t.tgt);
    t.mapobj = hom(t.src.obj, t.tgt.obj)(t.mapobj);
    t.mapmor = hom(t.src.mor, t.tgt.mor)(t.mapmor);
  }
  static map(x) {
    try {
      return this.mapobj(x);
    } catch (_) {
      return this.mapmor(x);
    }
  }
};

IdFunc = (cat) => {
  let result = class Identity extends Functor {
    static get src() { return cat; }
    static get tgt() { return cat; }
    static mapobj(c) { return c; }
    static mapmor(f) { return f; }
  };
  new result();
  return result;
};
IdStrCat = IdFunc(StrCat);

// IdStrCat is the identity functor on StrCat.
// It acts on objects and morphisms of StrCat.
logtry(()=>IdStrCat.map()); // undefined
logtry(()=>IdStrCat.map('foo')); // foo

StrLen = class StrLen extends Functor {
  static get src() { return StrCat; }
  static get tgt() { return NatPlus; }
  static mapobj() { }
  static mapmor(s) { return s.length; }
};
new StrLen();
logtry(()=>StrLen.map()); // undefined
logtry(()=>StrLen.map('foo')); // 3

// Category of Categories and Functors
Cat = class Cat extends Category {
  static obj(c) { return inheritsFrom(Category)(c); }
  static mor(f) { return inheritsFrom(Functor)(f); }
  static src(f) { return f.src; }
  static tgt(f) { return f.tgt; }
  static id(c) { return IdFunc(c); }
  static com([g, f]) {
    let Composite = class Composite extends Functor {
      static get src() { return f.src; }
      static get tgt() { return g.tgt; }
      static mapobj(c) { return g.mapobj(f.mapobj(c)); }
      static mapmor(h) { return g.mapmor(f.mapmor(h)); }
    };
    new Composite();
    return Composite;
  }
};
new Cat();

logtry(()=>Cat.com([StrLen, IdStrCat]).map('foo')); // 3

ArrOf = class ArrOf extends Functor {
  static get src() { return Contract; }
  static get tgt() { return Contract; }
  static mapobj(c) { return arrOf(c); }
  static mapmor(f) { return arrOf(f); }
};
new ArrOf();
logtry(()=>ArrOf.map(int32)([1, 2, 3])); // [1, 2, 3]
logtry(()=>ArrOf.map(int32)(['a'])); // Expected a 32-bit integer
logtry(()=>ArrOf.map((x)=>x.length)(['hi', 'there'])); // [2, 5]

Natural Transformations

NatTrans = class NatTrans {
  constructor() {
    let t=new.target;
    if (t === NatTrans) {
      throw new TypeError('Abstract');
    }
    inheritsFrom(Functor)(t.src);
    inheritsFrom(Functor)(t.tgt);
    // nat trans between functors F, G: C -> D
    let F = t.src;
    let G = t.tgt;
    if (F.src !== G.src || F.tgt !== G.tgt) {
      throw new TypeError('Expected parallel functors');
    }
    // assigns to every object in C a morphism in D
    // such that square commutes.
    let C = F.src;
    let D = F.tgt;
    t.map = hom(C.obj, D.mor)(t.map);
  }
};

// Given categories C, D, returns the functor category hom(C,D)
Hom = hom(
    inheritsFrom(Category),
    inheritsFrom(Category),
    inheritsFrom(Category))((C, D) => {
  let result = class Hom extends Category {
    static obj(f) {
      inheritsFrom(Functor)(f);
      if (f.src !== C || f.tgt !== D) {
        throw new TypeError('Wrong functor source or target');
      }
      return f;
    }
    static mor(nt) {
      inheritsFrom(NatTrans)(nt);
      let F = nt.src;
      if (F.src !== C || F.tgt !== D) {
        throw new TypeError('Wrong functor source or target');
      }
      return nt;
    }
    static src(nt) { return nt.src; }
    static tgt(nt) { return nt.tgt; }
    static id(f) {
      let result = class IdNat extends NatTrans {
        static get src() { return f; }
        static get tgt() { return f; }
        static map(c) { return D.id(f.mapobj(c)); } 
      };
      new result();
      return result;
    }
    static com([g, f]) {
      let result = class Composite extends NatTrans {
        static get src() { return f.src; }
        static get tgt() { return g.tgt; }
        static map(c) { return D.com([g.map(c), f.map(c)]); }
      }
      new result();
      return result;
    }
  };
  new result();
  return result;
});

// Category of functors from StrCat to NatPlus
Str2Nat = Hom(StrCat, NatPlus);
// StrLen is an object in Str2Nat
logtry(()=>Str2Nat.obj(StrLen)); // StrLen
// IdStrCat goes from StrCat to itself, not to NatPlus
logtry(()=>Str2Nat.obj(IdStrCat)); // Wrong functor source or target
// Identity natural transformation on StrLen functor
IdStrLen = Str2Nat.id(StrLen);
// IdStrLen is a morphism in Str2Nat from StrLen to itself
logtry(()=>Str2Nat.mor(IdStrLen).src); // StrLen

// Category of endofunctors on Contract
End = Hom(Contract, Contract);
Flatten = class Flatten extends NatTrans {
  static get src() { return Cat.com([ArrOf, ArrOf]); }
  static get tgt() { return ArrOf; }
  // c gets used by type checker
  static map(c) {
    return hom(arrOf(arrOf(c)), arrOf(c))(
      (aax) => aax.reduce((prev, cur)=>prev.concat(cur)));
  }
};
new Flatten();
logtry(()=>End.obj(ArrOf)); // ArrOf
logtry(()=>End.obj(Cat.com([ArrOf, ArrOf]))); // Composite
logtry(()=>End.mor(Flatten)); // Flatten
logtry(()=>Flatten.map(int32)([[1,2],[],[3,4,5]])); // [1,2,3,4,5]

Posted in Uncategorized | Leave a Comment »

February 17, 2016

Promise monad in ES6

ES6 is introducing classes to JavaScript. You can turn on the new features in Chrome by enabling chrome://flags/#enable-javascript-harmony or in v8 with v8 –harmony.

Functor = class Functor {
  constructor() {
    if (new.target === Functor) {
      throw new TypeError(
          'Cannot construct Functor instances directly');
    }
    if (typeof(this.map) !== 'function' ||
        typeof(new.target.map) !== 'function') {
      throw new TypeError('Must provide static and member map.')
    }
  }
};

// Base monad class
Monad = class Monad extends Functor {
  constructor() {
    super();
    if (new.target === Monad) {
      throw new TypeError(
          'Cannot construct Monad instances directly');
    }
    if (typeof(this.lift) !== 'function' ||
        typeof(new.target.lift) !== 'function') {
      throw new TypeError('Must provide static and member lift.')
    }
    if (typeof(this.flatten) !== 'function' ||
        typeof(new.target.flatten) !== 'function') {
      throw new TypeError('Must provide static and member flatten.')
    }
  }
  flatMap(f) {
    return this.map(f).flatten();
  }
  static flatMap(f) {
    return (mx) => mx.flatMap(f);
  }
};

// Promise monad
P = class P extends Monad {
  // Constructor expects a promise to wrap.
  constructor(p) {
    super();
    if (p && typeof(p.then) === 'function') {
      this.p = p;
    } else {
      throw new TypeError(
        'Expected an object with a "then" method.');
    }
  }
  static map(f) {
    return (px) => px.map(f);
  }
  map(f) {
    return new P(this.p.then(f));
  }
  static lift(v) {
    return new this(new Promise((resolve) => resolve(v)));
  }
  lift() { return this.constructor.lift(this); }
  static flatten(ppv) {
    return new this(new Promise((resolve) => {
      return ppv.map((pv) => pv.map(resolve))
    }));
  }
  flatten() { return this.constructor.flatten(this); }
};

// XHR + Promise
XHRP = (url) => new P(new Promise((resolve) => {
  var xhr = new XMLHttpRequest();
  xhr.onreadystatechange = () => {
    if (xhr.readyState == XMLHttpRequest.DONE) {
      if (xhr.status == 200) {
        resolve(xhr.responseText);
      }
    }
  };
  xhr.open('GET', url, true);
  xhr.send();
}));

// Search Google for your ip address
XHRP('http://jsonip.com').flatMap((json) =>
  XHRP('http://google.com/search?' + JSON.parse(json).ip).map((results) =>
    console.log(results)));

// New experimental GlobalFetch already returns promise
if (GlobalFetch) {
  GFP = (url) => new P(GlobalFetch.fetch(url));

  // Search Google for your ip address
  GFP('http://jsonip.com').flatMap((json) =>
    GFP('http://google.com/search?' + JSON.parse(json).ip).map((results) =>
      console.log(results)));
}

// setTimeout + Promise
DelayP = (value, delay) => new P(new Promise((resolve) =>
    setTimeout(() => resolve(value), delay)));

DelayP(1, 1000).flatMap((v) =>
  // Runs at t=1 sec, v = 1
  DelayP(2+v, 2000).flatMap((w) =>
    // Runs at t=3 sec, w = 3
    DelayP(3+v+w, 3000).map((x) =>
      // Runs at t=6 sec, x = 7
      // Logs 15
      console.log(4+v+w+x))));

DelayP(1, 1000)
    // Runs at t=1 sec, v=1
    .map((v) => 2+v)
    // Runs at t=1 sec, w=3
    .map((w) => 3+w)
    // Runs at t=1 sec, x=6
    // Logs 10
    .map((x) => console.log(4+x));

Posted in Uncategorized | Leave a Comment »

May 6, 2013

YouTube series

I’m going through all this stuff in videos on YouTube now. Nine have been uploaded; more to come.

Posted in Uncategorized | Leave a Comment »

March 20, 2013

For-comprehensions in JavaScript

I’m starting to learn Scala, and I love their for-comprehension style of monadic programming. Here’s a small library that uses eval and textual manipulations to do desugaring.

// A Monad class for Array and other monads to inherit from

function Monad() {
  throw "abstract";
}

Monad.prototype.flatMap = function (f) {
  return this.map(f).flatten();
};

// Make Array inherit from Monad
Array.prototype.__proto__ = Monad.prototype;

// Define the monadic multiplication
Array.prototype.flatten = function () {
  var result = [];
  var len = this.length;
  for (var i = 0; i < len; ++i) {
    result = result.concat(this[i]);
  }
  return result;
};

// The comprehension class
var M = function () {
  var pairs = [];
  this.for = function (v, e) {
    pairs.push({e: e, v: v});
    return this;
  };
  this.yield = function (body) {
    var desugared = pairs.map(function (pair, index) {
          return '(' + pair.e + ').' +
              ((index === pairs.length-1) ? 'm' : 'flatM') +
              'ap(function(' + pair.v + ') { return ';
        }).join('') + '(' + body + ');'
        + pairs.map(function () { return ' });' }).join('');
    pairs = [];
    return desugared;
  };
};

// Avoid the need to say (new M) at the start
M.for = function (v, e) {
  return (new M).for(v, e);
};

// Tensor product of lists
// eval(M.for('x','[1,2,3]').for('y','[5,6,7]').yield('x * y'));
// 5,6,7,10,12,14,15,18,21

// Aka Maybe
function Option() {
  throw "abstract";
}
Option.prototype = Object.create(Monad.prototype);
Option.prototype.map = function (f) {
  if (this instanceof None) { return this; }
  return new Some(f(this.value));
};
Option.prototype.flatten = function () {
  if (this instanceof None) { return this; }
  return this.value;
};
function None() {}
None.prototype = Object.create(Option.prototype);
None.prototype.toString = function () { return 'None'; };
function Some(v) {
  this.value = v;
}
Some.prototype = Object.create(Option.prototype);
Some.prototype.toString = function () {
  return 'Some(' + this.value + ')';
};

// var xs = [1,2,3];
// eval(M.for('x','xs').for('y','x % 2 ? new Some(x) : new None()').yield('x * y'));
// [Some(1), None, Some(9)]

The call to eval on the outside is necessary to capture the scope in which the for-comprehension occurs (e.g. the scope in which xs occurs in the second example).

Posted in Uncategorized | 2 Comments »

August 27, 2012

New contract library

I updated the source code page in preparation for a talk on this stuff I might be giving soon.

Posted in Uncategorized | Leave a Comment »

May 22, 2012

Opposite categories and profunctors

From any category $C$ you can form the opposite category $C^{\mbox{op}}$ , which has the same objects but you turn all the arrows around backwards. This makes sense if you think of a category as being presented as a (directed multi)graph plus a set of relations between paths: you just turn all the edges around and reverse the order of the edges in the relations.

However, if we’re thinking of a category like Set, we just “formally reverse” the arrows: we define a morphism from A to B in Set^op to be a function from B to A and define the composition of a morphism $f:A \to B$ and a morphism $g:B \to C$ to be the reversed composition of the functions (that is, in the only way that makes any sense: given an element c of C, return $f(g(c))$ ).

The point of using the opposite category is so that composition happens in the opposite order: if we want to wrap a function f in contracts, then the input contract should be applied before f and the output contract should be applied after f.

A profunctor is a functor of the form $P:C^{\mbox{op}} \times D \to \mbox{Set}.$ We’re already familiar with the profunctor

hom:Set^op × Set -> Set

that takes a pair of functions $(in, out)$ and produces a function that maps $f$ to $out\circ f\circ in$ . We can think of any profunctor as being the hom functor for some category.

This profunctor produces a contract for a pair of functions with the given input and output contracts:

var pair = function (aIn, bIn, aOut, bOut) {
  return makeProduct([hom(aIn, aOut), hom(bIn, bOut)]);
};

It’s the hom functor for Contract², the category of pairs of contracts and pairs of functions between them.

Here’s the hom functor for the free category on the complete graph with 26 nodes and self-loops. Objects are letters a-z; morphisms are strings beginning with the source node and ending with the target node. Composition is “overlapping” concatenation: we can only concatenate two strings where the last letter of the first string matches the first letter of the second string, and we “overlap” the matching letters so it only appears once: ‘cap’ + ‘ped’ = ‘caped’, not ‘capped’. The identity morphism on a letter is just the letter itself: ‘c’ + ‘c’ === ‘c’.

var overlap = function (strIn, strOut) {
  str(strIn); str(strOut);
  return function (s) {
    str(s);
    if (s.length >= 1 &&
        s[0] === strIn[strIn.length-1] &&
        s[s.length-1] === strOut[0]) {
      return strIn.slice(0, strIn.length-1) + s + strOut.slice(1);
    }
    throw new TypeError('Wrong shape string.');
  };
};

var tr = overlap('t', 'r');
tr('tubular') === 'tubular'; // passes the tr contract
tr('joe'); // throws a type error

var catran = typedConcat('cat', 'ran');
catran('tubular') === 'catubularan';
catMan('tamar') === 'catamaran';

The hom profunctor captures everything there is to know about a category; in Haskell, the interface Category is really for a hom profunctor.

Posted in Uncategorized | Leave a Comment »

May 20, 2012

Laziness

JavaScript is an eager language—that is, it evaluates the parameters to a function before evaluating the function itself. A lazy value in JavaScript is a function with no inputs that returns the result of some expression. The function effectively prevents the expression from being evaluated until it’s needed. There’s a functor that takes any contract and returns the lazy form of that contract:

var lazyOf = function (x) {
  return hom([], x);
};

This functor can be made into a monad; if you have a doubly-lazy value, you can just evaluate it to get a singly-lazy value. The unit wraps a value inside of a function to produce the lazy value.

var lazy = monadOf(lazyOf)({
  '*': function (veryLazy) {
    return veryLazy();
  },
  '1': function (x) {
    return function () {
      return x;
    };
  }
});

Here’s a list with a lazy tail:

var next = function (n) {
  return [n, lazy(int32)[1](next(n+1))];
};
var naturals = next(0);

Posted in Uncategorized | Leave a Comment »

May 16, 2012

Adjoint functors

The functor arrOf takes a contract for a set of elements and produces a contract for the set of lists of those elements. Concatenation of lists makes them into a monoid. Let Mon be the category of monoids and monoid homomorphisms; then we can say that arrOf is a functor from Set to Mon.

There’s another functor from Mon to Set that simply forgets the monoidal structure: it takes an element of a monoid and produces an opaque wrapper with one method, unwrap. Let’s call it setOf.

The contract setOf(arrOf(x)): Set -> Set is for a wrapped array of x‘s. Given any element xVal, we can produce a value wrap([xVal]) that passes setOf(arrOf(x)).

The contract arrOf(setOf(m)): Mon -> Mon is for lists of wrapped elements of a monoid. Given any list like

[wrap(mVal1), wrap(mVal2), wrap(mVal3)]

passing this contract, we can get a monoid element passing m by unwrapping each element and multiplying them all together.

The categories Set and Mon are not equivalent: setOf ○ arrOf is not isomorphic to the identity since there’s no way to take an element like wrap([xVal1, xVal2, xVal]) that passes setOf(arrOf(x)) and produce an element passing the contract x that doesn’t depend on x.

However, setOf and arrOf are related in a special way: with a little thought, it’s easy to see that the set of monoid homomorphisms from arrOf(x) to y is isomorphic to the set of functions passing hom(x, setOf(y)): a monoid homomorphism from arrOf(x) is completely specified by saying what it does to each of the values that pass x: you just map that function over the list and then multiply the results together.

Two functors $L:C \to D$ and $R:D \to C$ are adjoint functors if for all objects c in C and d in D,

$\hom_D(L(c), d) \cong \hom_C(c, R(d)).$

In the example above, $C = \mbox{Set},$ $\hom_C(c, c')$ is the set of functions from the set c to the set c’, $D = \mbox{Mon},$ and $\hom_D(d,d')$ is the set of monoid homomorphisms from the monoid d to the monoid d’.

Other examples of adjoint functors include

$\hom_{\mbox{PSet}}(L(c), d) \cong \hom_{\mbox{Set}}(c, R(d)).$ PSet is the category of “pointed sets”—i.e. sets with a special chosen element called the “point”—and functions between them that map the point of the domain to the point of the codomain. Here, $L(c)$ is the set c plus an extra point, while $R(d)$ forgets which element of d was the special one.
$\hom_{\mathbb{N}}(2m, n) \cong \hom_{\mathbb{N}}(m, \lfloor\frac{n}{2}\rfloor),$ where $\mathbb{N}$ is the category whose objects are natural numbers and there’s a morphism from $m$ to $n$ if $m\le n.$ Here, the floor function forgets the fractional part of $\frac{n}{2}.$
$\hom_{n+1}(\int_0^x f(y) dy, g(x)) \cong \hom_{n}(f(x), \frac{d}{dx} g(x)),$ where $n$ is the category of polynomials of degree $n$ and there’s a morphism from f to f’ if f is bounded above by f’. Here, the derivative operator forgets the constant term.
In general, any “forgetful” functor R that forgets some structure has a left adjoint L, the “free” structure of that kind.
$\hom_{\mbox{Set}}(c+c', d) \cong \hom_{\mbox{Set}^2}((c,c'), \Delta d),$ where Set² is the category of pairs of sets and pairs of functions between them, and $\Delta d = (d, d).$ This is a categorification of the fact that in real numbers, $d^{c+c'} = d^c d^{c'}.$
$\hom_{\mbox{Set}^2}(\Delta c, (d, d')) \cong \hom_{\mbox{Set}}(c, d \times d').$ This is a categorification of the fact that in real numbers, $(dd')^c = d^c d'^c.$
$\hom_{\mbox{Set}}(c \times c', d) \cong \hom_{\mbox{Set}}(c, \hom_{\mbox{Set}}(c', d)).$ This is a categorification of the fact that in real numbers, $d^{cc'} = (d^c)^{c'}.$
$\hom_{\mbox{Sub}}(c \cup c', d) \cong \hom_{\mbox{Sub}^2}((c,c'), \Delta d),$ where Sub is the category of sets and inclusions (i.e. there’s a morphism $c\to c'$ if $c \subseteq c'.$ )
$\hom_{\mbox{Sub}^2}(\Delta c, (d, d')) \cong \hom_{\mbox{Sub}}(c, d \cap d').$
$\hom_{\mbox{Bool}}(\exists x \in c \mbox{ such that } x \in s, d) \cong \hom_{\mathcal{P}s}(c, K(d)).$ Here Bool is the category with two objects F and T and an arrow from F to T—that is, there’s an arrow from one object to another if the one implies the other. $\mathcal{P}s$ is the set of subsets of $s,$ and $K(d)$ maps F to the empty set and T to $s.$
$\hom_{\mathcal{P}s}(K(c), d) \cong \hom_{\mbox{Bool}}(c, \forall x \in d. x \in s).$

Adjoint functors turn up all over the place.

Posted in Uncategorized | Leave a Comment »

May 15, 2012

n-Categories

We have

-1: a boolean T,
0: a set {T, F} of booleans,
1: a category Set of sets and functions,
2: a 2-category Cat of categories, functors, and natural transformations,
…
n: an (n+1)-category nCat of n-categories, functors, transformations, modifications, …, and n-cells.

In this hierarchy, a “0-category” is a set, a “(-1)-category” is a boolean, and the only “(-2)-category” is T. When we compare things in an n-category, we get this pattern:

0: two booleans are either equal or not,
1: two sets may be isomorphic without being equal,
2: two categories may be equivalent without being isomorphic,
…
n: two n-categories may be n-equivalent without being (n-1)-equivalent.

In particular,

1: two sets $X$ and $Y$ are isomorphic $(X \cong Y)$ if there are functions $f:X \to Y$ and $g:Y \to X$ such that
$g \circ f = id_X$ , and $f \circ g = id_Y$ .
2: two categories X and Y are equivalent $(X \simeq Y)$ if there are functors $f:X \to Y$ and $g:Y \to X$ such that
$g \circ f \cong id_X$ , and $f \circ g \cong id_Y$ .
…
n: two n-categories X and Y are n-equivalent $(X \simeq_n Y)$ if there are functors $f:X \to Y$ and $g:Y \to X$ such that
$g \circ f \simeq_{n-1} id_X$ , and $f \circ g \simeq_{n-1} id_Y$ .

To be really pedantic, we could also have said

0: two booleans $X$ and $Y$ are equal $(X = Y)$ if there are equations $f:X = Y$ and $g:Y = X$ such that
$g \circ f = id_X$ , and $f \circ g = id_Y$ ,

where $id_X$ is the equation $X = X$ and similarly for $Y.$

Posted in Uncategorized | Leave a Comment »

May 11, 2012

Natural transformations

We’ve seen stack homomorphisms and monoid homomorphisms. These are homomorphisms between implementations of an interface.

There’s also a general notion of a homomorphism between two arbitrary functors, which is a variant of the hom functor.

var natural = function (f, g) {
  func(f); func(g);
  return function (x, y) {
    y = y || x;
    func(x); func(y);
    return hom([f(x)], g(y));
  };
};

Just as we used hom when defining the interface of a monoid, we can use natural when defining the interface of a monad:

var compose = function (f, g) {
  func(f); func(g);
  return function(x) {
    return f(g(x));
  };
};

var monadOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return function (intr) {
    return function (t) {
      return makeInterface({
        '*': natural(compose(m, m), n)(t),
        1: natural(id, n)(t)
      })(intr);
    };
  };
};

Given categories $C$ and $D$ and functors $F:C \to D$ and $G:C \to D$ , a natural transformation $n: F \Rightarrow G$ assigns to every object $c$ of $C$ a morphism $n(c):F(c) \to G(c)$ such that for every morphism $m:c_1 \to c_2$ in C,

$n(c_2) \circ F(m) = G(m) \circ n(c_1).$

The flatten function is a natural transformation from compose(arrOf, arrOf) to arrOf. It takes a doubly-nested array to a singly-nested array, no matter what the type of the elements in the array. Also, it doesn’t matter if you first map a function over the list of lists and then flatten:

flatten(int)(arrOf(arrOf(function (x) { return x+1; }))([[1, 2], [3]]))

or if you flatten first and then map:

arrOf(function (x) { return x+1; }))(flatten(int)([[1, 2], [3]]).

Posted in Uncategorized | Leave a Comment »

May 2, 2012

Monads and parsing

A parser takes a string and produces a list of tokens and the remaining string, so we want a function p:str -> makeProduct([arr, str]).

To get the target type, let’s use a functor. The addState functor takes any contract x and turns it into the pair contract [arr, x], so it expects a tuple containing an array and a value satisfying x.

var addState = function (x) {
  return makeProduct([arr, x]);
};

To chain parsers together, we want to apply the next parser to the second element of the result of the last one, then concatenate the list of tokens. A monad will help with this process.

If we iterate the addState functor twice on the contract x, the resulting contract accepts objects of the form [a1, [a2, xVal]] where a1 and a2 are arrays and xVal satisfies x. The state monad’s multiplication concatenates the two arrays a1 and a2, while its unit provides the empty array for the first parser in the chain.

var state = monadOf(addState)({
  // Input is of the form [a1, [a2, xVal]]
  // where a1, a2 are arrays.
  '*': function (doubleState) {
    var a1 = doubleState[0];
    var a2 = doubleState[1][0];
    var xVal = doubleState[1][1];

    return [a1.concat(a2), xVal];
  },
  1: function (xVal) {
    return [[], xVal];
  }
})(str);

var Parser = function () {
  this.run = state[1];
};

The register method is where it all comes together: since addState is a functor, we can use it to apply a function to the second element of a tuple, and then the multiplication in the monad concatenates the two lists.

Parser.register = function (name, makeParser) {
  Parser.prototype[name] = function (varArgs) {
    var run = this.run;
    this.run = function (s) {
      return state['*'](
          addState( makeParser.apply({}, toArray(arguments)) )
          (run(s)));
    };
    return this;
  };
};

// Given a character, produce a parser
var char = function (c) {
  return hom([str], addState(str))(function (s) {
    if (s[0] !== c) {
      throw new Error('Expected the character "' + c + '"');
    }
    return [[c], s.substr(1)];
  });
};

Parser.register(char);

new Parser()
    .char('a').char('b').char('c')
    .run('abcde');
// === [["a", "b", "c"], "de"]

Posted in Uncategorized | Leave a Comment »

May 1, 2012

Monoids and monads

Here’s our definition of a monoid, slightly modified so you have to invoke the property 1 to get the identity element:

var monoidOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return makeInterface({
    '*': hom([m, m], n),
    1: hom([], n)
  });
};

Here’s a slight variant of this definition of a monoid:

var monadOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return function (intr) {
    return function (t) {
      return makeInterface({
        '*': hom([m(m(t))], n(t)),
        1: hom([t], n(t))
      })(intr);
    };
  };
};

Instead of the multiplication expecting a pair of functions, it expects the composite of functions. Here’s one way it’s used:

var flatten = monadOf(arrOf)({
  '*': function (arrayOfArrays) {
    var flattened = [], len = arrayOfArrays.length;
    for (var i = 0; i < len; ++i) {
      var innerLen = arrayOfArrays[i].length;
      for (var j = 0; j < innerLen; ++j) {
        flattened.push(arrayOfArrays[i][j]);
      }
    }
    return flattened;
  },
  1: function (x) { return [x]; }
});

var stringFlatten = flatten(str);

The stringFlatten example’s multiplication expects a doubly nested array of strings and returns an array of strings. It’s associative, in the sense that if you have a triply-nested array, it doesn’t matter if you flatten the inner or outer layer first. It’s unital in the sense that if you wrap a list in brackets and then flatten it, you get the same thing back; similarly if you wrap each element in brackets and flatten it, you also get the same thing back.

In a monoid, the multiplication wants two things and returns one; in a monad, the multiplication wants a functor applied twice to t and returns the functor applied once to t. In a monoid, the unit wants no elements and returns one; in a monad, the unit wants a functor applied no times to t and returns the functor applied once to t.

Monads are an exceptionally versatile design pattern. There are monads for lists, exceptions, simulating imperative programming on top of functional programming but still keeping the state explicit so you can mock out the state for easy testing, continuation passing style, parsing, promises (aka futures), event chaining, and more. jQuery, for example, is the combination of several of these monads.

Posted in Uncategorized | Leave a Comment »

May 1, 2012

Monoids, trees and tests

Here’s a simple data type and some implementations:

// Times should be associative and
// 1 should behave as the identity
var monoidOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return makeInterface({
    '*': hom([m, m], n),
    1: n
  });
};

var bool = function (b) {
  if (b !== 0 && b !== 1) {
    throw new TypeError('Expected 0 or 1');
  }
  return b;
}

var and = monoidOf(bool)({
  '*': function (b1, b2) { return b1 & b2; },
  1: 1
});

var xor = monoidOf(bool)({
  '*': function (b1, b2) { return b1 ^ b2; },
  1: 0
});

var or = monoidOf(bool)({
  '*': function (b1, b2) { return b1 | b2; },
  1: 0
});

var int32Add = monoidOf(int32)({
  '*': function (n1, n2) { return (n1 + n2) | 0; },
  1: 0
});

var strConcat = monoidOf(str)({
  '*': function (n1, n2) { return n1 + n2; },
  1: ''
});

Here’s a datatype for an unlabeled binary tree:

var treeOf = function (treeIn, treeOut) {
  treeOut = treeOut || treeIn;
  func(treeIn); func(treeOut);
  return makeInterface({
    node: hom([treeIn, treeIn], treeOut),
    leaf: treeOut
  });
};

var makeTree = treeOf(obj)({
  node: function (left, right) {
    return {left: left, right: right};
  },
  leaf: {}
});

The interfaces are the same except for the names of the methods. The difference is that we expect the multiplication in the monoid to be associative and unital, while there are no restrictions on node. The ability to enforce relations among functions is what makes this category theory instead of graph theory: categories can be presented as (directed multi-)graphs plus relations on paths.

The problem of deciding whether the multiplication is associative is undecidable: it’s as hard as the halting problem. Some research programming languages require you to provide a proof along with your code, but that’s still impractical for daily use. Instead, we rely on tests and hope that we got all the corner cases. If we provide a function to produce random elements of a type, we can use fuzzing.

var testMonoidOf = function (t) {
  func(t);
  return {
    testAssoc: hom([monoidOf(t), hom([], t), nat32])(
      function (m, rand, n) {
        var i;
        for (i = 0; i < n; ++i) {
          var a = rand();
          var b = rand();
          var c = rand();
          if (m['*'](a, m['*'](b, c)) !== m['*'](m['*'](a, b), c)) {
             throw new TypeError('Expected multiplication to be associative: ' + [a, b, c]);
          }
        }
      }),
    testUnit: hom([monoidOf(t), hom([], t), nat32])(
      function (m, rand, n) {
        var i;
        for (i = 0; i < n; ++i) {
          var a = rand();
          if (m['*'](a, m[1]) !== a || m['*'](m[1], a) !== a) {
            throw new TypeError('Expected m[1] to be the identity: ' + a);
          }
        }
      })
  };
};

var xorTest = testMonoidOf(bool);
var randBool = function () { return Math.floor(Math.random() * 2); };
xorTest.testAssoc(xor, randBool, 10);
xorTest.testUnit(xor, randBool, 10);

Now consider the function mod2 and the two parity objects below:

var mod2 = hom([int32], bool)(function (x) {
  return x % 2;
});

var parity1 = monoidOf(mod2, bool)(xor);
var parity2 = monoidOf(int32, mod2)(int32Add);

The times operation in both parity objects takes a pair of int32s and returns a bool. In parity1, mod2 is applied to the inputs and the results are xored together. In parity2, the numbers are added and then mod2 is applied. The end result is the same either way.

A monoid homomorphism from an implementation monoidOf(m)(x) to an implementation monoidOf(n)(y) is a function f: m -> n such that monoidOf(f, n)(y) is observably the same as monoidOf(m, f)(x).

Posted in Uncategorized | Leave a Comment »

April 30, 2012

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.

Posted in Uncategorized | 6 Comments »

April 30, 2012

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.

Posted in Uncategorized | Leave a Comment »

April 30, 2012

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.

Posted in Uncategorized | Leave a Comment »

April 30, 2012

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{array}{rcccl}& & Y & & \\ & \nearrow & \uparrow & \nwarrow {\scriptstyle s} \\ A & \to & X & \leftarrow & B \end{array}$

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

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

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]);
  };
};

Posted in Uncategorized | 2 Comments »

April 11, 2012

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.

Posted in Uncategorized | Leave a Comment »

April 5, 2012

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';
  }
});

Posted in Uncategorized | Leave a Comment »

April 3, 2012

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';
  }
});

Posted in Uncategorized | Leave a Comment »

April 2, 2012

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”.

Posted in Uncategorized | Leave a Comment »

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 »

Recent Posts

Archives

Meta

Preliminaries

Categories

Functors

Natural Transformations

Tags

Calendar

Archives

Blogroll