Hedin & Magnusson (2003) -- JastAdd: An Aspect-Oriented Compiler Construction System

Paper Summary

Hedin and Magnusson present JastAdd, a Java-based compiler construction system that combines two historically separate concerns: aspect-oriented modular extension and declarative attribute grammar evaluation. The central problem is the cross-cutting decomposition dilemma in compiler construction. An AST class hierarchy naturally decomposes by language constructs (expressions, statements, declarations), but compiler phases (name analysis, type checking, code generation) cut across all constructs. Neither the Visitor pattern nor traditional class hierarchies alone can cleanly separate both dimensions.

JastAdd’s first contribution is aspect-oriented imperative modules (Jadd modules, S3). Each Jadd module declares fields and methods that are woven into AST classes at generation time, following the inter-type declaration mechanism of AspectJ. Unlike the Visitor pattern, Jadd modules can introduce both fields and methods with fully-typed parameters and return values. The paper demonstrates this advantage concretely: a type-checking aspect can declare a typeError boolean field on expression nodes while simultaneously defining the typeCheck() method that computes it — impossible with visitors, which can only add methods with a uniform Object visit(C, Object) signature (S3.1). The class weaver reads all Jadd modules and generates complete AST classes, permitting free inter-module dependencies (e.g., an unparsing module accesses typeError computed by a type-checking module).

JastAdd’s second contribution is Reference Attributed Grammars (RAGs, S4) as the declarative formalism. Classical AGs allow only synthesized (upward) and inherited (downward) attribute propagation along the tree spine. RAGs extend this with reference attributes — attributes whose values are references to arbitrary AST nodes — establishing cross-tree connections that bypass the parent-child hierarchy. The canonical use is name analysis: an IdUse node has a synthesized reference attribute myDecl pointing to the Decl node of its binding declaration (S4.1, lines 37). Once myDecl links are established, subsequent aspects (type checking, code generation) access declaration-site information directly through these references, using the AST itself as the symbol table (S3.3). This eliminates separate symbol table data structures.

RAG specifications are written in Jrag modules — aspect-oriented declarative modules that declare attributes (with syn/inh modifiers) and equations (S4). The Jrag-to-Java translation (S5) is the paper’s formal core:

Synthesized attributes become abstract Java methods, with equations translated to concrete method implementations in subclasses (S5.1). A syn String type on Decl becomes abstract String type() on Decl, with String type() { return "int"; } on IntDecl.
Inherited attributes use an interface-based dispatch mechanism (S5.2). For a class Stmt with inherited attribute env, a ParentOfStmt interface is generated with method Block Stmt_env(Stmt theStmt). Every class containing Stmt components must implement this interface. The theStmt parameter disambiguates when a parent has multiple children of the same type with different equations. The env() accessor on Stmt delegates upward: ((ParentOfStmt) getParent()).Stmt_env(this).

The third contribution is demand-driven evaluation (S1, S4.2, S5.3). Rather than scheduling attribute evaluation in a fixed pass order, JastAdd uses an optimal recursive evaluator: accessing an attribute triggers a function call that computes the attribute’s semantic function, caches the result, and returns it. A cache flag prevents recomputation; a cycle flag detects circular dependencies at evaluation time. This scheme handles arbitrary acyclic dependency patterns, supporting general multi-pass compilation without explicit pass ordering. The paper notes this evaluation strategy was established by Madsen (1980), Jalili (1983), and Jourdan (1984), but JastAdd’s contribution is implementing it cleanly using Java’s virtual method dispatch, where synthesized attributes map to methods overridden in subclasses and inherited attributes map to interface methods implemented by parent classes.

The fourth contribution is seamless combination of declarative and imperative aspects (S4.2). Imperative Jadd modules can freely access declaratively-defined attributes, and declarative Jrag modules can (with care) access imperatively-computed fields. The paper recommends a core of declarative aspects defining fundamental attributes (name analysis, type analysis), consumed by imperative aspects for output-oriented tasks (code generation, error reporting). This hybrid approach allows each sub-problem to be solved by whichever paradigm is most natural.

The paper also discusses interface injection (S3.4), where Jadd modules add interface implementations to AST classes, enabling cross-cutting relationships orthogonal to the class hierarchy (e.g., an Env interface shared by Block, Method, and Class nodes for name lookup). The Null pattern for reference attributes (replacing null with sentinel objects implementing Declaration interfaces) demonstrates the practical utility of this mechanism.

Key Concepts

Inter-type declarations / Class weaving (S3.2): Separate aspect modules declare fields and methods for AST classes. A class weaver generates complete classes by merging all aspects. This is the static aspect mechanism from AspectJ applied to compiler construction, providing a safer and more powerful alternative to the Visitor pattern.
Reference Attributed Grammars (S4, based on Hedin 2000): Extension to AGs where attribute values can be references to arbitrary AST nodes. Enables cross-tree information flow (name analysis: myDecl linking use-sites to declaration-sites) without separate symbol table structures.
AST as symbol table (S3.3): Once reference attributes establish use-to-declaration links, the AST itself serves as the symbol table. Other aspects extend declaration nodes with new fields (type, activation record offset) and access them via the reference links. No external lookup structures needed.
Demand-driven evaluation with caching (S5.3): Attribute access triggers computation, caches the result, and detects cycles. Handles arbitrary acyclic dependencies without explicit pass scheduling. Implemented via Java methods (synthesized) and interface dispatch (inherited).
Synthesized-to-method, inherited-to-interface translation (S5.1-5.2): Synthesized attributes become overridable methods on the declaring class. Inherited attributes generate ParentOf<X> interfaces with disambiguation parameters. This maps declarative AG specifications to standard OO dispatch.
Aspect modularization for both declarative and imperative code (S3, S4): Jadd modules add imperative behavior (fields, methods, interface implementations). Jrag modules add declarative behavior (attributes, equations). Both are aspect-oriented: they specify additions to classes in separate files, woven together at generation time.
Interface injection for cross-cutting concerns (S3.4): Aspect modules can add interface implementations to AST classes, relating syntactically unrelated classes. Enables patterns like a shared Env interface for all block-like constructs, or the Null pattern for reference attributes.
Composition of visitors with aspects (S3.5): JastAdd supports both techniques simultaneously. Visitors remain useful for regular traversals; aspects handle everything else. The two interoperate: visitor methods access aspect-defined fields and attributes.

How gen uses this

gen-scope

gen-scope’s evaluation follows JastAdd’s demand-driven evaluator, with Nix’s lazy evaluation in place of explicit cache-flag methods.

Demand-driven attribute evaluation (S5.3). JastAdd’s recursive evaluator computes an attribute when it is accessed, caches it and returns the cached value afterwards. In gen-scope each node carries an _eval attrset whose entries are lazy thunks, computed on first access and memoised by Nix. JastAdd’s cache flag is implicit: a forced thunk is the cached value. The cycle flag corresponds to Nix’s infinite-recursion detection, or to evalDebug’s structured cycle traces.
Modular extension of attributes (S3.2). JastAdd lets separate modules contribute attributes to the same AST class. In gen-scope the caller supplies the attribute definitions, independent definitions are composed into one attribute map, and any attribute can read any other attribute on any node through self.get. JastAdd weaves at generation time. gen-scope composes at evaluation time through the self accessor, so adding an attribute does not regenerate anything.
Inherited attribute propagation (S5.2). JastAdd’s ParentOfX interfaces propagate inherited attributes by parent delegation. gen-scope’s inherit' walks the parent chain until its resolve function returns a non-null value. JastAdd’s disambiguation parameter (theStmt) is unnecessary because gen-scope nodes are identified by unique IDs instead of child position.
Circular attributes with declared lattices. gen-scope’s circular returns a declaration record carrying its carrier (bottom, order, height) and step, which the evaluator reads when the attribute is demanded. This follows JastAdd’s practice of declaring a circular attribute together with its lattice data, as described by Söderberg and Hedin 2013 (§2.4, Figure 5).

gen-dispatch

gen-dispatch’s README credits JastAdd with its design of open action types under framework-owned dispatch.

Framework-owned dispatch, open action types. JastAdd’s weaver owns dispatch through Java’s virtual method table, and users contribute implementations in aspect modules. gen-dispatch separates the same way. dispatch owns the protocol (NAC and condition matching, overrides, priority, firing, classification into groups), and the actions are opaque: consumers define them with mkActions and route them with their own classify function. Consumers contribute rules as independently written modules, and dispatch combines them.
Rules as modular units. Jadd modules are written independently and the weaver resolves their interactions. gen-dispatch rules are written independently and dispatch resolves their interactions through overrides, priority and the exclusive mode. With fromFunction, a Nix function’s argument pattern is the rule’s condition, as a Jrag equation’s class context determines where it applies.

JastAdd’s ideas in a gen configuration

Demand-driven evaluation. JastAdd built its cache flag, cycle flag and demand triggering in Java. A gen scope graph gets them from Nix: attributes compute only when accessed and import edges resolve only when queried.
The scope graph as symbol table (S3.3). JastAdd uses the AST as its symbol table, with reference attributes (myDecl) linking uses to declarations. A scope graph plays the same role: nodes carry declarations in decls, import edges link scopes, and query (Néron 2015, D < I < P) finds declarations along them.
A declarative core with imperative consumers (S4.2). JastAdd recommends a declarative core consumed by imperative modules. In gen, gen-scope is the declarative substrate of attributes and equations, and rules evaluated by gen-program and gen-dispatch read those attributes and produce actions that add structure to the graph.
Interface injection and classes (S3.4). JastAdd lets aspects add a shared interface to unrelated AST classes. A gen aspect can contribute content to several classes (nixos, darwin, homeManager), and each class is an output interface that different systems implement. gen-aspects’ keyCategory decides which part of an aspect goes where.

Appendix: Follow-up Work

Unexploited Ideas

Declared attribute classification (S4, S5.1-5.2). JastAdd distinguishes synthesised attributes (computed locally, passed up) from inherited ones (defined by the parent, passed down) and translates them differently. In gen-scope inherit' is explicitly inherited, and other attributes are plain self: id: functions. Declaring the classification for every attribute would enable static dependency analysis and clearer errors.
Equation-based attribute specification (S4). Jrag equations define attributes declaratively and make the data flow explicit (which attribute of which child is defined). gen-scope’s caller-supplied functions are flexible and hard to analyse. An equation layer over gen-scope could offer both.
Type-safe inherited attributes (S5.2). JastAdd generates ParentOf<X> interfaces that guarantee every parent of an X node provides its inherited attributes. gen-scope has no such guarantee: if inherit' walks to parents that never resolve the attribute, the error appears at evaluation time.
Composition of grammar modules (S7). The paper names composition of separately written abstract grammar modules as future work, developed later in JastAdd II (Ekman and Hedin 2007). gen-schema’s kind inheritance covers part of this for node kinds. Composition guarantees for independently extended attribute sets are not developed.
Dynamic aspects through join points (S6). JastAdd uses only static aspects. The paper notes interest in AspectJ’s join-point model. gen-dispatch rules fire at positions determined during evaluation, which is conceptually close, and a formal join-point model could give more precise control over where contributions land.

Potential New Libraries or Features

Attribute classification in gen-scope. A layer where attributes are declared synthesized, inherited or reference, following S4: synthesised attributes read only the node and its children, inherited attributes read parent-provided values, and reference attributes must point to existing nodes. It would validate and document the existing attribute definitions and support static dependency analysis.
Equation-based aspect content. A declarative notation for aspect content with explicit data flow, after Jrag equations. It would let tools detect aspects that define the same attribute of the same class without a merge strategy.
Contracts for inherited attributes. Extend inherit' with a contract, using gen-bind’s contracts, stating what the parent chain must provide. The check would run when a node is created, instead of when the attribute is read.

Research Directions

JastAdd weaving and NixOS module merge. JastAdd weaves aspect contributions into classes at generation time, and the NixOS module system merges contributions into options at evaluation time. Both can conflict: two aspects defining the same method, two modules setting the same option. The NixOS module system resolves conflicts with priorities (mkForce, mkDefault), and JastAdd treats a duplicate definition as an error. A formal comparison would show where the guarantees coincide.
Incremental weaving. When one aspect changes, only the scope-graph regions it touches need recomputation. Tracking which nodes each aspect contributes to, as JastAdd tracks which classes a module touches, would give gen-memo a precise dirty set for an aspect edit.
Aspect interaction analysis from dependencies. JastAdd’s translation (S5) yields a concrete dependency graph between attributes. Extracting the same graph from gen-scope attributes, which attributes each reads and on which nodes, would flag two aspects that contribute to the same class and read overlapping attributes as possible conflicts, extending the OAG orderedness check (Theorem 4.1, via Vogt 1989) to scope graphs.

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