Home » forums » LtU Forum

The replay bug

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?
By Denis Bredelet -jido at 2006-11-18 19:15 | LtU Forum | previous forum topic | next forum topic | other blogs | 5552 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Debugger

Programmers may also understand it this way:

A continuation is like a debugging session.

First you make sure that you have a fixed data set (same data file, same random seed) so that all executions of the program are the same.

Then you execute the program until the point you are trying to debug. There you examine the content of registers, of variables. You go forward one step at a time.

If you notice a value is off, you may bookmark the current execution position and replace the value that seems more correct to you. Then resume execution to see if the final result is the one you expected in the first place.

The bookmark is the continuation, and the replaced value is the parameter of the continuation. You can repeat the setting of the value and the resuming of the program as many times as you like, that is invoke the continuation.

Same remark applies that a continuation is for a single function not a whole program. But it can help to pass the idea.

By Denis Bredelet -jido at Sat, 2006-11-18 19:25 | login or register to post comments

Umm, no

Of course continuations are used for a single function, not for a whole program like the punched card description.

No. Undelimited continuations are (a functional representation of) the entire rest of the computation of the program.

Functions written in CPS take a continuation as an argument because the language is functional. The current continuation could as well be stored in a mutable register instead, using "call/cc" as the getter and function application as the setter.

I swear, continuation analogies are the source of more misunderstandings about continuations than anything else.

By Kevin Millikin at Sat, 2006-11-18 21:55 | login or register to post comments

The current continuation is "Getting Started"

Jido, how are you doing on your reading from the Getting Started thread? What I would recommend is picking a book that seems to suit you, possibly CTM, PLAI, or SICP, and starting to work through it.

It's tempting to cut to the chase and try to understand things like continuations directly in terms of what you already know, but unfortunately experience with languages like Java or Javascript don't by themselves provide the necessary foundations for these concepts. Also, as Kevin points out, analogies are often not helpful. You'll find it much easier to understand and put it all in context once you have even a little of the proper background.

You'll also find that you'll get better responses here if you're clearly making an effort to study the subject seriously, which means reading some of the material that many other members of this site have read. See points 10 and 12 in our site Policies.

By Anton van Straaten at Sat, 2006-11-18 22:56 | login or register to post comments

"Getting Started"

Reading, reading...
From the different comments I can make out that I did not understand continuations clearly yet. Maybe I should restrict my ratiocination to functional programming only, as they seem to be explained more clearly in that context.

By Denis Bredelet -jido at Sun, 2006-11-19 09:50 | login or register to post comments

Continuation passing style

I think I made some progress understanding CPS.
Does it look like that?

def fun1(x, next) = next(x + 5)
def fun2(y, next) = next(printout(y))
fun1(7, lambda(a) = fun2(a, lambda(b) = b))

evaluates ==>

printout(7 + 5)

With a bit of syntactic sugar it could look more like a normal program:

def fun1(x) = x + 5
def fun2(y) = printout(y)
fun1 7 -> a ; fun2 a -> stop!

I think that is what the Io language does...

By Denis Bredelet -jido at Mon, 2006-11-20 12:24 | login or register to post comments

Functional metalanguages

Maybe I should restrict my ratiocination to functional programming only, as they seem to be explained more clearly in that context.

I agree, that's a good idea to start out with. There's a reason that features like continuations are explained more clearly in the functional programming context, aside from the fact that many imperative languages simply can't directly express features such as first-class continuations. The reason is that mainstream imperative programming languages aren't well suited to being used as metalanguages, to provide definitions for programming languages and their features. This is especially true of current OO languages, which have a lot of baggage that's unnecessary for that purpose.

OTOH, a number of functional programming languages were designed for the purpose of being a metalanguage from the start, and most functional languages serve this purpose very well, because of their formal mathematical foundations (e.g. lambda calculus). If you write a language interpreter in a functional language, it's relatively straightforward to write it in such a way that the interpreter itself acts as a theoretical and mathematically sound definition for the language. This is useful for understanding and experimenting with language features, among other things.

So that's why, if you want to learn about advanced programming language features, functional programming is the place to start.

By Anton van Straaten at Tue, 2006-11-21 00:46 | login or register to post comments