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.
No comments:
Post a Comment