Knuth (1990) — The Genesis of Attribute Grammars

The paper

D. E. Knuth, “The genesis of attribute grammars,” Lecture notes in computer science, pp. 1–12, 1990.

doi:10.1007/3-540-53101-7_1

A summary of the paper and how gen uses it.

Paper Summary

The document read is “The Genesis of Attribute Grammars” (1990), Knuth’s retrospective on the creation of attribute grammars, presented at the First International Conference on Attribute Grammars and their Applications. It narrates the intellectual history behind his foundational 1968 paper “Semantics of Context-Free Languages” (Mathematical Systems Theory 2, pp. 127-145), which introduced the formal framework that the entire gen ecosystem rests upon.

The problem. By the mid-1960s, Chomsky’s context-free grammars had elegantly solved the syntax problem for programming languages, but semantics remained intractable. Every known method for defining program meaning had “roughly the same degree of complexity as compilers, or worse.” Ned Irons (1961) had shown that meanings of compound expressions could be synthesized bottom-up from sub-expression meanings — meaning(a + b) = meaning(a) + meaning(b) — but context-dependent semantics (type declarations, scoping, identifier resolution) required ad hoc global data structures. There was no declarative counterpart to BNF for meaning.

The key insight. During a weekend visit with Peter Wegner at Cornell in February 1967, Knuth described Irons’s bottom-up synthesis approach. Wegner asked: “Why can’t attributes be defined from the top down as well as from the bottom up?” Knuth’s initial reaction was that bidirectional flow was impossible, but he quickly realized that it was viable provided circular definitions could be detected and excluded. This single question — Wegner’s contribution that Knuth later regretted not crediting in his original paper — introduced inherited attributes: values that flow downward through the parse tree, carrying contextual information (symbol tables, type environments, enclosing scope declarations) from parent nodes to children.

The formal framework. In the 1968 paper, Knuth formalized attribute grammars as an extension of context-free grammars where:

1. Each grammar symbol (terminal or nonterminal) carries a finite set of named attributes.
2. Attributes are partitioned into two disjoint classes: synthesized (computed from children, flowing upward) and inherited (computed from parent and siblings, flowing downward).
3. Each production rule is augmented with semantic rules — equations defining how attribute values are computed from other attributes on the same production’s symbols.
4. A grammar is well-defined (non-circular) if there exists a consistent evaluation order for all attributes on every possible parse tree.
5. The translation (meaning) of a string is the set of synthesized attribute values at the root of its parse tree.

The circularity problem. Knuth proposed an algorithm for testing whether an attribute grammar is circular — whether any parse tree could produce a cycle in attribute dependencies. His original algorithm was flawed; Stein Krogdahl sent a counterexample in 1970. Knuth patched it, but the corrected algorithm had exponential worst-case complexity. Jazayeri, Ogden, and Rounds (1975) later proved that circularity testing is inherently exponential — one of the first “natural” problems shown to require exponential time. However, Knuth’s incorrect original algorithm turned out to define the useful class of “strongly non-circular” grammars, which became a practical restriction adopted by many AG systems.

Broader contributions. The paper established that the meaning of any context-free language — not just arithmetic expressions — could be defined declaratively by attaching equations to productions. This replaced operational, compiler-like semantic definitions with a purely declarative specification. Knuth demonstrated the framework on “Turingol,” a small imperative language, showing that type checking, scope resolution, and code generation could all be expressed as attribute computations. The framework unified what had previously been separate concerns: type analysis became inherited attributes flowing down, code generation became synthesized attributes flowing up, and scope resolution became the interplay between both.

Impact. By the time of the 1990 retrospective, the bibliography of Deransart, Jourdan, and Lorho’s 1988 monograph on attribute grammars cited approximately 600 papers extending the framework — a scale Knuth himself found “astonishing.”

Key Concepts

• Synthesized attributes: values computed bottom-up from children’s attributes. The mechanism Irons (1961) had pioneered for arithmetic expressions, generalized to arbitrary grammar symbols.
• Inherited attributes: values computed top-down from parent and sibling attributes. Wegner’s conceptual contribution. Carries contextual information (type environments, symbol tables, scope declarations) to where it is needed.
• Semantic rules: equations on productions defining attribute computations. Purely declarative — no evaluation order specified. The evaluation engine determines a valid order.
• Circularity: the central well-formedness condition. A grammar is non-circular iff no parse tree induces a dependency cycle among attributes. Testing is inherently exponential (Jazayeri et al. 1975).
• Strongly non-circular grammars: the class recognized by Knuth’s original (incorrect) algorithm. A practical restriction: circularity can be tested on the grammar itself, independent of particular parse trees.
• Declarative semantics: the philosophical contribution — meaning as a system of equations rather than an algorithm. “How simple to realize [semantic correctness] if you write a procedure. The problem is, however, to find a metalanguage for doing that in a declarative way, not in an operational way” (Caracciolo, quoted by Knuth).
• Parse tree as evaluation substrate: attributes live on nodes of the derivation tree. The tree provides both the structure for dependency flow and the memoization boundary for attribute values.
• Top-down and bottom-up unified: the framework allows both directions of semantic analysis at once, governed by dependency order.

How gen uses this

Foundational Influence

Knuth’s split between inherited and synthesised attributes underlies gen. Each library either implements attribute grammar concepts or operates on structures whose nodes carry attributes.

gen-scope is the direct descendant, a higher-order attribute grammar evaluator. Its inherit' combinator is Knuth’s inherited attribute: walk the parent chain until a value resolves. Synthesised attributes are computed from a node’s children. Each node’s lazy _eval attrset is the memoisation Knuth’s framework needs, one value per attribute per node, computed at most once. Nix’s lazy evaluation supplies the demand-driven scheduling, so gen-scope needs no explicit topological sort of attribute dependencies.

gen-aspects gives aspect content the form of attribute values on scope-graph nodes. Class keys (nixos, darwin, homeManager) are the root’s synthesised attributes, the value the grammar computes and hands out. Nested aspects extend the tree. Parametric aspects consume inherited attributes: they receive context such as the host or user from above and produce class content.

gen-select’s selectors run over the same tree and graph structures attributes are defined over. within and parentMatches navigate the tree, the substrate Knuth chose for attribute definitions.

gen-bind addresses a problem Knuth touches only in passing, delivering context to functions that cannot reach the tree. In attribute grammar terms, its bindings are inherited attributes delivered to leaf-level modules.

A framework built on gen expresses its configuration as a demand-driven attribute grammar evaluated by gen-scope, replacing an operational pipeline that threads state through handlers with equations on a graph that the evaluator schedules. This is the move Knuth argued for: declarative semantics in place of operational semantics.

Descendants

Vogt et al. 1989, Higher-Order Attribute Grammars. Vogt allows attributes whose values are trees, non-terminal attributes (NTAs). In Knuth’s framework attribute values are atomic. With NTAs an attribute computation can synthesise a subtree, which then takes part in further evaluation. gen-scope’s derived-children grows the node set on demand this way, and its nta channel lets a node read the attributes of the children it synthesised.

Hedin 2000, Reference Attributed Grammars. Hedin allows attributes to hold references to other nodes. This breaks the strict parent-child flow of classical attribute grammars: a node can reach across the tree through a reference. gen-scope’s import edges (decls.__edges.I) are such references, and they make cross-subtree resolution possible. The scope graph formalism gen-scope implements (Néron 2015) depends on this extension, since a tree alone cannot express imports.

Hedin and Magnusson 2003, JastAdd. JastAdd makes evaluation demand-driven (compute only what is accessed) and lets attributes be declared in separate modules. gen-scope’s lazy _eval is demand-driven evaluation through Nix laziness. JastAdd showed that demand-driven evaluation removes the need for explicit scheduling, which is why gen-scope has no scheduler: Nix is the scheduler.

Sloane et al. 2010, Kiama. Kiama embeds attribute grammars in Scala with higher-order functions as attribute combinators. Sloane shows that CachedAttribute, a memoised function from node to value, is the core implementation pattern, and gen-scope’s _eval is that pattern for non-parameterised attributes. Sloane’s circular attribute combinator (iterate to a fixpoint) corresponds to gen-scope’s circular.

Van Wyk et al. 2010, Silver. Silver adds forwarding (a production delegates to another) and collection attributes (several nodes contribute values to one named aggregate). Collection attributes correspond to gen-scope’s folds over contributions.

Appendix: Follow-up Work

Unexploited Ideas

McCarthy’s parameterised nonterminals. Knuth recalls a 1970 debate with John McCarthy, who proposed nonterminals with explicit parameters, E(s) with s a symbol table, in place of inherited attributes. Neither side won. In gen-scope a parameterised attribute is written as a function of its parameter, which is closer to McCarthy’s proposal, while inherit' follows Knuth. When each is preferable in Nix’s evaluation model, and whether McCarthy’s idea of eliminating inherited attributes has practical merit there, is unexplored.

Strongly non-circular subclasses. Knuth’s flawed first circularity test defines a strict subclass of non-circular grammars that can be checked efficiently. gen does no static circularity analysis for attributes and relies on Nix to report a cycle at evaluation time as infinite recursion. A definition-time check, even for a restricted subclass such as strongly non-circular grammars, would catch cycles before evaluation with a clearer error.

Natural language semantics. Knuth notes that inherited attributes correspond to context-dependent meaning in natural language and synthesised attributes to compositional meaning. gen works in the configuration domain. Whether the same machinery could drive structured language-processing pipelines is uncharted.

Research Directions

Static cycle detection for scope graphs. Knuth’s circularity problem carries over to scope graphs: can a configuration be shown free of dependency cycles before evaluation? The exponential lower bound (Jazayeri et al. 1975) applies to arbitrary grammars, and the restricted structure of configuration graphs (bounded depth, regular topology from entity kinds) may admit polynomial checks. gen-schema’s kind topology (_topology, _roots) gives the structural metadata such an analysis needs.

Incremental re-evaluation. Knuth assumes evaluation from scratch. JastAdd added demand-driven evaluation, and the next step is re-evaluating only what a changed definition affects. gen-memo decides which keys must be recomputed after a change and reuses the rest, with a byte-identical result to a cold run.

Composition of grammar fragments. Knuth defines a grammar as one monolithic unit. Silver introduced modular composition of fragments. An algebra of fragment composition with proven conditions under which composition preserves non-circularity would give aspect composition a firmer basis.

Circular attributes in practice. Knuth excluded circular definitions, and Sloane (2010) and others added controlled circular attributes with fixpoint semantics. gen-scope’s circular requires a declared carrier (bottom element, order and height), which records when iteration is expected to converge. Checking monotonicity of the step as well would catch divergent fixpoints before they run.