Hedin (2000) -- Reference Attributed Grammars

The paper

G. Hedin, “Reference Attributed Grammars,” 2000.

A summary of the paper and how gen uses it.

Paper Summary

Hedin addresses a persistent limitation of canonical attribute grammars (Knuth, 1968): their inability to express non-local dependencies concisely. In canonical AGs, attributes follow value semantics — all information propagated between distant syntax tree nodes must be threaded through intermediate nodes as aggregate attribute values (typically “environment” dictionaries). This leads to four concrete problems: (1) information replication, where declaration-site data must be copied into environment attributes distributed to all use sites; (2) aggregate complexity, where languages with inheritance, qualified access, and module-level scope rules require increasingly complex composite attributes; (3) poor extensibility, where adding a new property (e.g., declaration mode alongside type) requires modifying all intermediate environment threading; and (4) poor incremental evaluation, since a change to one declaration invalidates environment attributes across the entire tree.

Reference Attributed Grammars (RAGs) solve this by introducing reference semantics: attributes may be references to arbitrary nodes in the syntax tree, and attributes of the referenced node may be accessed via these references. This single extension eliminates the need for replicated aggregate environments. Rather than propagating a dictionary of all declarations to every use site, a use site holds a reference attribute decl pointing directly to the declaration node. Properties of the declaration (type, mode, etc.) are accessed by dereferencing: decl.type. The syntax tree itself, extended with reference attributes, becomes the data structure — no auxiliary environment domain is needed.

Section 3 formalizes RAGs. A reference attribute’s value is the unique identity of the denoted node. Crucially, this identity can be computed before the denoted node’s own attributes are evaluated, so reference attributes do not introduce evaluation-order dependencies on the target’s attributes — only dereferencing does. The dependency graph of a RAG thus has two kinds of edges: local dependencies (same as canonical AGs, between attributes of symbols in a single production) and non-local dependencies (via reference dereferencing, between attributes of nodes arbitrarily far apart in the tree). The non-local dependency from attribute b to attribute a via reference r can only be determined after evaluating r. This means the dependency graph cannot be computed statically before evaluation; it must be discovered during evaluation.

For evaluation, Hedin shows that demand-driven algorithms (where each attribute access calls the corresponding semantic function, with caching for memoization) work directly for any non-circular RAG and are optimal (Section 3.3). Static scheduling algorithms like Ordered Attribute Grammars (Kastens, 1980) are not directly applicable because they require the complete dependency graph before evaluation, which RAGs do not provide. This is the key evaluation result: demand-driven evaluation is both necessary and sufficient for non-circular RAGs.

Section 3.4 provides two translations from RAGs to canonical (but circular) AGs, establishing the formal relationship. The table translation introduces a global array allCt containing all node attributes, replacing reference dereferencing with array indexing. This introduces circular dependencies even for non-circular RAGs, but the resulting grammar is well-defined and evaluable by iterative methods. The substitution translation replaces references by the attribute tuples they denote, which produces infinite attribute values when references form cyclic structures. Both translations demonstrate that RAGs are strictly more expressive in practice than canonical AGs for non-local dependencies.

Section 4 introduces Object-Oriented RAGs (ORAGs) with two extensions. First, virtual function attributes generalize synthesized attributes to accept parameters. In canonical AGs, parameters can be modeled by inherited attributes since each attribute has a bounded number of accesses. In RAGs, a node may be referenced from an unbounded number of sites, so parameterless inherited-attribute encoding is insufficient — virtual function attributes are genuinely necessary. Second, an extended class hierarchy allows abstract nonterminals as supertypes for reference attribute typing, with inheritance, overriding, and factored-out default semantic rules.

Section 5 demonstrates the full power with PicoJava, a subset of Java with classes, inheritance, nested classes, qualified access, and reference assignment. The name analysis builds a graph of SEMEnv nodes connected by reference attributes: SEMClassClassEnv nodes link to the class’s block and to the superclass’s environment; SEMClassStaticEnv nodes combine class inheritance with block structure. The lookup virtual function attribute traverses these connections recursively to resolve names. The type analysis defines tp (type) attributes and a typesCompatible check for assignments that traverses the class hierarchy via recSubclassOf. The entire specification is non-circular, despite the cyclic data structures formed by reference attributes (e.g., mutual references between nodes B and C in the TINY example). The PicoJava example conclusively demonstrates that RAGs handle OO name and type analysis without circular dependencies and without the complex aggregate environments required by canonical AGs.

Key Concepts

• Reference Attributes (S3.1): Attributes whose values are node identities (references to syntax tree nodes). Abandons value semantics for reference semantics. A reference value can be computed before the denoted node’s attributes are evaluated, decoupling identity from content.

• Non-Local Dependencies (S3.2): Dependencies via reference dereferencing. A non-local dependency from attribute b (accessed via reference r) to attribute a exists only after r is evaluated. The dependency graph is discovered during evaluation, not before.

• Demand-Driven Evaluation (S3.3): The evaluation algorithm for non-circular RAGs: each attribute access calls its semantic function, with caching for O(1) subsequent access. Optimal for any non-circular RAG. Static scheduling algorithms (OAGs) are not directly applicable.

• Table Translation (S3.4): Translation to canonical AG via global allCt array. Establishes that RAGs are formally equivalent to a restricted class of circular canonical AGs. The circularity is introduced by the global table, not by the original RAG’s logic.

• Substitution Translation (S3.4): Alternative translation replacing references by attribute tuples. Produces infinite attribute values when reference structures are cyclic. Demonstrates that RAGs’ reference semantics cannot be straightforwardly reduced to value semantics.

• Virtual Function Attributes (S4.1): Parameterized synthesized attributes. Necessary in RAGs because unbounded reference fan-in means inherited-attribute encoding of parameters is impossible. Generalize synthesized attributes: w() (zero params) is equivalent to a synthesized attribute.

• Extended Class Hierarchy (S4.2): Abstract nonterminals as supertypes for reference attribute typing. Default semantic rules with overriding. Rooted single-inheritance hierarchy. Abstract nonterminals are irrelevant for context-free grammar but critical for attribution factoring.

• Semantic Nonterminals (S5.2): Convention for packaging related attributes into dedicated nodes (SEMClassStaticEnv, SEMClassClassEnv, etc.). Provides multiple interfaces on a single syntax node via delegation to semantic children. A reference can target the full node or a specific semantic child depending on the client’s needs.

• Constant Semantic Nodes (S5.2): Null object pattern in AG form. SEMMissingDecl and SEMUnknownType are constant nodes that serve as the reference target when a declaration or type is absent. Eliminates null checks by providing well-typed default behavior.

• Non-Circular OO Name Analysis (S5.4): SEMEnv nodes connected by reference attributes form the scope resolution data structure. Lookup is a virtual function attribute that traverses these connections. The graph of SEMEnv nodes and their reference links can be cyclic, but the dependency graph of attributes remains acyclic.

• Circularity Guard (S5.5): The isCircular attribute detects cyclic class hierarchies (an illegal but syntactically possible structure). Used to terminate recursive lookup functions by redirecting superE to SEMEmptyEnv when a cycle is detected, preventing non-termination.

How gen uses this

gen-scope

gen-scope describes itself as a hybrid HOAG/RAG evaluator. The RAG half implements Hedin’s core ideas.

• Import edges as reference attributes (S3.1). buildNodes stores each node’s labelled edges in decls.__edges, and the import edges under I hold the identifiers of other nodes. These are reference attributes in Hedin’s sense: node identity values that an attribute can dereference with self.get targetId attrName. The reference is computed before the target’s attributes, and dereferencing it creates a non-local dependency found during evaluation.

• Cross-node access through computed references (S3.2). self.get targetId attrName is dereferencing. When an attribute of node A computes a reference to node B, through an import edge, a query or any other means, and reads B’s attributes, the dependency of A on B appears only when A’s semantic function runs. This is the RAG evaluation model.

• Nix as the demand-driven evaluator (S3.3). Each attribute is a lazy thunk in its node’s _eval attrset. The first access runs the semantic function and caches the result, and later accesses return the cached value. This is S3.3’s algorithm, “call the semantic function on first access, cache and return on subsequent accesses”, provided by Nix’s laziness. gen-scope cannot schedule statically (as OAGs do) because import edges create dependencies that are known only during evaluation, the reason Hedin gives for demand-driven evaluation.

• query and queryAll as structured reference traversal (S5.4). query implements Néron (2015) resolution, and its traversal follows the shape of Hedin’s PicoJava lookup: local declarations (D), then imported scopes (I), then the parent scope (P), with specificity D < I < P. Following import edges during a query creates non-local dependencies. query tracks visited scopes in a _seen set to prevent import self-resolution, which parallels Hedin’s isCircular guard (S5.5): both stop non-termination when references form cycles.

• collectImports and collectionAttr. These combinators aggregate values from imported scopes. collectionAttr with the "imports" traversal follows every import edge that the boundary marks at the source admit (the read is the one-letter resolution wf = imports, ADR-0026), dereferences each target, extracts attribute values and combines them. This generalises Hedin’s virtual function attributes (S4.1), with aggregation as the call and fan-in coming from many nodes importing the same target.

• followEdge for other edge labels. gen-scope extends reference attributes beyond parent and import edges to arbitrary labelled edges (van Antwerpen 2018). followEdge label self id returns the targets of the node’s edges-<label> attribute as the one-letter resolution wf = label, so a boundary mark at the node withholds them, keeping the RAG semantics: compute the reference, dereference it, discover the dependency.

• queryReverse reads references backward, gathering the nodes that refer to a target. It is the reverse reference attribute over the same edges.

gen-graph

gen-graph’s accessor-based queries run over graphs whose edges can be gen-scope import edges. With an accessor such as edges = id: result.get id "imports", traversals like reachableFrom, canReach and pathsBetween follow chains of reference attributes. gen-graph stores no references itself. It queries through gen-scope’s memoised evaluation, so traversal stays demand-driven.

gen-select

gen-select’s adapters.scope.mkContext connects a gen-scope graph to selector matching. within (ancestor matching) walks parent edges and has (child matching) walks synthesised children. Selectors compose predicates over the reference-linked graph without implementing RAG semantics themselves.

References in place of aggregate environments

Hedin argues against threading aggregate environments through a tree (S2.2): they replicate information, make aggregates complex, resist extension and hurt incrementality. A gen scope graph holds references instead. Each scope node holds import edges to the scopes it depends on, and properties are read by dereferencing. Nothing is copied, the graph is the structure, adding an attribute to a node makes it available to every node that references it, and changing an attribute affects only the nodes that dereference it.

When an aspect is included in a scope, the scope gains an import edge to the aspect’s node. The scope’s output then depends on the aspect’s content through that reference, a non-local dependency discovered during evaluation. A gather over the graph that collects values from matching scopes is a generalised PicoJava lookup, collecting every match along reference paths instead of one name, with D < I < P deciding which contributions shadow which.

Hedin’s constant semantic nodes SEMMissingDecl and SEMUnknownType (S5.2) are a null-object pattern: a failed lookup returns a node with well-defined attributes instead of a null.

Appendix: Follow-up Work

Unexploited Ideas

• Table translation as an analysis tool (S3.4). The table translation produces a global allCt array of all node attributes. gen-scope distributes its caches across nodes’ _eval attrsets and keeps no global table. A debugging mode that builds the equivalent of allCt, a snapshot of all node attributes, would support global dependency analysis, visualisation of the attribute state and detection of values that depend on cyclic reference paths.

• Substitution translation for reference-free snapshots (S3.4). The substitution translation inlines referenced attribute values. For finite, acyclic reference subgraphs it would give a flattened view of a scope’s resolved state with no remaining references, useful for serialisation or for consumers that do not understand graphs.

• Static non-circularity checking (S8). Hedin names static non-circularity checking for RAGs as an open problem. APPLAB finds circular dependencies at evaluation time, and so does gen-scope, through Nix’s infinite-recursion error or evalDebug’s cycle tracing. A static analysis of which attributes create references and which dereference them could prove non-circularity before evaluation.

• Reference-precise incremental evaluation (S8). Hedin argues that RAGs suit incremental evaluation better than canonical AGs because aggregate attributes are gone. When a declaration changes, only nodes holding references to it need re-evaluation. gen-memo decides reuse over a caller-supplied dependency accessor, and reference edges give that accessor precise dependencies.

• Graph-based grammars (S8). Hedin sketches RAGs over syntax graphs instead of trees, for diagram-like languages. A scope graph is already a graph because of import edges. The unexploited part is input that is graph-structured by nature, such as cyclic dependencies between aspects that the evaluator resolves through reference attributes and fixpoint iteration.

• Semantic nonterminals from extension modules (S8). Hedin proposes adding semantic nonterminals and nodes in extension modules without changing the base syntax. gen-scope’s attributes are defined by callers and so are already extensible. There is no mechanism for adding semantic child nodes to an existing node kind without changing its children definition.

Potential New Libraries or Features

• Reference introspection in gen-scope. Expose which attributes of each node are reference-valued, which nodes they point to and what non-local dependencies exist, the “syntax graph” of S3.2 (the tree extended with reference edges). For example result.references id returning { attrName = targetId; }. The result would feed gen-graph for visualisation and gen-select for matching over reference topology.

• Flattened scope snapshots. A result.flatten id that produces the substitution-translation view of a node: every reference-valued attribute replaced by its target’s attributes, recursively, with cycle detection. It must handle cycles, by truncation or sentinel values. Flattened scopes could serve as gen-bind binding sources or gen-schema instance data.

• Virtual function attributes with dispatch. A parameterised attribute is written as a function of its parameter. Dispatch on the referenced node’s type, the OO dispatch Hedin describes, still needs manual case analysis. A virtualAttr { ClassDecl = self: id: param: ...; VarDecl = self: id: param: ...; } combinator dispatching on (self.node targetId).type would implement S4.1-4.2 directly.

• Semantic node extensions. Following Hedin’s S8 proposal, a registry where extensions contribute child node definitions by node kind, merged into the base children. Aspect modules and gen-dispatch rules could then add semantic children under conditions.

Research Directions

• The interaction of HOAGs and RAGs over scope graphs. Vogt (1989) describes tree expansion with NTAs, and Hedin (2000) describes references across the tree. gen-scope implements both, and their formal interaction is open. When NTA expansion adds a node with import edges, does non-circularity still hold? Can Vogt’s EDDP account for dependencies along reference paths? A formal treatment would establish soundness of hybrid HOAG/RAG evaluation.

• Static reference-reachability analysis. Hedin notes that non-local dependencies are known only during evaluation (S3.3). A conservative over-approximation from which attributes compute references and which dereference them could give the node kinds reachable through reference chains. That would allow detecting unreachable nodes early, pruning unneeded attribute computations and producing dependency metadata for caching.

• References in circular RAGs. Hedin restricts to non-circular RAGs. gen-scope’s circular combinator (Sloane 2010) supports circular attributes by fixpoint iteration. When a reference target’s attributes are themselves computed iteratively, whether dereferencing always converges, and under what conditions, is not characterised.

• Differential reference analysis. If a referenced node’s attribute changes, only the nodes that dereference that attribute need re-evaluation. Formalising which attribute changes reach which reference-reachable nodes would sharpen the dirty set an incremental evaluator such as gen-memo computes.

• References bridging static and dynamic scope. PicoJava’s reference attributes model both lexical scope (block structure through SEMClassStaticEnv.outerE) and dynamic resolution (inheritance through SEMClassClassEnv.superE). In a scope graph, parent edges model structural scope and import edges model composition. A formal account of how references unify the two would ground custom edge labels that model further scoping disciplines.