Spaghetti stack

Spaghetti stack

A spaghetti stack (also called a cactus stack or saguaro stack) in computer science is an N-ary tree data structure in which child nodes have pointers to the parent nodes (but not vice-versa). When a list of nodes is traversed from a leaf node to the root node by chasing these parent pointers, the structure looks like a linked list stack. You can just pretend that the one and only parent pointer is called "next" or "link", and ignore that the parents have other children, which are not accessible anyway since there are no downward pointers.

Spaghetti stack structures arise in situations when records are dynamically pushed and popped onto a stack as execution progresses, but references to the popped records remain in use.

For example, a compiler for a language such as C creates a spaghetti stack as it opens and closes symbol tables representing block scopes. When a new block scope is opened, a symbol table is pushed onto a stack. When the closing curly brace is encountered, the scope is closed and the symbol table is popped. But that symbol table is remembered, rather than destroyed. And of course it remembers its higher level "parent" symbol table and so on. Thus when the compiler is later performing translations over the abstract syntax tree, for any given expression, it can fetch the symbol table representing that expression's environment and can resolve references to identifiers. If the expression refers to a variable X, it is first sought after in the leaf symbol table representing the inner-most lexical scope, then in the parent and so on.

Use in programming language runtimes

The term spaghetti stack is closely associated with implementations of programming languages that support continuations. Spaghetti stacks are used to implement the actual run-time stack containing variable bindings and other environmental features. When continuations must be supported, a function's local variables cannot be destroyed when that function returns: a saved continuation may later re-enter into that function, and will expect not only the variables there to be intact, but it will also expect the entire stack to be there, so it can return again! To resolve this problem, stack frames can be dynamically allocated in a spaghetti stack structure, and simply left behind to be garbage collected when no continuations refer to them any longer. This type of structure also solves both the upward and downward funarg problems, so first-class lexical closures are readily implemented in that substrate also.

Examples of languages that use spaghetti stacks are:
* Languages having first-class continuations such as Scheme,
* The Felix programming language

ee also

* Persistent data structure

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Spaghetti code — is a pejorative term for source code which has a complex and tangled control structure, especially one using many GOTOs, exceptions, threads, or other unstructured branching constructs. It is named such because program flow tends to look like a… …   Wikipedia

  • Spaghetti Junction — is a nickname sometimes given to a complicated or massively intertwined interchange that resembles a plate of spaghetti. Canada* The interchange between Highway 401, Highway 427, Eglinton Avenue, and Highway 27 in Toronto near its boundary with… …   Wikipedia

  • N2/N3 Spaghetti Junction — The N2/N3 Spaghetti Junction near Durban in South Africa has been given various nicknames, the most famous one is the Spaghetti Junction . N3 is the busiest highway in South Africa and is a very busy truck route. Since Johannesburg is not located …   Wikipedia

  • Closure (computer science) — In computer science, a closure (also lexical closure, function closure, function value or functional value) is a function together with a referencing environment for the non local variables of that function.[1] A closure allows a function to… …   Wikipedia

  • Funarg problem — In computer science, the funarg problem refers to the difficulty in implementing first class functions (functions as first class objects) in stack based programming language implementations. The difficulty only arises if the body of a nested… …   Wikipedia

  • Continuation — For other uses, see Continuation (disambiguation). In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e. the… …   Wikipedia

  • Disjoint-set data structure — In computing, a disjoint set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union find algorithm is an algorithm that performs two useful operations on… …   Wikipedia

  • Felix (programming language) — Infobox programming language name = Felix paradigm = year = designer = developer = latest release version = latest release date = latest test version = latest test date = typing = implementations = dialects = influenced by = influenced =… …   Wikipedia

  • Tom Moreland Interchange — from I 85 traveling southbound Spaghetti Junction Location …   Wikipedia

  • Interchange (road) — A high capacity interchange: the Judge Harry Pregerson Interchange in Los Angeles, California, United States …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”