The Agent Can Read the Language
Part 11 of From Lists to Languages · Act III, Effects in Practice ·
The agent doesn't have to guess what the program means.
A coding agent usually works the way a person with a plain text editor would. It reads characters, writes characters, and runs something to find out whether it worked. Here's a typical request: rename x to y.
(let ((x 2) (y 5)) (+ x y)) ; => 7A text edit replaces every x:
(let ((y 2) (y 5)) (+ y y)) ; => 10The result reads, checks, and runs. It's also wrong, and nothing says so: the second binding of y now hides the first.
Text edits go wrong a second way, because quoted data looks like code:
(let ((n 2))
(do (print 'n) (* n n)))Replacing every n with count also changes what the program prints. 'n is a symbol the program prints, not a reference to the variable.
Part 10 built tools that read a program's representations. This post hands them to an agent, and adds edits that work on those representations too.
What a program means
To know whether an edit is safe, we have to say when two programs mean the same thing. Core almost says it already. Part 6 turned every name into a position, so two programs that differ only in their names elaborate to the same core, apart from the names kept for display and the spans. Drop those, and compare:
// What a program means, without what it's called. Core already
// turned every name into a position, so dropping names and spans
// leaves only meaning: two programs that differ only in their
// names have equal meanings.
const nowhere: Span = { start: 0, end: 0 };
const data = (x: Sexp): Sexp =>
x._tag === "List"
? { ...x, items: x.items.map(data), span: nowhere }
: { ...x, span: nowhere };
const anonymous = (c: Core): Core => {
switch (c._tag) {
case "Datum":
return { ...c, datum: data(c.datum), span: nowhere };
case "Local":
return { ...c, name: "", span: nowhere };
case "Lambda": {
const params = c.params.map(() => "");
const body = anonymous(c.body);
return { ...c, params, body, span: nowhere };
}
case "Call": {
const fn = anonymous(c.fn);
const args = c.args.map(anonymous);
return { ...c, fn, args, span: nowhere };
}
default:
return { ...c, span: nowhere };
}
};
// Schema derives structural equality for core.
const equal = Schema.toEquivalence(Core);
export const sameMeaning = (a: Core9, b: Core9) =>
equal(anonymous(erase(a)), anonymous(erase(b)));Schema.toEquivalence derives structural equality from the same Core schema that Part 6 used to save compiled artifacts. This kind of equal meaning is strict: it's the same core, not just the same answer. (+ 1 2) and 3 mean different things by this measure, and for a rename, that's the right side to err on.
Renaming by asking the checker
A rename starts from the symbol under the cursor. The candidates are the symbols with the same name that the program could be referring to. Symbols inside quoted data aren't candidates, and neither are symbols inside macro definitions, which belong to the macro:
// Every symbol named `name` that the program could be referring to:
// not inside quoted data, and not inside a macro definition.
export const occurrences = (source: string, name: string) =>
Effect.map(readAll(source), (forms) => {
const found: Span[] = [];
const walk = (x: Sexp): void => {
if (x._tag === "Sym" && x.name === name) found.push(x.span);
if (x._tag !== "List") return;
const head = x.items[0];
const skip = head?._tag === "Sym" &&
(head.name === "quote" || head.name === "defmacro");
if (!skip) x.items.forEach(walk);
};
forms.forEach(walk);
return found;
});Core says which of those are references, and to what. A Local that's depth functions out refers to a parameter of that function:
// The references to `name` in core, grouped by what they refer to.
// A Local `depth` functions out refers to that function's
// parameter; past the outermost function, to the prelude.
const references = (core: Core, name: string) => {
const groups = new Map<string, Span[]>();
const walk = (c: Core, functions: Core[]): void => {
if (c._tag === "Local" && c.name === name) {
const fn = functions[functions.length - 1 - c.depth];
const key = fn
? `${functions.indexOf(fn)}:${fn.span.start}:${c.slot}`
: "prelude";
groups.set(key, [...(groups.get(key) ?? []), c.span]);
}
if (c._tag === "Lambda") walk(c.body, [...functions, c]);
if (c._tag === "Call") {
[c.fn, ...c.args].forEach((inner) => walk(inner, functions));
}
};
walk(core, []);
return groups;
};What core doesn't say is where each binder was written. let and lambda both put their names into a core Lambda, but which symbol in the source was the parameter is up to the form, and since Part 8 forms belong to the prelude. An editor shouldn't have to know every form. So the rename asks the checker instead. Each candidate edit renames the references plus one possible binder, and the right candidate is the one that leaves the meaning unchanged:
// Rename the name under the cursor, and everything that refers to
// what it refers to. Which forms bind names is the prelude's
// business, so the binder is found by asking the checker: of the
// candidate edits, the right one is the one that leaves the
// meaning unchanged.
export const rename = (
prelude: Prelude,
source: string,
at: number,
to: string,
) =>
Effect.gen(function* () {
const target = symbolAt(yield* readAll(source), at);
if (!target) {
return yield* new Refused({
reason: "there's no name here",
span: { start: at, end: at + 1 },
});
}
const { name, span } = target;
const refuse = (reason: string) =>
new Refused({ reason, span });
const [read] = yield* readAll(to);
if (read?._tag !== "Sym" || read.name !== to) {
return yield* refuse(`${to} is not a name`);
}
const before = yield* check(prelude, source);
const places = yield* occurrences(source, name);
if (!places.some((p) => same(p, span))) {
return yield* refuse(`this ${name} is data, not a name`);
}
const groups = references(before, name);
if (groups.get("prelude")?.some((s) => same(s, span))) {
return yield* refuse(`${name} belongs to the prelude`);
}
groups.delete("prelude");
const used = [...groups.values()].flat();
if (!used.every((u) => places.some((p) => same(p, u)))) {
return yield* refuse(`${name} is used inside a macro`);
}
// The cursor is on a reference, so the binder is one of the
// other occurrences; or it's on the binder, and the references
// are one of the groups, or none.
const mine = [...groups.values()].find((g) =>
g.some((s) => same(s, span)),
);
const others = places.filter(
(p) => !used.some((u) => same(p, u)),
);
const candidates = mine
? others.map((binder) => [...mine, binder])
: [...[...groups.values()].map((g) => [...g, span]), [span]];
for (const spans of candidates) {
const after = splice(source, spans, to);
const checked = yield* Effect.result(check(prelude, after));
if (Result.isSuccess(checked)) {
if (sameMeaning(before, checked.success)) return after;
}
}
const change = "would change what the program means";
return yield* refuse(`renaming ${name} to ${to} ${change}`);
});A rename that can't be made safely is refused, with a reason and a span:
// A structured edit that would break the program says so, instead
// of making it.
export class Refused extends Schema.TaggedError<Refused>()(
"Refused",
{ reason: Schema.String, span: Span },
) {
override get message() {
return this.reason;
}
}Here's the opening example, renamed with the tool:
(let ((x 2) (y 5)) (+ x y))
; rename x to z
(let ((z 2) (y 5)) (+ z y))
; rename x to y
; refused: renaming x to y would change what the program meansThe quoted 'n is left alone:
(let ((count 2))
(do (print 'n) (* count count)))Pointing the cursor at the quoted n itself is refused with this n is data, not a name. Shadowed names are told apart, because their references point at different functions:
(let ((x 1)) (+ x ((lambda (x) (* x 10)) 3)))
; rename the outer x to y
(let ((y 1)) (+ y ((lambda (x) (* x 10)) 3)))
; rename the inner x to y
(let ((x 1)) (+ x ((lambda (y) (* y 10)) 3)))Since Part 8, a local name can shadow a form's name. So renaming x to if is fine in (lambda (x) (+ x 1)), which becomes (lambda (if) (+ if 1)). In (lambda (x) (if x 1 2)) it's refused, because (if if 1 2) would call the parameter instead of using the form. The rename tool doesn't know that rule. The checker does, and the rename asks it.
Two more cases are refused by design. Renaming print is refused with print belongs to the prelude: that would change the language, not the program. And a name used inside a macro's expansion is left to the macro:
(defmacro sq ((e) `((lambda (v) (* v v)) ,e)))
(let ((v 3)) (sq v))
; rename the second v to w
(let ((w 3)) (sq w))The macro's v isn't touched. Part 7's expander is hygienic, so the macro's v and the user's v were never the same name.
This approach has a cost. Every candidate is a full check, so a name with k occurrences can mean up to k checks. That's fine for one file. A real tool would keep each binder's span in core, which the Part 10 analyzer wanted too.
Replacing an expression
The other edit agents make constantly is "replace this with that". As a text edit, it can leave half an expression behind. As a structured edit, it can't:
// Replace one expression with another. The span must be exactly an
// expression the reader found, and the replacement must read as
// exactly one expression, so the result always reads too. Then the
// whole file is formatted.
export const replace = (
docs: Docs,
source: string,
span: Span,
text: string,
) =>
Effect.gen(function* () {
const forms = yield* readAll(source);
const nodes: Sexp[] = [];
const walk = (x: Sexp): void => {
nodes.push(x);
if (x._tag === "List") x.items.forEach(walk);
};
forms.forEach(walk);
const { start, end } = span;
const exact = (n: Sexp) =>
n.span.start === start && n.span.end === end;
if (!nodes.some(exact)) {
const reason = "no expression starts and ends there";
return yield* new Refused({ reason, span });
}
const replacement = yield* readAll(text);
if (replacement.length !== 1) {
const reason = "the replacement must be one expression";
return yield* new Refused({ reason, span });
}
return yield* format(splice(source, [span], text), docs);
});source: (do (print 1) (+ 1 2))
(+ 1 2) with (* 3 4) -> (do (print 1) (* 3 4))
"(+ 1 2" with x -> no expression starts and ends there
(+ 1 2) with "(* 3 4" -> this ( is never closed
(+ 1 2) with "1 2" -> the replacement must be one expressionreplace guarantees that the file still reads. It doesn't guarantee that the file checks, and it shouldn't refuse an edit that doesn't: an agent sometimes has to pass through a broken program to reach a working one. Instead, every edit returns Part 10's report on the result, so the agent sees the type and findings of what it just made.
Tools
An agent talks to tools through a narrow interface: a name, a description, a JSON Schema for the input, and JSON in and out. Each part of that is something the language already has:
// A tool is a name, a description, and schemas for what goes in and
// what comes out. Every failure is a problem: a message and a span.
export interface Problem {
readonly message: string;
readonly span: Span;
}
interface Tool<I, O> {
readonly name: string;
readonly description: string;
readonly input: Schema.Codec<I>;
readonly output: Schema.Codec<O>;
readonly run: (input: I) => Effect.Effect<O, Problem, Workspace>;
}
const tool = <I, O>(t: Tool<I, O>) => t;The file lives in a service. That's Part 4's idea again: the tools say what they need, and whoever runs them provides it, whether that's a test, an editor, or a disk.
// The file the agent is working on. Tools read and write it through
// a service, so a test, an editor, or a disk can provide it.
export class Workspace extends Context.Service<
Workspace,
{ readonly file: Ref.Ref<string> }
>()("Workspace") {}
export const inMemory = (source: string) =>
Effect.map(Ref.make(source), (file) => ({ file }));There are five tools:
return [
tool({
name: "read",
description: "The file, with its type and findings.",
input: Schema.Struct({}),
output: Edited,
run: () =>
Effect.flatMap(file, (source) =>
Effect.map(inspect(prelude, docs, source), (report) => ({
source,
report,
})),
),
}),
tool({
name: "type_at",
description: "The type of the expression at a position.",
input: Schema.Struct({ at: Offset }),
output: Schema.Struct({ type: Schema.NullOr(Schema.String) }),
run: ({ at }) =>
Effect.gen(function* () {
const core = yield* check(prelude, yield* file);
return { type: typeAt(core, at) ?? null };
}),
}),
tool({
name: "rename",
description:
"Rename the name at a position, and every reference to it. "
+ "Refused if the program's meaning would change.",
input: Schema.Struct({ at: Offset, to: Schema.String }),
output: Edited,
run: ({ at, to }) =>
Effect.flatMap(file, (source) =>
Effect.flatMap(rename(prelude, source, at, to), save),
),
}),
tool({
name: "replace",
description:
"Replace the expression from start to end with another.",
input: Schema.Struct({
start: Offset,
end: Offset,
with: Schema.String,
}),
output: Edited,
run: ({ start, end, with: text }) =>
Effect.flatMap(file, (source) =>
Effect.flatMap(
replace(docs, source, { start, end }, text),
save,
),
),
}),
tool({
name: "evaluate",
description:
"Run an expression. It may print and divide, nothing else.",
input: Schema.Struct({ expression: Schema.String }),
output: Schema.Struct({
value: Schema.String,
printed: Schema.Array(Schema.String),
}),
run: ({ expression }) => evaluate(prelude, expression),
}),
];evaluate is a REPL, and it's a host from Part 9. It allows Output and DivByZero, so an expression that needs anything else is refused before it runs:
// The REPL is a host from Part 9. It allows Output and DivByZero,
// so a program that needs anything else is refused before it runs.
// What it prints is recorded and returned.
const evaluate = (prelude: Prelude, expression: string) =>
Effect.suspend(() => {
const { lines, output } = recordedOutput();
return run(prelude, expression, ["Output", "DivByZero"]).pipe(
Effect.provideService(Output, output),
Effect.map((value) => ({
value: display(value),
printed: lines,
})),
);
});Calling a tool decodes the agent's JSON with the tool's input schema, runs the tool, and encodes the result with its output schema. Every problem comes back in the same shape, a message and a span: bad input, a refused edit, a type error, or a division by zero.
// What the agent sends is JSON text, and what it gets back is JSON
// text. The input schema rejects a malformed call before any tool
// runs, and every problem comes back as data.
type AnyTool = Tool<any, any>;
export const call = (
tools: ReadonlyArray<AnyTool>,
name: string,
json: string,
): Effect.Effect<string, never, Workspace> => {
const found = tools.find((t) => t.name === name);
if (!found) {
return Effect.succeed(problem(`no tool named ${name}`));
}
const input = Schema.fromJsonString(found.input);
const output = Schema.fromJsonString(found.output);
return Schema.decodeEffect(input)(json).pipe(
Effect.mapError((e): Problem => ({ message: e.message, span })),
Effect.flatMap(found.run),
Effect.flatMap((o) =>
Effect.orDie(Schema.encodeEffect(output)(o)),
),
Effect.catch((p: Problem) =>
Effect.succeed(problem(p.message, p.span)),
),
);
};
const span = { start: 0, end: 0 };
const problem = (message: string, at: Span = span) =>
JSON.stringify({ error: { message, span: at } });What the agent is told about each tool is derived from the same schemas:
// What the agent is told about the tools: names, descriptions, and
// a JSON Schema for each input, derived from the Effect Schema.
export const manifest = (tools: ReadonlyArray<AnyTool>) =>
tools.map(({ name, description, input }) => ({
name,
description,
input: Schema.toJsonSchemaDocument(input).schema,
}));{"name": "rename",
"description": "Rename the name at a position, ...",
"input": {
"type": "object",
"properties": {
"at": {"type": "integer", ...,
"description": "A position in the file, counting from 0"},
"to": {"type": "string"}},
"required": ["at", "to"]}}A session
Here's what an agent sees, working on the opening example. Each line starting with > is a call, and the line after it is the answer (wrapped here to fit):
> read {}
{"source": "(let ((x 2) (y 5)) (+ x y))",
"report": {"formatted": "(let ((x 2) (y 5)) (+ x y))",
"type": "Num", "findings": []}}
> type_at {"at": 20}
{"type": "(Num...) -> Num"}
> type_at {"at": "20"}
{"error": {"message": "Expected number\n at [\"at\"]",
"span": {"start": 0, "end": 0}}}
> rename {"at": 7, "to": "y"}
{"error": {"message":
"renaming x to y would change what the program means",
"span": {"start": 7, "end": 8}}}
> rename {"at": 7, "to": "base"}
{"source": "(let ((base 2) (y 5)) (+ base y))",
"report": {"formatted": "(let ((base 2) (y 5)) (+ base y))",
"type": "Num", "findings": []}}
> evaluate {"expression": "(do (print 1) (/ 6 2))"}
{"value": "3", "printed": ["1"]}
> evaluate {"expression": "(sleep 10)"}
{"error": {"message": "unhandled effect: Async",
"span": {"start": 0, "end": 10}}}The agent never had to guess. It asked for a type and got one. It asked for an unsafe rename and got a refusal, with a reason, pointing at the name. It asked to run something the REPL doesn't allow, and nothing ran.
Side by side:
| Editing text | Using the tools | |
|---|---|---|
| What the agent reads | Characters | Syntax, types, findings |
| How it learns an edit worked | Runs something | The report after every edit |
| Renaming | Find and replace | References, checked |
| Quoted data | Edited like code | Left alone |
| Half an expression | Possible | Refused |
| Running code | Whatever the shell allows | Only allowed effects |
What the tools don't do
They work on one file. Equal meaning is strict, so a refactoring that changes core, such as inlining a function, can't be checked this way. An agent can still write a wrong program that type-checks: types say what kind of value a program returns, not which value, so tests still matter. And the tools don't decide what to change. They make the agent's guesses checkable.
To try it, put Parts 2 through 10 in directories named 02 to 10, this post's files in 11, install effect version 4, and run this with Node 24 from inside 11:
import { Effect } from "effect";
import { standard } from "../09/prelude.ts";
import { rename } from "./rename.ts";
const source = "(let ((x 2) (y 5)) (+ x y))";
console.log(Effect.runSync(rename(standard, source, 7, "z")));
// (let ((z 2) (y 5)) (+ z y))What's next
Eleven posts built one language a piece at a time. Every piece took one of three things: Lisp's trees, Schema's descriptions, or Effect's runtime.
The last post puts those pieces to work on something that isn't a language demo: a small language for a real job, built with the prelude, checked by the kernel, and run with capabilities a host provides.
Next: Part 12, A Language for Building Languages. The final product isn't a Lisp. It's a language-building platform.
The code in this post lives in docs/snippets/blog/in-the-beginning/11 and runs in the site's test suite.