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.

No comments: