Tyranny of the stack

February 22, 2007

The call stack is a communication medium between the calling function and the receiver function. If I say “add (1 2)”, I am sending two parameters to the function ‘add’. Those parameters are copied onto the call stack, then the add function immediately get to work on it. Unfortunately, the caller blocks until the receiver returns a response message (in this case ‘3’). The function calls in a program can be arranged as a very complex call graph (that’s what compiler optimizations construct). The call stack, then, is a temporary trace of one path through that graph. A continuation allows you to freeze that trace, so you can restart it whenever you want. With continuations you can jump around in the call graph. However, the call stack and continuations still use a simple stack as the communication channel for sender and receiver functions. In my mind, it is like a linear series of communicating processes, where process A sends a message to process B, which sends a message to C, etc. Then the response messages flow backwards through response queues: C -> B -> A. I don’t know how to embed pictures, but that would probably help folks understand it.

I propose instead that all communication between functions be handled by a queue. This radically changes the semantics of normal programs. When a function is called, the parameters are put on a queue and the sending function does not block. Instead, the sender gets back a reference to a response queue, though the queue will probably only hold one message (would more than one be useful?). If it tries to fetch the response value, that expression will block until the receiver is finished. Why does this matter? Because if you decouple the sender and receiver with a message queue, then you can run both concurrently. That is, a programming language that tweaks the semantics of function calls can instantly become a massively concurrent language. This sounds like something Haskell should have already done. Note that lazy evaluation is different from concurrent evaluation. A lazy evaluation can be aborted: if no one needs the result, don’t bother doing it. A concurrent evaluation will get done, you just don’t know when. I’d prefer to mix the two in a concurrent language. Again, side-effects ruin everything, but Haskell has a work-around with monads. I’ll have to ask around to see if someone has done this.


3 Responses to “Tyranny of the stack”

  1. Letting ‘processed’ communicate by channels/queues is not something new. But it is perfect for ‘horizontal’ scaling: make better use of multi-core systems because each process can run on its own thread (you have to watch out for out of order processing, of multiple threads are executing the same process). And the same technique can be used the make use of a grid.

    I see a lot of code that could be improved by using processes connected by channels: piped algorithms (a sequence of transformations on data) are a perfect candidate for this.

    I have some stuff for this in the sandbox of a concurrency library I’m working on. If you want I can send you the sources. I would like to hear your opinion about.

  2. sorry for the typo’s (10″ laptop and not much light)

  3. projectshave Says:

    You’re right, but my post is describing a radically different programming paradigm where EVERY function is a “process” and EVERY function call is a message sent to a queue. Maybe Oz or Alice does this. I should look it up.

    The problem with Java (and others) is that concurrency is added as a library on top of a single-threaded programming model. You, the poor programmer, have to implement all the concurrency yourself. With my idea, everything is concurrent by default, the compiler optimizes by *removing* concurrency wherever possible.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: