Erdweg et al. (2015) -- Evaluating and Comparing Language Workbenches

The paper

S. Erdweg et al., “Evaluating and comparing language workbenches,” Computer Languages, Systems & Structures, vol. 44, pp. 24–47, 2015.

doi:10.1016/j.cl.2015.08.007 · read the paper

This page is our reading of it, not a substitute for it.

Paper Summary

This paper presents the most comprehensive systematic comparison of language workbenches to date, drawing on four years of the Language Workbench Challenge (LWC, 2011-2014) — an annual event where developers of different workbenches implement the same domain-specific language to enable direct comparison of approaches. The authors focus on LWC’13, where ten workbenches implemented a questionnaire DSL (QL) with an optional styling extension (QLS), producing the most controlled and comparable dataset of the series.

The paper’s first contribution is a feature model that taxonomizes the design space of language workbenches across six mandatory or optional subcategories: notation (textual, graphical, tabular, symbolic), semantics (translational vs. interpretive), editor support (free-form vs. projectional, with syntactic and semantic services), validation (structural, naming, types, programmatic), testing and debugging, and composability (syntax, validation, semantics, editor services). This feature model is the paper’s lasting methodological contribution — it provides a structured vocabulary for discussing what a language engineering tool does and does not support, independent of the tool’s own terminology.

The ten participating workbenches span a remarkable diversity: academic (Enso, Rascal, Spoofax, SugarJ, Whole Platform) and industrial (Mas, MetaEdit+, MPS, Onion, Xtext); ages from 1 to 18 years; editing paradigms from purely textual free-form (Rascal, Xtext) to purely projectional (MPS, Mas); single unified metalanguages (Rascal) to suites of specialized meta-DSLs (Spoofax with SDF3, NaBL, Stratego). The classification reveals that while certain features are near-universal (textual notation, model-to-text translation, syntax highlighting, error marking), others remain differentiators: declarative type system specification (MPS, SugarJ, Xtext), DSL program debugging (MPS, Whole Platform, Xtext), quick fixes, and live translation.

The empirical comparison of QL/QLS implementations provides quantitative data on solution size (83-2408 SLOC), feature coverage (24-97%), and deployment dependency chains. The authors caution heavily against ranking — solution sizes reflect architectural choices (web vs. desktop), language reuse (Enso, MPS, SugarJ, Xtext reuse existing expression languages), and developer experience, not workbench quality. Nevertheless, the data confirms that language workbenches provide meaningful abstraction over manual implementation: the median LWC solution is smaller than a hand-written Java equivalent (3100 SLOC median from 48 student implementations) while providing substantially more features including IDE support.

The paper’s second major contribution is a set of benchmark problems for future LWC editions, organized into three categories: notation (mathematical symbols, tabular views, metadata annotations, optional hiding, multiple notations, computed properties, skeleton editing, embedded code in prose, embedded black boxes), evolution and reuse (language extension, language embedding, extension composition, beyond-grammar restrictions, syntax migration, structure migration), and editing (incomplete programs, missing references, structure-agnostic copy/paste, restructuring, language demarcation, delayed decisions, end-user formatting, default formatting specification, formatting preservation). Each benchmark is designed to be self-contained, implementable, feasible, indicative, and state-of-the-art. Two detailed example solutions are provided: metadata annotations in MPS (demonstrating projectional editing’s NodeAttribute mechanism) and persistent user-defined formatting in Rascal (demonstrating concrete syntax tree preservation during rename refactoring).

A key finding running through the paper is a convergence trend: workbenches are moving toward hybrid notation (mixing textual, graphical, tabular, symbolic), toward extensible environments rather than standalone compiler generators, and toward language-oriented programming where composition of independently developed language fragments is a first-class concern. The composability dimension proves the most varied — ranging from Rascal’s generalized parsing for arbitrary grammar composition, to MPS’s projectional composition (unlimited syntactic composition but requiring intentions for activation), to Xtext’s LL(k)-constrained composition.

Key Concepts

• Language Workbench: an environment for simplifying the creation and use of computer languages, encompassing syntax definition, semantics, validation, editor services, and composition
• Feature Model: a hierarchical taxonomy capturing the design space of language workbenches across six subcategories (notation, semantics, editor, validation, testing, composability)
• Free-form vs. Projectional Editing: the two dominant paradigms — free-form parses persisted text; projectional edits a projection of the persisted AST in a fixed layout
• Translational vs. Interpretive Semantics: model-to-text/model-to-model compilation vs. direct execution without prior translation; Enso’s hypothesis that interpreters compose better than generators
• Language-Oriented Programming: a paradigm where multiple DSLs address different aspects of a system, requiring composability at syntax, semantics, validation, and editor levels
• Language Extension: modularly adding constructs to a base language without modifying it (the Expression Problem in workbench form)
• Language Embedding: using one independently developed language inside another with minimal glue code
• Extension Composition: combining independently developed extensions in the same program — the hardest composability challenge
• Single vs. Multiple Metalanguages: Rascal’s unified approach vs. Spoofax’s suite of specialized meta-DSLs (SDF3, NaBL, Stratego) vs. MPS’s extensible metalanguage base
• Beyond-Grammar Restrictions: context-sensitive constraints that reject semantically undesirable programs beyond what syntax alone can express
• Benchmark Problem: a self-contained, implementable, feasible, indicative challenge that highlights a specific tool capability independently from others
• Concrete Syntax Trees vs. ASTs: Rascal’s preservation of parse trees (including whitespace/comments) enables format-preserving transformations; most tools work at AST level and lose layout

Ecosystem Relevance

Landscape Context

The ten workbenches surveyed represent the traditional approach to language engineering: external tools that generate or interpret standalone languages with their own syntax, editors, and toolchains. gen-scope’s embedding approach occupies a fundamentally different point in this design space — rather than building an external AG evaluator that generates code or interprets models, gen-scope embeds attribute grammar evaluation directly into the host language (Nix) by leveraging its native lazy evaluation for demand-driven computation and lib.fix for memoization.

This positions gen-scope closest to Kiama (Sloane et al., 2010, not a LWC participant but cited in the gen ecosystem’s theoretical foundations). Kiama embeds AGs in Scala using Scala’s lazy vals and higher-order functions. gen-scope takes this further: where Kiama still defines an explicit evaluator with caching strategies, gen-scope’s _eval is simply a lazy attrset — the Nix runtime IS the evaluator. There is no separate evaluation phase.

The surveyed systems that come closest to gen’s concerns are:

• JastAdd (referenced but not a LWC’13 participant): demand-driven AG evaluation, aspect-oriented modular extension. JastAdd’s aspect-oriented decomposition of AG specifications (where attributes can be added to existing node types without modifying the type definition) directly parallels gen-aspects’ trait system and the neededBy reverse-edge mechanism. JastAdd compiles to Java; gen-scope stays in Nix.
• Spoofax/NaBL: Spoofax’s NaBL declarative name binding is the precursor to the scope graph formalism (Neron 2015) that gen-scope implements. Where NaBL generates a name resolver for a defined DSL, gen-scope provides scope graph resolution as a library primitive that den wires with domain semantics.
• SugarJ: library-based syntactic extensibility, where extensions are activated by import. This mirrors den’s aspect includes mechanism — both use import-style edges to compose independently developed language fragments. SugarJ’s composition is syntactic; den’s is semantic (scope graph I-edges).
• MPS: unlimited projectional composition without parsing. MPS’s NodeAttribute (metadata that attaches to nodes without the node’s definition knowing about it) is structurally similar to gen-aspects’ neededBy — both enable reverse-direction extension where the target does not declare the extension point.

The key differentiator: every surveyed workbench is a tool for building languages. The gen ecosystem is a set of libraries for building frameworks. The workbenches produce DSLs consumed by end users; gen produces evaluation machinery consumed by framework authors (den). This is a level-of-indirection difference — gen operates at the meta-framework level where the surveyed tools operate at the meta-language level.

Applicable Insights

Feature model as evaluation framework. The six-subcategory feature model (notation, semantics, editor, validation, testing, composability) could serve as a structured checklist for evaluating den’s user-facing capabilities. Den currently excels in semantics (the fx pipeline) and composability (aspects, policies, classes), but has no story for notation (no custom syntax), editor support (no IDE integration), or debugging (trace-based only). The feature model clarifies what den is NOT trying to be — it is purely a semantic composition framework, not a full workbench.

Composability as the hardest problem. The paper’s most consistent finding is that composability varies the most across tools and remains the most challenging feature. This validates den’s design focus: the entire pipeline exists to solve the composition problem (aspects composing into class outputs, policies mediating cross-entity relationships, pipes routing data between scopes). The benchmark problems on extension composition, language embedding, and beyond-grammar restrictions map directly to den’s aspect composition, policy-driven cross-entity delivery, and guard/constraint mechanisms.

Interpreters compose better than generators. Enso’s working hypothesis (Section 4.1) that interpretive semantics compose more cleanly than translational semantics resonates with gen-scope’s design. gen-scope’s demand-driven attribute evaluation is essentially an interpreter for the scope graph — attributes are computed on demand, not generated ahead of time. This is why gen-scope can compose arbitrary attribute definitions without code generation conflicts.

Convergence toward multi-notation. The trend toward hybrid notation (textual + graphical + tabular in the same environment) suggests that if den ever grows IDE tooling, it should plan for multiple views from the start. The diag/ subsystem (C4, Mermaid, Dot, fleet views) is already a step in this direction — it provides read-only graphical projections of the scope graph.

Benchmark methodology. The paper’s benchmark problem design criteria (self-contained, implementable, feasible, indicative, state-of-the-art) and evaluation criteria (assumptions, implementation, variants, usability, impact, composability, limitations) could inform den’s own test suite design. The CI suite already has 133+ test files, but they test internal correctness, not user-facing capability benchmarks.

Appendix: Follow-up Work

Unexploited Ideas

Declarative validation as a composable concern. Spoofax’s NaBL (declarative name binding) and MPS’s type system DSL demonstrate that validation can be specified declaratively and composed modularly. gen-schema’s refinement types and gen-bind’s contracts provide pieces of this, but den has no unified declarative validation language. A gen-validate library that composes validation rules with the same modularity as aspects would close this gap.

Structure migration as a first-class operation. The benchmark on structure migration (changing AST representation while preserving syntax) maps to den’s version upgrade problem. When den.aspects gain new structural keys or pipe semantics change, existing configurations need migration. A declarative migration mechanism (analogous to database schema migrations) could be built on gen-derive’s rule dispatch — migration rules fire on old-shape aspects and produce new-shape equivalents.

Computed properties in scope graphs. The benchmark on computed properties (editor displays derived read-only values inline) maps to gen-scope’s synthesized attributes. Currently, scope graph attributes are internal to the pipeline. Surfacing selected attributes as user-visible computed annotations on den configuration (e.g., showing which policies fired, which classes received content) would improve debuggability.

Beyond-grammar restrictions via selectors. The benchmark on context-sensitive restrictions (triggerself only valid inside state machine actions) maps directly to gen-select’s selector algebra. gen-select can express “this pattern is only valid when an ancestor matches predicate X” via the within combinator. This is currently used for gen-derive rule conditions but could be exposed as a user-facing constraint mechanism in den aspects.

Research Directions

Embedding benchmark for gen-scope. Implementing the LWC’13 QL/QLS challenge as a gen-scope attribute grammar (questionnaire structure as scope graph nodes, validation as inherited/synthesized attributes, rendering as terminal attributes) would provide a concrete comparison point against the ten surveyed workbenches. This would quantify the abstraction advantage (or cost) of the embedded AG approach vs. dedicated workbenches.

Composability metrics. The paper notes that no workbench achieves full composability across all six subcategories. Developing formal metrics for composability — measuring how many independently developed aspects can be combined without glue code, merge conflicts, or semantic interference — would provide a rigorous way to evaluate den’s claim that aspects are the right composition granularity.

Projectional editing for scope graphs. MPS demonstrates that projectional editing enables unlimited syntactic composition because there is no parsing ambiguity. A projectional editor for den configurations — where the user edits a projection of the scope graph rather than raw Nix — would bring den closer to a full workbench. The scope graph’s hierarchical structure (nodes with P/I edges) is naturally projectable as both tree views and graph diagrams.