☀ Light
code header

Markedly: A Cartographic Approach for Mapping eDSL Implementation Costs

Matthew P. Ahrens, Karl Cronburg, and Jeanne-Marie Musca — Siriusly PL Lab, Tufts University. — Back to overview — PDF poster — Talk slides

The problem

Embedded domain-specific languages (eDSLs) are difficult to design, implement, and maintain over time. eDSL creators want to:

  • Preserve — the correctness of the design D in the implementation I
  • Extend — D and I to support new features
  • Adhere — exclusively to D in I
  • Recognize — source spans in I as features in D

Definitions

  • Design D — a set of features
  • Implementation I — a set of source code spans (s, e), from start to end in characters

Running example: Type-Level Naturals (TLN)

Language creator Mark wants to create an eDSL in Haskell with the ability to annotate Haskell types with natural numbers. He writes down three desired features:

  1. Human-readable natural number weights
  2. Attach weights to arbitrary expressions
  3. Sum weights across function application

Mark implements a prototype of TLN:

data Nat = Z | S Nat
type Weighted (w :: Nat) a = a
type family
  (w1 :: Nat) :+: (w2 :: Nat) :: Nat
type instance Z :+: m = m
type instance (S n) :+: m = S (n :+: m)
($$) :: Weighted w1 (a -> b)
     -> Weighted w2 a
     -> Weighted (w1 :+: w2) b
($$) f a = f a

The TLN map

With the implementation in hand, Mark hand-draws a Markedly map depicting how meta-information flows through the code. The map connects each implementation element to the design features it realizes.

PEAR metrics

  • P (Preserve) — how many features in D are compromised in I?
  • E (Extend) — how many spans in I have inaccessible intermediate representations?
  • A (Adhere) — how many spans in I are merely supporting annotations for a feature in D?
  • R (Recognize) — how many spans in I do not map to any feature in D?

TLN PEAR costs

Element       P   E   A   R
Nat           1   ·   ·   ·
Weighted      ·   ·   1   ·
w :: Nat      ·   ·   ·   1
$$            ·   ·   1   ·
:+:           ·   ·   ·   1
──────────────────────────────
cost(D,I)  =  1   ·   2   4

Key observations

  • A weak or vague design D incurs high A and R costs
  • Prototype implementations sacrifice P in favor of E
  • Markedly fits into an iterative design-and-implementation workflow
  • Note: Adherence and Recognition costs are similar; distinguishing "superfluous" spans (present in D) from unrecognized spans (not in D) is an open question

Upcoming work

  • Markedly user study
  • Source span highlighting IDE support
  • Git integration
  • Extensible (multi-union) data types

Sponsored by DARPA (contract FA8750-15-2-0033). Views are those of the authors.