Hedin (2000) -- Reference Attributed Grammars

The paper

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

This page is our reading of it, not a substitute for 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.

Implementation Mapping

Current Usage in Gen Ecosystem

gen-scope (Major — core implementation)

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

• Import edges as reference attributes (S3.1). In gen-scope, import edges stored in decls.__edges.I are reference attributes in Hedin’s sense: they are node identity values (string IDs) pointing to other nodes in the scope graph. The imports attribute (self: id: (self.node id).decls.__edges.I or []) computes these references, which can then be dereferenced to access the target node’s attributes via self.get targetId attrName. This maps directly to Hedin’s formulation: the reference value (node ID) is computed before the target’s attributes, and dereferencing creates non-local dependencies discovered during evaluation. Concrete API: buildNodes { importGraph = engine.edge "host:web" "aspect:networking"; } creates import edges; self.get id "imports" resolves them.

• Cross-node attribute access via computed scope references (S3.2). gen-scope’s self.get targetId attrName is reference dereferencing. When an attribute of node A computes a reference to node B (via import edges, query, or any other mechanism), and then accesses B’s attributes, this creates the non-local dependency described in S3.2. The dependency from B’s attribute to A’s attribute is discovered only when A’s semantic function evaluates the reference. This is exactly the RAG evaluation model.

• Demand-driven evaluation as the RAG evaluator (S3.3). gen-scope leverages Nix’s lazy evaluation as the demand-driven evaluator Hedin describes. Each attribute is a lazy thunk in the _eval cache. First access evaluates the semantic function and caches the result; subsequent accesses return the cached value in O(1). This is precisely the “call the semantic function on first access, cache and return on subsequent accesses” algorithm from S3.3, implemented via Nix’s native laziness rather than an explicit evaluator. gen-scope cannot use static scheduling (OAGs) because import edges create non-local dependencies discoverable only during evaluation — the same fundamental reason Hedin gives for requiring demand-driven evaluation.

• query / queryAll as structured reference traversal (S5.4). The query combinator implements Neron (2015) resolution, but the traversal pattern mirrors Hedin’s PicoJava lookup: search local declarations (D), then imported scopes (I), then parent scope (P), with specificity ordering D < I < P. Import edges are reference attributes; following them during query creates non-local dependencies. The _seen set in query that prevents import self-resolution parallels Hedin’s isCircular guard (S5.5) — both prevent non-termination when reference structures form cycles.

• collectImports and collectionAttr with traverse mode "imports". These combinators aggregate values from imported scopes by following reference attributes. collectionAttr { traverse = "imports"; extract = ...; } traverses all import edges (reference attributes), dereferences each target, extracts attribute values, and combines them. This is a generalized version of Hedin’s virtual function attributes (S4.1) where the “function call” is the aggregation and the “unbounded fan-in” comes from multiple nodes importing the same target.

• followEdge for custom reference labels. gen-scope extends Hedin’s reference attributes beyond the P/I vocabulary to arbitrary labeled edges (van Antwerpen 2018). followEdge label self id accesses decls.__edges.${label}, returning reference attribute targets. This generalizes RAG references to a multi-label scheme while preserving the core semantics: compute reference, dereference, discover dependency.

• Concrete files/functions: eval (entry point, wires demand-driven evaluation), buildNodes (constructs nodes with import edges as reference attributes in decls.__edges.I), _eval (memoization cache implementing S3.3 caching), query/queryAll (structured reference traversal), collectImports (import-edge aggregation), followEdge (custom-label reference access), shadow (resolution specificity).

gen-graph (Minor — structural queries over reference-linked graphs)

gen-graph’s accessor-based queries operate over graphs where edges may be gen-scope import edges (reference attributes). When wired as edges = id: result.get id "imports", gen-graph traversals (reachableFrom, canReach, pathsBetween) follow reference attribute chains. The accessor pattern means gen-graph never stores reference values itself — it queries through gen-scope’s memoized evaluation, preserving the demand-driven property.

gen-select (Minor — pattern matching over reference-reachable positions)

gen-select’s adapters.scope.mkContext bridges gen-scope’s reference-attribute-based graph into selector matching. The within combinator (ancestor matching) walks P edges; has (child matching) walks synthesized children. Import edges are accessed via the context’s data accessor. Selectors compose predicates over the reference-linked graph without directly implementing RAG semantics.

Relevance to Den v2 HOAG Pipeline

Den v2 is a demand-driven HOAG over scope graphs. Reference attributes are the mechanism that makes cross-scope visibility work:

• Import edges ARE reference attributes. When den’s edge aspect effect adds an import edge from the current scope to an aspect node, it creates a reference attribute in Hedin’s sense. The scope node stores the target’s identity (node ID string) in decls.__edges.I. This reference can be dereferenced later to access the aspect’s attributes — its resolved content, its class modules, its collection data. The dependency from the importing scope’s output to the aspect’s content is non-local and discovered during evaluation, exactly as Hedin describes.

• Cross-entity provides are reference attribute lookups. When a user scope provides data to its parent host scope (the provides mechanism), the host accesses user-contributed values by following reference attributes. The host scope’s import edges reference aspect nodes that aggregate user contributions. Dereferencing these references during the host’s attribute evaluation creates the non-local dependency chain: host output depends on user attribute, discovered via reference resolution, not threaded through intermediate environments.

• Pipe gather is reference-based collection. Den’s pipe.gather pred traverses the scope graph collecting data from matching scopes. Each hop follows edges (reference attributes), and each data extraction dereferences the target scope’s attributes. This is a generalized version of Hedin’s PicoJava lookup (S5.4), where instead of searching for a single name, the pipe collects all matching values along reference paths. The D < I < P specificity ordering controls which contributions shadow which.

• Scope graph replaces aggregate environments. Den v1’s pipeline threaded context as aggregate attribute values (scope identifiers, entity records) through handler chains — precisely the “environment” pattern Hedin criticizes (S2.2). Den v2 replaces this with reference attributes: each scope node holds references (import edges) to the scopes it depends on. Properties are accessed via dereferencing, not via replicated environments. This eliminates the four problems Hedin identifies: no information replication (references, not copies), no aggregate complexity (the graph IS the structure), easy extensibility (adding an attribute to a node makes it available to all referencing nodes without changing intermediate threading), and better incrementality (changing a node’s attribute only affects nodes that dereference it).

• Virtual function attributes as paramAttr. gen-scope’s paramAttr f self id param (Sloane 2010 S3) corresponds directly to Hedin’s virtual function attributes (S4.1). In den v2, when a pipe stage needs to query a scope with parameters (e.g., gather with a specific filter predicate), this is a virtual function attribute call: the target scope’s attribute accepts a parameter and returns a computed result. The unbounded reference fan-in that motivates virtual function attributes in RAGs applies directly: many scopes may import the same aspect, each calling its parameterized attributes with different arguments.

• SEMEnv pattern as scope node topology. Hedin’s SEMClassStaticEnv and SEMClassClassEnv nodes, with their blk, superE, thisE, and outerE reference attributes connecting different resolution paths, maps to den v2’s scope node topology. A host scope node connects to its aspect nodes (import edges), its user nodes (parent-child), and its class outputs (terminal attributes). The lookup function that traverses these connections — first class-local, then inherited, then outer — parallels den’s D < I < P resolution over the scope graph.

• Constant semantic nodes as sentinel scopes. Hedin’s SEMMissingDecl and SEMUnknownType constant nodes (S5.2) correspond to den’s handling of missing or unresolved references. When a scope query returns no result (no matching declaration), den can provide a sentinel node with well-defined default attributes rather than propagating null, following the null-object pattern Hedin advocates.

Appendix: Follow-up Work

Unexploited Ideas

• Table translation as a debugging/analysis tool (S3.4). The table translation produces a global allCt array containing all node attributes. gen-scope does not maintain such a global table (it distributes caches via _eval). A debugging mode that constructs the equivalent of allCt — a materialized snapshot of all node attributes at a point in time — could enable global dependency analysis, visualization of the complete attribute state, and detection of attribute values that depend transitively on cyclic reference paths.

• Substitution translation for reference-free snapshots (S3.4). The substitution translation inlines referenced attribute values. For finite, acyclic reference subgraphs, this could produce a “flattened” view of a scope’s resolved state — all referenced values inlined into a single attrset with no remaining references. Useful for serialization, caching, or exporting scope state to non-graph-aware consumers.

• Static non-circularity checking (S8, Conclusion). Hedin identifies static non-circularity checking for RAGs as an open problem. APPLAB discovers circular dependencies at evaluation time, as does gen-scope (via Nix’s infinite recursion error or evalDebug’s cycle tracing). A static analysis that examines attribute definitions and reference patterns to prove non-circularity before evaluation would prevent a class of evaluation-time failures. This requires analyzing which attributes create references and which dereference them, then checking that no circular dependency can arise from any combination of reference resolutions.

• Incremental RAG evaluation (S8, Conclusion). Hedin argues RAGs are a better starting point for incremental evaluation than canonical AGs because aggregate attributes are eliminated. When a declaration changes, only nodes that hold references to it (via reference attributes) need re-evaluation, not every node carrying an environment attribute. gen-scope does not support incremental evaluation (Nix has no thunk invalidation mechanism), but the principle that reference-based dependencies are more precise than environment-based dependencies is exploitable if Nix gains incremental evaluation capabilities.

• Graph-based grammars (S8, Conclusion). Hedin sketches extending RAGs to work on syntax graphs rather than syntax trees, relevant for diagram-like languages (UML class diagrams, state machines). Den’s scope graph is already a graph (not a tree) due to import edges, so this direction is partially realized. The unexploited aspect is working with input that is inherently graph-structured — e.g., allowing a den configuration to express cyclic dependencies between aspects that the evaluator resolves via reference attributes and fixpoint iteration.

• Semantic nonterminals with extension modules (S8, Conclusion). Hedin proposes allowing semantic nonterminals and nodes to be added in extension modules without modifying the base context-free syntax. gen-scope’s attribute system is already extensible (callers define all attributes), but there is no mechanism for dynamically adding semantic child nodes to existing node types without modifying the children attribute definition. An extension-module system for gen-scope would allow libraries to register additional semantic nodes (with their own attributes) onto consumer-defined node types.

Potential New Libraries or Features

• gen-scope: Reference attribute introspection API. Expose the reference-attribute structure of the evaluated graph: for each node, which attributes are reference-valued, what nodes they point to, and what non-local dependencies exist. This would implement the “syntax graph” view Hedin describes in S3.2 (the syntax tree extended with reference edges). API: result.references id returning { attrName = targetId; } for all reference-valued attributes. Scope: small gen-scope extension. Interacts with gen-graph for visualization (reference edges become gen-graph edges) and gen-select for pattern matching over reference topology.

• gen-scope: Flattened scope snapshots via substitution. A result.flatten id combinator that produces the substitution-translation view of a node: all reference-valued attributes replaced by the inlined attribute tuples of their targets, recursively, with cycle detection. Useful for export/serialization scenarios where the consumer needs a self-contained attrset with no remaining scope graph references. Scope: medium. Must handle cycles gracefully (truncation or sentinel values). Interacts with gen-bind (flattened scopes as binding sources) and gen-schema (flattened scopes as instance data).

• gen-scope: Virtual function attribute combinator. A first-class virtualAttr { dispatch; } combinator that implements Hedin’s virtual function attributes (S4.1) with type-based dispatch. Currently, parameterized attributes are modeled via paramAttr (Sloane 2010), but dispatch based on the referenced node’s type (the OO dispatch Hedin describes) requires manual type-casing in attribute definitions. A virtualAttr combinator would automate this: virtualAttr { ClassDecl = self: id: param: ...; VarDecl = self: id: param: ...; }, dispatching on (self.node targetId).type. Scope: small gen-scope extension. Directly implements S4.1-4.2.

• gen-scope: Semantic node extension protocol. Following Hedin’s S8 proposal for extensible semantic nonterminals, a protocol allowing gen-scope consumers to register additional semantic children on existing node types without modifying the base children attribute. Implementation: a semanticChildren attribute registry where extensions contribute child node definitions by node type, merged into the base children output. Scope: medium. Interacts with gen-aspects (aspect modules as semantic node extensions) and gen-derive (rules that inject semantic children based on conditions).

Research Directions

• Formal interaction between HOAGs and RAGs over scope graphs. Vogt (1989) describes tree expansion (NTAs); Hedin (2000) describes cross-tree references (RAGs). gen-scope implements both, but their formal interaction is unexplored. When NTA expansion adds a node with import edges (reference attributes), does this affect the non-circularity guarantee? Can the EDDP (Vogt) be extended to account for reference-path dependencies (Hedin)? A formal treatment could prove soundness of the hybrid HOAG/RAG evaluation that gen-scope and den v2 rely on.

• Static reference-reachability analysis. Hedin notes that the non-local dependency graph can only be determined during evaluation (S3.3). However, conservative over-approximation might be possible: by analyzing which attributes compute references and which dereference them, a static analysis could determine the set of node types potentially reachable via reference chains. This would enable: (a) early detection of unreachable scope nodes, (b) pruning of unnecessary attribute computations, and (c) dependency metadata for build-system-level caching.

• Reference attributes in circular RAGs. Hedin restricts to non-circular RAGs. gen-scope’s circular attribute combinator (Sloane 2010) already supports circular attributes via fixpoint iteration. Extending RAG reference semantics to circular attributes — where a reference target’s attributes may themselves be iteratively computed — is not formally characterized. The interaction between reference dereferencing and fixpoint convergence (does dereferencing a circular attribute always converge? under what conditions?) is an open question with practical implications for den’s pipe gather over circular collection attributes.

• Differential reference analysis for incremental evaluation. Hedin argues RAGs enable better incrementality than canonical AGs (S2.2, S8). If a referenced node’s attribute changes, only nodes that dereference that specific attribute need re-evaluation — not all nodes carrying an environment. Formalizing this as a differential analysis (which attribute changes propagate to which reference-reachable nodes) could guide future incremental evaluation for Nix or Nix-like systems, where thunk invalidation granularity is currently all-or-nothing.

• Reference attributes as the bridge between static and dynamic scope. Hedin’s PicoJava example shows that reference attributes model both lexical scope (Algol-like block structure via SEMClassStaticEnv.outerE) and dynamic resolution (inheritance via SEMClassClassEnv.superE). In den v2, this duality appears as: parent edges (P) model lexical/structural scope, import edges (I) model dynamic composition. A formal characterization of how reference attributes unify static and dynamic scoping could inform den’s resolution policies and provide theoretical grounding for custom edge labels that model additional scoping disciplines.