Friday, October 01, 2004

Time travel, programming, long friday afternoons


Old basic joke

10. PRINT BASIC SUCKS
20. GOTO 10

--comp.lang.bashing.basic



Long day here on Friday, and I am so enamoured with the concept of continuations, that I am going to risk trying to explain it, by putting it up on the blog.

Warning: The following stuff is highly technical, but not difficult to understand. It's not a humourous article, but a good explanation of an esoteric programming concept. So, make a choice.

Having got that out of the way, let me try and explain what a continuation is, but before that I will have to explain what a program is.

Programs and their souls

A program is a set of instructions that you give the computer to execute. That's it. It's as simple as that. Advances in modern computing allow gives us leeway in expressing these instructions. So we right now set out only a few broad general policies, rather than the exact, electron wrenching, gate breaking, conductor doping instructions. And the general trend is towards higher, and higher level languages.

But how does it happen?

To understand that we need to examine the stack.

The stack is like a todo list we maintain in our heads, on a piece of paper, or in your cellphone. Where you store it isn't as important as what it actually is. A set of things that you do one by one by one, from top to bottom ( o.k. I work all over the place on my list, but for this article the todo list is just top to bottom).

The instructions that need to be executed are stored in the stack, and are executed, by whatever needs to execute these instructions. Why is it a whatever, and not a processor. Well many high level languages, don't want a moron programmer, to actually get hold of something as valuable as an actual processor. The programmer usually ended up thrashing any valuable resource (e.g. Windows). So the language, or an intermediate program execute the instructions on the stack.

Now consider a stack of instructions for making a sandwich:

1. Get the bread out of the fridge.

2. Pull out knife

3. Slice the bread with a knife.

4. Apply butter on the sliced bread.

5. Eat the sandwich.

Now at step 2 if you are like me, you must be trembling. I can't cut a sandwich for nuts and usually end up slicing off a quite substantial slice of my finger. So let's say you wish your bread were to get sliced magically. You don't care what you did, you just wanted it sliced... Then what....

Enter continuations....

At this point you take what is known as a continuation and stick it into your pocket.

And go on and slice the bread and your finger.

At the end of the bloddy ordeal you pull out the continuation and invoke it.

And voila'. You find yourself exactly at step two, but with all the bread sliced....

And that's what a continuation is....

Most people get confused here. Is it time travel?, is a question that's famously asked.

But I'd like to draw your attention that time by itself is just an interval between two events.

Let's say you were in a room, and I closed the door, and blindfolded you, how do you keep track of time then?

You can't.

Atleast not the way we all know it. Maybe you could count the number of your heartbeats and calculate the elapsed time.

What if you lost that ability too...

What if in a bizzare accident you lost all senses, including the ability to think. What is time then?

The simplicity of a processor

The processor ( by processor I mean all programs that are being executed), are very simple minded as in their view of the world, all of it, is restricted to what they can see on the processor stack.

If I were to put you in a house, and lock the doors, draw the curtains and claim that it was night, all you'd do is to walk out of the house. But if you couldn't.

Then at the absence of all possible information you'd have to assume that this was true. (Of course after 12 hours if it were still night, you'd suspect something was afoot, but that's because you have other information available).

Processers are like that. In this case, which instruction a program is executing on a stack indicates where it is temporally.

Time to a processor is it's location on a stack.

And processors can move both up and down a stack.

This does not mean it's time travel. The more fundamental truth is that time itself is just a basis of space (Einstein said this in one way).

If I were to mark a certain event as a passage of time (let's say water dripping from a jug), then if I did not have any other time keeper, if the interval between two drips grow faster or slower I cannot be certain if they have grown faster or slower. (For more fascinating discussions of this concept try and read up on Hindu reincarnations :) )

The intent of a program

The instruction a processor is executing on a stack, (I'll henceforth call this it's location on the stack), indicates the further intent of the program. It is infact the snapshot of the program, or what it intends to do. A snapshot of the stack at any instant is an intent of what the program probably means to do till the end. Consider the sandwich making stack...

1. Get the bread out of the fridge.

2. Pull out knife

3. Slice the bread with a knife.

4. Apply butter on the sliced bread.

5. Eat the sandwich.

Now instructions 2-4 indicate the intent of making a sandwich.

Instruction 4 is about buttering the sandwich

While 1-5 is the intent of making a sandwich and eating it.

Keep this in mind....

Enough. So what is a continuation anyway...

Well simply put it's the address of that stack location. (Well that's simplifying things a grand deal. It's actually a lexical closure over the stack.). More or less. So when you take a continuation at any point. You are saying what your program will do till the last instruction on the stack is met.

So in the sandwich making example if I were to tak e a continuation at step 2. The continuation consists of the address 3.

The fun thing about this is that all loops are primarily continuations....

Consider this while loop

i=1
while i<5
print i
i=i+1

You can express this in a similiar form

1. i=1
2. take a continuation here and put it in a special place register 1.
3. print i
4. i=i+1
5. goto the line number in register no. 1


Observe here that the value of i is retained through succeeding iterations of the stack. If you were to delcare the value of i after you take a continuation for i, i would get redeclared over and over and over again.

The purists among you, may object to the above code.

In fact I am sure some of you may scream, "It's nothing but a goto".

Well in a way it is...

But in some ways it's not.

So let's look at a few more examples of continuations..

To continue...

Continuations are a concept. This means that like object orientedness, it's just a feature that may or may not be supported by the language, compiler, version, library, so on and so forth.

The difference between a goto and a continuation is that while in a goto (no pun intended), the main stack is itself changed, in a continuation the contents of the stack are copied, and stored in another location on the stack. Since so many stacks can get confusing, computer scientists use the term 'frame'. The frame indicates the remainder of the stack upto the end of that scope/block. Who! What do I mean by that????

Consider the following pseudocode:

{
i=1; //Outer scope
print i;

{
j=2 // Inner scope
j=j+1; // j=3
i=i+1 //i=2
print j;
}

print j; // undefined j
print i; // 2
}

In the above example, the variable i can be accessed in the inner scope, the commands within the inner set of braces, but the value j cannot be accessed in the outer scope. Scoping is a nice mechanism for making sure you don't run out of variable names (besides other things). So consider the stack

1. set i,1
2. print i
3. make new stack
4.start new scope
5. set j, 2
6. j=j+i
7. i=i+1
8 print j
9. remove j
10. close scope
11. print j
12. exit

Any two instructions, and the instructions between them can constitute a frame, but usually a frame for purposes of understanding is a contiguous block of instructions that can be executed, without doing any branching. So 5-9 constitutes a frame. If we were to write this with gotos, the instructions would look something like this.

1. set i,1
2. print i
3. goto line no. 6
4. print j
5. exit
6. set j,2
7. j=j+1
8. i=i+1
9. print j
10. remove j
11. goto step 4.

So the actual stack contents are not modified but traversed in a completely confusing way. If you were to draw lines indicating the flow of instructions processed, it would look like one of the connect-the-dots pictures after a little too much white rum. In fact, it would look like spaghetti and that is what is known as sphaggeti programming, programming with too many gotos.

But with continuations this is what happens.

Frame 1:
1. set i,1
2. print i
4. execute the continuation stored in place B.
5. take a continuation and store it in place A,.
5. end


Place A (Storing the frame)
1. print j
2. end

Frame 2:
1. Take a continuation here and store it in place B
2. set j,2
3. j=j+1
4. i=i+1
5. print j
6. execute the continuation stored in Place A.

Place B (Storing the frame)
1. set j,2
2. j=j+1
3.i=i+1
4. print j
5. execute the continuation stored in Place A.

In the case of continuations, the main stack is over written with these frames, and the executing program/processor keeps swapping in frames back and forth.

Some of you may say, "Hey! a continuation is nothing but a subroutine".

Well, you wouldn't be wrong. It is. Just an orderly way of representing subroutines and the flow of a program. Previously the entire program was just tossed onto the stack, in a haphazard manner, but here the stack is neatly divided into frames, and everything looks cool.

You may also observe that there are a lot of places that the frames/continuations seem to be getting stored, that are global to the entire scheme of things. This could be the stack.

Notice also that frame 2 can access i, while frame 1 cannot access j. I will explain the advantages of that with another example.

O.K. That's a lot more confusing than the normal goto stack, but here's the deal. While programming complex loops with gotos is nearly impossible, continuations make possible a huge load of nearly impossible things. Resumable functions, co-routines, very light OS independent threading, and design patterns that are scrumptious....

Last examples....

So what stuff can be solved with a continuation. Consider this resumable function. I want this function to return a new value every time it's called, but without using a static variable. How do I do it.

function a{
i=1;
return a_continuation_from_this_point_to_the_end_of_this_function;
return i++;
}

get_the_continuation=a();

...do some other stuff...

execute get_the_continuation;


The a_continuation_from_this_point_to_the_end_of_this_function returns the frame upto the end of the function. The frame also contains the variable i, and also the code to increment the value of i.

The first time the function is called, the continuation is returned.

Every time the continuation is executed, the frame is pasted onto the stack, which is literally equivalent to jumping back into the function.

And each time the continuation executes, the value of i is incremented and returned, over and over again.

This is better than the one with static variables because
1. space is not wasted holding onto a static variable.
2. once the get_the_continuation variable is dropped, the associated frame can also be dropped saving memory.
3. the implementation is simply an order of magnitude easier.

So that's a continuation ladies, gents and wild programmers... I have written it out in simple pseudocode instead of actual real world examples involving Ruby, but that's a good thing, since this is meant to be a gentle introduction to it. Not an encyclopedia.

Conclusion:

There's a lot more to continuations than just this. In fact, it's one of the hottest research areas, in language design, and also spirituality.Just google for continuations to learn more about this concept, that in it's very simplicity, essence, and advancement is truly indistinguishable from magic.

Why the heck is it a continuation (The philosophical aspects of it):

It all started with the question.

How does a program exit? ***

At it's very basic, when a program exits, it calls an operating system function to kill it, clean up the mess it's going to leave behind, and that function then calls an OS function which restores control back to the operating system.

The program hasn't ended, or returned to the shell. It's just called another function. In other words, it continues. The program in itself has ceased to exist, but the flow is still taking place.

The death of a program ( end doesn't sound as dramatic), is not an end in itself. At it's very core, the program hasn't ended, there is no break, between the existence of a program, and it's non-existence. The program passes from being to gorily undead, it's shifted form, but nothing stops (well, atleast for well behaved programs). The OS continues, the cycle of life, and death, as the OS itself goes from being sunnily alive (when the system is idle), to completely dead (when another process is alive). When you think about that long and hard, you will realize that it's the same dance of life and death,the tandav, that is best exemplified, in other schools of programming, among them Zen and Hinduism.**

Old programs never die, they just continue....

Footnotes:

*** Well, it actually started of with a question about lambda calculus
** The ones I am familiar with. Please mail me if you want to talk about this and other metaphysical concepts in other releigons.

3 Comments:

At 11:27 AM, Anonymous Anonymous said...

Hey,

Nice long articel... Didnt read it fully... But I guess it is an indication of your workload at TCS :-)

So, how are you doing da, generally?

Venkat

 
At 7:48 PM, Anonymous Anonymous said...

I haven't read your article entirely but merely wanna tell you this: if youre interested in Continuations, you should probably use the mother-of-the-continuations-concept-language: Scheme.

I notice you haven't mentioned Scheme which is why I comment here. Scheme has some very pretty continuations and it'll help you understand it better. Plus, you'll have a better representations.

Warning: A language like Scheme has a sharp learning curve (though the enlightenment is well worth it) and terms like `scope' etc., have a much deeper meaning.

 
At 12:26 PM, Blogger Just Me said...

I have begun to appreciate the Pg Dn feature on the keyboard and also the auto scroll button on my mouse. This thing nearly put me to sleep without even reading it. But I liked the BASIC joke.

 

Post a Comment

<< Home