Vogt et al. (1989) -- Higher-Order Attribute Grammars

The paper

H. Vogt, S. D. Swierstra, and M. Kuiper, “Higher order attribute grammars,” PLDI89: Programming Language Design & Implementation, pp. 131–145, 1989.

doi:10.1145/73141.74830 · read the paper

A summary of the paper and how gen uses it.

Paper Summary

Vogt, Swierstra, and Kuiper address a fundamental limitation of classical attribute grammars (AGs): the rigid separation between the structure tree (built by the parser) and the attributes (computed during evaluation). In conventional AGs, the parse tree is fixed before semantic analysis begins, which means multi-pass compilation — where intermediate representations are constructed, transformed, and re-analyzed — cannot be expressed naturally within the AG formalism. Programmers must resort to encoding intermediate languages as attribute values and manually threading them through semantic functions, producing specifications that are difficult to write and harder to understand.

Higher-Order Attribute Grammars (HAGs) remove this boundary by introducing non-terminal attributes (NTAs): attributes whose values are themselves structure trees. During attribute evaluation, when an NTA is computed, the parse tree is expanded at the corresponding leaf — the virtual non-terminal is replaced by the computed subtree, which then becomes part of the attributed tree and participates in further attribute evaluation. The term “higher order” is chosen by analogy with higher-order functions: just as a higher-order function can return or accept functions, a higher-order AG can compute and consume tree structures as attribute values.

The paper formalizes HAGs by extending the standard AG definition (Definition 3.1) with NTAs (Definition 3.7), virtual vs. instantiated non-terminals (Definition 3.8), labeled trees with virtual leaves (Definition 3.9), and correct typing of NTA semantic functions (Definition 3.10). The Attribute Evaluation Algorithm (Figure 13) extends the classical work-list algorithm from Knuth (1968) and Reps (1982) with a tree-expansion step: when a selected work-list item is an NTA, the labeled tree is expanded at the corresponding virtual leaf, new dependency edges and attribute instances are added to the work-list, and evaluation continues.

Two correctness concerns arise. First, an NTA must not depend on its own synthesized attributes — those are only available after expansion. The paper handles this by defining Extended Direct Dependency Predicates (EDDP, Definition 3.12), which add synthetic dependencies from each NTA to all synthesized attributes of its non-terminal, ensuring that expansion precedes attribute computation on the expanded subtree. Lemma 3.1 proves that every virtual NTA will be computed if and only if the EDDP-augmented dependency graph remains acyclic during evaluation. Second, the tree must not expand indefinitely. Lemma 3.2 provides a sufficient condition: if on every path in every structure tree a particular NTA occurs at most once, expansion is finite. This amounts to requiring that each NTA roots a “non-recursive” separate context-free grammar — a decidable property (polynomial in the grammar size).

Theorem 3.2 combines these into the well-definedness criterion: a HAG is well-defined if it is complete, no partial tree contains EDDP-cycles, and NTAs satisfy the finite-expansion condition.

For efficient evaluation, the paper reduces a HAG to an ordinary AG (Definition 4.1) by replacing NTA occurrences with inherited attributes (X.atree). Theorem 4.1 shows that if the reduced AG is an Ordered Attribute Grammar (OAG, per Kastens 1980), then the HAG is ordered. Visit-sequences for the HAG (HVS, Definition 4.3) are derived from the OAG visit-sequences by mapping X.atree evaluations to NTA expansion instructions. The entire check — reduction, OAG test, visit-sequence derivation, finite-expansion check — runs in time polynomial in the grammar size.

The running example throughout is a four-step compiler for expressions in an Algol68-like language: parsing, operator-precedence restructuring, type checking with coercion insertion, and code generation. Each step produces an intermediate structure tree consumed by the next, demonstrating that HAGs naturally express multi-pass compilation as a single unified specification.

Key Concepts

• Non-Terminal Attributes (NTAs): Attributes whose values are parse trees derivable from the attribute’s non-terminal. During evaluation, the virtual non-terminal leaf is replaced by the computed tree, which is then attributed. (S2.4, Definition 3.7)

• Virtual vs. Instantiated Non-Terminals: A virtual NTA is an unevaluated leaf (depicted as an open circle); once its defining semantic function fires, it becomes an instantiated non-terminal (a filled circle) with a fully expanded subtree. (Definition 3.8)

• Tree Expansion During Evaluation: The Attribute Evaluation Algorithm extends the standard work-list algorithm: evaluating an NTA triggers tree expansion, adds new attribute instances and dependencies, and extends the work-list. (Figure 13)

• Extended Direct Dependency Predicates (EDDP): For each NTA X in a production, all synthesized attributes of X are made dependent on X itself. This prevents an NTA from depending on attributes that only exist after its own expansion. (Definition 3.12, Lemma 3.1)

• Finite Expansion Condition: If no NTA occurs twice on any path in any structure tree, expansion terminates. Equivalently, each NTA roots a non-recursive context-free grammar. This is decidable in polynomial time. (Lemma 3.2)

• Well-Definedness Theorem: A HAG is well-defined if complete, EDDP-acyclic for all partial trees, and satisfying the finite expansion condition. (Theorem 3.2)

• Reduction to OAG: A HAG is transformed into a conventional AG by replacing NTAs with inherited attributes. If the reduced AG is Ordered (Kastens 1980), the HAG is ordered. (Theorem 4.1)

• Visit-Sequences for HAGs (HVS): Derived from OAG visit-sequences by mapping X.atree evaluations to expansion instructions. The expansion-then-visit discipline ensures that no descendant of a virtual non-terminal is visited before instantiation. (Definition 4.3)

• Bounded Well-Definedness: Allows recursive NTA expansion (factorial example), giving the power to define recursive functions in the AG, but finite expansion is no longer guaranteed. (S3.3)

• Term Language / Signatures: Structure trees are represented as terms in a signature-generated term language, providing the linear notation used in semantic functions to construct NTA values. (Definitions 2.1—2.3)

How gen uses this

gen-scope

gen-scope evaluates attributes over a graph whose nodes can themselves be computed by attributes, Vogt’s NTA concept. It has three such channels:

• children as NTA (S2.4): the children attribute on a scope node is a synthesized attribute whose value is a set of new nodes. Each returned child gets a co-located _eval cache (the CachedAttribute of Sloane 2010) and becomes a fully attributed node. This is S2.4.1 (“Part of the structure tree := attribute value”): the tree structure is a computable attribute, expanded on demand.

• derived-children as a second stage (extends S2.4): derived-children can read attributes of the nodes children produced. In Vogt’s formalism the EDDP makes a child’s synthesized attributes available only after expansion, and this stage respects that by running after the first-stage children exist. A spawned child’s kind must be one its host’s kind declares in below, and below names only kinds registered earlier, so each spawn descends and expansion is finite (the ordering technique of Krishnan & Van Wyk 2012).

• nta-children: a third channel for children computed from the host’s own value. Its expansion is not guaranteed finite, the case of Def. 3.14 (“finite expansion of the structure tree, however, is no longer guaranteed”), and a cycle through it that no circular attribute covers ends in Nix’s infinite-recursion error. gen-scope’s debug evaluator (evalDebug) reports such a cycle by name.

• Demand-driven evaluation replaces visit-sequences: where the paper derives visit-sequences (HVS, Definition 4.3), gen-scope uses Nix’s lazy evaluation as the scheduler. A child’s synthesized attribute is computed only when demanded, which cannot happen before the child exists, so the EDDP constraint holds automatically. The _eval cache gives O(1) amortized access once an attribute is computed, without explicit traversal scheduling.

• Related combinators: eval (entry point), buildNodes (root construction from algebraic graph primitives), parseParent (recovers a node’s parent from its id), inherit' (inherited attributes), circular (fixpoint attributes), collectionAttr (aggregation across the structure).

Further directions

Unexploited Ideas

• Explicit visit-sequence derivation (S4.2, Definition 4.3). gen-scope relies entirely on Nix laziness for evaluation order, which is correct but opaque. The paper’s HVS derivation algorithm produces an explicit traversal schedule that could be used for: (a) static analysis of attribute dependencies before evaluation, (b) parallel evaluation scheduling (the paper’s conclusion mentions parallel evaluation research at Utrecht), and (c) better error diagnostics when attribute cycles occur.

• OAG orderedness checking (Theorem 4.1). The paper provides a polynomial-time algorithm to check whether a HAG is ordered by reducing to an OAG and testing the reduced grammar. gen-scope discovers cycles at evaluation time, through Nix’s infinite-recursion error or evalDebug’s cycle tracing. A static orderedness check could detect problematic attribute configurations before evaluation begins.

• Bounded well-definedness for recursive expansion (S3.3). The paper shows that HAGs can express recursive functions (the factorial example) by allowing NTAs to recur, trading finite expansion guarantees for computational power. gen-scope’s derived-children channel guarantees finite expansion. Bounded well-definedness could enable recursive aspect patterns — an aspect that conditionally spawns instances of itself based on computed attributes, with a convergence guard.

• Attribute value := part of the structure tree (S2.4.2). The paper describes storing existing subtrees as attribute values (not just creating new ones). gen-scope implements the NTA direction (compute trees, expand into structure) but does not provide a first-class mechanism to capture and store an existing subtree as a reified attribute value for later re-attachment or analysis.

• Semantic functions as attributed trees (S5, Conclusion). The paper’s conclusion sketches a unification where semantic functions themselves are defined by attributed trees, merging the tree and function formalisms. This would mean attribute rules are not opaque Nix functions but inspectable, analyzable tree structures — enabling program transformation and optimization of the evaluation itself.

Research Directions

• Incremental HOAG evaluation. The paper’s work-list algorithm (Figure 13) naturally supports incrementalism — when the tree changes, only affected attribute instances need re-evaluation. Combined with Reps’ work on incremental AG evaluation (cited by the paper), this is the approach gen-memo takes: it keeps its own trace next to Nix’s lazy thunks, which cannot be selectively invalidated, and recomputes only the keys a change affects.

• Higher-order attribute grammars over scope graphs with custom edge labels. The paper’s NTAs operate on tree structures. gen-scope operates on scope graphs (Neron 2015) with import edges and custom edge labels (van Antwerpen 2018). The formal interaction between HOAG tree expansion and scope graph resolution is unexplored: when an NTA expansion adds a node with import edges, how does this affect the resolution calculus? Can the EDDP be extended to account for resolution-path dependencies?

• Demand-driven NTA expansion with constraint propagation. Statix (van Antwerpen 2016) uses constraint-based scope graph resolution. Combining Vogt’s demand-driven NTA expansion with Statix-style constraints could yield a system where tree expansion is guided by constraint satisfaction — expand an NTA only when a constraint requires a name that would be declared in the expanded subtree. This would be a lazy, constraint-driven variant of HOAG evaluation.

• Formal verification of gen-scope’s EDDP compliance. gen-scope relies on structural properties of consumer-defined attribute functions to satisfy EDDP. A formal treatment could prove that gen-scope’s staged children/derived-children protocol correctly implements EDDP under Nix’s lazy evaluation semantics, providing a soundness guarantee.