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