Michael ArnaldiWhy do we even need custom domain-specific languages?
First of all, we should define what do we mean by custom domain-specific languages.
In everyday programming, we have to encode real-world problems in code. We are limited by the power of expressivity of the language we are using. The programming languages are fairly low when it comes to model the real world.
Basically, we translate from a human language to a more basic form of language that a computer can understand.
While translating, and for future reference, we would like to keep the code as close to the real world as possible (easier to get feedback, easier to maintain, to assess).
Domain-specific languages are what is required to fill this gap, your application can be thought of as a series of modules each translating into progressively lower-level concepts so you encapsulate implementation details from business features and keep the code in a maintainable state.
Each of those modules exposes an API that other modules consume, the API is itself a domain-specific language.
Domain-specific languages are challenging, and there are multiple ways to do things (and trade-offs attached).
Usually, we think of a DSL to be tied to a single interpreter but that is not always the case, for example, we can think of a DSL to describe domain objects and out of the description we would like to get things like a serializer, a deserializer, an arbitrary, a comparator and many other things.
Generally, we can think of a DSL as an algebra of operations that can be interpreted in one or many ways.
So how can we build DSLs efficiently? In this blog post, we are going to discuss Final Encodings and Initial Encodings and look at many ways of implementing those.
Final Encoding
Starting from the easy one, Final Encoding means defining the language in terms of its direct interpretation.
Final Encodings are usually efficient but they come at a price, defining the language in terms of its interpretation means not having the possibility of multiple interpretations, they are harder to optimize (sometimes impossible) and many times unsafe (primarily due to stack safety in the js space).
Let's take a base example, we would like to model synchronous failable computations, we could encode the problem using a type like the following:
import { pipe } from "@effect-ts/core/Function";
//
// DSL
//
export class Failure<E> {
readonly _tag = "Failure";
constructor(readonly error: E) {}
}
export class Success<A> {
readonly _tag = "Success";
constructor(readonly result: A) {}
}
export type Result<E, A> = Failure<E> | Success<A>;
export class IO<E, A> {
readonly _tag = "IO";
constructor(readonly thunk: () => Result<E, A>) {}
}
export function succeed<A>(a: A): IO<never, A> {
return new IO(() => new Success(a));
}
export function fail<E>(e: E): IO<E, never> {
return new IO(() => new Failure(e));
}
export function succeedWith<A>(f: () => A): IO<never, A> {
return new IO(() => new Success(f()));
}
export function failWith<E>(e: () => E): IO<E, never> {
return new IO(() => new Failure(e()));
}
export function tryCatch<E, A>(
f: () => A,
onError: (_: unknown) => E
): IO<E, A> {
return new IO(() => {
try {
return new Success(f());
} catch (e) {
return new Failure(onError(e));
}
});
}
export function chain<A, E1, B>(that: (a: A) => IO<E1, B>) {
return <E>(self: IO<E, A>): IO<E | E1, B> =>
new IO<E | E1, B>(() => {
const a = self.thunk();
if (a._tag === "Success") {
return that(a.result).thunk();
}
return a;
});
}
export function suspend<E, A>(f: () => IO<E, A>): IO<E, A> {
return new IO(() => f().thunk());
}
export function run<E, A>(io: IO<E, A>): Result<E, A> {
return io.thunk();
}
//
// Usage
//
const program = pipe(
succeed(0),
chain((n) => succeed(n + 1)),
chain((n) => succeed(n * 2)),
chain((n) =>
succeedWith(() => {
console.log(`computed: ${n}`);
})
)
);
You can find the code at the following sandbox: Link
In this case, we decided to encode a failable operation with a thunk of code and our language allows for composition of operations by composition of the thunks of each operation.
Separately we can execute the program by calling up the thunk via the run method and the operations contained in the program description (including side effects) will be executed to return a result.
Let's look at the trade-offs, in this case, perf can't get any better and we don't really need multiple interpretations of a program so everything looks good!
Except if we try large recursive procedures like:
import { pipe } from "@effect-ts/core/Function";
import * as IO from "./io";
function factorial(n: number): IO.IO<never, number> {
if (n === 0) {
return IO.succeed(1);
}
return pipe(
IO.suspend(() => factorial(n - 1)),
IO.chain((x) => IO.succeed(x * n))
);
}
And try to compute factorial(100_000) you will get:
RangeError
Maximum call stack size exceeded
Now, that's a dumb way to compute a factorial but in real life, you might encounter frequently problems that will blow up the stack.
Initial Encoding
The idea behind initial encoding is to encode the DSL itself so in the previous example we would like to encode IO in terms of its operations (succeed, fail, suspend, chain, etc).
That is not the easiest thing, before being able to do so we need to take a few steps.
The first concepts we will see are plain and simple ADTs (Algebraic Data Types).
For general reference Algebraic Data Type is a broader term that can refer to types constructed as results of operations on types, those can be A | B, A & B, A ^ B, A / B, A x B, and many more.
For the purpose of this blog and in general, when you hear ADTs we mean unions of types, so things of the form A | B | C | D.
Let's try to encode the following problem: We would like to express basic algebraic operations (add, mul, div, etc) for numeric values.
We can do something like:
import { pipe } from "@effect-ts/core/Function";
//
// DSL
//
export type Expr = Val | Add | Mul | Sub | Div;
export class Val {
readonly _tag = "Val";
constructor(readonly value: number) {}
}
export function val(value: number): Expr {
return new Val(value);
}
export class Add {
readonly _tag = "Add";
constructor(readonly left: Expr, readonly right: Expr) {}
}
export function add(right: Expr) {
return (left: Expr): Expr => new Add(left, right);
}
export class Mul {
readonly _tag = "Mul";
constructor(readonly left: Expr, readonly right: Expr) {}
}
export function mul(right: Expr) {
return (left: Expr): Expr => new Mul(left, right);
}
export class Sub {
readonly _tag = "Sub";
constructor(readonly left: Expr, readonly right: Expr) {}
}
export function sub(right: Expr) {
return (left: Expr): Expr => new Sub(left, right);
}
export class Div {
readonly _tag = "Div";
constructor(readonly left: Expr, readonly right: Expr) {}
}
export function div(right: Expr) {
return (left: Expr): Expr => new Div(left, right);
}
//
// Usage
//
export const operation = pipe(
val(0),
add(val(1)),
mul(pipe(val(1), div(val(3)))),
sub(val(2))
);
Sandbox at: Link
We've represented an Expr in a "free" way, meaning an Expr is the set of operations that is composed of.
We should note that we were able to write a program operation using multiple primitives without ever defining the meaning of the primitives themselves.
Lets now define an interpreter that computes the operation:
import * as Expr from "./expr";
export function compute(expr: Expr.Expr): number {
switch (expr._tag) {
case "Add": {
return compute(expr.left) + compute(expr.right);
}
case "Mul": {
return compute(expr.left) * compute(expr.right);
}
case "Div": {
return compute(expr.left) / compute(expr.right);
}
case "Sub": {
return compute(expr.left) - compute(expr.right);
}
case "Val": {
return expr.value;
}
}
}
And running compute(operation) will result in the computed value.
We can see here that the compute function (the interpreter) has a recursive nature, which means large expressions will fail and blow up the stack.
But that recursion is contained in a single procedure that we could "easily" rewrite in a non-recursive manner making our language safe.
For the purpose of completeness, it is worth taking a look at the steps necessary to transform a general recursive program into an iterative one, the idea is that we will have a series of loops that progressively traverse the operations while preserving a stack of the remaining things to do.
What before was a nice and simple procedure now becomes an awful (but safe) piece of code:
import * as Expr from "./expr";
export function computeSafe(expr: Expr.Expr): number {
let result: number | undefined;
type Frame =
| { _tag: "Add"; right: Expr.Expr }
| { _tag: "AddValue"; value: number }
| { _tag: "Mul"; right: Expr.Expr }
| { _tag: "MulValue"; value: number }
| { _tag: "Sub"; right: Expr.Expr }
| { _tag: "SubValue"; value: number }
| { _tag: "Div"; right: Expr.Expr }
| { _tag: "DivValue"; value: number };
const stack: Frame[] = [];
recursing: while (1) {
pushing: while (1) {
switch (expr._tag) {
case "Val": {
result = expr.value;
break pushing;
}
case "Add": {
stack.push({ _tag: "Add", right: expr.right });
expr = expr.left;
continue pushing;
}
case "Mul": {
stack.push({ _tag: "Mul", right: expr.right });
expr = expr.left;
continue pushing;
}
case "Sub": {
stack.push({ _tag: "Sub", right: expr.right });
expr = expr.left;
continue pushing;
}
case "Div": {
stack.push({ _tag: "Div", right: expr.right });
expr = expr.left;
continue pushing;
}
}
}
popping: while (1) {
if (stack.length === 0) {
return result!;
}
const frame = stack.pop()!;
switch (frame._tag) {
case "Add": {
expr = frame.right;
stack.push({ _tag: "AddValue", value: result! });
result = undefined;
continue recursing;
}
case "AddValue": {
result = frame.value + result!;
continue popping;
}
case "Mul": {
expr = frame.right;
stack.push({ _tag: "MulValue", value: result! });
result = undefined;
continue recursing;
}
case "MulValue": {
result = frame.value * result!;
continue popping;
}
case "Div": {
expr = frame.right;
stack.push({ _tag: "DivValue", value: result! });
result = undefined;
continue recursing;
}
case "DivValue": {
result = frame.value / result!;
continue popping;
}
case "Sub": {
expr = frame.right;
stack.push({ _tag: "SubValue", value: result! });
result = undefined;
continue recursing;
}
case "SubValue": {
result = frame.value - result!;
continue popping;
}
}
}
}
// eslint-disable-next-line
throw new Error("non reachable");
}
As we can see we are now in full control of how the interpreter b behaves and we can make it safe, with the same idea in mind we will be able to make the previous module (IO) safe to use.
Exercise to the reader: implement print(expression): string that renders the expression like (1 + (3 * (4 / 1)))
Phantom Types & GADTs
We are now able to encode a generic DSL but we haven't introduced generics into the equation, Expr from before was only representing a numeric expression, what if we want an expression that can be numeric or string-based?
Also what if some operations are only relevant to numeric expressions and literal expressions?
We would like to have some form of: type Expr<A> where A can be number | string depending on the type of the expression.
In languages like Scala, we are able to define closed "interfaces" (sealed traits, sealed abstract classes) meaning interfaces implementable only by a specific number of concrete classes (like only in the same file).
In TS we have union types, so we could say:
type Expr<A> = NumericValue | Add | Mul | ... | StringValue | Concat | Stringify
The problem is A is unused here (phantom), and also there is no information that given a value NumericValue that actually corresponds to Expr<number>.
To simulate this behavior we will add the A parameter to every primitive so NumericValue will become NumericValue<A> and in the definition of NumericValue we will not only require a value of type number but we will also require a function _A: (n: number) => A that converts a number into the generic A.
the function _A will be filled by the constructor function numericValue(value: number): Expr<number> as an identity function.
That ensures A is fixed to number in the context of a NumericValue and will be used in the interpreter to return a generic A when dealing with concrete values of type number.
Let's see the code:
import { identity, pipe } from "@effect-ts/core/Function";
export type Expr<A> =
| NumberValue<A>
| StringValue<A>
| Add<A>
| Mul<A>
| Sub<A>
| Div<A>
| Stringify<A>
| Concat<A>;
export class NumberValue<A> {
readonly _tag = "NumberValue";
constructor(readonly value: number, readonly _A: (_: number) => A) {}
}
export function numeric(value: number): Expr<number> {
return new NumberValue(value, identity);
}
export class StringValue<A> {
readonly _tag = "StringValue";
constructor(readonly value: string, readonly _A: (_: string) => A) {}
}
export function string(value: string): Expr<string> {
return new StringValue(value, identity);
}
export class Add<A> {
readonly _tag = "Add";
constructor(
readonly left: Expr<number>,
readonly right: Expr<number>,
readonly _A: (_: number) => A
) {}
}
export function add(right: Expr<number>) {
return (left: Expr<number>): Expr<number> => new Add(left, right, identity);
}
export class Mul<A> {
readonly _tag = "Mul";
constructor(
readonly left: Expr<number>,
readonly right: Expr<number>,
readonly _A: (_: number) => A
) {}
}
export function mul(right: Expr<number>) {
return (left: Expr<number>): Expr<number> => new Mul(left, right, identity);
}
export class Sub<A> {
readonly _tag = "Sub";
constructor(
readonly left: Expr<number>,
readonly right: Expr<number>,
readonly _A: (_: number) => A
) {}
}
export function sub(right: Expr<number>) {
return (left: Expr<number>): Expr<number> => new Sub(left, right, identity);
}
export class Div<A> {
readonly _tag = "Div";
constructor(
readonly left: Expr<number>,
readonly right: Expr<number>,
readonly _A: (_: number) => A
) {}
}
export function div(right: Expr<number>) {
return (left: Expr<number>): Expr<number> => new Div(left, right, identity);
}
export class Stringify<A> {
readonly _tag = "Div";
constructor(readonly child: Expr<number>, readonly _A: (_: string) => A) {}
}
export function stringify(child: Expr<number>): Expr<string> {
return new Stringify(child, identity);
}
export class Concat<A> {
readonly _tag = "Concat";
constructor(
readonly left: Expr<string>,
readonly right: Expr<string>,
readonly _A: (_: string) => A
) {}
}
export function concat(right: Expr<string>) {
return (left: Expr<string>): Expr<string> =>
new Concat(left, right, identity);
}
//
// Usage
//
// Expr<number>
export const operation = pipe(
numeric(0),
add(numeric(1)),
mul(pipe(numeric(1), div(numeric(3)))),
sub(numeric(2))
);
// Expr<string>
export const operationStr = pipe(
string("operation:"),
concat(stringify(operation))
);
Let's write for simplicity a recursive interpreter, we know from before how to eventually make it stack-safe.
import * as Expr from "./gadt-expr";
export function compute<A>(expr: Expr.Expr<A>): A {
switch (expr._tag) {
case "Add": {
return expr._A(compute(expr.left) + compute(expr.right));
}
case "Mul": {
return expr._A(compute(expr.left) * compute(expr.right));
}
case "Div": {
return expr._A(compute(expr.left) / compute(expr.right));
}
case "Sub": {
return expr._A(compute(expr.left) - compute(expr.right));
}
case "NumberValue": {
return expr._A(expr.value);
}
case "StringValue": {
return expr._A(expr.value);
}
case "Concat": {
return expr._A(compute(expr.left) + compute(expr.right));
}
case "Stringify": {
return expr._A(String(compute(expr.child)));
}
}
}
We can see that now compute is fully generic on A and how the identity function _A keeps track of the relationship concrete <> phantom.
Using the above compute(operationStr) will yield a string result, have a look at Link.
Existential Types
There is only one step left to do before being able to fully encode IO<E, A> using an initial representation, using the trick above we could implement almost all the primitives Success, Failure, etc except for Chain.
Chain should contain an operation of type IO<E, A> and a function f: (a: A) => IO<E1, B> and it should represent overall an IO<E | E1, B>.
If we think IO as type IO<E, A> = Success<E, A> | Failure<E, A> | ... | Chain we should have a Chain<E, A>.
There are a few types missing from the equation, those types are known as "Existential" meaning types that only exist within a bounded context in this case the Chain operation.
Existential types are very common when it comes to model continuations (like chain, operations that depend on the result of something else, and a set of functions that specify how to "continue", whatever "continue" means in context).
In order to model these additional parameters, we are going to model the behavior of using Chain instead of modeling Chain itself, meaning we will provide a use function that has to be used to access the content of Chain.
Let's get to code:
import { identity, pipe } from "@effect-ts/core/Function";
export type IO<E, A> =
| Success<E, A>
| Failure<E, A>
| Suspend<E, A>
| Chain<E, A>;
export class Success<E, A> {
readonly _tag = "Success";
constructor(readonly value: A, readonly _E: (_: never) => E) {}
}
export function succeed<A>(value: A): IO<never, A> {
return new Success(value, identity);
}
export class Failure<E, A> {
readonly _tag = "Failure";
constructor(readonly error: E, readonly _A: (_: never) => A) {}
}
export function fail<E>(error: E): IO<E, never> {
return new Failure(error, identity);
}
export class Suspend<E, A> {
readonly _tag = "Suspend";
constructor(readonly io: () => IO<E, A>) {}
}
export function suspend<E, A>(io: () => IO<E, A>): IO<E, A> {
return new Suspend(io);
}
export class Chain<E, A> {
readonly _tag = "Chain";
constructor(
readonly use: <X>(
body: <E0, A0, E1, A1>(_: {
readonly _E: (_: E0 | E1) => E;
readonly _A: (_: A1) => A;
readonly io: IO<E0, A0>;
readonly f: (a: A0) => IO<E1, A1>;
}) => X
) => X
) {}
}
export function chain<A0, E1, A1>(f: (a: A0) => IO<E1, A1>) {
return <E0>(io: IO<E0, A0>): IO<E0 | E1, A1> =>
new Chain((body) =>
body({
io,
f,
_E: identity,
_A: identity
})
);
}
export function succeedWith<A>(f: () => A): IO<never, A> {
return suspend(() => succeed(f()));
}
export function failWith<E>(e: () => E): IO<E, never> {
return suspend(() => fail(e()));
}
export function tryCatch<E, A>(
f: () => A,
onError: (_: unknown) => E
): IO<E, A> {
return suspend(() => {
try {
return succeed(f());
} catch (e) {
return fail(onError(e));
}
});
}
//
// Usage
//
export const program = pipe(
succeed(0),
chain((n) => succeed(n + 1)),
chain((n) => succeed(n * 2)),
chain((n) =>
succeedWith(() => {
console.log(`computed: ${n}`);
})
)
);
As we can see instead of having Chain contain io and f instead it contains a function use that takes a body thunk providing parameters to the body.
To interact with Chain we will use the use function by passing in use(({io, ...}) => do stuff).
Interpreter time, starting with the recursive one:
import * as E from "@effect-ts/core/Either";
import * as IO from "./existential-io";
export function run<E, A>(io: IO.IO<E, A>): E.Either<E, A> {
switch (io._tag) {
case "Success": {
return E.right(io.value);
}
case "Failure": {
return E.left(io.error);
}
case "Suspend": {
return run(io.io());
}
case "Chain": {
return io.use(({ io, f, _E, _A }) => {
const res = run(io);
if (res._tag === "Right") {
const resB = run(f(res.right));
if (resB._tag === "Left") {
return E.left(_E(resB.left));
} else {
return E.right(_A(resB.right));
}
} else {
return E.left(_E(res.left));
}
});
}
}
}
As we can see to deal with Chain we have to use a function (that is BTW not free perf-wise).
This simple recursive interpreter will have the same issue as the Final Encoding in running large recursive operations.
Also, the types are a bit verbose, on the plus side, everything is truly type-safe.
I personally think in most cases this encoding should be the first to be tried when building the first scratch of your modules and the perf compromise (calling _E, _A, use, etc) is negligible compared to the actual cost of the operations we model, leveraging the type-safety and the compiler help is definitely important in driving the correct implementation of the primitives and the interpreter.
When it comes to the conversion of the above to a non-recursive procedure we will, unfortunately, lose this nice safety.
Let's see how it would look like:
import * as E from "@effect-ts/core/Either";
import { pipe } from "@effect-ts/core/Function";
import * as IO from "./existential-io";
export function runSafe<E, A>(io: IO.IO<E, A>): E.Either<E, A> {
let result = undefined;
let isError = false;
let current: IO.IO<any, any> = io;
type Frame = { _tag: "ChainCont"; f: (_: any) => IO.IO<any, any> };
const stack: Frame[] = [];
recursing: while (1) {
pushing: while (1) {
switch (current._tag) {
case "Success": {
isError = false;
result = current.value;
break pushing;
}
case "Failure": {
isError = true;
result = current.error;
break pushing;
}
case "Suspend": {
current = current.io();
continue pushing;
}
case "Chain": {
current.use(({ io, f }) => {
stack.push({ _tag: "ChainCont", f });
current = io;
});
continue pushing;
}
}
}
popping: while (1) {
if (stack.length === 0) {
break recursing;
}
const frame = stack.pop()!;
switch (frame._tag) {
case "ChainCont": {
if (!isError) {
current = frame.f(result);
continue recursing;
} else {
continue popping;
}
}
}
}
}
return isError ? E.left(result) : E.right(result);
}
//
// Recursive factorial
//
function factorial(n: bigint): IO.IO<never, bigint> {
if (n === BigInt(0)) {
return IO.succeed(BigInt(1));
}
return pipe(
IO.suspend(() => factorial(n - BigInt(1))),
IO.chain((x) => IO.succeed(x * n))
);
}
Sandbox at Link
Running the above in sandbox will fail because browsers have limited memory but if you run it in node it will output an insanely large number.
Optimized Variant
Given at the end if we make stack safe interpreters we are bailing out of type safety at the interpreter level we could remove the need for calling _E, _A, use and relax the type safety of primitives using fake functions to instruct the type-system on the correct variance of parameters.
We will end up with something like:
/* eslint-disable @typescript-eslint/no-non-null-assertion */
/* eslint-disable no-constant-condition */
import * as E from "@effect-ts/core/Either"
import { pipe } from "@effect-ts/core/Function"
export type IO<E, A> = Success<E, A> | Failure<E, A> | Suspend<E, A> | Chain<E, A>
export class Success<E, A> {
readonly _tag = "Success"
readonly _E!: () => E
readonly _A!: () => A
constructor(readonly value: any) {}
}
export function succeed<A>(value: A): IO<never, A> {
return new Success(value)
}
export class Failure<E, A> {
readonly _tag = "Failure"
readonly _E!: () => E
readonly _A!: () => A
constructor(readonly error: any) {}
}
export function fail<E>(error: E): IO<E, never> {
return new Failure(error)
}
export class Suspend<E, A> {
readonly _tag = "Suspend"
readonly _E!: () => E
readonly _A!: () => A
constructor(readonly io: () => IO<any, any>) {}
}
export function suspend<E, A>(io: () => IO<E, A>): IO<E, A> {
return new Suspend(io)
}
export class Chain<E, A> {
readonly _E!: () => E
readonly _A!: () => A
readonly _tag = "Chain"
constructor(readonly io: IO<any, any>, readonly f: (a: any) => IO<any, any>) {}
}
export function chain<A0, E1, A1>(f: (a: A0) => IO<E1, A1>) {
return <E0>(io: IO<E0, A0>): IO<E0 | E1, A1> => new Chain(io, f)
}
export function succeedWith<A>(f: () => A): IO<never, A> {
return suspend(() => succeed(f()))
}
export function failWith<E>(e: () => E): IO<E, never> {
return suspend(() => fail(e()))
}
export function tryCatch<E, A>(f: () => A, onError: (_: unknown) => E): IO<E, A> {
return suspend(() => {
try {
return succeed(f())
} catch (e) {
return fail(onError(e))
}
})
}
//
// Usage
//
export const program = pipe(
succeed(0),
chain((n) => succeed(n + 1)),
chain((n) => succeed(n * 2)),
chain((n) =>
succeedWith(() => {
console.log(`computed: ${n}`)
})
)
)
//
// Safe
//
export function runSafe<E, A>(io: IO<E, A>): E.Either<E, A> {
let result = undefined
let isError = false
let current: IO<any, any> = io
type Frame = { _tag: "ChainCont"; f: (_: any) => IO<any, any> }
const stack: Frame[] = []
recursing: while (1) {
pushing: while (1) {
switch (current._tag) {
case "Success": {
isError = false
result = current.value
break pushing
}
case "Failure": {
isError = true
result = current.error
break pushing
}
case "Suspend": {
current = current.io()
continue pushing
}
case "Chain": {
stack.push({ _tag: "ChainCont", f: current.f })
current = current.io
continue pushing
}
}
}
popping: while (1) {
if (stack.length === 0) {
break recursing
}
const frame = stack.pop()!
switch (frame._tag) {
case "ChainCont": {
if (!isError) {
current = frame.f(result)
continue recursing
} else {
continue popping
}
}
}
}
}
return isError ? E.left(result) : E.right(result)
}
//
// Recursive factorial
//
export function factorial(n: bigint): IO<never, bigint> {
if (n === BigInt(0)) {
return succeed(BigInt(1))
}
return pipe(
suspend(() => factorial(n - BigInt(1))),
chain((x) => succeed(x * n))
)
}
Note how we erased types from the content of primitives and how now Chain no longer needs use.
Note also how we use function types to control the variance of the IO type, in every primitive we inhabit the following:
readonly _E!: () => E
readonly _A!: () => A
In this case, both E and A represent outputs so they need to be covariant if we had an input, contravariant, parameter like a context R the computation needs we would inhabit that using:
readonly _R!: (_: R) => void
End
The code in the article is available in github, try it out using gitpod
