A Gorn address is a method of identifying and addressing any node within a tree data structure, introduced by American computer scientist Saul Gorn in 1967. It is a sequence of zero or more integers conventionally separated by dots, such as 0 or 1.0.1. The notation is often used for identifying nodes in a parse tree defined by phrase structure rules, where each address uniquely encodes the path from the root to a specific node.
The root of the tree, which Gorn called *, is regarded as the empty sequence. For any node with address i, its j-th child (counting from 0) has the address i.j. For example, in a tree where the root has children 0, 1, and 2, the address 1.0 refers to the first child of the second child of the root. This recursive definition allows addresses to grow arbitrarily long as the tree deepens, with each integer in the sequence indicating the child index at the corresponding level.
Formal Definition
Formally, a Gorn address is a finite sequence of non-negative integers, often written as a1.a2....an where each ai is an integer. The empty sequence, denoted by * or an empty string, represents the root. The address of a node is constructed by concatenating the address of its parent with the child index, separated by a dot. This scheme is unambiguous: every node in a tree has exactly one Gorn address, and every valid address corresponds to exactly one node, provided the tree is finite and each node has a well-defined number of children.
The notation is particularly useful in formal language theory and computational linguistics, where parse trees are generated by phrase structure grammars. In such trees, each internal node corresponds to a nonterminal symbol, and its children correspond to the symbols in a production rule. Gorn addresses provide a compact way to refer to specific subtrees or leaves, enabling algorithms to traverse or manipulate tree structures without explicit pointers.
Applications in Computer Science
The primary application of Gorn addresses is in the representation and processing of syntax trees, especially in natural language processing and compiler design. In compilers, abstract syntax trees (ASTs) are often annotated with Gorn addresses to facilitate error reporting, debugging, and code generation. For instance, a compiler might report an error at address 2.1.0, indicating a specific leaf node in the AST.
Gorn addresses also appear in artificial intelligence and machine learning research, particularly in symbolic AI and knowledge representation. They are used to index nodes in decision trees and grammars, where each path from the root to a leaf represents a unique rule or classification. In deep learning, tree-structured neural networks, such as tree LSTMs, sometimes use Gorn addresses to align outputs with tree positions.
Relationship to Other Tree Addressing Schemes
Gorn addresses are one of several ways to identify nodes in a tree. Alternatives include heap indices (used in binary heaps, where the root is 1 and children of node i are 2i and 2i+1), XPath paths (which use element names and predicates), and Lisp S-expressions (which use nested lists). Unlike heap indices, Gorn addresses are not tied to a fixed arity; they work for trees where nodes have varying numbers of children. Unlike XPath, Gorn addresses are purely positional and do not depend on node labels, making them simpler but less descriptive.
The notation is also related to Unix file paths in that both use a hierarchical sequence of identifiers, but Gorn addresses use only integers and a dot separator, whereas file paths use names and slashes. This integer-based scheme is advantageous when the structure is known but labels are not, or when labels are redundant.
Historical Context and Influence
Saul Gorn introduced the address notation in his 1967 paper "Explicit definitions and linguistic dominoes," published in the proceedings of a symposium on systems and computer science at the University of Toronto. Gorn was a pioneer in computer science education and programming languages, and his work on tree addressing influenced later developments in data structures and formal language theory. The term "Gorn address" is now standard in textbooks on compiler design and parsing, though it is sometimes referred to simply as a "tree address" or "path string."
Despite its age, the notation remains relevant in modern systems. For example, XML and JSON processing tools often use similar positional addressing for debugging, and some databases use Gorn-like addresses for indexing hierarchical data. In programming language theory, Gorn addresses are used in attribute grammars to specify where attributes are computed.
Limitations and Extensions
One limitation of Gorn addresses is that they assume a fixed child ordering, which is natural for parse trees but may not hold for unordered trees. In such cases, addresses are still valid but may not be stable across different orderings. Another limitation is that addresses can become long for deep trees, but this is rarely a practical issue.
Extensions to Gorn addresses include using negative integers to denote special nodes (e.g., a virtual root) or using a different separator for readability. Some systems use a variant where the root is 0 instead of the empty sequence, but this is not standard. The notation is also sometimes combined with labels, as in NP.0.1, where NP is a node label, but this is an informal extension.
In summary, the Gorn address is a foundational concept in computer science, providing a simple, unambiguous way to reference nodes in a tree. Its use in parse trees and compilers has made it a lasting tool, and it continues to appear in modern research and applications involving hierarchical data.