One Program, Many Interpretations
Part 10 of From Lists to Languages · Act III, Effects in Practice ·
Programs become things we can reason about, not just execute.
Nine posts in, the language does one thing with a program: it runs it. The checker exists to make running safe, and everything else serves that.
But along the way the language picked up several representations of a program, and every one of them is data with a schema:
- Syntax: the s-expressions from Part 2, with a span on every node.
- Typed core: the six node types from Part 6, each with its settled type.
- The prelude: forms, and values with type schemes, from Part 8, with effects since Part 9.
Running is one interpretation of these. This post builds four more: a formatter, an analyzer, a hover tool, and a documentation generator. None of them runs the program, and each reads only the representation it needs.
Descriptions are data
Part 8 ended on a limit. A form's rule is a TypeScript function, so a tool can't learn what if accepts without running it. Some tools only need to know about a form: how to lay it out, how to explain it, what an example looks like. That can be data:
// A description of a form, as data. The form's rule is still a
// function, but tools can read this without running anything.
export const Example = Schema.Struct({
source: Schema.String,
type: Schema.String,
});
export const FormDoc = Schema.Struct({
syntax: Schema.String,
summary: Schema.String,
// How many parts stay on the first line when the form is split.
head: Schema.Number.check(Schema.isInt()),
examples: Schema.Array(Example),
});
export type FormDoc = typeof FormDoc.Type;
export const Docs = Schema.Record(Schema.String, FormDoc);
export type Docs = typeof Docs.Type;// How if is described. Nothing here runs: it's data for tools.
const ifDoc = {
syntax: "(if test yes no)",
summary: "yes unless test is 0, then no. Both have one type.",
head: 1,
examples: [{ source: "(if (< 1 2) 10 20)", type: "Num" }],
};The standard prelude's descriptions are decoded through Docs, so a bad one is caught when it's loaded. head: 1.5 fails with Expected an integer, at ["head"]. The rule is still a function. The description is what the next tools read.
A formatter
A formatter needs syntax and nothing else. The reader's shorthand runs in reverse, so (quote x) prints as 'x:
// The reader's shorthand, in reverse: (quote x) prints as 'x.
const marks = new Map([
["quote", "'"],
["quasiquote", "`"],
["unquote", ","],
["unquote-splicing", ",@"],
]);
const markOf = (x: List) => {
const [head, datum, ...extra] = x.items;
const mark = head?._tag === "Sym" && marks.get(head.name);
return mark && datum && extra.length === 0
? { mark, datum }
: undefined;
};
// One line, however long.
const flat = (x: Sexp): string => {
if (x._tag === "Num") return String(x.value);
if (x._tag === "Sym") return x.name;
const marked = markOf(x);
if (marked) return marked.mark + flat(marked.datum);
return `(${x.items.map(flat).join(" ")})`;
};A list that fits on the line stays on one line. One that doesn't is split, and how depends on what it is. A form keeps its first few parts on the first line, as many as its description's head says, and indents the rest by two. A call lines its arguments up under the first:
// Lay out x starting at `column`. A list that doesn't fit is split:
// a form keeps its first `head` parts on the first line and indents
// the rest by 2, a call lines its arguments up under the first one,
// and any other list puts each item on its own line.
export const layout = (docs: Docs, width: number) => {
const go = (x: Sexp, column: number): string => {
const line = flat(x);
if (x._tag !== "List" || column + line.length <= width) {
return line;
}
const marked = markOf(x);
if (marked) {
const { mark, datum } = marked;
return mark + go(datum, column + mark.length);
}
const [head, ...rest] = x.items;
if (head?._tag !== "Sym") return lines(x.items, column + 1);
const form = docs[head.name];
const kept = form ? form.head : 1;
const first = [head, ...rest.slice(0, kept)];
const text = sameLine(first, column);
const more = rest.slice(kept);
if (more.length === 0) return `${text})`;
const indent = column + (form ? 2 : head.name.length + 2);
return `${text}\n${pad(indent)}${lines(more, indent).slice(1)}`;
};
// "(" at `column`, then items one after another on its line. A
// long item may still split.
const sameLine = (items: ReadonlyArray<Sexp>, column: number) => {
let text = "(";
for (const [i, item] of items.entries()) {
if (i > 0) text += " ";
text += go(item, column + lastLine(text));
}
return text;
};
// Items one per line, all starting at `column`.
const lines = (items: ReadonlyArray<Sexp>, column: number) => {
const laid = items.map((item) => go(item, column));
return `(${laid.join(`\n${pad(column)}`)})`;
};
return go;
};
const pad = (n: number) => " ".repeat(n);
const lastLine = (text: string) =>
text.length - text.lastIndexOf("\n") - 1;// Format a whole source file: every form, a blank line between.
// It needs only syntax, so it works on programs that don't check.
export const format = (source: string, docs: Docs, width = 60) =>
Effect.map(readAll(source), (forms) =>
forms.map((form) => layout(docs, width)(form, 0)).join("\n\n"),
);So this:
(let ((twice (lambda (f x)
(f (f x))))) (do (print
(twice print 1)) (when (< 1 2)
(print 2)) (catch (/ 1 0) 0)))becomes this, at a width of 40:
(let ((twice (lambda (f x) (f (f x)))))
(do
(print (twice print 1))
(when (< 1 2) (print 2))
(catch (/ 1 0) 0)))Two properties keep a formatter honest, and the tests check both, on programs from this series at widths from 60 down to 12. Reading the output gives back the same tree. And formatting the output again changes nothing.
Because it reads only syntax, the formatter works on programs that don't check, such as (+ 1 'a). It also can't do what a real formatter must do: keep comments. The reader throws them away, so they never reach the tree.
An analyzer
An analyzer reads the typed core. It reports findings, which are diagnostics with a severity, and it can't fail:
// What a tool reports: a diagnostic with a severity.
export const Finding = Schema.Struct({
severity: Schema.Literals(["error", "warning"]),
message: Schema.String,
span: Span,
});
export type Finding = typeof Finding.Type;
// A checked program, as every analyzer sees it.
export interface Program {
readonly prelude: Prelude;
readonly core: Core;
}
// An analyzer can't fail. It reads a program and reports findings.
export type Analyzer = (
program: Program,
) => Effect.Effect<ReadonlyArray<Finding>>;Most analyses walk every node, so there's one walk:
// Every node in a core tree, with how many functions it's inside.
const nodes = (c: Core, level = 0): Array<[Core, number]> => [
[c, level],
...(c._tag === "Lambda" ? nodes(c.body, level + 1)
: c._tag === "Call"
? [c.fn, ...c.args].flatMap((inner) => nodes(inner, level))
: []),
];
const warning = (message: string, span: Span): Finding => ({
severity: "warning",
message,
span,
});The first analysis finds parameters nobody uses. In core, every name is a position, so "is x used?" means "is there a Local that points at it?":
// A parameter nobody refers to. Names with # were made by a form,
// and those are allowed to go unused.
const uses = (c: Core, depth: number, slot: number): boolean =>
c._tag === "Local" ? c.depth === depth && c.slot === slot
: c._tag === "Lambda" ? uses(c.body, depth + 1, slot)
: c._tag === "Call"
? [c.fn, ...c.args].some((inner) => uses(inner, depth, slot))
: false;
export const unused: Analyzer = ({ core }) =>
Effect.sync(() =>
nodes(core).flatMap(([c]) =>
c._tag !== "Lambda" ? [] : c.params.flatMap((name, slot) =>
name.startsWith("#") || uses(c.body, 0, slot)
? []
: [warning(`${name} is never used`, c.span)],
),
),
);warning: x is never used
1 | (let ((x 1) (y 2)) (+ y 1))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^Core doesn't keep a span for each parameter, only for the function, so the warning covers the whole let. A real tool would keep the span.
The second uses Part 9's effects. In (do a b), a's value is thrown away, so a only matters for what it does. If it does nothing, it's dead code:
// (do a b): a's value is thrown away, so a only matters for what it
// does. Warn when it surely does nothing. A call is surely pure if
// it calls a prelude function whose declared row has no labels.
export const discarded: Analyzer = ({ prelude, core }) =>
Effect.sync(() => {
const declared = [...prelude.values.values()].map(
({ scheme: { type } }) =>
type._tag === "TFun" && type.effects._tag === "TRow"
? type.effects.labels.length
: 1,
);
// At `level` functions deep, the prelude is `level` frames out.
const pure = (c: Core, level: number): boolean =>
c._tag !== "Call" ? true
: c.fn._tag === "Local" && c.fn.depth === level &&
declared[c.fn.slot] === 0 &&
c.args.every((arg) => pure(arg, level));
return nodes(core).flatMap(([c, level]) => {
if (c._tag !== "Call" || c.fn._tag !== "Lambda") return [];
const [first] = c.args;
if (c.fn.params[0] !== "#do" || !first) return [];
if (!pure(first, level)) return [];
const message = "this value is discarded, and computing it "
+ "does nothing";
return [warning(message, first.span)];
});
});warning: this value is discarded, and computing it does nothing
1 | (do (+ 1 2) (print 3))
| ^^^^^^^It reads each prelude function's declared row, not the type in the core. Unification made every call's row equal to the row of the code around it, so after checking, (+ 1 2) in this program has the type (Num...) -> Num ! {Output}. That's sound for checking, but too coarse for this question. The analysis is careful in one direction: it warns only when it's sure. (do (f 1) ...) with a pure user function f isn't flagged.
when gets the second analysis for free, because it's built from the same #do core as do:
warning: this value is discarded, and computing it does nothing
1 | (when 1 2)
| ^Analyses are independent of each other, so running them is a forEach over a list:
// Analyzers are independent, so they run side by side, and adding
// one is adding it to the list.
export const analyzers: Analyzer[] = [unused, discarded];
export const analyze = (program: Program) =>
Effect.map(
Effect.forEach(analyzers, (a) => a(program), {
concurrency: "unbounded",
}),
(found) => found.flat(),
);Hover
An editor's hover asks a different question: what's the type of the thing under the cursor? Every core node has a span and a type, so the answer is the smallest node around the position:
// The type of the smallest expression around a position.
export const typeAt = (core: Core, offset: number) => {
let best: Core | undefined;
for (const [c] of nodes(core)) {
const { start, end } = c.span;
if (start > offset || offset >= end) continue;
if (!best || end - start < best.span.end - best.span.start) {
best = c;
}
}
return best && showType(best.type);
};In this program, twice is defined once and used once:
(let ((twice (lambda (f x) (f (f x)))))
(twice print 1))Hovering the definition shows its general type. Hovering the use shows the type it has there, after print and 1 decided 'a and 'b:
; the definition, (lambda (f x) ...)
(('a) -> 'a ! 'b, 'a) -> 'a ! 'b
; the use, twice
((Num) -> Num ! {Output | 'a}, Num) -> Num ! {Output | 'a}Writing this tool found a bug. The first time I hovered the definition, it said (Num) -> Num. Part 8's generalize skipped a scheme's own variables after following the solver's answers, and both count from zero. So once this run's variable 1 had an answer, the prelude's variable 1 seemed to have it too, and twice quietly stopped being polymorphic. (do (twice print 1) (twice print 'a)) was rejected. Parts 8 and 9 now skip own variables first, and both have a test for it. The checker's tests looked only at the types of whole programs, which were right. The hover tool looked inside.
Documentation that can't go stale
The documentation generator reads the prelude and its descriptions. A value's entry comes from its type scheme, so it's always current. A form's entry comes from its description, and descriptions can drift from the rule, so every example is checked before it's printed:
// Documentation that no longer matches the language.
export class StaleDocs extends Schema.TaggedError<StaleDocs>()(
"StaleDocs",
{ form: Schema.String, problem: Schema.String },
) {
override get message() {
return `${this.form}: ${this.problem}`;
}
}// A Markdown reference for a prelude. Values are documented from
// their type schemes, so they can't go stale. Forms are documented
// from their descriptions, and every example is checked against
// the form's real rule before it's printed.
export const document = (prelude: Prelude, docs: Docs) =>
Effect.gen(function* () {
const out = ["## Forms"];
for (const name of prelude.forms.keys()) {
const doc = docs[name];
if (!doc) {
const problem = "has no description";
return yield* new StaleDocs({ form: name, problem });
}
out.push(`### \`${doc.syntax}\``, doc.summary);
for (const { source, type } of doc.examples) {
const checked = yield* example(prelude, name, source);
if (checked !== type) {
const problem = `${source} is documented as ${type}, `
+ `but checks as ${checked}`;
return yield* new StaleDocs({ form: name, problem });
}
out.push(` ${source} : ${type}`);
}
}
out.push("## Values");
for (const [name, { scheme }] of prelude.values) {
out.push(`- \`${name} : ${showType(scheme.type)}\``);
}
return out.join("\n\n");
});
// An example that doesn't check at all is stale too.
const example = (prelude: Prelude, form: string, source: string) =>
compile(prelude, source).pipe(
Effect.map(({ core, effects }) =>
showComputation(core.type, effects),
),
Effect.mapError(({ message }) =>
new StaleDocs({ form, problem: `${source}: ${message}` }),
),
);Part of the output:
### `(if test yes no)`
yes unless test is 0, then no. Both have one type.
(if (< 1 2) 10 20) : Num
...
- `print : ('a) -> 'a ! {Output}`
- `sleep : (Num) -> Unit ! {Async}`Change if's example to claim (if 1 2 3) has type Data, and generation fails:
if: (if 1 2 3) is documented as Data, but checks as NumRemove the description of when, and it fails with when: has no description. These are doctests: the documentation is another program the language checks.
Composing interpretations
Each interpretation is an Effect, and its type says what it needs and how it can fail:
format: Effect<string, Diagnostic>
analyze: Effect<ReadonlyArray<Finding>>
document: Effect<string, StaleDocs>
run: Effect<Value, CheckError | Diagnostic | DivByZero, Output>Only run needs a service. Only run can fail at runtime. The formatter can fail only if the source can't be read. Those facts are in the types, the same way Part 9 put them in the language's types.
Effects that say how they fail compose without try. Here's one report on a program, from all of the tools at once:
// Everything the tools found out about one program, as data.
export const Report = Schema.Struct({
formatted: Schema.NullOr(Schema.String),
type: Schema.NullOr(Schema.String),
findings: Schema.Array(Finding),
});
export type Report = typeof Report.Type;
export const ReportJson = Schema.fromJsonString(Report);// Format, check, and analyze one program. Formatting needs only
// syntax, so a program that fails to check is still formatted, and
// the check's error becomes a finding instead of stopping the rest.
export const inspect = (
prelude: Prelude,
docs: Docs,
source: string,
): Effect.Effect<Report> =>
Effect.gen(function* () {
const [formatting, checking] = yield* Effect.all(
[
Effect.result(format(source, docs)),
Effect.result(compile(prelude, source)),
],
{ concurrency: "unbounded" },
);
const formatted = Result.getOrNull(formatting);
if (Result.isFailure(checking)) {
const { message, span } = checking.failure;
const severity = "error";
const findings = [{ severity, message, span }] as const;
return { formatted, type: null, findings };
}
const { core, effects } = checking.success;
const type = showComputation(core.type, effects);
const findings = yield* analyze({ prelude, core });
return { formatted, type, findings };
});Effect.result turns a failure into a value, so a program that doesn't check still gets formatted, and its type error becomes one more finding. Formatting and checking don't depend on each other, so they run side by side.
The report is data with a schema, so it encodes to JSON. For (let ((x 1)) (do 0 (print 2))):
{"formatted":"(let ((x 1)) (do 0 (print 2)))",
"type":"Num ! {Output}",
"findings":[
{"severity":"warning","message":"x is never used",
"span":{"start":0,"end":30}},
{"severity":"warning",
"message":
"this value is discarded, and computing it does nothing",
"span":{"start":17,"end":18}}]}For (+ 1 'a), formatted is still there, type is null, and the one finding is the error expected Num, got Data. For (+ 1, nothing can be read, and formatted is null too.
To try it, put Parts 2 through 9 in directories named 02 to 09, this post's files in 10, install effect version 4, and run this with Node 24 from inside 10:
import { Effect } from "effect";
import { standard } from "../09/prelude.ts";
import { standardDocs } from "./describe.ts";
import { inspect } from "./inspect.ts";
const source = "(do (+ 1 2) (print 3))";
const report = inspect(standard, standardDocs, source);
console.log(Effect.runSync(report).findings[0]?.message);
// this value is discarded, and computing it does nothingWhat's next
Every tool in this post is a function from a representation to an answer, and every answer is data with a schema. None of them had to guess what the program means: the spans say where things are, the types say what they are, and the prelude says what the words do.
That's exactly what a coding agent needs. Today, an agent edits Lisp as text and finds out whether it worked by running something. It could read this report instead, and ask for a type at a position, and make edits that are trees, not strings.
Next: Part 11, The Agent Can Read the Language. The agent doesn't have to guess what the program means.
The code in this post lives in docs/snippets/blog/in-the-beginning/10 and runs in the site's test suite.