Giving the List a Schema
Part 02 of From Lists to Languages · Act I, Foundations ·
A program is data with a shape.
Part 1 ended with two trees that didn't match. The interpreter worked on s-expressions: plain numbers, symbols, and arrays. The schema at the end described something else, an add node with named fields. This post closes that gap. The s-expression gets a schema, the schema gets a second schema for what programs mean, and parsing becomes a transformation from one to the other.
Along the way, errors stop being exceptions with vague messages. They become data that points at the source text you wrote.
Where did that come from?
Give Part 1's reader a program with a missing parenthesis:
(+ 1 (* 2 3)It says unexpected end of input. True, but unhelpful: the problem is the first (, which is never closed, and the error can't say so because a Part 1 tree has nowhere to keep a location. The 1 in that program is just the number 1.
So every node now carries a span, the start and end offsets of the text it was read from. A bare number can't carry a span, so each kind of node becomes a tagged struct:
// Every node remembers where it came from: offsets into the source.
export const Span = Schema.Struct({
start: Schema.Number,
end: Schema.Number,
});
export type Span = typeof Span.Type;
export const Num = Schema.TaggedStruct("Num", {
value: Schema.Number,
span: Span,
});
export const Sym = Schema.TaggedStruct("Sym", {
name: Schema.String,
span: Span,
});
// A list holds more s-expressions, so its schema refers to itself.
export interface List {
readonly _tag: "List";
readonly items: ReadonlyArray<Sexp>;
readonly span: Span;
}
export type Sexp = typeof Num.Type | typeof Sym.Type | List;
const LazySexp = Schema.suspend((): Schema.Codec<Sexp> => Sexp);
export const List = Schema.TaggedStruct("List", {
items: Schema.Array(LazySexp),
span: Span,
});
export const Sexp = Schema.Union([Num, Sym, List]);This is the same three-part language as Part 1: numbers, symbols, and lists of s-expressions. Now it's written as a schema, so the shape can be checked on data from anywhere, not only on data our reader made. List refers to Sexp, which includes List, so the reference goes through Schema.suspend. As in Part 1, the explicit Schema.Codec<Sexp> return type is what lets TypeScript follow the recursion.
The number 1 in (+ 1 x) now reads as:
{ "_tag": "Num", "value": 1, "span": { "start": 3, "end": 4 } }Reading with diagnostics
When reading fails, the reader returns a diagnostic instead of throwing. A diagnostic has a shape too, so it gets a schema:
// A diagnostic is data too: a message and the source it is about.
export const Diagnostic = Schema.Struct({
message: Schema.String,
span: Span,
});
export type Diagnostic = typeof Diagnostic.Type;The reader is Part 1's reader with spans attached. It returns an Effect<Sexp, Diagnostic>: either a tree, or a diagnostic saying what went wrong and where.
type Read = Effect.Effect<Sexp, Diagnostic>;
const fail = (message: string, span: Span) =>
Effect.fail<Diagnostic>({ message, span });
export const read = (source: string): Read => {
const tokens = [...source.matchAll(/[()]|[^\s()]+/g)].map((m) => {
const span = { start: m.index, end: m.index + m[0].length };
return { text: m[0], span };
});
let position = 0;
const next = (): Read =>
Effect.gen(function* () {
const token = tokens[position++];
if (!token) {
const end = { start: source.length, end: source.length };
return yield* fail("unexpected end of input", end);
}
const { text, span } = token;
if (text === ")") return yield* fail("unexpected )", span);
if (text === "(") {
const items: Sexp[] = [];
while (tokens[position]?.text !== ")") {
if (position >= tokens.length) {
return yield* fail("this ( is never closed", span);
}
items.push(yield* next());
}
const { end } = tokens[position++]!.span;
const list = { start: span.start, end };
return { _tag: "List", items, span: list } as const;
}
return /^-?\d+(\.\d+)?$/.test(text)
? ({ _tag: "Num", value: Number(text), span } as const)
: ({ _tag: "Sym", name: text, span } as const);
});
return Effect.gen(function* () {
position = 0; // an Effect can run more than once
const program = yield* next();
const extra = tokens[position];
if (extra) {
return yield* fail(`unexpected ${extra.text}`, extra.span);
}
return program;
});
};When the token stream runs out inside a list, the reader blames the ( that opened it, not the end of the file. A small renderer turns a diagnostic into the familiar compiler display:
// Point at the source a diagnostic is about.
export const render = (source: string, diagnostic: Diagnostic) => {
const { start, end } = diagnostic.span;
const lineStart = source.lastIndexOf("\n", start - 1) + 1;
const newline = source.indexOf("\n", start);
const lineEnd = newline === -1 ? source.length : newline;
const lines = source.slice(0, lineStart).split("\n");
const number = String(lines.length);
const width = Math.max(1, Math.min(end, lineEnd) - start);
const gutter = " ".repeat(number.length);
const caret = " ".repeat(start - lineStart) + "^".repeat(width);
return [
`error: ${diagnostic.message}`,
`${number} | ${source.slice(lineStart, lineEnd)}`,
`${gutter} | ${caret}`,
].join("\n");
};error: this ( is never closed
1 | (+ 1 (* 2 3)
| ^Two shapes: syntax and meaning
Every program is an s-expression, but not every s-expression is a program. These all read without complaint:
() ; an empty list
(2 3) ; a number where the operator should be
(quote x y) ; quote with two argumentsPart 1 found these problems while it was evaluating, if at all. (quote x y) didn't fail; it quietly returned x.
So there's a second tree: the abstract syntax, which only has room for programs that mean something. A symbol on its own is a reference to a name. A list headed by quote is a quotation of exactly one datum. Any other list headed by a symbol is a call.
// The abstract syntax: what a list means, not how it was written.
export const Ref = Schema.TaggedStruct("Ref", {
name: Schema.String,
span: Span,
});
export const Quote = Schema.TaggedStruct("Quote", {
datum: Sexp,
span: Span,
});
export interface Call {
readonly _tag: "Call";
readonly op: typeof Ref.Type;
readonly args: ReadonlyArray<Expr>;
readonly span: Span;
}
export type Expr =
| typeof Num.Type
| typeof Ref.Type
| typeof Quote.Type
| Call;
const LazyExpr = Schema.suspend((): Schema.Codec<Expr> => Expr);
export const Call = Schema.TaggedStruct("Call", {
op: Ref,
args: Schema.Array(LazyExpr),
span: Span,
});
export const Expr = Schema.Union([Num, Ref, Quote, Call]);Some details are deliberate. Num is shared because a number means itself. Quote holds an Sexp, not an Expr: quoting a program turns it back into data, so it doesn't need to mean anything. And a call's operator is a Ref for now. Calling the result of an expression has to wait for functions, in Part 4.
There's no Expr for (), (2 3), or (quote x y). If a value has this type, its shape is meaningful by construction.
Parsing is decoding
Turning syntax into meaning is a function from Sexp to Expr that can fail. Effect Schema already has a name for that: a transformation. The decode direction does the checking:
// Sexp -> Expr. A list that means nothing fails with an issue that
// carries a diagnostic: a message and the offending node's span.
const invalid = (message: string, { span }: Sexp) =>
Effect.fail(new SchemaIssue.InvalidValue({ message, span }));
type Decoded = Effect.Effect<Expr, SchemaIssue.Issue>;
const toExpr = (x: Sexp): Decoded =>
Effect.gen(function* () {
if (x._tag === "Num") return x;
if (x._tag === "Sym") return { ...x, _tag: "Ref" } as const;
const [head, ...rest] = x.items;
if (!head) return yield* invalid("() is not an expression", x);
if (head._tag !== "Sym") {
const message = `${show(head)} is not an operator`;
return yield* invalid(message, head);
}
if (head.name === "quote") {
const [datum, ...extra] = rest;
if (!datum || extra.length > 0) {
const message = "quote takes exactly one argument";
return yield* invalid(message, x);
}
return { _tag: "Quote", datum, span: x.span } as const;
}
const op = { ...head, _tag: "Ref" } as const;
const args = yield* Effect.forEach(rest, toExpr);
return { _tag: "Call", op, args, span: x.span } as const;
});Each failure is a SchemaIssue, the same kind of value Schema produces when a field has the wrong type. Its annotations hold a message and the span of the node to blame. For a bad operator that's the operator; for a bad quote it's the whole form.
A transformation also runs backwards. Encoding turns an Expr back into an Sexp, in about fifteen lines:
// Expr -> Sexp: the way back, so the same schema can also print.
const toSexp = (e: Expr): Sexp => {
switch (e._tag) {
case "Num":
return e;
case "Ref":
return { ...e, _tag: "Sym" };
case "Quote": {
const { datum, span } = e;
const quote = { _tag: "Sym", name: "quote", span } as const;
return { _tag: "List", items: [quote, datum], span };
}
case "Call": {
const items = [toSexp(e.op), ...e.args.map(toSexp)];
return { _tag: "List", items, span: e.span };
}
}
};Schema.decodeTo joins the two schemas with the transformation. Parsing is then read, then decode:
export const ExprFromSexp = Sexp.pipe(
Schema.decodeTo(Expr, {
decode: SchemaGetter.transformEffect(toExpr),
encode: SchemaGetter.transform(toSexp),
}),
);
// Find the issue our transformation raised; its annotations are a
// Diagnostic, so the Diagnostic schema reads them back.
const diagnose = (issue: SchemaIssue.Issue): Diagnostic =>
"issue" in issue ? diagnose(issue.issue)
: Schema.decodeUnknownSync(Diagnostic)(
issue._tag === "InvalidValue" ? issue.annotations : undefined,
);
export const parse = (source: string) =>
read(source).pipe(
Effect.flatMap(Schema.decodeEffect(ExprFromSexp)),
Effect.mapError((error) =>
Schema.isSchemaError(error) ? diagnose(error.issue) : error,
),
);ExprFromSexp is one schema with two layers. Decoding first checks that the input has the Sexp shape, then runs toExpr. When toExpr fails, diagnose finds the issue it raised. The issue's annotations are exactly a Diagnostic, so the Diagnostic schema reads them back out.
Now the programs Part 1 struggled with fail before anything runs, and the diagnostics point at the cause:
error: quote takes exactly one argument
1 | (+ 1 (quote x y))
| ^^^^^^^^^^^
error: 2 is not an operator
1 | (+ 1 (2 3))
| ^
error: () is not an expression
1 | (+ 1 ())
| ^^Spans are offsets into the whole source, so a program that spans several lines works without extra effort:
error: quote takes exactly one argument
2 | (quote a b))
| ^^^^^^^^^^^Diagnostics are data
The caret display is one rendering of a diagnostic, for humans in a terminal. Underneath, a diagnostic is a value with a schema:
{ "message": "quote takes exactly one argument",
"span": { "start": 5, "end": 16 } }An editor can underline that range. A test can compare it. A program can read it without scraping text from an error message, and in Part 11 that program will be a coding agent.
Two kinds of wrong
The reader isn't the only way to get an Sexp. Another tool might send a tree as JSON, and ExprFromSexp accepts that too:
const json = {
_tag: "List",
items: [{ _tag: "Num", value: "1", span: { start: 1, end: 2 } }],
span: { start: 0, end: 3 },
};
Schema.decodeUnknownEffect(ExprFromSexp)(json);
// fails with SchemaError:
// Expected number
// at ["items"][0]["value"]The same schema reports two kinds of failure in two ways. When the shape is wrong, as with this string where a number belongs, Schema reports a path into the data. When the shape is right but the meaning is wrong, our transformation reports a span in the source. One describes the data structure; the other describes the program.
The way back
Those fifteen lines pay off at once. Decode messy source, encode it again, and print the result:
const expr = Effect.runSync(parse("(+ 1\n (quote (a b)))"));
show(Schema.encodeSync(ExprFromSexp)(expr));
// (+ 1 (quote (a b)))That's a crude formatter, almost for free. Encoding is how one shared representation will feed several tools at once in Part 10.
A smaller evaluator
With shapes settled by parsing, the evaluator shrinks. It no longer asks whether a list is empty, whether the head is a symbol, or how many arguments quote got. The type of its input already answers all three.
// The evaluator no longer checks shapes; parsing already did. It
// only checks values: you still can't add a quoted symbol.
export type Value = number | Sexp;
const numbers = (op: string, args: ReadonlyArray<Value>) =>
args.map((arg) => {
if (typeof arg === "number") return arg;
const got = display(arg);
throw new TypeError(`${op} expects numbers, got ${got}`);
});
const primitives: Record<string, (args: Value[]) => Value> = {
"+": (args) => numbers("+", args).reduce((a, b) => a + b, 0),
"*": (args) => numbers("*", args).reduce((a, b) => a * b, 1),
};
export const evaluate = (e: Expr): Value => {
switch (e._tag) {
case "Num":
return e.value;
case "Quote":
return e.datum;
case "Ref":
throw new ReferenceError(`${e.name} is not defined`);
case "Call": {
const { name } = e.op;
const fn = primitives[name];
if (!fn) throw new ReferenceError(`${name} is not defined`);
return fn(e.args.map(evaluate));
}
}
};
export const display = (v: Value) =>
typeof v === "number" ? String(v) : show(v);(+ 1 2) ; => 3
(+ 1 (+ 2 3)) ; => 6
(quote (+ 1 2)) ; => (+ 1 2)To try it, save the four snippet files (sexp.ts, read.ts, expr.ts, and evaluate.ts), install effect version 4, and run this with Node 24:
import { Effect } from "effect";
import { display, evaluate } from "./evaluate.ts";
import { parse } from "./expr.ts";
const expr = Effect.runSync(parse("(+ 1 (+ 2 3))"));
console.log(display(evaluate(expr))); // 6What Schema did, and what it didn't
Some failures are left, and they're the instructive ones. (+ 1 (quote x)) parses fine: it's a call to + with two arguments. Evaluating it still throws + expects numbers, got x. So does x, with x is not defined. Both errors are exceptions, and neither knows its span.
That's the boundary. Schema checked that the program has a meaningful shape: every node is one we know how to evaluate, and every failure points at the source. It didn't check that + receives numbers. That's a question about what values flow where, and answering it before running the program takes a type checker. Schema describes representations; the language still has to establish its own typing rules. Part 5 builds that checker.
First, the evaluator should stop throwing. Errors became data in the parser, and the runtime deserves the same treatment.
Next: Part 3, Errors Are Not Exceptions. A language runtime should know how it can fail.
The code in this post lives in docs/snippets/blog/in-the-beginning/02 and runs in the site's test suite.