Reps, Teitelbaum & Demers (1983) -- Incremental Context-Dependent Analysis for Language-Based Editors

Paper Summary

Reps, Teitelbaum, and Demers attack the problem of keeping a program’s context-dependent (non-context-free) properties consistent as the program is edited, one small change at a time, inside an interactive language-based editor (the Cornell Program Synthesizer / Synthesizer Generator) (Abstract, p449; S1, p449-450). Context-free grammars cannot express constraints that interrelate widely separated parts of a program (declarations vs. uses, scoping, types); attribute grammars (Knuth [19]) extend CFGs declaratively to do so (S1, p450; S2, p451). The editor represents a program as an attributed tree, and edits are derivation-tree operations — pruning, grafting, deriving (S1, p450; S3, p453-454). After each edit the editor must restore a consistent, fully attributed tree; the paper’s contribution is a family of incremental attribute-evaluation algorithms, culminating in one that is asymptotically optimal in time (Abstract, p449; S1, p450).

An attribute grammar attaches synthesized and inherited attributes to grammar symbols; each production carries semantic equations defining one attribute as a semantic function of others in that production (S2, p451). In normal form, every equation defines a synthesized attribute of the left side or an inherited attribute of a right-side symbol from inherited attributes of the left side and synthesized attributes of the right side (S2, p451). A derivation-tree node labelled X has attribute instances; a semantic tree assigns each instance a value or the token null (null = “unavailable”, outside every attribute’s domain) (S2, p452). Functional dependencies are captured by a dependency graph D(T): a vertex b' per attribute instance b, and an edge (b', c') iff b is an argument of c (“b' is used to determine c'”) (S2, p452). An instance is consistent iff its arguments are available and its value equals its semantic function applied to those arguments; a tree/graph is consistent iff all its instances are (S2, p452). The grammar is assumed well-formed and noncircular — D(T) acyclic for every derivation tree (noncircularity decidable [18], intrinsically exponential [14] but feasible in practice) (S2, p453). To keep partial programs fully attributed, each nonterminal X has a completing production X → ⊥ (“unexpanded”); every edit — insertion, deletion, derivation — is modelled as a subtree replacement of one X-rooted tree by another (S3, p453-454). Replacement = pruning U then grafting U'; grafting copies the old node’s synthesized attributes and the new root’s inherited attributes, so all initial inconsistencies are confined to the attributes of the single modification point r (normal form) (S3, p454; S4.1, p455).

The core quantity is AFFECTED: let T' be the inconsistent tree just after replacement and T'' the same tree after updating; AFFECTED is the set of attribute instances that have different values in T' and T'' (S4.3, p457). Crucially, AFFECTED is not known a priori — “it is not known which attributes are members of AFFECTED; AFFECTED is determined as a result of the updating process itself” (S1, p449-450; S4.3, p458). Because O(|AFFECTED|) is the minimum work any updater must do (you must at least write the new value of every attribute that changed), an evaluator is optimal-time iff it runs in O(|AFFECTED|) steps, counting each semantic-function evaluation as unit cost (S4.3, p457-458).

The paper builds up to the optimal algorithm through two naive ones (S4). Change propagation (Algorithm 1, p456) keeps every attribute available-but-possibly-inconsistent and a work-list S of attributes whose arguments changed; it reevaluates an attribute, and if the new value differs from the old, inserts the successors into S — “if reevaluating an attribute instance yields a value equal to its old value, changes need not be propagated further” (S4.1, p455). This unchanged-value cutoff is the heart of incrementality, but naive change propagation is sensitive to evaluation order: with attributes joined by more than one path, following dependencies blindly can be quadratic (FIFO) or exponential (LIFO) in the number of attributes reevaluated (S4.1, p456; Appendix, p474-475). Nullification/reevaluation (Algorithm 2, p457) instead NULLIFYs the modification point and propagates null, then EVALUATEs consistent values; each attribute is touched once, so it is linear in the attributes considered — but the set of attributes reachable from the modification point bears no fixed relation to |AFFECTED|, so it does extensive needless propagation when AFFECTED is small (S4.2-4.3, p456-458). Neither naive method is optimal.

The fix (S4.3, p458): a temporarily-wrong value propagates spurious changes “arbitrarily far beyond the boundaries of AFFECTED.” So an attribute must not be reevaluated until all its arguments hold their correct final values — equivalently, AFFECTED must be enumerated in topological order w.r.t. D(T). Nonincremental evaluators get this from Knuth’s topological sort [20] over D(T) in O(|D(T)|) [17, 22]; the incremental problem is to generate AFFECTED in topological order in O(|AFFECTED|) (S4.3, p458).

Optimal-time change propagation (S5; Algorithm 3, p462; refined as Algorithms 4-5) is a generalization of Knuth’s topological sort in which the vertex set of the scheduling graph is generated dynamically while it is enumerated (S5, p458-459). It keeps a work-list of attributes ready for reevaluation (in-degree zero) and a model graph M of dependencies among not-yet-reevaluated attributes; an attribute joins the work-list when its in-degree in M drops to zero (S5, p458-459; S5.2, p461). The decisive trick is characteristic graphs: for a node s, the subordinate graph s.C = D(T_s)/V_s projects the dependencies of the subtree rooted at s onto s’s own attributes, and the superior graph s.C̄ = (D(T) − D(T_s))/V_s projects the rest-of-tree dependencies onto s’s attributes (S5.1, p459; projection A/V' defined p459). These transitive-dependency edges let PROPAGATE skip, in unit time, arbitrarily large sections of D(T) whose values do not change and ensure an attribute is never updated before all its ancestors are consistent — so no attribute is ever assigned a temporarily-wrong value (S5.2, p463). M starts as r.C ∪ r.C̄ (just the modification point’s attributes); it is expanded one production instance at a time (procedures EXPAND, ExpandedSubordinate, ExpandedSuperior, Figure 3, p462) only when a changed attribute is an argument of an attribute outside M — i.e. only when a new member of AFFECTED is discovered (S5.2, p461-462). Therefore M never exceeds O(|AFFECTED|), each vertex costs one semantic-function application plus constant bookkeeping, and both the total number of evaluations and the total bookkeeping cost are O(|AFFECTED|) — PROPAGATE is asymptotically optimal (S5.2, p462-463).

Three refinements complete the surface. (1) A bare M-enumeration still evaluates some attributes that join M but whose arguments never changed (an attribute at r up to 3 times, others up to twice — not a violation of the bound, but wasteful since evaluations may be costly); the set NeedToBeEvaluated removes them: an attribute is reevaluated only if a predecessor actually changed value (S5.3, p464-465; Algorithm 4, p465). (2) Characteristic graphs are maintained lazily relative to the cursor. Maintaining every node’s graphs is too expensive (a replacement at r can alter graphs arbitrarily far away); instead the tree is kept “prepared for propagation at the cursor r”: r carries both r.C and r.C̄, each node on the path r→root carries its superior graph, every off-path node carries its subordinate graph (S5.4, p465-466; Figure 6). Cursor motion (AscendToParent/DescendToChild) re-establishes this invariant at unit cost per step, so moving the cursor over a path of length m costs O(m) (S5.4, p466). (3) The single-edit restriction is dropped: for an arbitrary restructuring, let R be the smallest connected region containing all initially-inconsistent attributes; initialize M to D(R) ∪ root(R).C̄ ∪ {subordinate graphs of R's frontier} and NeedToBeEvaluated to all of R’s attributes — this also drops the normal-form assumption (S5.5, p467).

Section 6 adds practical machinery. Identity-function (copy-rule) optimization (S6.1, p468-469): a large fraction of semantic functions are identities [40]; once a copy-rule chain’s head changes, the rest must change, so the equality tests along the chain can be skipped (valid only when the chain’s old values were consistent — the only possible inconsistencies are inside R) (S6.1, p468-469). Demand attributes (S6.2, p469-470): attributes whose values are not observable right after an edit need not be kept consistent — they are evaluated only when a demand arises (user query, screen display, or a neighbouring regular attribute needing the value); a demand attribute that loses an argument’s value is set to null and lazily recomputed via DEMANDVALUE (Algorithm 5, p470). This is exactly demand-driven / pull-based evaluation, dual to the topological push: “start from the vertices with no successors, reverse the edges, and do depth-first endorder” (S6.2, p469-470). The authors note the characteristic graphs themselves are graph-valued demand attributes linked to the cursor (S6.2, p469). Efficient large attributes (S6.3, p471-472): symbol-table-valued attributes are shared through indirection so identical values share storage and copy-rules copy pointers; sharable 2-3 trees let nearly-identical values share all but O(log n) structure, giving O(log n) MEMBER/INSERT vs. O(n) for linked lists [34] (S6.3, p471-472). Section 7 contrasts the declarative AG approach with the imperative semantic-action approach (Gandalf, AVID): action routines can record nonlocal dependencies and thus skip large tree regions an AG evaluator must visit node-by-node, but require hand-written, order-independent semantic retractions to undo effects on deletion — the AG approach needs no explicit undo because consistency is re-established automatically from the equations (S7, p472-474).

Key Concepts

Attributed tree / semantic tree (S2, p452). A derivation tree plus an assignment of a value or null to each attribute instance. null (“unavailable”) is outside every attribute’s domain; fully attributed = every instance non-null; an instance is ready for evaluation when all its arguments are available.
Dependency graph D(T) (S2, p452). Vertex b' per attribute instance b; edge (b', c') iff b is an argument of c (“b' determines c'”). The single structure over which all propagation runs. Noncircular AG ⇒ D(T) acyclic for every tree (S2, p453).
Consistency (S2, p452). Instance b is consistent iff (1) its arguments are available and (2) value(b) equals its semantic function applied to those arguments. The editor’s job after each edit: restore a consistent, fully attributed tree (S3, p455).
Subtree replacement confines inconsistency to one node (S3, p454; S4.1, p455). Grafting copies the old node’s synthesized + new root’s inherited attributes; under normal form all initial inconsistencies sit at the single modification point r. This is what lets PROPAGATE start from r alone.
AFFECTED = {attributes whose value differs before vs. after updating} (S4.3, p457). The exact set that must be rewritten. Determined only by the updating process itself, never known a priori (S1, p449-450; S4.3, p458). |AFFECTED| is the information-theoretic lower bound on update work.
Optimal-time = O(|AFFECTED|) (S4.3, p457-458). An incremental evaluator is optimal iff its cost (semantic-function evals as unit steps, plus bookkeeping) is proportional to |AFFECTED|, not to |D(T)| or to the reverse-reachable set from r.
Unchanged-value cutoff (S4.1, p455). “If reevaluating an attribute instance yields a value equal to its old value, changes need not be propagated further.” The cutoff that bounds propagation to AFFECTED — a recomputed-but-unchanged attribute does not enqueue its successors.
Order sensitivity of naive propagation (S4.1, p456; Appendix, p474-475). Following dependencies blindly when two attributes are joined by multiple paths gives quadratic (FIFO) or exponential (LIFO) behaviour. The cure is to never reevaluate an attribute until all its arguments are final ⇒ topological enumeration of AFFECTED (S4.3, p458).
Characteristic graphs s.C / s.C̄ (S5.1, p459). s.C = D(T_s)/V_s (subordinate: subtree-below transitive deps projected onto s’s attributes); s.C̄ = (D(T) − D(T_s))/V_s (superior: rest-of-tree transitive deps). They encode transitive dependencies that travel entirely outside the modeled region, so propagation can skip unchanged regions in unit time and never assigns a temporarily-wrong value (S5.2, p463).
The model M + dynamic topological sort (S5, p458-459; S5.2, p461). PROPAGATE = Knuth’s topological sort whose vertex set is generated while being enumerated. M holds dependencies among not-yet-reevaluated attributes; it starts at r.C ∪ r.C̄ and grows one production instance per newly-discovered AFFECTED member (EXPAND, Fig 3, p462), so |M| = O(|AFFECTED|) always. Result: O(|AFFECTED|) total (S5.2, p462-463).
NeedToBeEvaluated (S5.3, p464-465). Avoids reevaluating attributes that enter M but whose arguments never changed (≤3× at r, ≤2× elsewhere otherwise). An attribute is reevaluated only when a predecessor actually changed — prunes wasted evaluations without affecting the asymptotic bound.
“Prepared for propagation at r” invariant (S5.4, p465-466). Only r needs both characteristic graphs; path-to-root nodes carry superior graphs, off-path nodes carry subordinate graphs. Re-established at unit cost per cursor step (AscendToParent/DescendToChild), so cursor motion of length m costs O(m). Avoids maintaining every node’s graphs (which an edit could invalidate arbitrarily far away).
Generalization to a region R (S5.5, p467). For multi-node restructurings, seed M with D(R) ∪ root(R).C̄ ∪ {frontier subordinate graphs} and NeedToBeEvaluated with all of R. Drops both the single-edit and the normal-form restrictions.
Demand attributes = pull-based laziness (S6.2, p469-470). Attributes unobservable right after an edit are recomputed only on demand (query / display / a regular attribute needing the value); a demanded attribute that lost an argument is nulled and lazily recomputed (DEMANDVALUE, Alg 5, p470). The reverse-edge depth-first endorder evaluator — the demand-driven dual of topological push.
Copy-rule (identity-function) optimization (S6.1, p468-469). Skip equality tests down an identity chain once its head changes (most semantic functions are identities [40]); valid except inside the modified region R, where copy-rule attributes must be tested individually.
Sharable structures for large attributes (S6.3, p471-472). Indirection + structure sharing so identical/near-identical attribute values share storage; sharable 2-3 trees give O(log n) set ops with O(log n) extra nodes per update vs. O(n) for linked lists.
Declarative AG vs. imperative semantic actions (S7, p472-474). AG re-establishes consistency automatically with no explicit undo/retraction; semantic-action editors gain nonlocal-dependency shortcuts (skip large regions) but must hand-code order-independent retractions and cannot be made optimal by these methods in the presence of nonlocal deps (S7, p474).

How gen uses this

gen-memo

gen-memo is gen’s incremental rebuilder, the rebuilder of Mokhov 2018. Given a changed input over a dependency graph, it decides which keys to recompute and reuses the rest, and its output is byte-identical to a cold evaluation. RTD is the optimality result for that decision in the static-tree, single-edit setting: it defines the minimal recompute set (AFFECTED), proves O(|AFFECTED|) is the lower bound, and gives an algorithm meeting it. Mokhov gives the taxonomy of rebuilders and Acar 2002 gives change propagation with a soundness proof. RTD gives the minimality theorem: the recompute set can be exactly the attributes whose values change, enumerated in topological order, at cost proportional to that set. The correspondence:

D(T) = gen-memo’s dependency record. build evaluates every key into a flat store (an id-keyed map of plain values) and records a verifying trace, each key’s dependencies and a content hash. RTD’s attribute instance b is a key in that store. RTD’s edge (b', c') (“b' determines c'”) is a recorded dependency from source key to consumer key (S2, p452). The dependency graph comes from a gen-graph accessor passed in by the caller.
dirtySet and affectedSet = the cone and AFFECTED. dirtySet is the reverse-dependency cone of the changed keys, an over-approximation of AFFECTED. affectedSet is RTD’s AFFECTED exactly: “the attribute instances that have different values” before and after the update (S4.3, p457), found by recomputing over the cone and keeping the keys whose hash moved. RTD proves that set is the lower bound (S4.3, p457-458) and achievable (Algorithms 3-4, S5.2, p462-463).
earlyCutoff = the unchanged-value cutoff (S4.1, p455). RTD’s rule “if reevaluating an attribute yields a value equal to its old value, changes need not be propagated further” is earlyCutoff: a recomputed but unchanged key does not pass the change on, so propagation stays within AFFECTED.
needsEval = NeedToBeEvaluated (S5.3, p465). The pre-recompute guard: a key in the cone is recomputed only if one of its inputs actually changed value. earlyCutoff compares after recomputing and needsEval decides before, as RTD describes them as complementary tests.
Evaluation order = topological enumeration of AFFECTED (S4.3, p458; S5, p458-459). Reevaluating an attribute before its arguments are final propagates spurious changes “arbitrarily far beyond the boundaries of AFFECTED” (S4.3, p458), the FIFO-quadratic / LIFO-exponential blowup of the Appendix (p474-475). The cure is “an attribute should not be reevaluated until all of its arguments are known to have their correct final values”, so AFFECTED is enumerated in topological order (S4.3, p458). propagateEager recomputes over a producers-first rank order and forces only O(|AFFECTED| + frontier) keys. propagate, the general default, recomputes over the whole cone.
override / propagate = PROPAGATE over the model M. applyDelta records a change and propagate drains it to quiescence; override is the two composed. RTD’s PROPAGATE (Algorithms 3-4, p462, 465) seeds M with the changed point’s characteristic graphs, drains the in-degree-zero work-list, and expands M by one production only when a new AFFECTED member is found (S5.2, p461-462). The guarantee |M| = O(|AFFECTED|) is why a rebuild need not touch the unaffected store.
batch = region-seeded propagation (S5.5, p467). RTD generalizes single-edit propagation to an arbitrary connected region R. batch applies several changes and propagates them together.
restabilize / runScc = cyclic components. RTD assumes a noncircular grammar. gen-memo handles a strongly connected component separately: runScc iterates each member’s lattice from bottom until every member stops changing.
affected / support / why = D(T) reachability. affected is forward reachability from a changed key through the dependency graph. support and why read the argument instances a value depends on (S2, p452). D(T) is the provenance graph these queries read.

gen-scope

RTD presents both evaluation disciplines gen uses. The push discipline is the topological PROPAGATE (S5), which gen-memo implements. The pull discipline is demand attributes (S6.2, p469-470): “start from the vertices with no successors, reverse the edges, do depth-first endorder”, which is Nix lazy thunk forcing and gen-scope’s self.get. RTD’s observation that the characteristic graphs are themselves graph-valued demand attributes linked to the cursor (S6.2, p469) prefigures gen-scope storing derived dependency data with the node.

gen-graph

RTD’s D(T) is a typed DAG, and gen-graph provides the reachability that affected, support and why read (gen-memo’s dirtySet is dependentsOf over each changed key). RTD adds one structural operation beyond plain reachability: the projection A/V' = (V', E') where E' records a path in A between two V' vertices avoiding other V' vertices (S5.1, p459). It is the operation that builds characteristic graphs.

Summary

RTD concept	gen realization
`AFFECTED` set (S4.3, p457)	`affectedSet`: the cone filtered to keys whose hash moved
Reverse-dependency cone	`dirtySet`, the over-approximation `affectedSet` is filtered from
`O(\|AFFECTED\|)` optimality (S4.3, p458)	`propagateEager` forces only `O(\|AFFECTED\| + frontier)` keys
Unchanged-value cutoff (S4.1, p455)	`earlyCutoff` (post-recompute value compare)
`NeedToBeEvaluated` (S5.3, p465)	`needsEval` (pre-recompute guard)
Topological enumeration of `AFFECTED` (S4.3, p458)	producers-first rank order in `propagateEager`
Dynamic topological sort / model `M` (S5, p459)	`override` = `propagate` after `applyDelta`
Region `R` generalization (S5.5, p467)	`batch`
Demand attributes (S6.2, p469)	the pull half, gen-scope’s `self.get`

Minimality is a theorem about a set: AFFECTED is the set of keys whose value actually changes, and it is achievable in O(|AFFECTED|) when (a) recomputation proceeds in topological order, so no key is recomputed before its inputs are final, and (b) the unchanged-value cutoff prunes the cone down to the changed set. RTD proves these two ingredients sufficient for optimality in the static-tree single-edit case.

Further directions

Unexploited Ideas

Transitive-dependency summary edges (characteristic graphs) (S5.1-5.2, p459-463). RTD’s characteristic graphs, transitive-dependency edges projected onto a region boundary, let propagation skip unchanged subgraphs in unit time and never assign a non-final value. A summarized-edge layer (precomputed transitive dependencies across an unchanged subgraph, invalidated lazily relative to the change point as in the “prepared for propagation” invariant, S5.4) would let dirtySet itself shrink from cone-sized toward AFFECTED-sized.
The projection/contraction operation as a gen-graph primitive (S5.1, p459). A/V', transitive paths between a vertex subset with the interior contracted away, builds characteristic graphs and underlies the optimal bound. gen-graph has reachability but not transitive contraction onto a boundary.
Copy-rule optimization (S6.1, p468). An identity-edge fast path would skip equality tests down a chain of copy rules.

Research Directions

Does O(|AFFECTED|) optimality survive a dynamic dependency graph? RTD’s theorem is for a static AG over a fixed tree with a single subtree replacement whose inconsistency is confined to one node (S3, p454; S4.1, p455). gen-memo also handles structural changes (retract, applyEdgeDelta) that alter the graph’s shape, and dependencies can be discovered on demand. RTD’s confinement-to-r and its characteristic graphs both assume the dependency structure is known and stable around the edit. What is the minimal-recompute analogue of AFFECTED when an edit changes which edges exist, and is it still computable in time proportional to the changed set?
Topological order vs. cyclic / fixpoint attributes. RTD assumes a noncircular AG, D(T) acyclic for every tree (S2, p453), which makes topological enumeration well-defined and guarantees an in-degree-zero start vertex (S5.1, p459). gen has cyclic computations: gen-scope circular attributes and gen-memo’s runScc. Topological order is undefined on a cycle, and the O(|AFFECTED|) bound and the “never assign a non-final value” invariant both break. The optimal-incremental theory for circular attribute grammars is a separate, harder problem outside RTD’s scope.
Batch deltas vs. single-edit minimality. RTD’s optimal algorithm is per-edit (REPLACE updates after each subtree replacement, S3, p455). Its region generalization (S5.5) handles a single arbitrary restructuring, not a sequence of independent deltas demanded together. For many changes coalesced into one rebuild, the minimal recompute set is the union of per-change AFFECTEDs minus keys that change and change back, which RTD does not characterize. (RTD defers updating “only after the whole sequence of structural modifications has been completed,” S5.5, p467, but does not give the optimal batch algorithm.)
Retraction without explicit undo (S7, p472-474). RTD’s advantage over the semantic-action approach is that deletion needs no hand-coded retraction: consistency is re-established automatically because attribute flow is purely along tree edges (S7, p473-474). The price is that values “flow only along edges of the derivation tree”, so an AG evaluator must visit unchanged nodes on the path that a nonlocal-dependency structure could skip (S7, p474). gen-memo’s flat store is closer to the semantic-action data structures (nonlocal edges) than to RTD’s tree, so it handles retraction explicitly: retract deletes a key and splices it out of its dependents, the counterpart of Acar’s obsolete-edge splice-out. RTD shows that nonlocal dependency shortcuts and automatic retraction are in tension.
Demand-driven laziness vs. eager optimality (S6.2, p469-470). RTD’s optimal PROPAGATE is an eager push that keeps the whole tree consistent. Its demand attributes are a separate, opt-in lazy mechanism for unobservable values, and RTD does not prove O(|AFFECTED|) for them. gen’s native setting is lazy (Nix). Whether the minimality theorem holds when recomputation is demand-ordered rather than pushed in topological order, i.e. whether recomputing only the demanded path achieves O(|AFFECTED ∩ demanded|) without the characteristic-graph cutoff edges, is open.

Palettes adapted from Catppuccin (Macchiato) (MIT), Tokyo Night (Apache-2.0), gruvbox (MIT), Catppuccin (Latte) (MIT), Rosé Pine (Dawn) (MIT).