TypeScript
Challenge 4: Mini compiler
Solve a task testing the full advanced level.
Mini compiler: AST + guard + exhaustive
The advanced level in summary: model an AST with a discriminated union, narrow with type guards and switch, enforce exhaustiveness with never, and build the expression tree with a recursive type. Together they yield a mini compiler that is compile-time safe and runtime-correct.
type Expr =
| { kind: "num"; value: number }
| { kind: "add"; left: Expr; right: Expr };
function evalE(e: Expr): number {
switch (e.kind) {
case "num": return e.value;
case "add": return evalE(e.left) + evalE(e.right);
}
}
If you add a new node kind, the never check forces every switch to be updated.
Exercise Expression evaluator
Write an Expr discriminated union: num (value: number), add (left, right: Expr), mul (left, right: Expr). Write evalE(e: Expr): number with a switch and an exhaustive const _: never = e in the default branch. Build the expression (1 + 2) * 3 and print the result.
Show example solution
type Expr =
| { kind: "num"; value: number }
| { kind: "add"; left: Expr; right: Expr }
| { kind: "mul"; left: Expr; right: Expr };
function evalE(e: Expr): number {
switch (e.kind) {
case "num":
return e.value;
case "add":
return evalE(e.left) + evalE(e.right);
case "mul":
return evalE(e.left) * evalE(e.right);
default:
const _: never = e;
throw new Error("exhaustive");
}
}
const expr: Expr = { kind: "mul", left: { kind: "add", left: { kind: "num", value: 1 }, right: { kind: "num", value: 2 } }, right: { kind: "num", value: 3 } };
console.log(evalE(expr));
Exercise Evaluate with a type guard
Write the same Expr union. Define a type guard isNum(e: Expr): e is { kind: "num"; value: number }. In evalE, narrow first with isNum(e), then handle add and mul. Build the expression 5 + 10 and print the result.
Show example solution
type Expr =
| { kind: "num"; value: number }
| { kind: "add"; left: Expr; right: Expr }
| { kind: "mul"; left: Expr; right: Expr };
function isNum(e: Expr): e is { kind: "num"; value: number } {
return e.kind === "num";
}
function evalE(e: Expr): number {
if (isNum(e)) return e.value;
if (e.kind === "add") return evalE(e.left) + evalE(e.right);
return evalE(e.left) * evalE(e.right);
}
const expr: Expr = { kind: "add", left: { kind: "num", value: 5 }, right: { kind: "num", value: 10 } };
console.log(evalE(expr));
Test yourself
-
What does the exhaustive check with `never` guarantee?
- Every case contains a `return`
- The switch never loops forever
- A new variant causes a compile error
- The function runs faster
Show answer
A new variant causes a compile error — The exhaustive `never` check produces a compile error when a new variant is added to the union but the `switch` is not updated, catching missed cases early.
-
Exhaustive variable
function evalE(e: Expr): number {
switch (e.kind) {
case "num": return e.value;
case "add": return evalE(e.left) + evalE(e.right);
default:
const _: ____ = e;
throw new Error("exhaustive");
}
}
Show answer
function evalE(e: Expr): number {
switch (e.kind) {
case "num": return e.value;
case "add": return evalE(e.left) + evalE(e.right);
default:
const _: never = e;
throw new Error("exhaustive");
}
}
-
Compiler parts
- Discriminated union
- AST node types
- switch + case
- type narrowing
- never
- exhaustive check
- Recursive type
- nested expression tree
Next lesson: Advanced section exam
