Implementing a DSL

The simplest thing that works: keep the AST and write an evaluator that recurses over it. A hundred lines for a small language, easy to debug because everything is a host-language call stack, and easy to extend because a new construct is a new case in one function.

It is also slow — every evaluation re-dispatches on node types and re-walks the tree — and slow is often fine. A validation rule set evaluated once per request, a configuration expression evaluated at startup, a query filter over a few hundred rows: none of these care. The rule of thumb is that tree walking is right until the program is evaluated in a loop over many items, at which point the dispatch overhead starts to dominate the actual work.

The thing tree walking gets uniquely right is error attribution. The evaluator is holding the node, and the node has a source span, so a run-time failure can point at the exact character range in the user's file. Every other strategy has to work to preserve that, and several lose it. For a language whose users are not programmers, this alone can settle the choice — see [[tree-walk-interpreter]].

Translate the DSL program into host-language source or host AST nodes, and let the host compiler do the rest. The generated code then runs at full host speed, is optimized by the host optimizer, and is debugged by the host debugger. For a domain language whose programs are hot, this is usually the highest-value strategy per unit of effort, because the entire back end is somebody else's.

The catch is semantic drift, and it is subtle. Emitting a + b for the DSL's addition inherits the host's addition: its overflow behaviour, its string-versus-number coercion, its precision. If the DSL specifies saturating arithmetic and the host wraps, the generated code is wrong in a way that appears only at the boundary. Every construct needs its semantics checked against the host's rather than assumed, and where they differ the emitted code must be explicit — a call to a helper rather than an operator.

The second catch is diagnostics. A type error in the generated code is reported by the host compiler, at a line in a generated file, in the host's vocabulary. Users see a message about a construct they never wrote in a file they have never opened. Mitigating this means either checking thoroughly enough in your own front end that the host never rejects the output — the right answer — or emitting source maps so positions map back, which is [[source-maps]] and is real work.

Between the two: lower the AST to a linear instruction sequence for a small virtual machine you write, and interpret that. The dispatch is now a switch over opcodes on a flat array rather than a recursive walk over pointers, which is typically several times faster than tree walking for the same program, and far less work than compiling to the host.

Bytecode buys three things beyond speed. The program becomes a compact artifact that can be cached, shipped and versioned separately from its source. Execution can be bounded: a step counter in the dispatch loop gives a hard limit on how long a program can run, and a memory cap gives one on how much it can allocate — which matters enormously for any language that runs untrusted programs. And the VM is a natural sandbox, because a program can only do what the instruction set permits.

The cost is that you now own a VM, an instruction set and a debugging story for both. A bug in the compiler produces bytecode that misbehaves, and diagnosing it means reading the instruction stream. If the language is small and the performance is adequate from tree walking, this rung is skippable — see [[bytecode]] and [[stack-based-vm]] for the machinery itself.

The same translation as compiling to the host, moved earlier: run it during the build, write host source into the repository or into a build directory, and compile it with everything else. Protocol Buffers, GraphQL client generators, ORM model generators and parser generators all work this way.

The advantage is that every error moves to build time, in your own front end, with your own messages, before anything is deployed. The generated code is ordinary host code — readable, steppable, profilable — and the host toolchain sees it as it sees everything else. For a language whose program set is known ahead of deployment, this is frequently the best of all the options.

The costs are build-system costs. The generated artifact must be regenerated whenever its input changes or the two silently diverge, which means the dependency has to be declared properly — a build-graph problem, and the usual failure is a stale artifact that compiles fine and behaves as an older version of the rules. Checking generated code into the repository makes diffs noisy and merges unpleasant; not checking it in makes the build a prerequisite for reading the code. Both are defensible and both are annoying.

The cheapest strategy, and the one people do not count as implementing a language: express the programs as JSON, YAML or TOML, validate them against a schema, and interpret the resulting structure. There is no parser to write — the format has one — no grammar to design, and the schema ecosystem provides validation, editor completion and documentation generation for free.

It is worth being explicit that this *is* a DSL. A JSON document with a schema, interpreted by an engine that gives its fields meaning, is a program in a language whose grammar happens to be JSON's. Calling it configuration rather than a language does not change what it is, and it does change how carefully people think about its design — which is precisely why so many of these grow into unmaintainable systems one field at a time.

The strategy is right when the programs are genuinely declarations: no conditionals, no loops, no name binding, no reuse. It stops being right the moment any of those is needed, and the standard failure is to add them anyway, in the format, as templating or as string-encoded expressions. At that point you have a language with no parser, no types and no diagnostics, which is the most expensive point on the whole spectrum — see [[configuration-languages]] for that trajectory in detail.

The strategies are not exclusive and the good implementations mix them. A common and effective shape: parse and check in a front end you own, interpret by tree walking for correctness and for the error messages, and add a compilation path later only for the programs that turn out to be hot. Because the front end is shared, both paths agree by construction, and the tree walker becomes the reference implementation the compiled path is differentially tested against — which is [[differential-testing]] applied to your own language.

The decision order that works: start with the cheapest strategy that could plausibly serve, and move only when a measurement says to. Data plus schema if the programs are declarations. Tree walking if they are not. Bytecode if execution needs bounding or the programs are evaluated in a loop. Host compilation or build-time generation if they are genuinely hot or the program set is known in advance.

And whichever is chosen, the error path is the part that determines whether the language is usable. Spans from the source file must survive into every message the user can see, at parse time, at check time and at run time. Every strategy above can do this and most implementations of each do not, and that single omission is the difference between a language people adopt and one they route around.