Today, let's look at the continuation-function.
Now, here is an interesting bird, if there ever was one.
And there is, and it's call the continuation-function. So there!
First of all, let's define what a function does. A function is simply an arrow that points from one thing to another.
Let's tighten that up, a bit.
A function from A -> B maps a value in the A-category to the B-category, and, in some cases, the B-category doesn't even have to be a different category. For example, the successor function maps a integer value to an integer value:
succ 5 = 6
succ 41 = 42
etc.
But a function can map from one type to another type:
number_of_letters "foo" = 3
number_of_letters "bar" = 3
number_of_letters "food" = 4
etc.
So, let's talk about the 'types' of the functions as things unto themselves.
So, succ is a function that maps integers to integers, e.g.: 5 -> 6 and 41 -> 42, etc, and we show this mapping of types thus:
succ :: Integer -> Integer
And number_of_letters maps strings to integers, and so we represent that as:
number_of_letters :: String -> Integer
Now there are generalization of functions. We can say, for example, that we have a function, f, that takes an object of type a and maps that object to a different kind of object of type b. We show this representation thusly:
f :: a -> b
We don't specify the types when we declare the function here, the definition of the function may flesh that out, or, when we actually come down to applying the function to an actual object, then the object will specify the input type and the actual result of the function will specify the output.
This generalization or abstraction is a very powerful tool in the right hands.
And even in the wrong hands.
For it allows us to express truths of objects regardless of what kind of object they are: you can express universal truths in mathematics. Or, you can even, if you wish, partially constrain the types of the objects, and therefore express more specific, or more existential, truths, and there are various ways of going about doing that.
(This type-constraining may or may not be the subject of some future entry. Type-constraints are not the point of this entry.)
(So I do not digress. In this case.)
(Or I do digress, in that I am stating I'm not digressing.)
(As always.)
So, some functions operate with specific kinds of objects (and are not of general interest here) and some functions operate with universals.
Now, there are special kinds of functions that, simply by their types, their declarations, express a truth. The truth-expressing function we'll examine here is the continuation-function.
The continuation function's type is as follows:
c :: (p -> r) -> r
What is this type declaration? And what does it declare, actually?
The type declaration says this:
Given that I'm operating with an object that, itself, is a function from p -> r, I give an r result.
This sounds something like a syllogism (you can look that up if you're a bit rusty on syllogisms), and that's what it is, but it's also rather (or very) reductionist.
In other words it says: If I'm given something that proves r from a given p, then I can prove (or provide you) r.
But wait!
No, really: wait. You're saying I give you p proves r and you'll give me r? What's the point?
Actually, there is not, from proof theory. If you already have p -> r then you also have r, too, don't you?
Yes.
The kicker is this: in certain domains.
Because, what if I give you a function p -> r but p is false? Well then p -> r gives you nothing, nada, zip, zitch! So you can just take your r and ...
Well, you may not even have an r in that case, anyway, so the rest of my statement can remain unsaid.
So in the domain where there is no 'false' or no negation, the (p -> r) -> r works, and it is intuitively obvious: I've got p -> r so I've also got r, given that I've got p.
Math is hard.
The obvious has to be stated, or else falsehood and inconsistency rears it's ugly, nondeterministic head, and we have to wake up and smell the coffee.
But, okay, we're in the continuum of truths, were I do have a p, and p is true, and I have a p -> r, so I've got me an r, so what's the point of continuations?
Well, not that I've got p -> r, I can get my r out any time I want to: now, or later, and 'later' being that the context has entirely changed and the world has moved on, but, if I want to 'reset the clock' or 'turn back time' I now can! All I do is feed my p into my p -> r function and I get my r out in the state when I originally got them.
Importantly, not now messed up by everything else that's come along after.
And therefore the name of the continuation-function, because at time
(p -> r) -> r
I create a continuation from that point, and then I go along and do something else, but then I have my p and I continue from the continuation point in the context of the state of the prior continuation.
The classic, humorous example:
I buy chocolate mousse cake and a latte, create the continuation, eat the cake, drink the coffee, gain weight after eating and drinking.
But then.
I take my little continuation function, my weight goes right back down (because I'm now in the old context of 'before I ate the cake'), and there, lo, and behold! is the cake, all ready to be eaten. So, I sit down, and enjoy my cake. Again. As often as I'd like.
With continuation-functions, you can have your cake, and eat it, too.
But it gets better than even that!
How? you demand.
Thank you for asking.
Because there's this little thing calle the 'continuation-passing style.' When you're working with continuations, you never really ... activate continuations. You just pass them around, as if they're arguments, composing them together, and eventually you pass in your activation function after you're all done and your whole system gets executed or proved all in one go.
Great.
But here comes the better.
Because, usually, continuation-functions are of some generic types p -> r, you can exercise your system with one set of types, then, when you find that wasn't exactly what you were looking for, you just simply ...
... do nothing.
You don't change one thing in your proof system, you just feed in the new, or desired, type at the beginning of the proof, and all the types adjust themselves along the way.
Here's what a coding effort is, in the traditional sense. You code a solution, or so you thought, but somewhere in the middle, you wanted to do something different.
If, instead, you were using the continuation-passing style, instead of changing that middle bit, you just simply pass in the continuation you actually wanted instead. Zero code change.
Or, you code a solution, or so you thought, but you were using the wrong types, and it could be something as simple as changing from British Imperial to Metric (and therefore you just lose a satellite at launch, is all), or it could be something as drastic as using plowshares instead of swords, I don't know.
But the thing is, in the traditional coding paradigm, you're stuck, you have to change all the functions, what type of arguments they take and what value-types they return.
Seventy-two hours. A team in the Nation's Capital spent seventy-two hours recoding an integer to a string because the two-billionth row was reached and the entire system crashed with the computer couldn't index higher than that, and some frikken genius notice the indices weren't being used as numbers, they were just row identifiers, so they could be arbitrarily-lengthed strings instead of integers with an artificial maximum.
Frikken brilliant.
Seventy-two frikken hours of everybody's life wasted on that snafu. A whole weekend.
I'm a consultant. I got paid for my trouble. Some other folks didn't.
That system was coded in the traditional sense.
If the continuation-passing style had been used, how much recoding would we had to have done?
None.
Why?
Because p, the input type, whereas before was (arbitrarily) designated as an integer now could simply be a string. There were no counting functions used against the indices, just simply identifying functions: "Are you row x?" "Why, yes, I am." "Well, then, we're done."
That would have been our seventy-two hours: a simply "well, then, we're done."
Okay, smarty-pants, if continuations are so hot, then why isn't everyone using them?
Actually, everybody coding in the language Scheme is using continuations, and transparently at that. A joke from the BrainF community is that they have continuations built into their language: it's called the enter key.
So why isn't everybody else?
I don't know.
Actually, I do.
Continuations require you work with functions-as-arguments as a coding style, so instead of just coding the for-loop or the if-statement, you actually have to think, and to think strategically, about what you're doing with the system. Meaning you have to know what you're doing, not only right here and right now, but with entire system or subsystem. You have to know the details, but you also have to know the overall plan.
And having a good grasp of everything is just too much for some people. For most people who just want to code that for-loop.
But what are you actually doing with that for-loop? Why do you have that if-statement? Why are you adding those two numbers? What story is your code telling the reader, be it the customer who will use the system or you, again, months later, when you come back to that part of the system and try to decipher what the heck you were doing, and why ...
Well, then, looking at code that I've looked at, that's just way too hard for most. That for-loop? It's tight! What need is it supposed to be addressing? I have no idea. And all the unit tests on the code (which for most coders, is 'none') are so helpful in clearing up these open questions.
But, now, with continuations, does teasing out the meaning of a particular piece of code become harder or easier?
Well, it actually becomes much harder, and in most cases. Why? Because this particular piece of code depends on a continuation passed in (or injected) from elsewhere, and depending (a 'dependency') on what's injected, the entire behavior changes.
This is the dependency-injection style of coding, or, instead of object-oriented, it becomes aspect-oriented, and most traditional, imperative-style coders simply loathe the aspect-oriented approach for it's dearth of for-loops and if-statements.
Most software projects fail. Spectacularly, with huge cost overruns and a complete failure to deliver on promised feature sets.
Spectacularly as in 'billions of dollars' spectacularly. I'm not speaking hypothetically.
Two projects that used generic typing and the continuation-function passing style made over forty million dollars, and the problem with these projects is that they overdelivered on promised feature sets and the users got accustomed to working with software that actually worked. I talked with both product owners of those projects. Nice guys. Really relaxed outlook on life.
Eh. But I digress. As always.
The continuation, it's a function c :: (p -> r) -> r that gives you the power 'to rewind time,' as it were. And what does that give you?
Freedom.
You have the freedom to experiment, because if a particular approach doesn't work, you hit the continuation-'button' and try again with something else, ...
... without having to retool.
Or, if you were working with one set of types, and the situation or the story changes and you now have to work with an entirely new set of things doing a similar set of processes in the work-flow, you hit the continuation-'button' with the new types, ... without having to retool ... and try it with the new types. Got your solution? Great! Need to change something in the middle? Okay, just pass in a new continuation and try again.
'Programming,' ... 'coding' is considered brittle and expensive, and for the most part it is, but there's one thing that just works and works sweet.
The World-wide Web.
There's this very flexible style of coding to web-programming called functional-reactive programming. Web-frameworks have been prototyped, stood up, changed on-the-fly, what have you, using this functional-reactive style.
Guess what's under the hood of this approach.
The little, plain-old continuation-function.
See you tomorrow.
Unless I reset my continuation-function from before I wrote this article.
But then I'd have to rewrite this article. Oops! Let's press forward, then!
No comments:
Post a Comment