A spaghetti stack in computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 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

Linked list

In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...

 stack

Stack (data structure)

In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...

. It can be analogized to a linked list having one and only parent pointer called "next" or "link", and ignoring that each parent may 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

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

 for a language such as C

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

 creates a spaghetti stack as it opens and closes symbol table

Symbol table

In computer science, a symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier in a program's source code is associated with information relating to its declaration or appearance in the source, such as its type, scope level and...

s 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

Abstract syntax tree

In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...

, 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.

A similar data structure appears in disjoint-set forests, a type of disjoint-set data structure

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 subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:* Find: Determine which set a particular element...

.

Use in programming language runtimes

The term spaghetti stack is closely associated with implementations of programming language

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

s that support continuation

Continuation

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...

s. 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

Garbage collection (computer science)

In computer science, garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program...

 when no continuations refer to them any longer. This type of structure also solves both the upward and downward funarg problem

Funarg problem

In computer science, the funarg problem refers to the difficulty in implementing first-class functions in stack-based programming language implementations....

s, so first-class lexical closure

Closure (computer science)

In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...

s are readily implemented in that substrate also.

Examples of languages that use spaghetti stacks are:

• Languages having first-class continuations such as Scheme, Standard ML
  Standard ML
  Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
  
  
• Languages where the execution stack can be inspected and modified at runtime such as Smalltalk
  Smalltalk
  Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
  
  
• Felix
• Rust
  Rust (programming language)
  Rust is an experimental, concurrent, multi-paradigm, compiled programming language developed by Mozilla Labs. It is designed to be practical, supporting pure-functional, concurrent-actor, imperative-procedural, and object-oriented styles....