Spaghetti Stack

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

A SpaghettiStack 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 LexicalScope. 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!

SpaghettiStacks are used at run-time in languages that support CallWithCurrentContinuation. They allow control to return to a frame that has previously executed and returned. The elements of the SpaghettiStack 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 SpaghettiStack, 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 SchemeLanguage, this kind of jumping around is done with continuations. There is even a special construct for winding and UnwindingTheStack 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 CallWithCurrentContinuation, ContinuationExplanation CategoryContinuation