Monday, November 25, 2013

Abstract Nonsense: chapter 2s, Stately Statefulness

This is about continuations, really.

This is the continuing series of articles of continuing on continuations. Really.

And State. Oh, and State. Ugh.

So, the State monad is a monad on a 'stateful-like' function.

Still with me?

So I have this beautiful implementation in Java — No, really. I do. — and, so ... how do I test that it works?

Well, you know I have to use it. I have this State monad transformer example, but I want something really, really simple, so:

> inc :: State Int Int
> inc = do x <- get
>             put (x + 1)
>             return x

But the thing is, we don't have the do-notation in Java, so we have to unwind this as a set of monadic binds, so:

> inc1 = get >>= \x -> put (x + 1) >> return x

Cool! But we don't have (>>) ('then') in Java, we have (>>=) ('bind'), so one more transformation:

> inc2 = get >>= \x -> put (x + 1) >>= \_ -> return x

AND we're done! Now, an example:

> runState (inc2 >> inc2 >> inc2) 2

and we get:

(4, 5)

as expected.

Shoot, do we have to write (>>) ('then') as a convenience function? We still have to take the argument and declare the type of the function, but the function itself simplifies. Let's see the Java implementation first as:

> runState (inc2 >>= \_ -> inc2 >>= \_ -> inc2) 2

(still works...)

(Holy Chajoles, Batmans, my Java-State-thingie just frikken worked!)1

So, State is a straight transliteration from Haskell to Java. It's a monad of a function:

public class State<STATE, DATUM> implements Monad<State, DATUM> {

    protected State(Arrow<STATE, Tuple<DATUM, STATE>> f) {
state = f;
    }

// get and put are straight from the haskell standard library:

    // get = State $ \x -> (x, x)
    // so is x <- get the same as get >>= State $ \state -> (x, state1)
    public static <STATE1> State<STATE1, STATE1> get(STATE1 basis) {
return new State<STATE1, STATE1>(Tuple.dupF(basis));
    }

    // put :: a -> State a ()
    public static <STATE1> State<STATE1, Unit> put(final STATE1 s) {
Arrow<STATE1, Tuple<Unit, STATE1>> putter =
    new Function<STATE1, Tuple<Unit, STATE1>>() {
    public Tuple<Unit, STATE1> apply(STATE1 ignored) throws Failure {
return Tuple.pair(Unit.instance, s);
    }
};
return new State<STATE1, Unit>(putter);
    }

// eval/exec/run State functions are yawn-worthy:

    public DATUM evalState(STATE s) throws Failure {
return state.apply(s).fst();
    }
    public STATE execState(STATE s) throws Failure {
return state.apply(s).snd();
    }
    public Tuple<DATUM, STATE> runState(STATE s) throws Failure {
return state.apply(s);
    }

// now here comes the fun stuff. Functor:

    // Functor override --------------------
    /*
instance Functor (State s) where
    fmap f m = State $ \s -> let
        (a, s') = runState m s
        in (f a, s')
    */
    public <A, B> Arrow<Functor<A>, Functor<B>> fmap(final Arrow<A, B> fn) {
return new Function<Functor<A>, Functor<B>>() {
    public Functor<B> apply(final Functor<A> functor) throws Failure {
// TODO: implement -- uh, fmap and >>= are the same for state
// ... almost
Arrow<STATE, Tuple<B, STATE>> stater =
    new Function<STATE, Tuple<B, STATE>>() {
    public Tuple<B, STATE> apply(STATE s) throws Failure {
State<STATE, A> m = (State<STATE, A>)functor;
final Tuple<A, STATE> tup = m.runState(s);
return Tuple.pair(fn.apply(tup.fst()), tup.snd());
    }
};
return new State<STATE, B>(stater);
    }
};
    }

// and monad bind and return and then:

    // Monad overrides ---------------------
    public <X> Monad<State, X> unit(final X d) {
Arrow<STATE, Tuple<X, STATE>> lifter =
    new Function<STATE, Tuple<X, STATE>>() {
    public Tuple<X, STATE> apply(STATE st) throws Failure {
return Tuple.pair(d, st);
    }
};
return new State<STATE, X>(lifter);
    }

    // state >>= f = State $ \st ->
    //               let (x, st') = runState state st
    //               in  runState (f x) st'
    public <B> Monad<State, B> bind(final Arrow<DATUM, Monad<State, B>> fn)
throws Failure {
final State<STATE, DATUM> status = this;
Arrow<STATE, Tuple<B, STATE>> binder =
    new Function<STATE, Tuple<B, STATE>>() {
    public Tuple<B, STATE> apply(STATE st) throws Failure {
Tuple<DATUM, STATE> tup = status.runState(st);
return ((State<STATE, B>)fn.apply(tup.fst()))
.runState(tup.snd());
    }
};
return new State<STATE, B>(binder);
    }

    // join() ???
    public Monad<State, ?> join() throws Failure {
      throw new Failure("Okay, why are you joining on state?");
    }
    public <A, B> Arrow<A, Monad<State, B>> liftM(Arrow<A, B> fn) {
return Monad.Binder.lifter(this, fn);
    }
    public <B> Monad<State, B> liftThenBind(Arrow<DATUM, B> fn)
throws Failure {
return bind(liftM(fn));
    }

    public <T> Monad<State, T> then(final Monad<State, T> m) throws Failure {
return bind(new Function<DATUM, Monad<State, T>>() {
public Monad<State, T> apply(DATUM ignored) throws Failure {
    return m;
}
    });
    }

    // just capture types here -----
    private final Arrow<STATE, Tuple<DATUM, STATE>> state;
}

... and with that we have (functional) state!

Now, to test it with our inc2 function(al):

    // So we need to test the hell out of this ...
    public static void main(String args[]) throws Failure {
// TODO: test me! well a simple test is monadic succ, so ...
// inc2 :: State Int Int
// inc2  = get >>= \x -> put (x + 1) >> return x
Monad<State, Integer> inc2 =
    State.get(0).bind(new Function<Integer, Monad<State, Integer>>() {
    public Monad<State, Integer> apply(final Integer x)
    throws Failure {
return State.put(x + 1)
            .then(new State<Integer, Integer>(
Tuple.mkWithFst(x, 0)));
    }
});
System.out.println("runState (inc2 >> inc2 >> inc2) 2 is (4,5): "
  + ((State<Integer, Integer>)
      (inc2.then(inc2).then(inc2))).runState(2));
System.out.println("runState (inc2 >> inc2 >> inc2) 17 is (19, 20): "
  + ((State<Integer, Integer>)
      (inc2.then(inc2).then(inc2))).runState(17));
    }

And the results output are as expected. YAY!

You see that I did implement the (>>) ('then') operator in Java. It was very easy to do: just a bind-ignore-return.

Now.

Now.

Now. (Now, I'm going to stop saying 'now.' Really.)

Now that we have state, we can use it along with continuations to create a threading or coroutining model of computation without having to use the (dreaded/revered) call/cc.2

Tune in next week, Ladies and Gentlemen, for another thrilling chapter on our continuing saga of continuations!

-----

(1) 'Thingie' is a technical term ... 'frikken' is ... not so technical.

(2) "Oh, you code with call/cc?" the awed neophyte whispers reverentially, then bows down and worships.3

(3) Thus spake the Zen Master: "Why are you in awe of those who use call/cc and similar parlor tricks? The real miracle is that when I wish to sum, I use (+), and when I wish to 'continue' I hit the carriage return." Then he concluded his lesson with the cryptic utterance: "One bowl of rice" and departed their presence for Nirvana (he likes Soundgarden, as well).

Chapter Postlude

The problem that this chapter addresses is what I've had in my java categories library for some time now. I've had this thing called 'MutableBoxedType<T>' with a very easy implementation:

@Effectual public class MutableBoxedType<T>
    implements Functor<T>, Copointed<T> {

    public MutableBoxedType(T val) {
this.value = val;
    }

    @Effectual public void put(T newval) {
this.value = newval;
    }

    @Effectual public final Effect<T> putF = new Effect<T>() {
@Override protected void execute(T obj) throws Failure {
    put(obj);
}
    };

    // Functor implementation -----------------------------------
    public <X, Y> Arrow<Functor<X>, Functor<Y>>
fmap(final Arrow<X, Y> fn) {
return new Function<Functor<X>, Functor<Y>>() {
    public Functor<Y> apply(Functor<X> obj)
throws Failure {
MutableBoxedType<X> mbt =
    (MutableBoxedType<X>)obj;
return new MutableBoxedType<Y>(fn.apply(mbt.extract()));
    }
};
    }

    // Copointed implementation --------------------------------
    public T extract() {
return value;
    }

    private T value;
}

Simple enough, we just put a box around a mutable type. The problem is all those @Effectual annotations and the very mutability-ness of the type itself. Once we make the guts of an instance mutable we lose all provability as 'equals' and '==' now have been reduced to meaningless, vis:

MutableBoxedType<Integer> five = new MutableBoxedType<Integer>(5);
oldFive= five;
five.put(12);
five.equals(oldFive); ... is true

Yes, five and oldFive are equal, but their shapes have changed during the course of the program and we need deep copy semantics here to sniff that out.

The (functional) state monad doesn't 'change' ... not via mutation, anyway. What happens instead is that when the state gets updated, we have a new state. It just makes sense (provably so) and gives us our beloved 'mutation' (by all appearances) even in the functional domain.

Thursday, November 21, 2013

Abstract Nonsense: Chapter 2pc, Continuations with Choice


So, okay, we've shown how to lift continuation functions up into the monadic domain, so we could control the input to a continuation, just as we've shown how we can (very easily) control the output from such a function.

And the '(very easily)' is the rub there. If it's the output of the function that concerns us,1 then let's simply work with the output, good or bad.

There's a pattern that addresses this, it's known as the Either data type:

> data Either a b = Left a | Right b

The Either type, itself, is not a functor, as it represents choice. By convention this falls very nicely into failure conditions where we wish to know what went wrong:

> type Answer a = Either a String

If we get back a Left a solution, we know our answer is good; but if we get back a Right String answer, then we know we had an error, and the error message is contained in the string. We can use the either function to dispatch on our called-function's output:

> either :: (a -> c) -> (b -> c) -> Either a b -> c

So, all that heavy lifting of CPS-functions we did in the last chapter to make them monadic ...?

Let's return to the drawing board, restarting from the example code base where we made our divBy function in the CPS-style for unit values:

    public ANS appDivBy(final Arrow<Integer, ANS> tail, Integer by)
            throws Failure {
return Continuity.divBy(basis).apply(by)
    .apply(new Function<Integer, ANS>() {
    public ANS apply(Integer x) throws Failure {
return app(tail, basis, x);
    }
});
    }

And with the Either type ...

Whoopsie, we need to define our Either type in Java, first, before we can use it! Java is particular about these kinds of things. 

Funny, that.

Well, the type is very easy to declare:

interface Either<LEFT, RIGHT> {
    public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> afn, Arrow<RIGHT, ANSWER> bfn)
throws Failure;
}

The Either type gives us the data structure of choice (materializing that choice, once it's made), and the function that dispatches on that choice.

I'd give you the implementation for Left and Right, the two materialized options of the Either choice, but we have to do a bit of ground-work to make them happen. Or should I just try to develop the two subtypes of Either and let the basic types fall out, as what happened when I did the development work? Yes, let's do that.

First, let's define our Right option of our Either choice-point:

public class Right<LEFT, RIGHT>
    implements Functor<RIGHT>, Either<LEFT, RIGHT> {
    public Right(Right value) {
this.arg = value;
    }
    // Functor implementation -----------------------
    public <A, B> Arrow<Functor<A>, Functor<B>> fmap(final Arrow<A, B> fn) {
return new Function<Functor<A>, Functor<B>>() {
    public Functor<B> apply(Functor<A> func) throws Failure {
Right<?, B> ans = null;
try {
    Right<?, A> righto = (Right<?, A>) func;
    ans = new Right<?, B>(fn.apply(righto.arg()));
} catch(Exception ex) {
    throw new Failure("Unable to fmap(Right) for " + func);
}
return ans;
    }
};
    }

    public Right arg() { return arg; }

    // Either implementation -------------------
    public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> a, Arrow<RIGHT, ANSWER> b)
throws Failure {
return b.apply(arg());
    }
    // Object override ----------------
    @Override public String toString() {
return getClass().getSimpleName() + "<" + arg() + ">";
    }

    private final RIGHT arg;
}

So, then we have the 'left' option of an Either choice point:

public class Left<LEFT, RIGHT>
    implements Functor<LEFT>, Either<LEFT, RIGHT> {
    public Left(LEFT value) {
this.arg = value;
    }
    // Functor implementation -----------------------
    public <A, B> Arrow<Functor<A>, Functor<B>> fmap(final Arrow<A, B> fn) {
return new Function<Functor<A>, Functor<B>>() {
    public Functor<B> apply(Functor<A> func) throws Failure {
Left<B, ?> ans = null;
try {
    Left<A, ?> louie = (Left<A, ?>) func;
    ans = new Left<B, ?>(fn.apply(louie.arg()));
} catch(Exception ex) {
    throw new Failure("Unable to fmap(Left) for " + func);
}
return ans;
    }
};
    }

    public LEFT arg() { return arg; }

    // Either implementation -------------------
    public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> a, Arrow<RIGHT, ANSWER> b)
throws Failure {
return a.apply(arg());
    }
    // Object override ----------------
    @Override public String toString() {
return getClass().getSimpleName() + "<" + arg() + ">";
    }

    private final LEFT arg;
}

There's a lot of red in the above code. Why? Well, because we already implemented all that code in the Right<?, RIGHT> type. All the red code is repeated, nearly verbatim, just replacing 'Left's for 'Right's. What's going on here? It seems like there's shared functionality here.

There is.

The thing is, are functors require to carry around some unit type? I argue: no. The intrinsic property of a functor is that it is mappable from one category to the other: fmap(). I further argue that it is not intrinsic to a functor-type to carry a value. So I said arg() is not part of the Functor protocol.2

And this, by definition, fits in very nicely with the whole concept of monads. Once you're lifted into the monadic domain, you stay there, and you are not allowed to extract() values from the monad. For example: try extracting a value from Maybe.NOTHING, or from [] ... you get an error. I argue even more strongly than this arg() against a(n unspecified) monad should not compile!

And that's my heart-ache with the above code. Left, by declaration, is a Functor, but it shouldn't have to carry around all these marshalling and unmarshalling functions around a carried type. A generic type-carrying type should have all that functionality and Left and Right should shunt or delegate all this functionality to that type-carrying type.

What could this type be?

Well, the obvious candidate is Id.

public class Id<T> implements Functor<T> {

    public Id(T val) {
arg = val;
    }

    public T arg() { return arg; }

    // Functor override --------------------------
    public <A, B> Arrow<Functor<A>, Functor<B>> fmap(final Arrow<A, B> fn) {
return new Function<Functor<A>, Functor<B>>() {
    public Functor<B> apply(Functor<A> func) throws Failure {
Id<B> ans = null;
try {
    Id<A> id = (Id<A>) func;
    ans = constructor(fn.apply(id.arg()));
} catch(Exception ex) {
    throw new Failure("Unable to fmap(id) for " + func);
}
return ans;
    }
};
    }

    protected <X> Id<X> constructor(X val) {
return new Id<X>(val);
    }

    // Object overrides --------------------------
    @Override public String toString() {
return getClass().getSimpleName() + "<" + arg() + ">";
    }
    @Override public int hashCode() {
int hash = getClass().hashCode();
if(arg() != null) {
    hash += 7 * arg().hashCode();
}
return hash;
    }
    @Override public boolean equals(Object obj) {
if(obj instanceof Id) {
    Id id = (Id)obj;
    if(arg() == null) return id.arg() == null;
    return arg().equals(id.arg());
}
return false;
    }
    private final T arg;
}

With this common class as a parent, both in functionality and in type-inheritance (both Left and Right are identifying types or type labels on the underlying values), both Left and Right reduce to much smaller implementations:

public class Left<LEFT, RIGHT> extends Id<LEFT>
    implements Either<LEFT, RIGHT> {
    public Left(LEFT value) {
super(value);
    }
    // Id override -----------------------
    protected <X> Id<X> constructor(X val) {
return new Left<X, Unit>(val);
    }

    // Either override -------------------
    public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> a, Arrow<RIGHT, ANSWER> b)
throws Failure {
return a.apply(arg());
    }
}

and for Right:

public class Right<LEFT, RIGHT> extends Id<RIGHT>
    implements Either<LEFT, RIGHT> {
    public Right(RIGHT value) {
super(value);
    }
    // Id override -----------------------
    protected <X> Id<X> constructor(X val) {
return new Right<Unit, X>(val);
    }
    // Either override -------------------
    public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> a, Arrow<RIGHT, ANSWER> b)
throws Failure {
return b.apply(arg());
    }
}

Much, much simpler!

You see in these implementations the constructor() function supplies our (sub-)type, so that fmap() on Id works equally well for these types, as well.

You also saw in the original implementation the following (questionable) type: ? That type has been replaced by the Unit type (familiar to you Haskell-functional programmers).  Unit is what? One? Well, yes, there's only one Unit instance, because it represents the null or nothing value in the unit category:

public class Unit {
    private Unit() { }

    @Override public String toString() { return "()"; }
    public static final Unit instance = new Unit();
}


Easy, peasy!

And, in fact, with just these elements, we have a system sufficient to handle normal and erroneous states (or any left or right paths) for our simple arithmetic system:

class ResultE extends Result<Either<Integer, String>> {
    public ResultE(Either<Integer, String> res) {
super(res);
    }

    public Either<Integer, String>
apply(final Arrow<Integer, Either<Integer, String>> tail)
throws Failure {
return appE(tail, basis, 3);
    }

    private static Either<Integer, String>
appE(final Arrow<Integer, Either<Integer, String>> tail,
    final Either<Integer, String> basis, Integer in) throws Failure {
return Continuity.g(basis).apply(in)
    .apply(new Function<Integer, Either<Integer, String>>() {
    public Either<Integer, String> apply(Integer x) throws Failure {
return Continuity.f(basis).apply(x).apply(tail);
    }
});
    }
    public Either<Integer, String> 
appEDivBy(final Arrow<Integer, Either<Integer, String>> tail,
  Integer by)
            throws Failure {
Either<Integer, String> ans = null;
try {
    Continuation<Integer, Either<Integer, String>> cont =
Continuity.divBy(basis).apply(by);
    ans = cont.apply(new Function<Integer,
    Either<Integer, String>>() {
    public Either<Integer, String> apply(Integer x)
    throws Failure {
return appE(tail, basis, x);
    }
});
} catch(Exception ex) {
    ans = new Right<Integer, String>("Failed with error " + ex);
}
return ans;
    }

    public static void main(String args[]) throws Failure {
eitherCPSdivBy0();
    }
   
    private static void eitherCPSdivBy0() throws Failure {
final Either<Integer, String> basis = new Left<Integer, String>(0);
final ResultE inf = new ResultE(basis);
looper(new Callee<Either<Integer, String>>() {
public Either<Integer, String> call(Integer inni)
    throws Failure {
    return inf.appEDivBy(new Function<Integer,
Either<Integer, String>>() {
    public Either<Integer, String> apply(Integer x)
throws Failure {
return new Left<Integer, String>(x);
    }
}, inni);
}
    }, "either-CPS");
    }
}

Note that it is the caller that determines what is 'good' (left) and what is 'bad' (right) and what to do in either case. And notice that in the below output, how simple and obvious everything is, we either have a left/number or a right/error condition.

javac -d .classes ResultE.java
java -cp .classes ResultE
Hey, for either-CPS (20 divBy 0 + 1) * 2 is Right<Failed with error java.lang.ArithmeticException: / by zero>
Hey, for either-CPS (20 divBy 1 + 1) * 2 is Left<42>
Hey, for either-CPS (20 divBy 2 + 1) * 2 is Left<22>
Hey, for either-CPS (20 divBy 3 + 1) * 2 is Left<14>
Hey, for either-CPS (20 divBy 4 + 1) * 2 is Left<12>
Hey, for either-CPS (20 divBy 5 + 1) * 2 is Left<10>
Hey, for either-CPS (20 divBy 6 + 1) * 2 is Left<8>
Hey, for either-CPS (20 divBy 7 + 1) * 2 is Left<6>
Hey, for either-CPS (20 divBy 8 + 1) * 2 is Left<6>
Hey, for either-CPS (20 divBy 9 + 1) * 2 is Left<6>

... aaaaaand we're done!

Apprennez le leçon, s'il vous plaît

So, okay, what's the take-away from all this? Besides the fact that Either is easy to implement and to apply and that lifting continuations to monadic binding is hard?

Well, just that. The previous two chapters are a reinvention of the ContT, the continuation monadic transformer, where I developed a need or justification for its use and then I wrote the thing out by hand from scratch.

THEN I looked up ContT in the Haskell standard library.

The journey of Haskell programmers is reimplementing functionality of the standard libraries. Enlightenment comes when they realize they are doing just that.

But I'm actually feeling pretty good from all this exercise. I never saw the 'point' before of continuations, and I never 'got' ContT; I didn't even look at it as a thing, and now, it's ... 'Ah! A Kleisli arrow on the continuation function! Now I see!" and I didn't see the 'point' of the Either type. It was just choice. So what?

Choice is a powerful thing. It's more than just error handling, as we have and show here, but even just that is powerful enough: it's simple to implement and easy to apprehend.

Continuations. It's shown us ... well, continuations, but the control pattern also exposes opportunity to explore data types that are very simple to use, but why? Because the patterns that arise beg the simplicity that are filled by these data types.

That's what I like about these simple concepts: rigorously applied, they open new vistas, yes, but they also facilitate the exploration with these patterns that allow us to try something, ContT, perhaps, and if that doesn't work well, then, well, how about Either, then? Or perhaps Maybe? Or a monadic or comonadic List? An applicative functor?

An universe of space to explore, and, with these tool, a (type-)safe, fun and exciting set of ways to branch off in these explorations.

I'll see you on the other side.

Next chapter. Tuples? Coroutining with continuations? We shall see.

-----

(1) In most cases, it is so that the output of functions is what concerns us. That's a reason monads are so pervasive: they allow us to control the output of functions safely in the monadic domain.

(2) This was my personal little crisis. I just couldn't see the point of functor types not carrying a datum. I mean: what did that look like? I was stuck on the idea of functor-as-id, and id carried a value it identified, even if it were the empty/null/unit-type instance. Same for monads. Yes, monads are the triple {T, μ, η} but if they aren't carrying a datum, what's the point? Monads not carrying a value seemed to be a rather abstract (and pointless) exercise to me. After all, even Nothing has a value: Nothing.

But that's where I missed it, right? But I'm in good company: the ancient Greeks looked upon the concept of zero as anathema and heretical. 'Something' exists, and 'nothing' doesn't exist. It can't. Conceptualizing it is error.

Or so they thought, and so did I. And looked what that blocking ... block? Math was stuck until zero was admitted, and then from zero, came everything ('infinity'). Same for me. By forcing Functor and, consequently, Monad to have arg(), I was boxing Functor into having something that it mayn't, and forcing Monad into something that it isn't: you extract from comonads, to extract from a monad is an error.

Let's look at Nothing again.

Nothing :: Maybe a

Nothing has the (Maybe'd) a-type, but it doesn't carry an a-instance.

Same thing for any kind of list:

[] :: [a]

The empty list has the (listed) a-type, but it doesn't carry an a-instance. It's an error to ask to extract an a-instance from an empty list.

Same thing for any mzero (dependent) (sub) type of a monoidally-typed (or -kinded) type.

So, whereas before I would have arg() for monads and throw an error when I encountered a Nothing or [] or other mzero-value, now I'm thinking that arg() depends on the type of the value. There's no arg() for [] and none for Nothing, either, and it's now a compiler error to ask for an arg() from those values. You just can't ask for arg() from Maybe nor from list any more when they're monadic, you have to obey the math of monads now, and fmap() the monadic function against the monad itself, then join() to get the monadic result.

Much cleaner, and now provably correct, because now the above doesn't yield a runtime error. When this new concept of monads is applied in programs, compiling the program successfully means it works now.

And this reconceptualization means I can now explore monads that do not carry an underlying value. I can have some monad m that itself has values m1, m2, m3, ..., mn and those (monadic) values, themselves, have their own intrinsic meaning: I don't have to ask() for their arg()ed values for the context of them: I can now use comonads for that when I need that.

Where will this new understanding lead me?

I don't know. I'm excited to find that out for myself.

Monday, November 18, 2013

Abstract Nonsense: chapter 2m, (Re)Introducing Monads


Abstract Nonsense: chapter 2M, (Re)Introducing Monad

... So, we were stuck. We did all this wonderful continuation passing stuff but we still got our divide by zero. There seems to be no getting around it, because the underlying functionality works with integers, and division by (unknown) integers can be unsafe, no matter how you (continuationally) slice it.

Or.
Is.
It?

Well, yeah, sure (that's stated with scientifically-precise certainty, did you notice that?): integers qua integers when you hit the div-by-zero, you're stuck.

But who says we have to have as inputs (strictly) integers? The function says 20 / x and x + 1 and 2 * x, so long as the x we're working with can be applied to those arithmetic operators, we're good.

Oh, and we're not going to redefine the arithmetic operators to mean (neither denotationally nor operationally) anything other than what they do mean in Java.

That's considered bad form in Java. For some reason. For now.

But, as you saw in the previous chapter, continuations allow you to retarget the function's return value and type. Well, we can also do the same thing with the input: we can re-source the resource to be sourcedly sourced in a source-y sourced source.

Source-wise, that is.

AND make sense, too. Even if that seems like an impossibility for me.

So, reformulating the problem statement, we have this function, divBy, that when we pass it an integer, either straight away or in the continuation-passing style, it blows up and fandangos on core like nobody's business.

(Damn fine summary, geophf) (why, thank you, geophf!)

So, the problem is not divBy, it does what it's supposed to do, and when it can't, it throws an exception. That's straight-up Java-y semantics, so deal with it, buster!

No, the problem is the caller's. It's your problem you're passing in a zero, and what were you thinking? Who do you think you are, that you can just pass in a zero like that?

AHEM! I digress.

So, let's make the function safe, no matter what number we pass in.

How do we do that?


A monad with monoidal properties has binary-like properties, and the Maybe monad fits the bill nicely here, because we want either 'Just' our answer back or 'Nothing' if something went awry.

A recap of monads (in Java, no less) is here. And we declare our monadic type as:

interface Monad<M extends Monad, T> extends Functor<T> {
    public Monad<M, ?> join() throws Failure;
    public <X> Monad<M, X> unit(X unit);
    public <X> Monad<M, X> bind(Arrow<T, Monad<M, X>> fn) throws Failure;
    public <X, Y> Arrow<X, Monad<M, Y>> liftM(Arrow<X, Y> fn);
    public <X> Monad<M, X> liftThenBind(Arrow<T, X> fn) throws Failure;
}

With an inner-class helper for binding as:

    public static class Binder {
public static <A, B, M extends Monad> Monad<M, B> 
binder(Monad<M, A> m,
      Arrow<A, Monad<M, B>> fn)
        throws Failure {
    return ((Monad)m.fmap(fn).apply(m)).join();
}
public static <A, B, T, M extends Monad> Arrow<A, Monad<M, B>>
  lifter(final Monad<M, T> mType,
final Arrow<A, B> fn) {
    return new Function<A, Monad<M, B>>() {
public Monad<M, B> apply(A input) {
    return mType.unit(fn.apply(input));
}
    };
}
    }

Realizing the Maybe type, which is:

> data Maybe a = Just a | Nothing

as a monad, then, is a trivial exercise:

public abstract class Maybe<T> implements Monad<Maybe, T> {

    // Constructor method -----------------------------------
    public static <X> Maybe<X> nullOr(X unit) {
if(unit == null) return NOTHING;
return new Just<X>(unit);
    }

    // ------------- FUNCTOR overrides ----------------------
    public <A, B> Arrow<Functor<A>, Functor<B>> fmap(final Arrow<A, B> fn) {
return new Arrow<Functor<A>, Functor<B>>() {
    public Functor<B> apply(Functor<A> in) {
if(in == Maybe.NOTHING) {
    return in;
}
Just<A> jus = (Just<A>)in;
return in.unit(fn.apply(in.arg()));
    }
};
    }
    // Monad overrides --------------------
    public abstract Monad<Maybe, ?> join() throws Failure;
    public <A> Monad<Maybe, A> unit(A unit) {
if(unit == null) {
    return Maybe.NOTHING;
}
return Just<A>(unit);
    }
    public abstract <B> Monad<Maybe, B> bind(Arrow<T, Monad<Maybe, B>> fn)
throws Failure;
    public <X, Y> Arrow<X, Monad<Maybe, Y>> liftM(Arrow<X, Y> fn) {
return Monad.Binder.lifter(this, fn);
    }
    public <X> Monad<M, X> liftThenBind(Arrow<T, X> fn) throws Failure {
return bind(liftM(fn));
    }

    protected static class Just<T> extends Maybe<T> {
protected Just(T unit) {
    arg = unit;
}
protected T arg() { return arg; }
@Override public Monad<Maybe, ?> join() throws Failure {
    if(!(arg() instanceof Maybe))
throw new Failure("Cannot join unit type");
    Maybe<?> ans = (Maybe<?>)arg();
    return ans;
}
@Override public <B> Monad<Maybe, B>
        bind(Arrow<T, Monad<Maybe, B>> fn) throws Failure {
    return fn.apply(arg());
}

private final T arg;
    }
    public static final Maybe<?> NOTHING = new Maybe<Object>() {
// join() on NOTHING is NOTHING
@Override public Monad<Maybe, ?> join() throws Failure {
    return this;
}
// bind() on nothing returns nothing
@Override public <B> Monad<Maybe, B>
        bind(Arrow fn) throws Failure { return this; }
    };
}

So, now that we have the Maybe monad, we can use its monoidal properties (not made explicit here, by the way, although I, in my own class libraries, do declare the Monoid and Semigroupoid types) to make our calls to the continuation arithmetic functions safe by changing the input from the (unit type) Integer to the (lifted type) monadic integer ... and we can do that as the caller, without changing the continuation-passing styled arithmetic functions. That's one of the nice features of the continuation-passing style. Rapid prototyping? No problem!

So, then we reformulate our call with the monad to do this (which is the same thing as what it's been doing):

class ResultM<ANS extends Monad> extends Result<ANS> {
    public ResultM(ANS res) {
super(res);
    }

    private static <MONAD extends Monad> MONAD
    appM(final Arrow<Integer, MONAD> tail,
          final MONAD basis, Integer in) throws Failure {
return Continuity.g(basis).apply(in)
    .apply(new Function<Integer, MONAD>() {
    public MONAD apply(Integer x) throws Failure {
return Continuity.f(basis).apply(x)
    .apply(tail);
    }
});
    }
    public ANS appDivByM(final Arrow<Integer, ANS> tail, Integer by)
             throws Failure {
Continuation<Integer, ANS> result = Continuity.divBy(basis).apply(by);
ANS n = (ANS)result.apply(new Function<Integer, ANS>() {
    public ANS apply(Integer x) throws Failure {
return appM(tail, basis, x);
    }
});
return n;
    }

    public static void main(String args[]) throws Failure {
monoidalCPSdivBy0();
    }
   
    private static void monoidalCPSdivBy0() throws Failure {
// monadic-CPS style succeeds with 'failure' or with 'just' the answer
final ResultM<Monad<Maybe, Integer>> minf =
    new ResultM<Monad<Maybe, Integer>>(Maybe.nullOr(0));
looper(new Callee<Monad<Maybe, Integer>>() {
public Monad<Maybe, Integer> call(Integer inni)
        throws Failure {
    return minf.appDivByM(Maybe.liftF(inni), inni);
}
    }, "monadic-CPS");
    }
}

Where looper() is defined in ResultM's parent class as:

    protected static class Callee<T> {
public T call(Integer inni) throws Failure { return null; }
    }

    protected static <OUT> void
    looper(Callee<OUT> called, String type) throws Failure {
for(int x = 10; x > -1; x--) {
    System.out.print("Hey, for " + type 
    + " (20 divBy " + x + " + 1) * 2 is ");
    System.out.flush();
    System.out.println(called.call(x));
}
    }

Then calling our new main() we get ... (drum roll, please):

make -f ya.mk run
javac -d .classes ResultM.java
Note: Some input files use unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
java -cp .classes ResultM
Hey, for monadic-CPS (20 divBy 10 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 9 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 8 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 7 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 6 + 1) * 2 is Just 8
Hey, for monadic-CPS (20 divBy 5 + 1) * 2 is Just 10
Hey, for monadic-CPS (20 divBy 4 + 1) * 2 is Just 12
Hey, for monadic-CPS (20 divBy 3 + 1) * 2 is Just 14
Hey, for monadic-CPS (20 divBy 2 + 1) * 2 is Just 22
Hey, for monadic-CPS (20 divBy 1 + 1) * 2 is Just 42
Hey, for monadic-CPS (20 divBy 0 + 1) * 2 is Exception in thread "main" java.lang.ArithmeticException: / by zero
at Continuity$3$1.apply(Continuity.java:29)
at Continuity$3$1.apply(Continuity.java:28)
at ResultM.appDivByM(ResultM.java:20)
at ResultM$3.call(ResultM.java:39)
at ResultM$3.call(ResultM.java:37)
at Result.looper(Result.java:58)
at ResultM.monoidalCPSdivBy0(ResultM.java:36)
at ResultM.main(ResultM.java:29)
make: *** [run] Error 1

What? Wait! NOOOOOOOOOOES!

What happened? All that work (after all that work), and we get the exact same undesirable result? WHY? Why, geophf, why? And how could life could be cruel?

Well, no answers that I'll give you for that last question, but let's see what happened with the monadic approach, and why.

What happened is this: we didn't alter the inputs at all, did we? No, the input type
was still Integer, it was the output type that became Monad<Maybe, Integer>, so, no changing the input, no changing the result.

Right?

Wrong, actually.

We do want to make the continuation system monadic, and the monadic signature is, indeed:

a -> m b

as we have it in this system here: the input starter function is of type Function<Integer, MONAD> where MONAD is defined as the type of the instance Maybe.nullOr(0).

So, yes, the continuing function is in the monadic shape.

But.

But, the CPS-system ('Continuation Passing Style'-system) is called using apply(). This doesn't help at all, because we wish to bind() to monads not apply() to their arguments.

So, not only did we have to pass in a monad to work with, but we also have to ask the CPS to bind to the argument, instead of apply the argument to the function, because we know, in this case, that the argument is monadic.

But so what? So we bind to the monad, but if the monad is still M0, we still have a divide-by-zero exception thrown. We have to deal with that, because if we, the caller, do not, then the system will, by wrenching control from us as it passes the exception up through the call stack. 

This is not what we desire.

Nor is it desirable for us to tell the function: "Oh, I know, for this value, that you are going to fail, so here's a mzero, so you don't have to deal with it."

I mean, in this case, it's patently obvious that if you pass in a zero, your computation bombs. But what if we have a patently 'in'obvious scenario, such as that we are calling a foreign function or a compiled one where we do not know the inner workings of the function, or we have a horribly complex function where we can't take the time to decipher what works and what doesn't.

Suppose, say, our divBy function was written horribly complex...ily, like, say, this:

> divByHorriblyComplexily x = 20 / (x - 1)

So that now x = 0 isn't the problem, but x = 1 is, and how could we possibly know this, just by looking?

(Um, that's a rhetorical question. Don't answer that.)

Or, for continuity, written in CPS like this:

> divByHorriblyComplexily x c = c (20 / (x - 1))

OH, NOES! There's a continuation there, so now we have NO CLUE what's going on! geophf, why do you write such horrible code?

Do you mean to say: code that works in scenarios where previous iterations didn't?

Yeah, geophf, why! Why plague us so?

Yeah. Whatevs.

So, yeah. So in these horribly complex...ily situations, the code, once it evaluates the function's equation will go BOOM for some x, even though we don't know what that 'some x' is.

No idea at all.

But the code knows. So we could 'ask' it, very nicely: "Please, o code, please tell me when you go boom, huh?"

The code's reply: "No."

Huh. So much for asking nicely.

But the code does tell us, by going 'boom,' when it doesn't like chewing the grizzle we gave it to eat, and so we can incorporate that into our monad and into our CPS-system. And that is: we ask, nicely, for the function to evaluate our expression, and it either returns the result, like the good little function that it is, or it goes boom, being the bad, bad function it turned out to be, and what will its parents think?

Once we arrive at the outcome, then we proceed with our computation, and we let the monoidal property of the monad determine how we proceed, either onto the next function or fall through to the end.

So, how do we go about doing that?

Firstly, we need a (monadic) binding function that lifts a CPS function into the monadic domain so we can bind against it:

    // actually, we need a function that takes a continuity and returns
    // a continuation based on the success of application, either success
    // or failure.
    private static <MONAD extends Monad>
Monad<Maybe, Continuation<Integer, MONAD>>
cpsBinder(Continuity<Integer, MONAD> f, Integer seed, MONAD basis)
throws Failure {
Monad<Maybe, Continuation<Integer, MONAD>> ans = 
    (Monad<Maybe, Continuation<Integer, MONAD>>)Maybe.NOTHING;
try {
    ans = Maybe.nullOr(f.apply(seed));
} catch(Exception ex) {
    // throw new Failure(ex);
    ex.printStackTrace();
}
return ans;
    }

    // now we need a function that takes the monadic continuation
    // and allows us to bind our int -> Monad<Maybe, int> function to it
    private static <MONAD extends Monad> MONAD
cpsBind(Continuity<Integer, MONAD> f,
final Arrow<Integer, MONAD> cont,
MONAD basis, Integer input) throws Failure {
return (MONAD)Maybe.nullOr(f.apply(input))
    .bind(new Function<Continuation<Integer, MONAD>,
      Monad<Maybe, Integer>>() {
    public Monad<Maybe, Integer> 
apply(Continuation<Integer, MONAD> c)
throws Failure {
MONAD ans = (MONAD)Maybe.NOTHING;
try {
    ans = c.apply(cont);
} catch(Exception ex) {
    // throw new Failure(ex);
    // ex.printStackTrace(); // here /0 occurs
}
return (Monad<Maybe, Integer>)ans;
    }
});
    }

So our cpsBind() is our apply function when our CPS-functions are monadic.

With that we rewrite the f-and-g composition:

    private static <MONAD extends Monad> MONAD
appCPSmBind(final Arrow<Integer, MONAD> tail,
    final MONAD basis, Integer in) throws Failure {
Arrow<Integer, MONAD> cont = new Function<Integer, MONAD>() {
    public MONAD apply(Integer x) throws Failure {
return cpsBind(Continuity.f(basis), tail, basis, x);
    }
};
return cpsBind(Continuity.g(basis), cont, basis, in);
    }

Then we call that with our divBy()-wrapper:

    public ANS appDivByM(final Arrow<Integer, ANS> tail, Integer by)
throws Failure {
Arrow<Integer, ANS> cont = new Function<Integer, ANS>() {
    public ANS apply(Integer x) throws Failure {
return appCPSmBind(tail, basis, x);
    }
};
return cpsBind(Continuity.divBy(basis), cont, basis, by);
    }


Ooh, ouch! That was a lot of code! But what did we do, basically?

Well, basically, we went through the CPS-call-chain, and replaced the apply-to-the-unit function calls with monadic-binds, that is: we replaced the apply()s with binds() ... but in a type-safe Java-escque manner (so therefore all that code around this simple conceptual change).2

Okay, so, but I didn't say what it does for us, basically-basically.

This is what it does for us:

java -cp .classes ResultM
Hey, for monadic-CPS (20 divBy 10 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 9 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 8 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 7 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 6 + 1) * 2 is Just 8
Hey, for monadic-CPS (20 divBy 5 + 1) * 2 is Just 10
Hey, for monadic-CPS (20 divBy 4 + 1) * 2 is Just 12
Hey, for monadic-CPS (20 divBy 3 + 1) * 2 is Just 14
Hey, for monadic-CPS (20 divBy 2 + 1) * 2 is Just 22
Hey, for monadic-CPS (20 divBy 1 + 1) * 2 is Just 42
Hey, for monadic-CPS (20 divBy 0 + 1) * 2 is NOTHING

TA-DA! We were able to compute what was computable and no compute what wasn't!

Hm, you don't look suitably impressed.

Let's suitably impress you.

So, with the non-monadic approach, if we wended our way UP (instead of down) the iteration, we would've stopped right away at zero:

Hey, for unit-CPS (20 divBy 0 + 1) * 2 is Exception in thread "main" java.lang.ArithmeticException: / by zero
at Continuity$3$1.apply(Continuity.java:29)
at Continuity$3$1.apply(Continuity.java:28)
at Result.appDivBy(Result.java:23)
at Result$5.call(Result.java:74)
at Result$5.call(Result.java:73)
at Result.looper(Result.java:58)
at Result.unitCPSdivBy0(Result.java:72)
at Result.main(Result.java:35)

BAM! ZOOEY! OUCH! 

BUT! But-but-BUT! If we take our monadic bind approach:

java -cp .classes ResultM
Hey, for monadic-CPS (20 divBy 0 + 1) * 2 is NOTHING
Hey, for monadic-CPS (20 divBy 1 + 1) * 2 is Just 42
Hey, for monadic-CPS (20 divBy 2 + 1) * 2 is Just 22
Hey, for monadic-CPS (20 divBy 3 + 1) * 2 is Just 14
Hey, for monadic-CPS (20 divBy 4 + 1) * 2 is Just 12
Hey, for monadic-CPS (20 divBy 5 + 1) * 2 is Just 10
Hey, for monadic-CPS (20 divBy 6 + 1) * 2 is Just 8
Hey, for monadic-CPS (20 divBy 7 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 8 + 1) * 2 is Just 6
Hey, for monadic-CPS (20 divBy 9 + 1) * 2 is Just 6

Here, yes, we do not compute the divBy zero function, and that entire computation falls through, but it, significantly does not abort the entire program, and we are able to proceed with the computations we can process.

Non-monadic, we crash the system. Monadically-bound CPS? We fail-through/fall-through what we cannot do, and continue onto what we can do.

Any questions from the class?

"Yeah, geophf, but all that code? Isn't there a simpler way to ..."

No questions. Thought not, and thank you!

Q.E.D.

So, there!

Post Script: So, Not Really 'Q.E.D.' and stuff (yes, it is) (no, not really)

So, yes, we've proved that yes, we can use monads to ensafe-ify calling foreign methods from throwing nasty system-stopping exceptions that we don't want to have happen.

Yes.

That's all well and good. AND I got to use monads, by gum! so I proved my point, no matter what the cost!

But, is there a better, simpler, easier way to do the exact same, safe thing?

Read the next chapter and weep.

-----

(1) Well, the standard way is to use the Either type actually, and have a Left Integer result mean 'everything's good, move along!' and a Right String contain the error message of why you are a jerk, but I don't want to deal with error handling in this example, I just want my divBy()-whatever-or-not, so that's why I go with the Maybe monad here.

(2) So, you know that's a dead-ringer. Every time you go around replacing one kind of (unit) application with another kind (this case, monadic-binding), you have to ask yourself: "I'm just changing the kind of application, right? Right. Gee, I wish there was some kind of generalization on application!"

Well, in fact, there is. It's called applicative functors, and there's a lovely, gentle introduction to applicative functors by Conor McBride and Ross Patterson.