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

A summary of the paper and how gen uses 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

How gen uses this

Landscape Context

The ten surveyed workbenches are external tools that generate or interpret standalone languages with their own syntax, editors and toolchains. gen-scope sits at a different point in this design space. It embeds attribute grammar evaluation in the host language, Nix, and uses Nix’s lazy evaluation for demand-driven computation, memoisation and cycle detection.

This places gen-scope closest to Kiama (Sloane et al. 2010, not an LWC participant), which embeds attribute grammars in Scala using lazy vals and higher-order functions. Kiama defines an explicit evaluator with caching strategies. In gen-scope each node carries a lazy attrset of its attribute computations, _eval, and the Nix runtime is the evaluator. There is no separate evaluation phase.

The surveyed systems closest to gen’s concerns:

• JastAdd (referenced, not an LWC’13 participant): demand-driven attribute grammar evaluation with aspect-oriented modular extension, where attributes can be added to existing node types without changing their definition. gen-aspects composes configuration concerns in the same modular way. JastAdd compiles to Java, and gen-scope stays in Nix.
• Spoofax/NaBL: NaBL’s declarative name binding is the precursor of the scope graph formalism (Néron 2015) that gen-scope implements. NaBL generates a name resolver for a defined DSL. gen-scope provides scope-graph resolution as a library primitive that a framework gives domain meaning.
• SugarJ: library-based syntactic extensibility, where extensions are activated by import. A gen aspect’s includes works the same way, composing independently developed fragments through import-style edges. SugarJ composes syntax, and gen composes through scope-graph import edges.
• MPS: projectional composition without parsing. MPS’s NodeAttribute attaches metadata to nodes whose definition does not know about it. gen-view’s neededBy is the reverse half of reference resolution: it gathers the nodes that reference a target without the target declaring them.

Every surveyed workbench is a tool for building languages. gen is a set of libraries for building frameworks. The workbenches produce DSLs for end users, and gen produces evaluation machinery for framework authors. gen works one level up, at the meta-framework level where the surveyed tools work at the meta-language level.

Applicable Insights

The feature model as an evaluation checklist. The six-part feature model (notation, semantics, editor, validation, testing, composability) is a structured checklist for a framework built on gen. gen concentrates on semantics and composability. It defines no custom notation and ships no editor integration. Its inspection support is gen-inspect, which queries a configuration graph and renders it as a diagram.

Composability is the hardest problem. The paper’s most consistent finding is that composability varies most across tools and remains the hardest feature. gen is organised around that problem: aspects composing into class outputs, rules adding relationships between entities, and channels carrying data between scopes. The benchmark problems on extension composition, language embedding and beyond-grammar restrictions correspond to aspect composition, rule-driven delivery between entities, and guards.

Interpreters compose better than generators. Enso’s working hypothesis (Section 4.1) is that interpretive semantics compose more cleanly than translational semantics. gen-scope’s demand-driven attribute evaluation interprets the scope graph: attributes are computed on demand with no code generated ahead of time. Attribute definitions from different sources therefore compose without generation conflicts.

Multiple notations. The trend toward hybrid notation (textual, graphical and tabular in one environment) suggests planning for several views of a configuration from the start. gen-inspect’s renderers, such as Mermaid output over the same materialised graph, are read-only graphical projections of this kind.

Benchmark methodology. The paper’s criteria for a benchmark problem (self-contained, implementable, feasible, indicative) and for evaluating a solution (assumptions, implementation, variants, usability, impact, composability, limitations) could shape capability benchmarks for gen that test what a user can do, alongside the libraries’ correctness suites.

Appendix: Follow-up Work

Unexploited Ideas

Declarative validation as a composable concern. Spoofax’s NaBL and MPS’s type system DSL show validation specified declaratively and composed modularly. gen-schema’s refinement types, gen-types’ validators and gen-bind’s contracts provide pieces of this. A validation vocabulary that composes with the same modularity as aspects would join them.

Structure migration as a first-class operation. The structure-migration benchmark (changing the AST representation while preserving syntax) corresponds to upgrading configurations when a framework changes its aspect keys or channel semantics. A declarative migration mechanism, like a database schema migration, could run on gen-dispatch: migration rules fire on old-shape aspects and produce new-shape equivalents.

Computed properties in scope graphs. The computed-properties benchmark (the editor shows derived read-only values inline) corresponds to gen-scope’s synthesised attributes. Surfacing selected attributes as user-visible annotations, such as which rules fired or which classes received content, would help debugging.

Beyond-grammar restrictions through selectors. The context-sensitive restriction benchmark (triggerself is valid only inside state machine actions) maps onto gen-select’s selector algebra. within expresses “this pattern is valid only when an ancestor matches X”. Selectors serve as rule conditions and could also be offered as a user-facing constraint on aspects.

Research Directions

An embedding benchmark for gen-scope. Implementing the LWC’13 QL/QLS challenge as a gen-scope attribute grammar, with the questionnaire as scope-graph nodes, validation as inherited and synthesised attributes and rendering as output attributes, would give a concrete comparison with the ten workbenches and measure the cost or benefit of the embedded approach.

Composability metrics. No workbench achieves full composability across all six parts. Formal metrics, such as how many independently developed aspects combine without glue code, merge conflicts or semantic interference, would test whether aspects are the right composition granularity.

Projectional editing for scope graphs. MPS shows that projectional editing allows unlimited syntactic composition because nothing is parsed. An editor where the user edits a projection of the scope graph instead of raw Nix would move a gen framework toward a full workbench. The scope graph’s hierarchy, nodes with parent and import edges, projects naturally as tree views and graph diagrams.