Continuation Monad

Last month I worked on a TopCoder problem that led me to continue my exploration of monads. The problem is to sort a set of elements using comparisons whose cost is a function of the comparands. Solutions comprise a pair of methods, one of which initializes the program with the costs, and the other of which is invoked repeatedly to effect the dialog between the program and the less-than oracle.

Now choose your own adventure. Do you:

1. Ask how a real computer scientist would solve it
2. Watch me muddle through comparison-based sorting with variable costs
3. Follow my continuation monad implementation in Java

Comparison-based sorting with variable costs

Sidebar: true story

I've seen a related problem in real life. Our app iDeal helped salespersons develop contract terms subject to Boolean constraints called guidelines, analogous to the Boolean trees examined in Charikar et al. We didn't actually have to buy our guideline results, but we did care about evaluation speed. There were basically two prices: low (computable on our local app server) and high (computable at a minicomputer reached by at least two SOAP hops and a batch job. Unlike the Charikar model, our cost function was not additive: it behaved like or, giving a result of "expensive" whenever at least one guideline couldn't be computed locally and "cheap" otherwise. Consequently, the real-life challenge was less about algorithm design and more about software engineering: given that guideline evaluation is demanded at many call sites, how can we avoid unnecessarily consulting the minicomputer?

I first thought of divide and conquer approaches to avoid redundant queries (don't ask a < c if it is already known that a < b and b < c). I thought about algorithms for the special case when C(a, b) = 1: mergesort, heapsort, and quicksort. All of these relate to binary trees, and I thought about properties a binary search tree constructed at optimal cost would have in the general case.

Shouldn't the root of the tree be the element for which the sum over pairs of itself with each of its descendants is minimal? Intuitively, we compare every element with the root to locate the element in the tree, and we want to minimize the cost of inserting each element by this recursive process. Not quite: this fails to account for tree shape (consider p < q < r with costs C(p, X) = 1 for all X in {p, q, r}; C(q, r) = 2). And thinking back to the special case of a constant cost function, it's clear that this root selection heuristic has no power. It's also often mentioned in discussions of e.g., quicksort, that it's important to have a balanced tree. But we're not looking just to balance and fill the tree; It's easy to ensure that every left child in an optimal tree is a leaf node by carefully choosing the cost function.

The shape of the tree is determined both by the sequence of queries the program makes and by the order of elements determined by the oracle. The best choice for the root is the median of the elements, so an exact solution is O(n^2) but we could think about approximate selection and average-case performance.

What about a bottom-up approach? Do our trees have optimal substructure? First: in an optimal tree, is every subtree optimal? Suppose not. Then some optimal tree has a subtree that can be rearranged for lower cost. But this doesn't affect the cost to construct the rest of the tree, so after the rearrangement the overall cost is lowered. This contradicts the supposition that our original tree was optimal with a suboptimal subtree. But second: can we efficiently combine optimal subsolutions to derive optimal solutions?

A straightforward mergesort would guarantee a minimal number of comparisons, but not necessarily a minimal-cost set of comparisons. Although a minimal tree implies minimal subtrees, not all combinations of minimal subtrees constitute a (rearrangement of a) minimal tree. To see this, imagine a cost function that does not have the triangle property. In this case, the cheapest way to combine two trees might involve using additional vertices not a part of either original tree.

Let g(t) = sum(C(n, n') for n in t for n' in ~t). Recursively merge the runs with the lowest g.

Pf. g-ordered mergesort yields optimal solutions.

Let A and B represent two C-optimal subsolutions whose g-costs are least among all subsolutions. Claim: the combination S of A and B is C-optimal. Suppose not. Then there is a (sub)solution S' containing all the elements of a and b such that C(S) > C(S'). S' is a proper superset of S, so we can obtain it by adding elements from the complement of S. These missing elements must exist in other optimal subsolutions having higher g-costs than that of S. Also, each of these elements must have edges to each of a and b in the optimal tree of S. Consider any subsolution G hosting one of these missing elements. It's g-cost is \sum_{g \in G}(\sum_{a \in A}(C(g, a)) + \sum_{b \in B}(C(g, b)) + \sum_{c' \in c}(C(g, c'))), where a, b, and c' are drawn from our input sets and the complement of their union respectively. To simplify the notation, I'm going to switch now to using implicit summations: the g-cost of subsolution G is C(g, a) + C(g, b) + C(g, c). The g-cost of S is c(a, c) + c(b, c) + c(s, c). The g-cost of a is c(a, b) + c(a, c). The g-cost of b is c(a, b) + c(b, c). A little algebra and the observation that the complement of the union of a and b includes all the g \in G, we can derive a contradiction from the assumption that there exist elements outside the min-g-cost subsolutions a and b that would improve the C-cost of the combination of a and b:

c(s a) + c(s b) + c(s c) > max(c(a c) + c(a b); c(b c) + c(a b))
> max(c(S) - c(s, c) - c(b, c) + c(a, b);
c(S) - c(s, c) - c(a, c) + c(a, b))
c(s a) + c(s b) + 2c(s c) - c(a b) - c(S) > max(- c(b, c); - c(a c))
- c(s c) - c(a c) - c(b c)
c(s a) + c(s b) + c(s c) - c(a b) - c(a c) - c(b c) > -max(c(b c); c(a c))
c(s a) + c(s b) + c(s c) - c(a b) - c(a c) > 0
c(s a) + c(s b) + c(s c) - c(a b) - c(b c) > 0
c(s a) + c(s b) + c(s c) > c(a b) + c(a c)
c(s a) + c(s b) + c(s c) > c(a b) + c(b c)
c(a c) includes c(a s) so c(a c) > c(a s)
c(s b) + c(s c) > c(a b)
c(s a) + c(s c) > c(a b)
c(s b) - c(s a) > 0
c(s a) - c(s b) > 0
⟶⟵

Sadly, although this heuristic won't mislead us, it may often fail to answer by telling us that more than two trees have the least g-cost.

A more dynamic heuristic could rely on probabilistic estimates of the information gain at each query. Assuming uniform random permutation, initially we should just do the cheapest comparison. As we progress, we'll develop equivalence classes: these elements could be anywhere; those elements could only be in the top 6. Comparisons involving elements in large classes or classes near the min or max yield relatively little information. We could combine estimates of value with the given cost information to get reasonable average-case performance.

I decided not to work harder to prove a tight lower bound on the solution to the problem or to find a better algorithm or heuristic. It's TopCoder after all, and speed is important. I decided instead to move on to implementation and Google for a better answer later.

So in a nutshell my solution is: initially regard every element as a subsolution. Order them by g-cost and merge the two lowest-ranked solutions. Recurse.

Continuation monad

The online interactions between the TopCoder oracle and my solution raises an interesting question. The first thing that occurred to me of course was to write g and merge, arrange to store state in instance variables, and update my instance state incrementally in the two callback functions whose existence is mandated by the oracle. On second thought, I wondered if my code could more closely resemble the nutshell description I gave above, with the state maintenance handled separately. It seemed like a good excuse to get some first-hand experience with continuation-passing style, a canonical form for programs that can be paused and restarted. The continuation monad brings cps into a more general framework, improving modularity.

So I broke out my old favorites Monads for Functional Programming and Comprehending Monads. I also found a couple of new sources: Lecture notes: Continuations and call/cc and The Continuation Monad in Clojure. Continuations are also discussed at some length in the lambda papers, although the idea originated a decade earlier.

First, the monad preliminaries. When I implemented the maybe monad in C#, I had the ambition to support composition of different monads and that led to some difficulty with the type system. Also, I noticed how cumbersome the syntax was and what effect that had on my enthusiasm for explicit and separate expression of an abstraction for monads. And that was with C# 3, which has overtaken Java in its evolution towards greater expressive power. So this time I decided to focus strictly on the continuation monad and the question of whether it could enable me to separate the oracle i/o from the specification of my sort algorithm.

Recall the monad laws:


@Test
// unit a ⋆ λb. n = n[a/b]
public void leftUnit() {
Func1<String, CMonad<Integer>> f =
new Func1<String, CMonad<Integer>>() {
public CMonad<Integer> f(String a) {
return CMonad.unit(a.length());
}
};

String a = "a";
CMonad<Integer> expected =
f.f(a);
CMonad<Integer> actual =
CMonad.map(
f,
CMonad.unit(a));

assertMEquals(expected, actual);
}

@Test
// m ⋆ λa. unit a = m
public void rightUnit() {
CMonad<Integer> m =
CMonad.unit(42);
Func1<Integer, CMonad<Integer>> id =
new Func1<Integer, CMonad<Integer>>() {
public CMonad<Integer> f(Integer x) {
return CMonad.unit(x);
}
};

assertMEquals(
m,
CMonad.map(id, m));
}

@Test
// m ⋆ (λa. n ⋆ λb. o) = (m ⋆ λa. n) ⋆ λb. o
public void associative() {
Func1<String, CMonad<Integer>> fa =
new Func1<String, CMonad<Integer>>() {
public CMonad<Integer> f(String x) {

return CMonad.unit(x.length());
}
};

Func1<Integer, CMonad<Integer>> fb =
new Func1<Integer, CMonad<Integer>>() {
public CMonad<Integer> f(Integer x) {
return CMonad.unit(x * 2);
}
};

final CMonad<String> m =
CMonad.unit("m");

final CMonad<Integer> n =
CMonad.unit(5);

final Func1<Integer, CMonad<Integer>> o =
new Func1<Integer, CMonad<Integer>>() {
public CMonad<Integer> f(Integer x) {
return CMonad.unit(x - 1);
}
};

CMonad<Integer> expected =
CMonad.map(
new Func1<String, CMonad<Integer>>() {
public CMonad<Integer> f(String x) {
return
CMonad.map(
o,
n);
}
},
m);

CMonad<Integer> actual =
CMonad.map(
o,
CMonad.map(
new Func1<String, CMonad<Integer>>() {
public CMonad<Integer> f(String x) {
return n;
}
},
m));

assertMEquals(expected, actual);
}


(assertMEquals is more or less what you'd expect):


private void assertMEquals(CMonad expected, CMonad actual) {
Func1 id =
new CostlySorting.Func1() {
public T f(T x) {
return x;
}
};
T exp = expected.f(id);
T act = actual.f(id);
assertEquals(exp, act);
}


My continuation monad satisfies those:


public abstract static class CMonad<X> {
private CMonad() {}
public abstract <R> R f(Func1<X, R> k);
public static <X> CMonad<X> unit(final X x) {
return
new CMonad<X>() {
public <R> R f(Func1<X, R> k) {
return k.f(x);
}
};
}

// aka bind aka ★
public static <X, R> CMonad<R> map(final Func1<X, CMonad<R>> f, final CMonad<X> mx) {
return new CMonad<R>() {
public <S> S f(Func1<R, S> k) {
return mx.f(f).f(k);
}
};
}
}


call/cc seemed like a useful abstraction, so I implemented that in terms of my monad:


public Integer divideByZeroEg(final int x, final int y) {
CMonad<Integer> eg =
CMonad.callcc(
new Func1<Func1<Integer, CMonad<Integer>>, CMonad<Integer>>() {
public CMonad<Integer> f(Func1<Integer, CMonad<Integer>> esc) {
return
CMonad.map(
new Func1<Integer, CMonad<Integer>>() {
public CMonad<Integer> f(Integer z) {
return CMonad.unit(x / z);
}
},
(y == 0 ? esc.f(42) : CMonad.unit(y)));
}
});
return eg.f(
new Func1<Integer, Integer>() {
public Integer f(Integer x) {
return x;
}
});
}

@Test
public void divideByZeroEg() {
assertEquals((Object)5, divideByZeroEg(20, 4));
assertEquals((Object)42, divideByZeroEg(20, 0));
}

public static <X, Y> CMonad<X> callcc(final Func1<Func1<X, CMonad<Y>>, CMonad<X>> g) {
// .\ k -> g(.\x -> .\k' -> kx)k
// g :: ((X -> MY) -> MX)
// g :: ((X -> (Y -> R)) -> (X -> R'))
// k :: X -> R''
// R'' = R
// R = X -> R'
return
map(
new Func1<X, CMonad<X>>() {
public CMonad<X> f(X x) {
return unit(x);
}
},
new CMonad<X>() {
public <R> R f(final Func1<X, R> k) {
CMonad<X> gresult =
g.f(
new Func1<X, CMonad<Y>>() {
public CMonad<Y> f(final X x) {
return new CMonad<Y>() {
public <S> S f(Func1<Y, S> kprime) {
return (S)k.f(x);
}
};
}
});
return gresult.f(k);
}
});
}


and then I implemented a while loop atop continuation monad and call/cc:


@Test
public void finiteWhile() {
final int [] countdown = new int [] {3};
CMonad.cpswhile(
new Func0<Boolean>() {
public Boolean f() {
return countdown[0] > 0;
}
},
new SideEffectful() {
public void f() {
countdown[0] -= 1;
}
});
assertEquals(0, countdown[0]);
}

private static <T> CMonad<T> recurse(CMonad<T> m) {
final WhateverClosure<CMonad<T>> loop =
new WhateverClosure<CMonad<T>>();
loop.whatever =
CMonad.map(
new Func1<T, CMonad<T>>() {
public CMonad<T> f(T x) {
System.out.println("recurse");
return loop.whatever;
}
},
m);
return loop.whatever;
}

public static void cpswhile(final Func0<Boolean> loopInvariant, final SideEffectful body) {
callcc(
new Func1<Func1<Object, CMonad<Object>>, CMonad<Object>>() {
public CMonad<Object> f(final Func1<Object, CMonad<Object>> esc) {
return recurse(
new CMonad<Object>() {
public <R> R f(Func1<Object, R> f) {
System.out.println("start.f");
if (!loopInvariant.f()) {
System.out.println("done");
return
esc.f(null).f(f);
}
System.out.println("body.f");
body.f();
return f.f(null);
}
});
}
}).f(new Func1<Object, Object>() {
public Object f(Object x) {
return x;
}
});
}

public interface SideEffectful {
public void f();
}


Why reimplement the while? Java's while keyword only composes in the predefined ways that Java's language designers cared about. I wouldn't be able to effect oracle I/O between loop iterations, except by resorting to contrived method invocations in the loop body or test. Also, because of the communications mechanism is method invocation, I couldn't actually use while without also using threads. By using composable continuation monads for control flow, I hoped to express my sort algorithm separately from managing the data flow between the program and the TC oracle.

Of course, Lisp and Haskell don't always translate easily to Java:


@Test
// (recipe for stack overflow)
public void infiniteWhile() {
// customize this value for your stack size/patience
int approximatelyInfinity = 1;

final Calendar finish = Calendar.getInstance();
finish.add(Calendar.SECOND, approximatelyInfinity);
//CMonad.cpsbounce(
CMonad.cpsbouncewhile(
new Func0<Boolean>() {
public Boolean f() {
return finish.after(Calendar.getInstance());
}
},
new SideEffectful() {
public void f() {
}
});
}

public static void cpsbouncewhile(final Func0<Boolean> loopInvariant, final SideEffectful body) {
CMonad<Object> mo =
callcc(
new Func1<Func1<Object, CMonad<Object>>, CMonad<Object>>() {
public CMonad<Object> f(final Func1<Object, CMonad<Object>> esc) {
final CMonad<Object> start =
new CMonad<Object>() {
public <R> R f(Func1<Object, R> f) {
System.out.println("start.f");
if (!loopInvariant.f()) {
System.out.println("done");
return
esc.f(null).f(f);
}
System.out.println("body.f");
body.f();
return f.f(null);
}
};

final WhateverClosure<CMonad<Object>> restartHolder = new WhateverClosure<CMonad<Object>>();
restartHolder.whatever =
map(
new Func1<Object, CMonad<Object>>() {
public CMonad<Object> f(Object x) {
System.out.println("restart.f");
return
esc.f(
Bounce.wrap(
restartHolder.whatever));
}
},
start);

return restartHolder.whatever;
}
});
for (; mo != null;
mo =
(CMonad<Object>)mo.f(new Func1<Object, Object>() {
public Object f(Object x) {
return x;
}
})) {
if (!(mo instanceof Bounce)) continue;
System.out.println("bouncey");
}
}


So then how'd I do? Well, the test code for while loops is fairly readable, but my goal was to write something like


// T is a priority queue of sorted runs
while (T.size() > 1) {
T.add(merge(comparator, T.remove(), T.remove());
}


and have that automatically translated to a continuation monad representing the progress of the loop as a function from Booleans (comparison results) to pairs of its own type and pairs of elements to compare next.

Dealing with the while per se was not bad, but translating the body requires quite a lot of fussiness. We need not only a restartable outer (while) loop, but also a restartable inner (merge) loop and we want these flattened so that the while's client code can be oblivious to the implementation choice to use functional composition in the while body. Looking at things a different way, we would like to encapsulate data flow so that a caller can repeatedly supply data to meet the demands of the callee until the callee finishes.

We could use call/cc whenever we need input to obtain a restart wherever we need input. These restarts are relatively easy to pass around (no need for joins), but they only support one standard operation (escape). Accordingly, each adjacent caller/callee pair have to be tweaked to expect/return restarts (analogously to monads in the above paragraph) and each caller has to branch at each invocation to either pass back a restart or move on with its own computation.

Alternatively, we could add a function to represent function application within the continuation monad framework. We could tweak while so that its body argument has a result type of continuation-monad, and then this new apply function could yield such a monad; while could be responsible for composing that result into its own result (using the join operation from MMA -> MA).

Although we're able to dispense with the repetitive branching at function invocations in the call/cc approach by using monads, we can't escape the need to reimplement Java all along the way. If the body of a while loop includes its own function delegation, we'll have make that monadic. If we need a conditional branch, we'll have to make that monadic. Even to implement merge sort we'd wind up with multiple nested anonymous class instance creation expressions. In between scads of braces, parens, brackets, and repetitions of type names like "Func1," we'd have the names of the functions we used to replace all the Java primitives. Lacking syntactic abstraction, the readability of the resulting DSL doesn't scale beyond the simple examples in this blog post.

Andand.NET via monads

In my previous post, I discussed a direct implementation of andand in C#. This time, I'll show a monadic implementation.

As Justin Wick pointed out on Reg Braithwaite's blog announcing Object#andand, andand can be viewed as a special case of the Maybe Monad. I've been hearing about how useful monads are for a few years, but until recently I hadn't occasion to use them directly. Would a monad formulation of andand be simpler and clearer to read? Would it be easier to understand, if not for everyone then at least for readers who are already familiar with the monad formalism? Here was an opportunity to find out.

For those who are totally unfamiliar with monads: they're a means of accommodating side-effects within the functional paradigm. By structuring input, output, exceptions, etc. with monads, you can restore referential transparency to functions that make use of these kinds of features. Monads are surprisingly versatile. You can build lists and arrays from monads, and in the case of arrays the use of monads makes it easy to use the type system to guarantee that client code fulfills a contract on which an efficient implementation of arrays depends. The famous applications of all the functional goodies in LINQ, such as data access and data-parallel computation, are organized around monads.

So, I refreshed my memory with Monads for Functional Programming and Confessions of a Used Programming Language Salesman followed some of their references: Comprehending Monads, Guarded Recursive Datatype Constructors, and Generalized Algebraic Data Types and Object-Oriented Programming. Thus fortified, I was ready to write some tests:

public class TestMonad<M> where M : MonadImpl<M>, new() {
    [Test]
    public void leftUnit() {
        var a = new Object();
        Assert.AreEqual(a, Monad.Star(Monad.Unit<Object, M>(() => a), b => Monad.Unit<Object, M>(() => b)).Just());
    }

    [Test]
    public void rightUnit() {
        var a = new Object();
        var m = Monad.Unit<Object, M>(() => a);
        Assert.AreEqual(
            Monad.Just(m),
            Monad.Just(
                Monad.Star(m, b => Monad.Unit<Object, M>(() => b))));
    }

    public Monad<String, M> an(Object o) {
        return Monad.Unit<String, M>(() => o.ToString());
    }

    public Monad<Int32, M> bo(Object o) {
        return Monad.Unit<Int32, M>(() => o.GetHashCode());
    }

    [Test]
    public void associative() {
        var m = Monad.Unit<Object, M>(() => new Object());
        Assert.AreEqual(
            Monad.Just(
                Monad.Star(
                    m,
                    a => Monad.Star(an(a), b => bo((String)b)))),
            Monad.Just(
                Monad.Star(
                    Monad.Star(m, a => an(a)),
                    b => bo(b))));
    }
}

I'm following the definitions from Monads for Functional Programming here: a Monad is a triple <M, Unit, ★> where M is a type constructor (generic type), Unit is a function from computations of type a to M a, and ★ applies a function to a monad.

My use of the name "Just" here is regrettable. The Maybe monad's type constructor is conventionally defined as a simple union:

Maybe a = Nothing | Just a

. So, by convention,

Just a

takes a computation of arbitrary type

a

to a monad representing that computation. My function "Just" is the inverse, taking a Monad to the computation it represents. I gather that the primitive monad operators are normally encapsulated so that control of side-effects is well localized/modularized. Usually, function composition on monad values is accomplished by ★, so it's not often necessary to explicitly extract raw computations from monads. Finally, monads seem to be most popular within the Haskell community, and pattern-matching is a pretty ubiquitous in Haskell programs. I think these reasons explain why (as far as I know) there's not much use and no standard name for the operation I call "Just" in my code.

Having translated the mathematical and Haskell definitions of monad into C#, I was ready to check that my translation could extend to an example application shown elsewhere:

[TestFixture]
public class TestMaybeMonad : TestMonad<MaybeMonadImpl> {
    private Monad<String, MaybeMonadImpl> lookup(string name, Dictionary<String, Monad<String, MaybeMonadImpl>> db) {
        Monad<String, MaybeMonadImpl> result;
        db.TryGetValue(name, out result);
        return result;
    }
        
    [Test]
    public void MailSystem() {
        //based very loosely on haskell.org's example
        // (I don't understand why their mplus is relevant)
        var fullnamedb = new Dictionary<String, Monad<String, MaybeMonadImpl>>();
        var nicknamedb = new Dictionary<String, Monad<String, MaybeMonadImpl>>();
        fullnamedb.Add("nicholas", Monad.Unit<String, MaybeMonadImpl>("n@m.com"));
        nicknamedb.Add("nick", Monad.Unit<String, MaybeMonadImpl>("nicholas"));
        var mnick = Monad.Unit<String, MaybeMonadImpl>("nick");
        Assert.AreEqual(
            "n@m.com",
            Monad.Star(
                Monad.Star(mnick, nick => lookup(nick, nicknamedb)),
                name => lookup(name, fullnamedb)).Just());
    }

And finally, I can restate andand in terms of monads:

private class D {}
private class C {
    public D d;
}
private class B {
    public C c;
}
private class A {
    public B b;
}
[Test]
public void andand() {
    A nil = null;
    A a = new A();
    A ab = new A() { b = new B() };
    Assert.IsNull(MaybeMonad<D>.Andand<A>(() => null));
    Assert.IsNull(MaybeMonad<D>.Andand(() => (A)null));
    Assert.AreEqual(a, MaybeMonad<D>.Andand(() => a));
    Assert.IsNull(MaybeMonad<D>.Andand(() => a.b));
    Assert.AreEqual(ab.b, MaybeMonad<D>.Andand(() => ab.b));
    Assert.IsNull(MaybeMonad<D>.Andand(() => ab.b.c));
    Func<Object> x = null;
    Func<Func<Object>> y = null;
    y = () => null;
    Assert.IsNull(MaybeMonad<D>.Andand(() => y()()));
    Assert.IsNull(MaybeMonad<D>.Andand(() => a.b.c));
    Assert.IsNull(MaybeMonad<D>.Andand(() => a.b.c.d));
}

OK then, let's see how this is implemented:

public class MonadImpl<M> where M : MonadImpl<M>, new() {
    public virtual Monad<B, M> Star<A, B>(Monad<A, M> ma, Func<A, Monad<B, M>> f) {
        return f(ma.Just());
    }
}
public class Monad<T, M> where M : MonadImpl<M>, new() {
    public M impl = new M();
    public T Just() {
        return a();
    }
    internal protected Func<T> a;
    public Monad<B, M> Star<B>(Func<T, Monad<B, M>> f) {
        return impl.Star<T, B>(this, f);
    }
    public static Monad<A, M> Unit<A>(A a) {
        return new Monad<A, M>() { a = () => a };
    }        
}

A monad represents a computation of arbitrary type and some sort of side-effect whose control motivates the use of monads. Wrapping and unwrapping the computation associated with the monad is a straightforward example of parametric polymorphism. Slightly more interesting is recursive nature of the Monad type, whose method signatures involve the type on which they are defined. Simple parametric polymorphism permits us to define methods that behave uniformly on values of any type. If we want to make use of non-universal structure on those values we can restrict the values to a range of types that share the structure we need. Often, in a recursively-defined type, we want this range of types to itself involve a type parameter. For example, in this case we want Star to take a Monad and to return a Monad of a similar type. This requires f-bounded polymorphism, which is supported in .NET's generics; c#'s where clause not only binds type parameters, but can (re)use those parameters in the bounds.

Managing the side-effects is less straightforward. Here we want uniform packing/unpacking behavior across all computations, but side-effect management behavior that is peculiar to the kind of side-effect captured by the monad. We've had some support for behavioral refinement that follows subtyping relationships since the beginning of .NET, with virtual methods. But the Star function takes a monad (with behavior b and computation c) and a function from c to d and returns a monad with behavior b and computation d. It builds a value whose type is merely related and not identical to any of its type arguments. This is characteristic of Guarded Recursive Datatype Constructors. These g.r. datatypes, also known as Generalized Algebraic Data Types (GADTs), are not yet well-supported in .NET. Fortunately, the work-around shown above is sufficient for seeing the connection between monads and andand.

The Maybe Monad represents "just" a computation, or "nothing." The monad structure makes it easy and convenient to treat Maybes in a uniform way, regardless of whether a particular Maybe represents "nothing" or a non-nothing computation. If you're familiar with the Null Object pattern, you'll recognize the benefit of this uniformity and you'll see that Maybe monad is a more general alternative to Null Object in many contexts.

So finally we're ready to see andand, implemented in terms of the MaybeMonad:

public class MaybeMonadImpl : MaybeMonadImpl<MaybeMonadImpl> {}
public class MaybeMonad<T> : Monad<T, MaybeMonadImpl> {
    private static Expression andandifyme(MemberExpression me) {
        var objectParameter = Expression.Parameter(me.Expression.Type, "target");
        var parameters = new ParameterExpression [] {objectParameter};
        //TODO: simplify by using the parameter f rather than by duplicating
        // the subexpression: andandify(me.Expression) in slotValue and
        // in the Just of Star of Unit below (the subexpression could occur
        // solely in slotValue, and then its value could be used by
        // dereferencing f in the Just of Star of Unit.
        var slotValue =
            andandifyinr(
                Expression.Invoke(
                    Expression.Lambda(
                        Expression.MakeMemberAccess(
                            objectParameter,
                            me.Member),
                        parameters),
                    andandify(me.Expression)));
        var f = Expression.Parameter(me.Expression.Type, "f");
        return
            Expression.Call(
                typeof(Monad),
                "Just",
                new Type [] { me.Type, typeof(MaybeMonadImpl) },
                Expression.Call(
                    typeof(Monad),
                    "Star",
                    new Type [] { me.Expression.Type, me.Type, typeof(MaybeMonadImpl) },
                    Expression.Call(
                        typeof(Monad),
                        "Unit",
                        new Type [] { me.Expression.Type, typeof(MaybeMonadImpl) },
                        andandify(me.Expression)),
                    Expression.Lambda(
                        Expression.Call(
                            typeof(Monad),
                            "Unit",
                            new Type [] { me.Type, typeof(MaybeMonadImpl) },
                            slotValue),
                        f)));
    }
    private static Expression andandifyi(InvocationExpression i) {
        return
            andandifyinr(
                Expression.Invoke(
                    andandify(i.Expression),
                    i.Arguments));
    }
    private static Expression andandifyinr(InvocationExpression i) {
        var l = i.Expression;
        var f = Expression.Parameter(l.Type, "f");
        return
            Expression.Call(
                typeof(Monad),
                "Just",
                new Type [] { i.Type, typeof(MaybeMonadImpl) },
                Expression.Call(
                    typeof(Monad),
                    "Star",
                    new Type [] { l.Type, i.Type, typeof(MaybeMonadImpl) },
                    Expression.Call(
                        typeof(Monad),
                        "Unit",
                        new Type [] { l.Type, typeof(MaybeMonadImpl) },
                        l),
                    Expression.Lambda(
                        Expression.Call(
                            typeof(Monad),
                            "Unit",
                            new Type [] { i.Type, typeof(MaybeMonadImpl) },
                            i),
                        f)));
    }
    private static LambdaExpression andandifyl(LambdaExpression l) {
        return
            Expression.Lambda(
                andandify(l.Body),
                Enumerable.Select(
                    l.Parameters,
                    p => (ParameterExpression)andandify(p)).ToArray());
    }
    private static Expression andandify(Expression expr) {
        var me = expr as MemberExpression;
        if (me != null) {
            return andandifyme(me);
        }
        var i = expr as InvocationExpression;
        if (i != null) {
            return andandifyi(i);
        }
        var l = expr as LambdaExpression;
        if (l != null) {
            return andandifyl(l);
        }
        return expr;
    }
    public static U Andand<U>(Expression<Func<U>> expr) {
        var aexpr = (Expression<Func<U>>)andandify(expr);
        try {
            return (U)aexpr.Compile().DynamicInvoke();
        }
        catch (Exception e) {
            throw new Exception(
                          String.Format(
                               "trouble evaluating {0}", 
                               aexpr),
                          e);
        }
    }
}

By conflating null and Maybe's Nothing, we preserve the simple approach Identity monad can use for Star: just unwrap the computation from the input monad and wrap it in the output monad. This approach doesn't work in general, because there might be state associated with the monads that we'd need to migrate.

Now, comparing the direct implementation to the monadic implementation, you might be ready to decide that monads might be theoretically interesting but are impractical. I think that on one hand, the more stateful monads benefit more fully from the paradigm than the Maybe monad; on the other hand, C# exaggerates the ceremony of monad implementation relative to Haskell. Microsoft hasn't highlighted their use of monads in LINQ or EF or PLINQ, and they haven't exposed any analog to my Monad<T, M> type, so I couldn't share that implementation for andand. In summary, I don't think the monadic implementation of andand carries its weight, but if I saw an opportunity to benefit from other kinds of monads in my program, the benefits might easily outweigh the amortized costs of monads.

Andand.NET sans monads

I motivated this material in my previous post.

One way to view andand is as a syntactic transformation of the code: the effect we want is to write

a.b.c.d

and have that automatically translated to

(a != null && b != null && c != null) ? a.b.c.d : null

C# doesn't support syntactic abstraction in the style of Lisp macros, but later in this post we'll see that recent versions of C# give us much more flexibility than we had in 2.0 and earlier.

Before we look at the techniques in detail, I want to acknowledge that syntactic regularity is a key motivation for Ruby Object#andand. Ruby Object#andand uses infix "andand" in imitation of the built-in guarded assignment operator &&=. We have no such operator in C#, and I am a prefix sympathizer anyway, so neither of my andand implementations share this emphasis with the Ruby inspiration.

So, my first implementation of andand for C# used LINQ expression tree transformation. The first step is to gain the ability to manipulate the program defined by the source code whose meaning I want to reinterpret (e.g., the compound member access expression a.b.c.d shown above):

public static T Andand<T>(Expression<Func<T>> f) {
    try {
        f = (Expression<Func<T>>)aar(f);
        return f.Compile()();
    }
    catch (Exception e) {
        throw new Exception(String.Format("trouble with {0}", f), e);
    }
}

One of the main ideas in LINQ is type-directed expression quoting. Here, I've written a function that takes an Expression tree as an argument. If I apply this function to a lambda expression, the compiler will translate the lambda to a value representing the abstract syntax tree of the lambda rather than generating an anonymous delegate. So, a typical call site for Andand looks like this:

private class D {}
private class C {
    public D d;
}
private class B {
    public C c;
}
private class A {
    public B b;
}

A ab = new A();
ab.b = new B();
Assert.AreEqual(ab.b, Andand(() => ab.b));
Assert.IsNull(Andand(() => ab.b.c.d));

Once I have my expression tree, I'm ready for a transformation. Clearly from my starting example, member access expressions constitute an important case. I'd like to be able to handle some other cases though, like method chaining. I'll give you a taste of tree inspection and construction here; for complete details see andand-sans-monads at googlecode.

private static Expression aar(Expression e) {
    var me = e as MemberExpression;
    if (me != null) {
        return
            guard(me.Expression, me);
    }
    var l = e as LambdaExpression;
    if (l != null) {
        return
            Expression.Lambda(
                guard(
                    l.Body,
                    l.Body),
                Enumerable.Select(
                    l.Parameters,
                    p => p).ToArray());
    }
    var ie = e as InvocationExpression;
    if (ie != null) {
        var args =               
            Enumerable.Select(
                ie.Arguments,
                (arg, i) => Expression.Parameter(arg.Type, String.Format("arg{0}", i))).ToArray();
       return
            Expression.Invoke(
                guard(
                    ie.Expression,
                    Expression.Lambda(
                        nullExpr(ie.Expression.Type),
                        args),
                    Expression.Lambda(
                        ie.Expression,
                        args)),
                Enumerable.Select(
                    ie.Arguments,
                    arg => aar(arg)));
    }
    return e;
}

It sure is a lot of work to construct expression trees "by hand" as opposed to using the type-directed quoting facility. I could be a lot more concise with Lisp quasiquote. Maybe later we'll experiment with using type-directed quotation of expression tree transformations, but for now I was more interested in exploring the connection between andand and monads.

But I have to work tomorrow morning and I'd like you to be able to read this now, so I'll save the monad and GADT discussion for my next post in this series.

motivation for Andand.NET

Some of my followers on twitter encouraged me to post about my andand implementation, so here is the first in a series.

In brief: I wanted to replace

if (a != null && a.b != null && a.b.c != null) {
    return a.b.c.d;
}
else {
    return null;
}

by

return andand(a.b.c.d);

and I manged to learn a little bit about monads, generalized algebraic data types, and .NET on the way to achieving

return andand(() => a.b.c.d)

About a month ago I was working with an instance of a generic type:

var page = Potpourri.Page.getPage(s, count.Value);
ViewData["reverse-memento"] = page.reverseMemento.itemNumber;

This code obtains a range of rows from a database given a starting position and a window size. Simple integer offsets don't work for the general case of concurrent access by lay users to a mutable table. My approach requires getPage to know an equivalence relation on elements, but it doesn't require that getPage know about itemNumber specifically or even that there be just one field/property that's sufficient to determine equality.

So, AFAICT, there's no good way to avoid violating Demeter here.

Certainly there remains a practical problem that the next and previous page references could be undefined for any given page. In this case, reverseMemento could be null.

The awkward conditional needed to avoid NullReferenceException here brought to mind Object#andand. Informally, andand provides short-circuit behavior for chained accesses. The Ruby andand relies on Ruby metaprogramming features. The closest thing we have to a macro facility in c# is Linq expression trees, and I hadn't had an excuse to use System.Linq.Expressions yet, so this seemed like a good opportunity.

My first implementation directly transformed expression trees, replacing member accesses by conditional member accesses that return null whenever a is null in a.b.

My second implementation was inspired by a question about the relation between andand and the Maybe monad. I thought it would be a good idea to (re)read some papers about monads and test my understanding by implementing a few, including Maybe Monad. I also thought it would be instructive to implement Maybe monad in terms of andand, and andand in terms of Maybe monad.

I'll discuss the code in detail in my next post. For now, you can download a snapshot. I guess I'll migrate my existing hg repo to googlecode in time for the next post to make browsing easier.