- Spaghetti stack
A spaghetti stack (also called a cactus stack or
saguarostack) in computer scienceis an N-ary tree data structurein 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 nodeby chasing these parent pointers, the structure looks like a linked liststack. 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
compilerfor 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 stackcontaining 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,
Felix programming language
Persistent data structure
Wikimedia Foundation. 2010.
См. также в других словарях:
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. 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