# Parent pointer tree > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Parent_pointer_tree > Markdown URL: https://mediated.wiki/source/Parent_pointer_tree.md > Source: https://en.wikipedia.org/wiki/Parent_pointer_tree > Source revision: 1304313250 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Tree data structure}} {{one source |date=May 2024}} thumb|120px|Spaghetti stack with an "active" stack frame highlighted In [computer science](/source/computer_science), an '''in-tree''' or '''parent pointer tree''' is an {{mvar|N}}-ary [tree data structure](/source/tree_data_structure) in which each node has a [pointer](/source/pointer_(computer_programming)) to its [parent node](/source/parent_node), but no pointers to [child node](/source/child_node)s. When used to implement a set of [stacks](/source/Stack_(abstract_data_type)), the structure is called a '''spaghetti stack''', '''cactus stack''' or '''saguaro stack''' (after the [saguaro](/source/saguaro), a kind of cactus).{{Cite book | doi = 10.1145/62678.62692| chapter = Implementation strategies for continuations| title = Proceedings of the 1988 ACM conference on LISP and functional programming - LFP '88| pages = 124-131| year = 1988| last1 = Clinger | first1 = W. | last2 = Hartheimer | first2 = A. | last3 = Ost | first3 = E. | isbn = 089791273X}} Parent pointer trees are also used as [disjoint-set data structure](/source/disjoint-set_data_structure)s. The structure can be regarded as a set of [singly linked list](/source/singly_linked_list)s that [share](/source/structure_sharing) part of their structure, in particular, their tails. From any node, one can traverse to ancestors of the node, but not to any other node. ==Use in compilers== A [compiler](/source/compiler) for a language such as [C](/source/C_(programming_language)) creates a spaghetti stack as it opens and closes [symbol table](/source/symbol_table)s representing block [scope](/source/Scope_(computer_science))s. 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 it remembers its higher level "parent" symbol table and so on. Thus when the compiler is later performing translations over the [abstract syntax tree](/source/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 as call stacks== The term ''spaghetti stack'' is closely associated with implementations of [programming language](/source/programming_language)s that support [continuation](/source/continuation)s. Spaghetti stacks are used to implement the actual [run-time stack](/source/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 present so the function is able to return again. To resolve this problem, [stack frame](/source/stack_frame)s can be [dynamically allocated](/source/dynamic_memory_allocation) in a spaghetti stack structure, and simply left behind to be [garbage collected](/source/garbage_collection_(computer_science)) when no continuations refer to them any longer. This type of structure also solves both the upward and downward [funarg problem](/source/funarg_problem)s, as a result first-class lexical [closure](/source/closure_(computer_science))s are readily implemented in that substrate. Examples of languages that use spaghetti stacks are: * Languages having first-class continuations such as [Scheme](/source/Scheme_(programming_language)) and [Standard ML of New Jersey](/source/Standard_ML_of_New_Jersey) * Languages where the execution stack can be inspected and modified at runtime such as ** [Smalltalk](/source/Smalltalk) ** [Felix](/source/Felix_(programming_language)) ** [Cilk](/source/Cilk) [Mainframe computers](/source/Mainframe_computers) using the [instruction set architecture of the Burroughs B6500 and its successors](/source/Burroughs_B6x00-7x00_instruction_set), running the [MCP](/source/Burroughs_MCP) operating system, can spawn multiple tasks within the same program. Since these were originally [ALGOL](/source/ALGOL_60)-based systems they have to support [nested functions](/source/nested_functions) and the result is that task creation results in a fork in the stack, which [Burroughs](/source/Burroughs_Corporation) informally described as a "saguaro stack.". ==See also== * [Persistent data structure](/source/Persistent_data_structure) ==References== {{reflist}} Category:Trees (data structures) Category:Continuations Category:Metaphors referring to spaghetti --- Adapted from the Wikipedia article [Parent pointer tree](https://en.wikipedia.org/wiki/Parent_pointer_tree) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Parent_pointer_tree?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.