Saturday, November 16, 2013

Abstract Nonsense: chapter 2c, Continuing on Continuations


So, continuing on Continuations (like you thought we're done with this? We're NEVER done with this!)

So. Yeah. That.

So, like printing out the number eight, like, to display the true power of continuations? Like, sigfpe can get away with that, and with style, too, but can I do that to you?

"Continuations are AWSM! Lookit me! I just printed the number 8! (and not even '8 factorial' but just '8')."

Weaksauce.

So, this is where we spice up the weaksauce and take things up a notch.

Continuously.

Okay, so first off, we do what we should have done in the first place: generalize all the continuations from (int -> int) -> int to (int -> a) -> a. We keep the input int, because in this example, we are working with integers and with functions that take integers as inputs, but the outputs are totally up to us, the function-caller, not to the function itself.

Did you get that? With continuations, the caller determines the output, and, if we so choose to do, determines even the input to the functions being continuationified.

That's a word now.

So, generalizing, Function's id function is now:

    public static <T> Function<T, T> id(T basis) {
return new Function<T, T>() {
    public T apply(T x) { return x; }
};
    }

The same generalization applies for functions f and g in Continuity:

    public static <ANS> Continuity<Integer, ANS> f(ANS basis) {
return new Continuity<Integer, ANS>() {
    public Continuation<Integer, ANS> apply(final Integer x) {
return new Continuation<Integer, ANS>() {
    public ANS apply(Arrow<Integer, ANS> arr) {
return arr.apply(2 * x);
    }
};
    }
};
    };
    public static <ANS> Continuity<Integer, ANS> g(ANS basis) {
return new Continuity<Integer, ANS>() {
    public Continuation<Integer, ANS> apply(final Integer x) {
return new Continuation<Integer, ANS>() {
    public ANS apply(Arrow<Integer, ANS> arr) {
return arr.apply(x + 1);
    }
};
    }
};
    }

Then we finally generalize the Result type, calling f, g, and id with the specified (generalized) result type (instead of assuming it's an integer):

class Result<ANS> extends Continuation<Integer, ANS> {
    public Result(ANS res) {
basis = res;
    }
    public ANS apply(final Arrow<Integer, ANS> tail) {
return Continuity.g(basis).apply(3)
                               .apply(new Function<Integer, ANS>() {
public ANS apply(Integer x) {
    return Continuity.f(basis).apply(x).apply(tail);
}
    });
    }
    private final ANS basis;

    public static void main(String args[]) {
Result<Integer> just8 = new Result<Integer>(0);
System.out.println("Continue this! " + just8.apply(Function.id(0)));
    }
}

Compiling and running this new set gets us the same result:

$ javac -d .classes Result.java
$ java -cp .classes Result
Continue this! 8

Okay, no biggie. We've proved that by a half-generalization of the continuation type from (int -> int) -> int to (int -> a) -> a gets us the same output from the same input.

Good.

Now, let's take that up a notch.

Aspects

So, I want to change what the program returns to me. I don't want an integer. I hate integers. Now, strings? Strings and I have this thing for each other. We're MFEO, actually.

Result<String> foo8 = new Result<String>("");
System.out.println("Foo that! "
  + foo8.apply(new Function<Integer, String>() {
  public String apply(Integer x) {
      return "foo " + x;
  }
      }));

Compiling and running this gets us:

Foo that! foo 8

Do you see what we just did? We didn't change one line of the called code, but we, as the caller, determined the type returned from two plain, ordinary math functions. Integers, right?

Nope, strings, because that's how we call the shots, and in CPS, we can call the shots.

Exception Handling

So, like, not in this example, but in other examples, you run into the problem that the data causes the system to crash. Like a divide-by-zero error, but there's no trying and catching all over the place here, and, with continuations, we don't need to add them.

What happens when we divide by zero? Well, the question quickly becomes a math philosophy one, and then devolves into 'well, what do you want to have happen?' really.

Like, for example: which zero are we talking about? Zero approaching from negative or positive infinity?

See?

Well, okay.

So, in some cases we want to abort the program (why?) gracefully (why?) in other cases we wish to discard this result, in still other cases, we wish to use a default value.

With continuations, we, the caller, get to choose the course of action.

Let's say I want to discard the computation if I have a divide-by-zero error, nice, and simple, and it doesn't cause the system to crash (which, the system crashing, is usually considered a Bad Thing (tm)).

So, we have some function:

> divBy x = 20 / x

or in Java:

    public static Integer divBy(Integer x) {
return 20 / x;
    }

Which blows up nicely in either language as we approach zero:

> map (divBy >>> g >>> f) [10,9..0]

[6.0,6.444444444444445,7.0,7.714285714285714,8.666666666666668,10.0,12.0,15.333333333333334,22.0,42.0,Infinity]

(oops, Haskell doesn't blow up. Bummer, and curse you, Haskell for being a pretty darn good programming language ... and smart, at that, too!)

(but in our beloved Java ...)

for(int x = 10; x > -1; x--) {
    System.out.print("Hey, (20 divBy " + x + " + 1) * 2 is ");
    System.out.flush();
    System.out.println(2 * (1 + Continuity.divBy(x)));
}

Hey, (20 divBy 10 + 1) * 2 is 6
Hey, (20 divBy 9 + 1) * 2 is 6
Hey, (20 divBy 8 + 1) * 2 is 6
Hey, (20 divBy 7 + 1) * 2 is 6
Hey, (20 divBy 6 + 1) * 2 is 8
Hey, (20 divBy 5 + 1) * 2 is 10
Hey, (20 divBy 4 + 1) * 2 is 12
Hey, (20 divBy 3 + 1) * 2 is 14
Hey, (20 divBy 2 + 1) * 2 is 22
Hey, (20 divBy 1 + 1) * 2 is 42
Hey, (20 divBy 0 + 1) * 2 is Exception in thread "main" java.lang.ArithmeticException: / by zero
at Continuity.divBy(Continuity.java:36)
at Result.main(Result.java:35)

BOOM!

So how do we not go boom?

Well, we continuationify the function:

    public static <ANS> Continuity<Integer, ANS> divBy(ANS basis) {
return new Continuity<Integer, ANS>() {
    public Continuation<Integer, ANS> apply(final Integer x) {
return new Continuation<Integer, ANS>() {
    public ANS apply(Arrow<Integer, ANS> arr) {
return arr.apply(20 / x);
    }
};
    }
};
    }

and, if we pass in a continuation-handler function, that does business-as-usual, then we'll continue to get business-as-usual results:

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

    private static <ANSWER> ANSWER
app(final Arrow<Integer, ANSWER> tail,
    final ANSWER basis, Integer in) {
return Continuity.g(basis).apply(in)
    .apply(new Function<Integer, ANSWER>() {
    public ANSWER apply(Integer x) {
return Continuity.f(basis).apply(x).apply(tail);
    }
});
    }

    // So we refactored apply() simply to call the generic method app()
    public ANS apply(final Arrow<Integer, ANS> tail) {
return app(tail, basis, 3);
    }

gives the same arithmetic exception:

// unit-CPS style fails with arithmetic error:
Result<Integer> inf = new Result<Integer>(0);
for(int x = 10; x > -1; x--) {
    System.out.print("Hey, in unit-CPS, (20 divBy " + x
    + " + 1) * 2 is ");
    System.out.flush();
    System.out.println(inf.appDivBy(Function.id(0), x));
}

Hey, in unit-CPS, (20 divBy 10 + 1) * 2 is 6
Hey, in unit-CPS, (20 divBy 9 + 1) * 2 is 6
Hey, in unit-CPS, (20 divBy 8 + 1) * 2 is 6
Hey, in unit-CPS, (20 divBy 7 + 1) * 2 is 6
Hey, in unit-CPS, (20 divBy 6 + 1) * 2 is 8
Hey, in unit-CPS, (20 divBy 5 + 1) * 2 is 10
Hey, in unit-CPS, (20 divBy 4 + 1) * 2 is 12
Hey, in unit-CPS, (20 divBy 3 + 1) * 2 is 14
Hey, in unit-CPS, (20 divBy 2 + 1) * 2 is 22
Hey, in unit-CPS, (20 divBy 1 + 1) * 2 is 42
Hey, in 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:20)
at Result.main(Result.java:38)

Ick. ALL THAT WORK FOR NOTHING?!?!? NOOOOOOOOOOOOOES!

BUT!

Despair not, fair maiden!

Or, if you're not a fair maiden, because you're not fair, or a maid, then whatevs, and equal opportunity and fairness for all.

You get my drift.

The thing is, we're treating ANS as an integer or a string or some other unit type.

But we don't have to.

Read my next article to see what we can do.
Posted by at No comments:
Labels: ,

Thursday, November 14, 2013

Abstract Nonsense: chapter 2, continuations, or whaaaaaa?


We consider the continuation.

Logically, the continuation is a bit of (abstract) nonsense:

(P -> R) -> R

That is: if we have the proof 'P implies R' then we have R.

Well, that's obvious. We got 'R' already from the veracity of 'P implies R,' so why do we need 'R' again?

Looks suspiciously redundant.

And, in fact, it is. 

Or, that is to say: you can go about doing the business now or later. Continuations allow you to defer something to later, so it gives us a powerful mechanism to do what we need to do in the middle of a computation, so, therefore allows us to program in a very different way, but that doesn't mean you can't go on with your life and program in the way you've always been programming and ... well, keep getting the same results you've been getting.

(Ooh, I just peeked at the Unlambda page after reading sigpfe's article in Monad.Reader about classical logic and call-cc being Peirce's proof)

(Peirce as in 'purse,' as sigpfe points out)

So, what does a continuation look like? Well, now that we have Arrows, continuations are simple enough to create in Java:

abstract class Continuation<P, R> 
    extends Function<Arrow<P, R>, R> { }

Where Arrow, in a very, very (wrong) (I meant:) simple case is:

interface Arrow<X, Y> {
  public Y apply(X arg);
}

And so function is just:

abstract class Function<X, Y> implements Arrow<X, Y> {
  public static final Function<Integer, Integer> id =
    new Function<Integer, Integer>() {
      public Integer apply(Integer x) { return x; }
    }
  };
}

And really, that's all you need.

But how do you use them?

Well, continuations often take the place of tail calls, so:

> f x = 2 * x
> g x = x + 1
> result = f (g 3) -> 8

is the standard functional style, so we rewrite that using CPS (continuation passing style) as:

> f x c = c (2 * x)
> g x c = c (x + 1)
> result c = g 3 (\x -> f x c)

Note the type of result :: (p -> r) -> r. Result is our continuation, and 'c' our 'continuation-function' is ... well, nothing:

> result id -> 8

Let's follow the substitution-chain:

result id = g 3 (\x -> f x id)
            = (\x -> f x id) (3 + 1)
            = f 4 id
            = id (2 * 4)
            = id 8 -> 8

Q.E.D.

So, how do we write that in Java using the Continuation type?

class Result extends Continuation<Integer, Integer> {
  public Integer apply(final Arrow<Integer, Integer> tail) {
    return Continuity.g.apply(3).apply(new Function<Integer, Integer>() {
      public Integer apply(Integer x) {
        return Continuity.f.apply(x).apply(tail);
      }
    }
  }
}

but of course we have to define f and g, and they fall into a category of continuation-using functions:

abstract class Continuity<In, Out> 
    extends Function<In, Continuation<In, Out>> { 
  public static Continuity<Integer, Integer> f = 
        new Continuity<Integer, Integer>() {
    public Continuation<Integer, Integer> apply(final Integer x) {
      return new Continuation<Integer, Integer>() {
        public Integer apply(Arrow<Integer, Integer> arr) {
          return arr.apply(2 * x);
        }
      };
    }
  };

// and g is just the same thing as f, except the function application 
// of the continuer to the successor function (I'll leave 'g' as an exercise 
// to the reader)
//
// ... no I won't be that cruella-de-ville:

  public static Continuity<Integer, Integer> g = 
        new Continuity<Integer, Integer>() {
    public Continuation<Integer, Integer> apply(final Integer x) {
      return new Continuation<Integer, Integer>() {
        public Integer apply(Arrow<Integer, Integer> arr) {
          return arr.apply(x + 1);
        }
      };
    }
  };

}

So, what happens when we apply Function.id to Result?

public static void main(String args[]) {
    System.out.println("Continue this! " + new Result().apply(Function.id));
}

Yeup! We get our beloved 8!

So, we have the continuation passing style in Java, complete with an example program, to boot, in 57 lines of Java code. Pretty impressive! That's worth a sammich! [ref, wikipedia article on continuations sammich example] http://en.wikipedia.org/wiki/Continuation

Post Script (Rant-alert!)

But what does all this buy?

So many times, a coder is confronted with the following problem: I do all this set-up code and all the tear-down code that's exactly the same, and it's only the bit in the middle that changes, so I'm forced to do copy-and-paste coding because I can't do all this generic set-up and tear-down code around a function body, right? I can't pass in a function as an argument, right? So I have to have all my stuff do all the same stuff over and over again, and the juicy bits are always buried deeply in the middle!

Well, now with the continuation type, you now can do this. Or not do that. 'That' being the bane of every elegant programmer's ideal: copy-and-paste coding.

What you can do is to do all your set-up coding once! and all your tear-down coding once! and then pass in the continuation function, the juicy bits to the generic set-up-tear-down function, where it executes the continuation in the context of a properly established environment.

Voilà! You've just reduced the amount of code you write every day by a factor of 7.3 and have discovered the silver bullet AND the perpetual motion machine, too.

AND, as continuationally (or 'continuously') pointed out to me, since no software engineer actually studies computer science any more, none are cognizant of the continuation-passing style, and will not know what the heck is going on with your code.

"geophf," they tell me, "you've written your code for job security reasons, haven't you?"

Um, actually: no. My code is 7.3 times smaller than the system it replaced (verified over and over again ... ever see a series of if-statements in seven layers? I have) and actually does the functionality intended (instead of not), so, yeah, that.

You're welcome!
Posted by at No comments:
Labels: , ,

Friday, November 1, 2013

Abstract Nonsense, chapter 1: the List


Abstract Nonsense: Rambling thoughts of a Category Theorist

Synopsis: Looking at things through the lens of category theory, where 'things' may be anything from writing a good (a really, awesomely good) piece of code to ... well, what else is there in this life?

Chapter 1: the List

We consider the list: to monad or not to monad.

We consider the monad: to monad or to comonad, and, if we consider the monad, shall we consider the monoidal implications that monad lends itself it to?

A monad is not intrinsically monoidal, but, then again, the monad and the comonad are not intrinsically functors, but thinking of monads and comonads and thinking of them not as functors is a blocker for me ... it gives me a bit of a headache, thinking of a monad (the triple (T, mu (or 'join'), eta (or 'unit')). I mean, it is simple to think of monads as monads only when considering the join function, but what is the point of eta if you are not thinking of the monad in terms of a functor?

So I do not consider the monad, or the comonad (W, epsilon (or extract), delta (or duplicate)) (definition from "Introduction to Higher-Order Categorical Logic), http://books.google.com/books?isbn=0521356539, as being independently or intrinsically defined from the functor, Fa, as, after all unit and extract are functorable.

Okay. So we consider lists. We can consider lists free of the monadic and comonadic implications, because, after all, a list is simply a structure, and can be viewed as tree-like structure, where we define 

data list a = nil | (a, list a) 

we see that, firstly list is monoidal on a where mzero = nil and mappend is easily defined as append or (++).

So, anywhere along the list, one can grab the pair, and the tree falls out of the structure:

(a, |->) -> (b, |->) -> nil

The pairwise operators, fst and snd, are head and tail on list a, and the fundamental constructor of the list is cons, where cons :: a -> list a -> list a

(which looks like a continuation, now that I look at it, OMG!)

(The continuation monad is the 'mother of all monads', and the continuation is the 'mother of all function calls,' perhaps?)

from cons, mappend is simply defined:

nil ++ b = b
  a ++ b = cons (head a) (tail a ++ b)
             
Since list a is functor a (leaving aside nil) we have fmap for lists, too:

fmap f nil = nil
fmap f (head:tail) = cons (f head) (fmap f tail)

as you can see, list definitions lend themselves naturally to induction.

Okay. Lists qua lists (of course, as monoids and functors) are very easily defined in just a few lines of code in any programming language with any heft (I've demonstrated Haskell here, the definitions are similar in Java once monoid and functor are properly established as types. This requires that Arrows and functors be defined, but that is not part of the scope of this article ... it's hard, but doable).

Monadic Lists

Now let's consider the case of lists as monads.

First, monad:

class Monad m where
    return :: a -> m a
    join :: m (m a) -> m a

That definition is unusual in the programming community, but not to a categorist. Programmers are used to the more applicative definition of monad:

class MonadForProgrammersButNotForMeTheCategorist m where
    return :: a -> m a
    m >>= f :: m a -> (a -> m b) -> m b

The issue with defining monads in terms of bind (>>=) is that sometimes wrapping your head around what bind should be for a particular monad can be tricky (sometimes it isn't, but sometimes it is), but if one knows what join is for a monad, and, if that monad is a functor, then we have a very simple, and a very general, definition of bind:

bind m f = join . fmap f

proof

bind is defined as above

bind (m a) f = (join . fmap f) (m a) = m b (supposition)
                 = (join . fmap (a -> m b)) (m a)
                 = (join . (m a -> m (m b))) (m a)
                 = (join (m (m b)) = m b
Q.E.D.

So, given that we have join and fmap defined for a monad, bind falls out easily from their composition, and that's why I declare monads as per category theory, as being the triple of the monadic type, the unit function (in Haskell, it's called 'return') and the join function.

Now, the monadic aspect of list a is simply this:

instance Monad list where
  return a = [a]
  join [] = []
  join (head:tail) = head ++ join tail (where head and tail are (monadic) lists)

... or join for list [a,b,c] is a ++ b ++ c.

And thus we have have monadic lists defined and may therefor use lists monadically, e.g.:

[1,2,3] >>= return . succ = [2,3,4]

and, even better:

[1,null, 3] >>= return . succ = [2,4]

It. Just. Works.

(side note: it really works in Haskell, as, after all, 'null' is not a number so the list [1,null, 3] does not exist in Haskell.

In Java, null very much exists, but if we make monadic list construction dependent on the monadicity of the units then the lifting function (which we will cover later) from a 'plain' list to the monadic list gets us into the a good position already:

return [1,null, 3] = [1,3] (monadic)

And if we don't do that, then the binding operation will use the Maybe type to guarantee the safety of the operation:

[1,null,3] >>= return . succ == succ (Just 1) : succ (Nothing) : succ (Just 3) = [2, 4]

end side note.)

Comonadic Lists

Now that we have monadic lists defined, let's define comonad lists.

Why? Because whereas with monads we have bind, which lends itself nicely to each element of lists, with comonads we have extend which also extends itself very nicely to operations on lists as a whole, iteratively reductively.

So, a comonad is

class Comonad w where
    extract :: w a -> a
    duplicate :: w a -> w (w a)

Again, instead of making extend intrinsic to the definition of comonads, I chose, instead, the mathematical definition, again, using duplicate.

Again, for gainful reasons, because extend can be defined in terms of duplicate:

extend :: w a -> (w a -> b) -> w b

Or: 

extend f (w a) = (fmap f . duplicate) (w a) = w b (supposition)

proof:

extend f (w a) = (fmap f . duplicate) (w a)
                     = (fmap (w a -> b) . duplicate) (w a)
                     = ((w (w a) -> w b) . duplicate) (w a)
                     = ((w (w a) -> w b) (w (w a))
                     = w b

Q.E.D.

So for lists:

instance Comonad list where
    extract [] = doesn't happen. Really
    extract (head:_) = head
    duplicate [] = []
    duplicate list@(_:tail) = list : (duplicate tail)

... and we're done.

So, if we have the basic list type defined as (a, list a) or nil

Then we convert to mlist (monadic list) or wlist (comonadic list) by defining nil for each of the particular types and then just adding elements (with cons) to each of those container types:

asMonad [] = m[]
asMonad (h:t) = h m: asMonad t

asComonad [] = w[]
asComonad (h:t) = h w: asComonad t

and in the derived times

asMonad mlist = mlist
asComonad wlist = wlist

Piece of cake.

Or.
Is.
It?

Constructing Lists: Lists as Streams.

The 'problem' of these functional list types is that they look more like Stacks than Queue, so we can interact very easily with the most recent element and cdr down through the list in an orderly fashion, but if we have a preexisting list of one type and wish to view it from a different aspect, not only do we have to build it iteratively, but we have to make sure that iterative build is not penalized (linearly) for each insert at the end of the list (which turns out to be an exponential punishment).

How do we do this?

Lists are functions in a functional aspect.

So, the problem commonly faced by users of them in the functional domain is that when one has to construct a large one iteratively, one faces the problem of continuously appending the next element to the end of the list, and since naïve append is O(N) time (linear), then doing that, iteratively incurs a near O(N*N) time cost.

(side note: the cost is actually O(N*(N-1)/2) time)

What can we do about that?

Simple, actually, if you come from a Prolog programming background, just use difference lists.

A difference list is a list representation of a pair of lists, one list representing the whole and one representing a part of the this:

data dlist a = DL { realize :: list a -> list a }

In Prolog, logic variables are used to provide the (declarative) representation (and consequently, the implementation):

List = [1,2,3|L] - L

Since we have L and L is a part of the whole list, we have a reference into a latter part of the list that in standard list representations we do not. Further, as L can be anything, it can even be the 'end' of the list, and so 'prepending' onto L allows us, by consequence (actually: 'by accident') to 'postpend' onto the list we're working with.

We saw how to represent difference lists using unification and logic variables in Prolog. How do we represent difference lists functionally?

It comes down to the fundamental function of lists, cons:

cons :: a -> list a -> list a

that is, if we give cons an element and a list we get a cons'ed list in return.

What happens if we don't give cons the list to cons to, but instead, we defer it? We then get the partial or curried function:

(cons x) :: list a -> list a

Which is no different than before.

Or.
Is.
It?

Well, recall that a difference list is the difference of two lists. Look at the signature of (cons x) above and what do we have? We have a function that, when given a list, returns a list.

What is a difference list again? A think that, when given a list, gives the full list back.

(cons x), that is: the curried cons function, and the difference list type can be viewed as the same thing, and from that we have our difference list definition (of the realize function):

realize = cons x

So, given realize, we can define prepend and postpend operations:

prepend :: a -> dlist a -> dlist a
prepend x dl = DL { cons x . realize dl }
x |> dl = prepend x dl

postpend :: a -> dlist a -> dlist a
postpend x dl = DL { realize dl . cons x }
dl <| x = postpend x dl

So what? Well, for prepend, there's no big deal, the operation occurs in constant time, but so does cons for (regular) lists. But for postpend, the operation takes the same constant time, but for regular lists, if we were to define postpend in the regular fashion:

postpend :: a -> list a -> list a
postpend a list = list ++ [a]

we would be traversing to the tail of the list each time to append the new element, and that traversal incurs a linear-time cost. Upshot: postpend for regular lists has an O(n) cost, but for difference lists, it occurs in constant time.

And that's the payoff, if you are working with a large list from an external source and need to enlistify it in an order-preserving fashion, doing so with a regular list would incur an exponential cost (nearly O(N*N)) but using difference lists has a logarithmic flattening effect (O(2N)).

Using difference lists saved my bacon on a project where I did a scan-then-process operation on a framework that processes large documents.

Back to Java.

One way to convert from one representation of lists to another is to rebuild the list in the new type. Unfortunately, Java doesn't have the linear construct

mlist [] = m[]
mlist (h:t) = h m: mlist t

So what it does is iteratively build the new list with mappend (as lists are monoidal).

Well, using the O(N) mappend in an iterative fashion incurs an exponential-time cost for list-revisualization.

So, I've replaced my fromCollection() methods in Java from:

public static <L> L fromCollection(Collection coll, L basis) {
  L ans = basis.mzero();
  for(T elt : coll) {
    ans = ans.mappend(basis.singleton(elt)); // exponential cost
  }
  return ans;
}

to be:

public static <L> L fromCollection(Collection coll, L basis) {
   DifferenceList ans = DifferenceList.nil(basis);
   for(T elt : coll) {
      ans = ans.postpend(elt); // constant time cost
   }
   return ans.realizeFrom(basis);
}

so list construction that was at a cost of exponential time now become linear time, as it should be.

This way, I can work with a list either monadically or comonadically and pay only a linear cost when I change my (aspect) perspective on the list.

Posted by at No comments:
Labels: , , , ,

Monday, June 17, 2013

Thoughts on Kleisli Arrows in Java (WIP)

Here are some ramblings as I puzzle my way through on how to represent Kleisli arrows in Java (and why I would want to do that, anyway). This is very much a work in progress, so no solid conclusions from this posting.


Categories are abstractions. They have objects and morphisms. The thing of Category theory is that the objects can be anything, as they are atomic, and the morphisms aren't necessarily functions. So, the objects can be numbers, not that we care, or they could be arrows (another term for morphisms), or they could be categories themselves, so the morphisms become morphisms between categories. Or if the objects are arrows then the morphisms are higher-order functions.

Neat-o!

So, John Baez did some wonderful pieces on higher-order categories in the direction of physical math: topologies and groups and such, and this was replicated in Edward Kmett's work with ... what are they called? Ah, yes: semigroupoids (how could I forget), where the monoids have no zero bases and so identity functions aren't necessary, I suppose.

Interesting! Half-monoids!

But if we look at Categories as simply that: objects and morphisms, and we look at morphisms as simply arrows from a to b, then does that simplify my implementation of my categories library?

Monads no longer are generically typeful but now use inheritance to describe the type families:

Monad<a> is the interface and Maybe<a> extends Monad<a> instead of

Monad<M extends Monad, a> being the interface as Maybe<a> extends Monad<Maybe, a>.

The problem is in the generic functions, how does one grab the 'm' in the monadic type? Or is it as simple as using inheritance and forgetting the thorny problem of genericity, or passing that problem off to the inheritance structure?

Same thing for Arrow ...

instead of Arrow<a, b, c>

we have Arrow<b, c>

and then the Kleisli arrow becomes more simple, perhaps? Because

KleisliArrow<m, b, c> extends Arrow<b, m c>

... but how does that work? Can it work? I don't see how that works.

for first :: a b c -> a (b, d) (c, d)

how does that work for the KleisliArrow, and for chaining the monadic computation?

It appears further research is necessary for me to get a solid grasp of this to be able to implement this properly in Java (as opposed to writing a haskell parser on top of Java, which is also a viable way of going about it, except for the fact that there is political resistance to learning a domain-specific language from devs brought on to code 'only' in language-of-choice X).

So that's my problem, because in my 'Monads in Java' article I concluded with a:

So you see we can now do the following:

f.apply(m).bind(g).bind(h)

and I now know that f.apply(m) is a weakness in coding. This should all be strung together with Kleisli arrows and the resulting morphism be run through the Kleisli computer.

"The (explicit) use of apply considered harmful"?

I mean, Gah! How bold! How daring! How so against the grain!

And it isn't even really 'harmful' either. More like obtuse or obnoxious. And not even that, more like: inelegant. That's the word: inelegant. And we're not even 'using' apply in the above computation. I mean, we are, but we are always using apply. It's so inherent that now just juxtaposition is now apply, so it's not the '(explicit) use' of apply, it's the '(explicit) call' or '(explicit) invocation' of apply that's inelegant.

I mean, when I see the above formulation, I now shudder, whereas before I might've said, with a pause so slight it didn't even register, 'What do we do here? Oh, use apply!' knowing, at the back of my mind, that this didn't sit perfectly right, but what else was there to do?

Well, with Kleisli composition, there is nothing to do at all, but just do it

runKleisli (f <+> g <+> h) m

and we're done.

Now, how to represent that in Java, ... well, I do have a KleisliArrow type that does return the underlying arrow, but what about composition ... it probably has that, too:

f >>> g >>> h

But the gnawing problem there is that KleisliArrow is not related to Arrow, because, properly, it isn't: KleisliArrow on a specific monadic type m IS related to Arrow.

And I don't know how to represent that in Java.

Yet.
Posted by at No comments:
Labels: , , , ,

Tuesday, May 7, 2013

Small survey of Category Theory introductions


Some time ago a friend asked for a good introductory work on Category theory. I never did answer his question to my satisfaction, as the stuff I picked up on the subject was here and there as I needed it, and I thought there was never any succinct introductory work.

Well, I thought wrongly.

http://en.wikipedia.org/wiki/Categories_for_the_Working_Mathematician

Above link ... links to the seminal summa, available for you if you wish to pursue this delightful area of research into expressivity in mathematics.

Also, of course, there's the working-quantum-physicist's introduction at:

http://math.ucr.edu/home/baez/categories.html

Having a working knowledge of quantum computation is not necessary, probably not even helpful, but a very nice introduction is Quantum Computation and Quantum Information by Nielsen and Chuang, if you wish to see the source from where I got to categories and Category Theory.

Dr. Baez's work starts off lightly and playfully, but then gets pretty deep pretty quickly, as he goes into the Groupoid/Topoid theoretical application of Category Theory, but that's to be understood, as quantists are always concerned about (super-)symmetries, and I, not so much, as I look for the more practical application of Categories in Monoids and the Relational Calculus, but there it is.

I do, of course, have more advanced works on this topic if you wish to research further, and there's always this blog, where I look at the logical implications of cat theory (heh: 'logical' 'implications' ... Math humor).  There is, e.g., an introductory article on monads and their computational application at:

http://logicaltypes.blogspot.com/2011/09/monads-in-java.html
Posted by at 1 comment:
Labels: , ,

Wednesday, December 19, 2012

That's a pretty good guess... Naïve Bayesian Classifiers

... so, I don't need to write any more, correct? Classification problem? Apply a naïve bayesian system to it, and you are way ahead of the curve, and you've expended a fraction of the effort to stand the system up.

... shortest posting ever written.

So, anyway.

So, a Bayesian classifier is a predictor.  It says, that is, if it were to speak, it says, "Hm, I've seen this before, so I think this is a that." And, well, given a reasonable tolerance for error or noise, it's pretty good at doing its job. In fact, it works supremely well in noisy environments, shines in them, even, where other models that are more rigidly defined tend rapidly to become unstable at the slightest irregularity (the inductive-logic-programming model comes to mind).

Yes, I've worked on classification systems. We've had a hybrid system composed of a deductive rule-based system (that we hashed out with Subject Matter Experts over months of establishing, parameterizing, then fine tuning each rule) running in parallel with a Bayesian classifier. Guess where 99% of our usable results came from?

Sir Bayes walked away with the win, nearly every time.

How does the naïve Bayesian classifier work?

The algorithm is simplicity itself ... embarassingly so. It does an observation, and that observation is that there is a probability of something happening or being so, and that case depends on all of its antecedents.

Obviously. All these effects occured, lining up to cause this thing to be.

Let's give a real-world example.

The probably of Tennessee winning last Monday's game (they did) was predicated on:
  • It was a Monday night game -- Monday or  F1
  • They were playing on their home field -- Home or  F2
  • They were favored to win (with an even 2-point spread advantage) -- 2.0 spread or  F3
  • They were playing against the New York Jets -- vs(NYJ) or  F4
or p(win(Tennessee) | Monday, Home, 2.0 spread, vs(NYJ))

That works, but only when everything lines up exactly so.

So the brilliancy of Bayes was that the above probability can be rewritten with the following observation:

p(win(Tennessee)) * Πi p(Fi)

And there you have your classifier: you run your classes through the probabilities of their antecedents and for the class where the probability is the greatest is the winner.

Simple, and as the system gets more input data, matched against labeled classes, the better it gets at classification.

Problems

Well, I never promised you a rose garden...

One of the problems is a real-world concern, not a mathematical one, and that is many of these probabilities are minute, and multiplying them to each other ramps the scale down to the miniscule, very quickly. These days computers are ... well: 'eh' at handling very small fractional numbers, and they are architected in such a way that imprecision gets rolled into these numbers, compounding the problem with each multiplication.

How to handle these very small numbers?

Well, obviously, scale them. And this is very simply handled, for, after all, if it's a sense of scale that concerns you, you just rescale your domain. The logarithm does that. 'Automagically.'

SO, the above classifier can be rewritten:

log(p(win(Tennessee))) + Σi log(p(Fi))

And the scaling issue for computers just goes away.

There's another problem, however, and that is how to deal with the messiness of real-world input data.

The naïve Bayesian classifier assumes that all the evidence is present for each class. If a single piece of evidence is missing, that probability will be zero, instantly voiding the entire formula.

So, what to do?

I've observed that voiding the formula for one datum often leads to classifiers that oscillate too wildly and are therefore unusable.

So, I neutralize the nulled probability, instead of nulling it and making the formula void, I set it to unit and it therefore acts as a 'pass-through.'

This is an artifice, I know. I'm intentionally saying a missing datum is actually fully present, but I've found that this works 'eh' ... that is 'passably well.'

I've done this on two classifiers so far, and the classifiers are pretty darn good, but not good enough to my mind.

This is a fundamental problem with the naïve Bayesian classifier, and I'm sure everyone who undertakes this approach has to deal with this, one way or the other. What are good ways to make the naïve Bayesian classifier much more effective, but without excessive effort or thought around null data points that come up?

A problem, but not a crippling one.

I won last week's picks, after all, and that's not the first time
Posted by at 1 comment:
Labels: ,
Subscribe to: Posts (Atom)