Skip to main content

Posts

Showing posts from September, 2008

Tagless Interpreters in C#

Creating DSLs is all the rage these days, and for good reason. Most abstractions are actually a little language struggling to get out. Design consists of creating abstractions with maximum power, and minimum restrictions, and reusing this abstraction as much as possible. Small domain-specific languages are the ticket.

However, language implementations are often written in fairly ad-hoc ways, and most interpreters are difficult to extend to compilers and partial evaluators. Languages are usually described by an "initial algebra", which basically just means that language terms are described by data types. Here's a simple definition of a language with integers, variables and addition:

(*
* Expressions := [0-9]* | e1 + e2 | e1 - e2
*)
type expression = Int of int | Add of expression * expression | Sub of expression * expression
So a program in this language can consist of integers, subtraction or addition expressions. The interpreter for this language unpacks the expression by c…