Spaghetti Stack

"The continuation that obeys only obvious stack semantics, O grasshopper, is not the true continuation."

A Spaghetti Stack is a stack structure in which the frames that are pushed onto the stack are not destroyed when they are popped. Instead, they persist indefinitely, and continue to refer to the parent frames. They can be re-visited and popped again.

This idea may be familiar to some people who have written C compilers. When scanning a statement block scope, you push a symbol table which points to the parent symbol table. This creates a Lexical Scope. When the block terminates, the symbol table is popped from the stack---but references to it remain in the constructed parse tree, and it keeps a pointer back to the parent!

Spaghetti Stacks are used at run-time in languages that support Call With Current Continuation. They allow control to return to a frame that has previously executed and returned. The elements of the Spaghetti Stack are dynamically allocated objects that are subject to garbage collection, rather than a flat array of memory with a moving pointer.

If an implementation of the C language were equipped with a Spaghetti Stack, it would become legal to save a context with setjmp() in some function, return from that function and then jump back in with a longjmp(), then return from that function again!

In the Scheme Language, this kind of jumping around is done with continuations. There is even a special construct for winding and Unwinding The Stack called dynamic-wind, by which one can indicate some set-up actions to be done on the way down, and clean-up actions on the way up. These are invoked repeatedly, as many times as you go in and out.


See original on c2.com