The Interpreter Becomes a Compiler
Part 06 of From Lists to Languages · Act II, Types and Extension ·
Syntax is what you write. Core is what it means.
Part 5 put a type checker in front of the evaluator, and ended by pointing out how little the two share. The pipeline was:
parse(source).pipe(
Effect.tap(check),
Effect.flatMap((expr) => evaluate(expr, globals)),
);check works out a type for every expression, and tap throws all of them away. Then evaluate walks the same surface tree again. It looks up every name by string, again. It still checks for unbound names, calls to non-functions, wrong argument counts, and non-numbers passed to +. None of those can happen in a program that checked.
This post makes checking produce something: a second, smaller language called the core, where everything the checker learned is written into the tree. The step from surface syntax to core is called elaboration. Once it exists, the program has two halves: a front end that turns source into core, and a back end that runs core without ever seeing source. That split is what makes it a compiler.
Two languages
The surface language, from Part 4, is what people write. Its Ref is a name, and what it refers to is a question someone has to answer later. Its nodes have spans but no types.
The core language answers those questions up front:
// The core language. Every node carries its settled type and its
// span, and every name is already resolved: a Local is a position
// in the frames around it, and a Global names a built-in.
export const Lit = Schema.TaggedStruct("Lit", {
value: Schema.Number,
type: Type,
span: Span,
});
export const Datum = Schema.TaggedStruct("Datum", {
datum: Sexp,
type: Type,
span: Span,
});
export const Local = Schema.TaggedStruct("Local", {
name: Schema.String,
depth: Schema.Number,
slot: Schema.Number,
type: Type,
span: Span,
});
export const Global = Schema.TaggedStruct("Global", {
name: Schema.String,
type: Type,
span: Span,
});
export interface Lambda {
readonly _tag: "Lambda";
readonly params: ReadonlyArray<string>;
readonly body: Core;
readonly type: Type;
readonly span: Span;
}
export interface Call {
readonly _tag: "Call";
readonly fn: Core;
readonly args: ReadonlyArray<Core>;
readonly type: Type;
readonly span: Span;
}
export type Core =
| typeof Lit.Type
| typeof Datum.Type
| typeof Local.Type
| typeof Global.Type
| Lambda
| Call;
const LazyCore = Schema.suspend((): Schema.Codec<Core> => Core);
export const Lambda = Schema.TaggedStruct("Lambda", {
params: Schema.Array(Schema.String),
body: LazyCore,
type: Type,
span: Span,
});
export const Call = Schema.TaggedStruct("Call", {
fn: LazyCore,
args: Schema.Array(LazyCore),
type: Type,
span: Span,
});
export const Core = Schema.Union([
Lit,
Datum,
Local,
Global,
Lambda,
Call,
]);Three things changed.
- Every node has a type. The checker's work isn't thrown away; it's stored on the node it describes.
- Names are gone. A
Refbecomes either aGlobal, one of the built-ins, or aLocalwith a depth (how many frames out) and a slot (which parameter in that frame). Thenamefield stays only so people can read it. - Nothing is ambiguous. A surface
Callmight call anything. A coreCallhas a function type on itsfn, and the right number ofargs.
The core is still described by a schema, like the syntax in Part 2 and the types in Part 5. That will matter at the end of the post.
Elaboration
At compile time, a frame records the parameters' names and types:
// At compile time, a frame is parameter names and their types.
// Where a name sits (how many frames out, which slot) is all the
// running program will need.
interface Frame {
readonly params: ReadonlyArray<string>;
readonly types: ReadonlyArray<Type>;
readonly parent: Frame | undefined;
}The elaborator is Part 5's checker with one change. Every case used to return a type; now it returns a core node that has a type:
// Part 5's checker, with one change: every case returns a core node
// instead of only a type.
export const elaborate = (expr: Expr): Elab =>
Effect.gen(function* () {
const { fresh, resolve, unify } = makeSolver();
const go = (e: Expr, frame: Frame | undefined): Elab =>
Effect.gen(function* () {
const { span } = e;
switch (e._tag) {
case "Num":
return { _tag: "Lit", value: e.value, type: num, span };
case "Quote":
const { datum } = e;
return { _tag: "Datum", datum, type: data, span };
case "Ref":
return yield* ref(e, frame);
case "Lambda": {
const params = e.params.map((param) => param.name);
const types = params.map(() => fresh());
const inner = { params, types, parent: frame };
const body = yield* go(e.body, inner);
const type = fun(types, body.type);
return { _tag: "Lambda", params, body, type, span };
}
case "Call":
return yield* call(e, frame);
}
});
// Resolve a name now, once, instead of every time it runs.
const ref = (e: Of<"Ref">, frame: Frame | undefined): Elab =>
Effect.gen(function* () {
const { name, span } = e;
let depth = 0;
for (let f = frame; f; f = f.parent, depth++) {
const slot = f.params.indexOf(name);
if (slot === -1) continue;
const type = f.types[slot]!;
return { _tag: "Local", name, depth, slot, type, span };
}
const typeOf = globalTypes.names.get(name);
if (typeOf) {
const type = typeOf(fresh);
return { _tag: "Global", name, type, span };
}
return yield* new UnboundName({ symbol: name, span });
});
const call = (e: Of<"Call">, frame: Frame | undefined): Elab =>
Effect.gen(function* () {
const { span } = e;
const fn = yield* go(e.fn, frame);
const args: Core[] = [];
for (const arg of e.args) args.push(yield* go(arg, frame));
const f = resolve(fn.type);
if (f._tag === "TVar") {
const type = fresh();
const types = args.map((arg) => arg.type);
yield* unify(f, fun(types, type), fn.span);
return { _tag: "Call", fn, args, type, span };
}
if (f._tag !== "TFun") {
const expected = "a function";
const got = showType(f);
const { span } = fn;
return yield* new Mismatch({ expected, got, span });
}
const params = paramsFor(f, args.length);
if (!params) {
const expected = f.params.length;
const got = args.length;
return yield* new ArityError({ expected, got, span });
}
for (const [i, arg] of args.entries()) {
yield* unify(params[i]!, arg.type, arg.span);
}
return { _tag: "Call", fn, args, type: f.result, span };
});
// Inference is over: write the final answers into every node.
const settle = (c: Core): Core => {
const type = resolve(c.type);
switch (c._tag) {
case "Lambda":
return { ...c, type, body: settle(c.body) };
case "Call": {
const args = c.args.map(settle);
return { ...c, type, fn: settle(c.fn), args };
}
default:
return { ...c, type };
}
};
return settle(yield* go(expr, undefined));
});ref is where names stop being names. It walks outward through the frames, counting, until it finds the parameter, and records where it was found. Shadowing falls out of the walk: the innermost frame is checked first.
settle is new. During inference, a node's type may be an unknown that only gets solved later, such as a parameter whose type is decided by how the body uses it. Once inference is finished, settle resolves every node's type, so the core that comes out holds final answers.
Reading core
Here is ((lambda (x) (+ x 1)) 41) after elaboration, printed one node per line:
// Print core as an indented tree: one node per line, with its type.
export const showCore = (
c: Core,
names = new Map<number, string>(),
indent = "",
): string => {
const line = (label: string) =>
`${indent}${label} : ${showType(c.type, names)}`;
const child = (inner: Core) =>
showCore(inner, names, indent + " ");
switch (c._tag) {
case "Lit":
return line(`lit ${c.value}`);
case "Datum":
return line(`datum ${show(c.datum)}`);
case "Local":
return line(`local ${c.name} @${c.depth}.${c.slot}`);
case "Global":
return line(`global ${c.name}`);
case "Lambda":
return [line(`lambda (${c.params.join(" ")})`), child(c.body)]
.join("\n");
case "Call":
return [line("call"), child(c.fn), ...c.args.map(child)]
.join("\n");
}
};call : Num
lambda (x) : (Num) -> Num
call : Num
global + : (Num...) -> Num
local x @0.0 : Num
lit 1 : Num
lit 41 : Numx is now @0.0: zero frames out, slot zero. A name from an enclosing function points further out. In ((lambda (x) ((lambda (y) x) 2)) 1), the inner x elaborates to local x @1.0.
Polymorphic built-ins are settled at each use, too. print has type ('a) -> 'a in general, but in (print (quote hi)) the core records the one type it has there:
call : Data
global print : (Data) -> Data
datum hi : DataUnknowns that stay unknown stay in the core as type variables, which is just what a polymorphic function looks like:
lambda (f x) : (('a) -> 'a, 'a) -> 'a
call : 'a
local f @0.0 : ('a) -> 'a
call : 'a
local f @0.0 : ('a) -> 'a
local x @0.1 : 'aChecking is elaboration
There's no separate check any more. The type of a program is the type at the root of its core:
export type Failure = Diagnostic | CheckError | DivByZero;
// The front end: source in, typed core (or a diagnostic) out.
export const compile = (source: string) =>
parse(source).pipe(Effect.flatMap(elaborate));
// The back end: runs core. It never sees source or infers a type.
export const run = (
source: string,
): Effect.Effect<Value, Failure, Output> =>
compile(source).pipe(
Effect.flatMap((core) => execute(core, undefined)),
);
// Checking is now elaboration, keeping only the type at the root.
export const typeOf = (source: string) =>
compile(source).pipe(Effect.map((core) => showType(core.type)));
export const report = (source: string, error: Failure) =>
render(source, { message: error.message, span: error.span });The site's tests run the programs from Part 5 through both, and they give the same types and the same errors, at the same spans. ((lambda (x) (+ x 1)) (quote a)) still fails before anything runs, with the caret on (quote a).
A runtime that trusts its input
The back end runs core. Its values look like Part 4's, except that a runtime frame holds values in slots and has no names:
// A runtime frame holds values in slots. It has no names: core
// already turned every name into a position.
export interface Env {
readonly slots: ReadonlyArray<Value>;
readonly parent: Env | undefined;
}
export interface Closure {
readonly _tag: "Closure";
readonly params: ReadonlyArray<string>;
readonly body: Core;
readonly env: Env | undefined;
}
export interface Arg {
readonly value: Value;
readonly span: Span;
}
export interface Primitive {
readonly _tag: "Primitive";
readonly name: string;
readonly apply: (args: ReadonlyArray<Arg>) => Run;
}
export type Value = number | Sexp | Primitive | Closure;
// The only way a checked program can fail: dividing by zero.
type Run = Effect.Effect<Value, DivByZero, Output>;
export const display = (v: Value): string =>
typeof v === "number" ? String(v)
: v._tag === "Primitive" ? `#<primitive ${v.name}>`
: v._tag === "Closure" ? `#<closure (${v.params.join(" ")})>`
: show(v);Here is the whole evaluator:
export const execute = (c: Core, env: Env | undefined): Run =>
Effect.gen(function* () {
switch (c._tag) {
case "Lit":
return c.value;
case "Datum":
return c.datum;
case "Global": {
const value = globals.get(c.name);
return value ?? (yield* broken(`no global ${c.name}`));
}
case "Local": {
// Walk out `depth` frames, then read a slot.
let frame = env;
for (let i = 0; i < c.depth; i++) frame = frame?.parent;
const value = frame?.slots[c.slot];
return value ?? (yield* broken(`no slot for ${c.name}`));
}
case "Lambda": {
const { params, body } = c;
return { _tag: "Closure", params, body, env } as const;
}
case "Call": {
const fn = yield* execute(c.fn, env);
const args: Arg[] = [];
for (const arg of c.args) {
const value = yield* execute(arg, env);
args.push({ value, span: arg.span });
}
if (typeof fn === "object" && fn._tag === "Primitive") {
return yield* fn.apply(args);
}
if (typeof fn === "object" && fn._tag === "Closure") {
const slots = args.map((arg) => arg.value);
return yield* execute(fn.body, { slots, parent: fn.env });
}
return yield* broken(`${display(fn)} is not a function`);
}
}
});Compare it with Part 4's. Looking up a Local walks a fixed number of frames and reads an array, with no string comparisons and no chance of finding the wrong binding. Calling a closure doesn't count its arguments. And the error type has shrunk. Part 4's evaluator could fail with UnboundName, NotCallable, WrongArity, NotANumber, or DivByZero. This one can fail with DivByZero, and that's all:
run: (source: string) =>
Effect<Value, Diagnostic | CheckError | DivByZero, Output>Read that type as two phases. Diagnostic | CheckError is everything the front end can reject. DivByZero is the only thing a checked program can still do wrong, because types say what kind of value an expression produces, not which value.
Failures and defects, again
The checks didn't all vanish. A few are still there, because the evaluator handles cases that "can't happen", such as a Local with no slot or a call to a number. What changed is what they mean:
// The checker proved these can't happen. If one does anyway, the
// core is wrong: that's a defect, not an error in the program.
const broken = (what: string) =>
Effect.die(new Error(`ill-typed core: ${what}`));Part 3 drew the line between failures, which mean the program is wrong, and defects, which mean the interpreter is. These checks have moved across it. If one fires, the core broke its own promise. That's a bug in the compiler, so it's a defect and stays out of the error type. The same goes for the primitives, which used to report NotANumber and now treat a non-number as broken core:
const numbers = (args: ReadonlyArray<Arg>) =>
Effect.forEach(args, ({ value }) =>
typeof value === "number"
? Effect.succeed(value)
: broken(`${display(value)} is not a number`),
);
const sum = (ns: number[]) => ns.reduce((a, b) => a + b, 0);
const mul = (ns: number[]) => ns.reduce((a, b) => a * b, 1);
const divide = (args: ReadonlyArray<Arg>) =>
Effect.gen(function* () {
const [first = 1, ...divisors] = yield* numbers(args);
let result = first;
for (const [i, divisor] of divisors.entries()) {
if (divisor === 0) {
const { span } = args[i + 1]!;
return yield* new DivByZero({ span });
}
result /= divisor;
}
return result;
});
const print = ([arg]: ReadonlyArray<Arg>) =>
Effect.gen(function* () {
if (!arg) return yield* broken("print needs an argument");
const output = yield* Output;
yield* output.print(display(arg.value));
return arg.value;
});
const primitive = (name: string, apply: Primitive["apply"]) =>
[name, { _tag: "Primitive", name, apply } as const] as const;
export const globals = new Map<string, Value>([
primitive("+", (args) => Effect.map(numbers(args), sum)),
primitive("*", (args) => Effect.map(numbers(args), mul)),
primitive("/", divide),
primitive("print", print),
["pi", Math.PI],
]);Compile now, run later
So far run still does both halves in one call. Because core is data with a schema, the halves can happen at different times, in different places:
// Core is data with a schema, so the compiler's output can be text.
const CoreJson = Schema.fromJsonString(Core);
// Compile once, to JSON that can be saved, sent, and run later.
export const build = (source: string) =>
compile(source).pipe(
Effect.flatMap(Schema.encodeEffect(CoreJson)),
);
// Load it back. Decoding checks the artifact's shape, not types.
export const load = (json: string) =>
Schema.decodeUnknownEffect(CoreJson)(json);build("(+ 1 2)") produces a JSON artifact. It's verbose, because every node carries its type and span, but it's plain data (abbreviated here):
{"_tag":"Call",
"fn":{"_tag":"Global","name":"+","type":{"_tag":"TFun",...},...},
"args":[{"_tag":"Lit","value":1,"type":{"_tag":"TNum"},...},
{"_tag":"Lit","value":2,"type":{"_tag":"TNum"},...}],
"type":{"_tag":"TNum"},"span":{"start":0,"end":7}}load turns it back into core, and execute runs it, with no reader, parser, or checker involved. That's the classic shape of a compiler: it translates one language into another, and the output runs on something that doesn't know the input language. Our target is a tree, not machine code. Compiling core further, to JavaScript or bytecode, would be the same step again.
Decoding does real work: a malformed artifact, such as a Lit whose value is a string, fails with a path to the problem. But it's worth being exact about what it checks. Schema proves the artifact has the shape of core. It doesn't prove the types written in it are true. Edit the JSON so the call's function is pi instead of +, and it still decodes. Running it doesn't fail with an EvalError; it dies with a defect:
ill-typed core: 3.141592653589793 is not a functionThat's the line from the previous section, working as designed: tampered core is broken core. Real compilers often close this gap by re-checking core before running it. Because every node is already typed, that check needs no inference and is cheap; GHC's Core Lint is the classic example. We'll leave it out for now.
To try it, put Parts 2 through 5 in directories named 02 to 05, this post's files in 06, install effect version 4, and run this with Node 24 from inside 06:
import { Effect } from "effect";
import { consoleOutput, Output } from "../04/capabilities.ts";
import { display, execute } from "./execute.ts";
import { build, load } from "./run.ts";
const json = Effect.runSync(build("(+ (print 1) (print 2))"));
// ...later, somewhere else:
const program = load(json).pipe(
Effect.flatMap((core) => execute(core, undefined)),
Effect.provideService(Output, consoleOutput),
);
console.log(display(Effect.runSync(program))); // 1, 2, then 3What's still missing
The core is small on purpose: numbers, data, names, functions, and calls. Every program the language can express comes down to those six nodes.
That makes the next question pressing. Suppose we want let. We don't need a new core node, because let is already expressible:
(let ((x 1)) (+ x x))
; means
((lambda (x) (+ x x)) 1)So let belongs in the surface language, as a rewrite into forms that already exist. That's Part 1's square again: a function from trees to trees, run before elaboration. Today the only place to write that function is the compiler's TypeScript source, in the parser, which every new form would touch. And Part 1 already warned that a careless rewrite can duplicate work or capture the wrong variable.
The fix is to let programs write those rewrites themselves, in the language, safely. That's what macros are for.
Next: Part 7, Macros Are Programs About Programs. The compiler can be extended in its own language.
The code in this post lives in docs/snippets/blog/in-the-beginning/06 and runs in the site's test suite.