Harnessing OCaml GADTs to Build a Type‑Safe Domain‑Specific Language

Why Type‑Safe DSLs Matter

Domain‑specific languages (DSLs) are great for expressing domain logic concisely. But when the DSL is interpreted at runtime, a typo or a mismatched operand can cause a crash or, worse, subtle bugs that only show up in production. OCaml’s Generalized Algebraic Data Types (GADTs) give you a way to encode these invariants at compile time, turning many classes of runtime errors into compile‑time failures.

The Problem: Untyped Arithmetic Expressions

Consider a simple arithmetic DSL that supports integers, booleans, and addition. A naïve representation might look like this:

type expr =
  | Int of int
  | Bool of bool
  | Add of expr * expr
  | Eq  of expr * expr

When you write an evaluator, you’ll need to pattern‑match on every constructor and manually enforce that operands are of the correct type. A mistake such as adding a boolean to an integer will compile, but will throw a runtime exception when the evaluator tries to interpret the expression.

GADTs to the Rescue

GADTs let each constructor specify the exact type it returns, so the compiler can track the “type” of an expression as a type parameter. Here’s a minimal GADT that captures the same DSL but guarantees that operations are applied only to compatible operands:

type _ expr =
  | Int : int -> int expr
  | Bool : bool -> bool expr
  | Add : int expr * int expr -> int expr
  | Eq  : 'a expr * 'a expr -> bool expr

The underscore in _ expr introduces a type parameter that the compiler will infer. Each constructor now carries a concrete return type, e.g., Int returns int expr, Add returns int expr only if both operands are int expr, and Eq returns bool expr only if both operands have the same type.

How the Compiler Helps

• Type Inference: When you write Add (Int 1, Int 2), the compiler infers the type as int expr and rejects Add (Int 1, Bool true) at compile time.
• Exhaustiveness Checking: Pattern matching on expr will enforce that all constructors are handled, and the compiler will warn if you forget a case.
• No Runtime Checks: Since the type system guarantees validity, the evaluator can be written without explicit type tests.

A Concrete Worked Example

Let’s walk through a minimal project that defines the GADT, an evaluator, and a few test expressions. Create a file expr.ml with the following content:

(* expr.ml *)

(* 1. GADT definition *)

type _ expr =
  | Int : int -> int expr
  | Bool : bool -> bool expr
  | Add : int expr * int expr -> int expr
  | Eq  : 'a expr * 'a expr -> bool expr

(* 2. Evaluator *)
let rec eval : type a. a expr -> a = function
  | Int n -> n
  | Bool b -> b
  | Add (x, y) -> eval x + eval y
  | Eq (x, y) -> eval x = eval y

(* 3. Sample expressions *)
let expr1 = Add (Int 3, Int 4)            (* 7 *)
let expr2 = Eq (Int 5, Int 5)              (* true *)
let expr3 = Eq (Bool true, Bool false)     (* false *)

(* 4. Compile‑time safety test: this line would fail to compile
   let bad = Add (Int 1, Bool true)   *)

Compile with the OCaml compiler or Dune:

# Using the compiler directly
ocamlc -c expr.ml

# Using Dune (create dune file with (library (name expr)))
dune build

If you uncomment the line that constructs bad, the compiler emits an error similar to:

Error: This expression has type bool expr but an expression was expected of type int expr

Notice that the error is caught before the program runs. Running the evaluator on expr1, expr2, and expr3 yields the expected results, which you can test in the OCaml REPL:

# #use "expr.ml";;
# eval expr1;;
- : int = 7
# eval expr2;;
- : bool = true
# eval expr3;;
- : bool = false

Trade‑Offs and Limitations

• Compile Time: GADTs add extra type‑checking work. In large codebases, you may notice longer compile times, especially when many GADT definitions interact.
• Readability: The syntax type _ expr = | C : ty -> expr can be unfamiliar to developers who haven’t seen GADTs before. Adding comments or a small “cheat sheet” inside the module helps.
• Verbose Pattern Matching: When the compiler can’t infer the type, you may need to add explicit type annotations to pattern matches, which can clutter the code.
• Debugging Messages: Type errors in GADTs can be cryptic. Using the -w +A flag to warn about unused patterns often surfaces hidden problems early.
• Overkill for Simple DSLs: For very small or trivial DSLs, the added complexity may not justify the safety benefits. Use GADTs when you need to encode non‑trivial invariants.

Actionable Next Steps

1. Start Small: Create a tiny GADT for a subset of your DSL and write an evaluator. Verify that ill‑typed expressions fail to compile.
2. Incrementally Refactor: Replace existing ordinary ADTs with GADTs one module at a time. Keep tests in place to catch regressions.
3. Leverage Dune: Use Dune to manage compilation and automatically recompile when dependencies change. Add (warnings +A) to your dune file to catch unreachable patterns.
4. Document the Invariants: In module comments, describe the type‑level guarantees each constructor enforces. This aids future maintainers.
5. Explore Advanced GADTs: Once comfortable, experiment with polymorphic GADTs or higher‑rank types to encode more powerful invariants—e.g., a matrix DSL that tracks dimensions at the type level.

By embracing GADTs, you shift error detection from runtime to compile time, gaining confidence that your DSL behaves as intended. While the upfront learning curve is real, the payoff in safety and maintainability—especially for complex domain logic—can be substantial.