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.