Lambda the Ultimate

I am trying to understand continuations (yes, one more!).

I found the Javascript example proposed here quite helpful in understanding the basic idea.

Let me describe it that way:

Imagine that I am a bug in one of these old relay computers of the past. Bulbs are buzzing, relays are snapping all around. Being a curious animal, I decide to follow the noises to understand.

There is the operator, one of these funny animals with rags and the eyes forward facing. He is-- or is it a she?-- feeding some paper-like thing punched with holes (the program) in the machine and adjusting some switches (the data). Before he came in, the place was quiet and silent. That was the entry point of the program.

Then the machine started coming to life, relays activating in succession, bulbs blocking or passing the signal. That was the executed part of the program.

At the moment a relay just changed state; that is the Now.

Following the relays being activated, I can see that there is still more to come. The punched card still has more holes to be read, more relays need to be triggered. That is the program to be executed.

When all the punched card is consumed, some lights will come up in front of the operator, or some printing device will print an output: the result of the program.

The continuation is like putting the Now in a bottle.

If I was sitting at the wrong place, a relay may malfunction, a 1 become a 0, and the result would be different-- that is a different instance of the same continuation.

Another explanation is that a continuation is like the Replay function of an arcade game that I used to play. The game would replay everything I did during the last game. Then I could stop at one point, and take the game over from that point.

Of course continuations are used for a single function, not for a whole program like the punched card description. The entry point is the function call, and the data is the arguments of the function. Invoking the continuation is like replaying in fast forward the past execution of the function till the continuation point (the Now in a bottle) then injecting some new arguments to be used in the rest of the function to be executed.

For the program to stay coherent, the new arguments should not be used before the continuation point. It is also interesting to note that when the function terminates, the result is available to the program that invoked the continuation-- it is not returned to the original invoker of the function.

There remain some questions:

• If the above is correct, how is it different from simply invoking the function again with slightly different arguments? (supposing no side effects)
• How do you determine at which point in the call stack the entry point is, is it necessarily the current function? That will determine how much of the current state needs to be stored
• Why is it called continuation and not replay?

I have been reading up on row/record polymorphism (thanks to Andreas and Daniel for the pointers), but so far I haven't seen anything which apply the concept of a row variable to tuples.

If I understand my theory correctly, record types without labels are in fact tuples (or product types if you prefer). So if you have a row without labels, what would that be? An "unlabeled row"?

Viewed from another angle, I want to describe tuples with row variables. The nitty gritty of the whole thing is that I am working on devising an acceptable way to describe stack configurations using type theory.

A stack with an integer on top, and anything else on the bottom can be described as:

  T = int * A 

where A is the "unlabelled row variable". Perhaps these are examples of "stack types" or I could call them "column types" to distinguish them from rows?

Any ideas or suggestions would be much appreciated!

Here is a simple idea intended to plug a few semantic holes in the imperative programming style. The idea is to provide a full proof way to handle mutable state in imperative programs. Basically we want to introduce a class called an ASTB or applicative state transition block. The definition is simple. We will need four data structures: a read only state, and a write only temporary state a structure to hold the input and one for the output. There seem to be six external methods: a driver that provides an input and starts the computation of the new state, and returns the output on completion. A constructor and a destructor, and a method to read the state and output at any time. We need one more external method to initialize the state. This is a little more tricky so we will provide some sort of security, and only allow update when a transition is not in progress (some sort of mutex lock).

Internally the object does the following: when an input is supplied a series of functions compute new state values and output values and puts them in the temporary state data structure, and the output data structure. Internally there is a method that has permission to transfer the temporary state to the state when the output is returned. That seems to be enough to do the job, although we might also want a temporary output, and an output, and transfer that on completion with a lock. This wouldn't be needed if we output through the driver return value.

There is certainly nothing new about this and we suspect that there are patterns for doing this. The point is that we want to make the case that there are sound ways to handle state, get comments, and perhaps encourage a little more attention to these issues.