The Environment Is Not the World
Part 04 of From Lists to Languages · Act I, Foundations ·
Names resolve in scopes. Capabilities resolve through services.
Part 3 gave the evaluator an honest type, Effect<Value, EvalError, Environment>, and left a crack in the third slot. The Environment was one flat map that the host chose before the program started. Two very different things lived in it:
- Names, like
+andpi. They're part of the language's vocabulary, and soon programs will define their own. - Capabilities, like a future
printorread-file. These are things the host does on the program's behalf, and a sandbox might refuse them.
This post adds functions, which forces the question of where names live. The answer splits the environment in two. Names go into scopes: plain data that the evaluator passes around and closures keep. Capabilities go into services: Effect's context, which the host fills in when it runs the program.
Functions
The language gets exactly one new form, lambda:
((lambda (x) (* x x)) 7) ; => 49
(((lambda (n) (lambda (x) (+ x n))) 10) 5) ; => 15The second line is the important one. A function returns a function, and the returned function still remembers n after the outer call is finished.
The abstract syntax gains a Lambda node, and Call changes in one place. Its operator used to be a Ref; now it's any expression. That's the change Part 2 promised for this post:
export const Ref = Schema.TaggedStruct("Ref", {
name: Schema.String,
span: Span,
});
export const Quote = Schema.TaggedStruct("Quote", {
datum: Sexp,
span: Span,
});
export interface Lambda {
readonly _tag: "Lambda";
readonly params: ReadonlyArray<typeof Ref.Type>;
readonly body: Expr;
readonly span: Span;
}
export interface Call {
readonly _tag: "Call";
readonly fn: Expr;
readonly args: ReadonlyArray<Expr>;
readonly span: Span;
}
export type Expr =
| typeof Num.Type
| typeof Ref.Type
| typeof Quote.Type
| Lambda
| Call;
const LazyExpr = Schema.suspend((): Schema.Codec<Expr> => Expr);
export const Lambda = Schema.TaggedStruct("Lambda", {
params: Schema.Array(Ref),
body: LazyExpr,
span: Span,
});
export const Call = Schema.TaggedStruct("Call", {
fn: LazyExpr,
args: Schema.Array(LazyExpr),
span: Span,
});
export const Expr = Schema.Union([Num, Ref, Quote, Lambda, Call]);Parsing lambda follows Part 2's pattern. Each malformed shape fails with a diagnostic that points at the cause:
// (lambda (x y) body): a parameter list of distinct symbols, and
// exactly one body.
const toLambda = (x: List): Decoded =>
Effect.gen(function* () {
const [, params, body, ...extra] = x.items;
if (params?._tag !== "List" || !body || extra.length > 0) {
const message = "lambda takes a parameter list and one body";
return yield* invalid(message, x);
}
const names: Array<typeof Ref.Type> = [];
for (const param of params.items) {
if (param._tag !== "Sym") {
const message = "a parameter must be a symbol";
return yield* invalid(message, param);
}
if (names.some((name) => name.name === param.name)) {
const message = `${param.name} is already a parameter`;
return yield* invalid(message, param);
}
names.push({ ...param, _tag: "Ref" });
}
const { span } = x;
const expr = yield* toExpr(body);
return { _tag: "Lambda", params: names, body: expr, span };
});error: x is already a parameter
1 | (lambda (x x) x)
| ^There's still no let. You can write it as an immediately called lambda, ((lambda (x) body) 3), which is what let is. Parts 7 and 8 bring it back as a form defined outside the kernel, rather than one more case in the evaluator.
Scopes are data
A scope is a frame of names plus the scope around it. Looking up a name walks outward until it finds the name or runs out of frames:
// A scope is a frame of names and the scope around it. It's plain
// data: a closure can hold on to one, and a call can extend one.
export interface Scope {
readonly names: ReadonlyMap<string, Value>;
readonly parent: Scope | undefined;
}
export const extend = (
parent: Scope,
names: Iterable<readonly [string, Value]>,
): Scope => ({ names: new Map(names), parent });
export const lookup = (
scope: Scope | undefined,
name: string,
): Value | undefined =>
scope === undefined ? undefined
: scope.names.has(name) ? scope.names.get(name)
: lookup(scope.parent, name);A scope is an ordinary immutable value, not a service, a global variable, or a mutable table. That matters because a function value has to hold on to one. A closure is a function's parameters and body, together with the scope it was created in:
// A closure is a function plus the scope it was created in.
export interface Closure {
readonly _tag: "Closure";
readonly params: ReadonlyArray<string>;
readonly body: Expr;
readonly scope: Scope;
}
export interface Arg {
readonly value: Value;
readonly span: Span;
}
export interface Primitive {
readonly _tag: "Primitive";
readonly name: string;
readonly apply: (
args: ReadonlyArray<Arg>,
call: Span,
) => Effect.Effect<Value, EvalError, Output>;
}
export type Value = number | Sexp | Primitive | Closure;
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);The evaluator
The evaluator now takes the scope as an argument, and its result type mentions Output where Part 3 mentioned Environment. We'll get to Output shortly.
// Names come in as an argument. Capabilities come in through R.
export const evaluateWith = (rule: ScopeRule) => {
const evaluate = (e: Expr, scope: Scope): Eval =>
Effect.gen(function* () {
switch (e._tag) {
case "Num":
return e.value;
case "Quote":
return e.datum;
case "Lambda": {
const params = e.params.map((param) => param.name);
return { _tag: "Closure", params, body: e.body, scope };
}
case "Ref": {
const value = lookup(scope, e.name);
if (value !== undefined) return value;
const { name: symbol, span } = e;
return yield* new UnboundName({ symbol, span });
}
case "Call": {
const fn = yield* evaluate(e.fn, scope);
const args: Arg[] = [];
for (const arg of e.args) {
const value = yield* evaluate(arg, scope);
args.push({ value, span: arg.span });
}
if (typeof fn === "object" && fn._tag === "Primitive") {
return yield* fn.apply(args, e.span);
}
if (typeof fn === "object" && fn._tag === "Closure") {
const expected = fn.params.length;
if (args.length !== expected) {
const { span } = e;
const got = args.length;
return yield* new WrongArity({ expected, got, span });
}
const bindings = fn.params.map(
(param, i) => [param, args[i]!.value] as const,
);
const body = extend(rule(fn, scope), bindings);
return yield* evaluate(fn.body, body);
}
const symbol = show(toSexp(e.fn));
const { span } = e.fn;
return yield* new NotCallable({ symbol, span });
}
}
});
return evaluate;
};
export const evaluate = evaluateWith(lexical);Lambda captures the current scope in a closure. Ref looks the name up in the scope it's given. Call evaluates the operator and arguments, then runs a closure's body in a new frame that binds its parameters. A closure called with the wrong number of arguments gets a new tagged error:
// Functions bring a new way to fail: the wrong number of arguments.
export class WrongArity extends Schema.TaggedError<WrongArity>()(
"WrongArity",
{ expected: Schema.Number, got: Schema.Number, span: Span },
) {
override get message() {
const { expected, got } = this;
const s = expected === 1 ? "" : "s";
return `expected ${expected} argument${s}, got ${got}`;
}
}
export type EvalError = Part3Error | WrongArity;The evaluator is written with a parameter, rule, that decides which scope the new frame extends. The next section shows why that one line is the whole question.
Which scope?
When a function body runs, which scope does it see? There are two reasonable answers:
// Which scope does a function body run in? The one where the
// function was written, or the one where it was called?
export type ScopeRule = (closure: Closure, caller: Scope) => Scope;
export const lexical: ScopeRule = (closure) => closure.scope;
export const dynamic: ScopeRule = (_closure, caller) => caller;Lexical scope extends the scope where the function was written. Dynamic scope extends the scope where it was called. One program tells them apart:
((lambda (x)
((lambda (f)
((lambda (x) (f 0)) 100))
(lambda (y) (+ x y))))
1)The function f is written where x is 1, and called where a different x is 100. Under the lexical rule, the program returns 1. Under the dynamic rule, it returns 100.
Lexical scope is the right rule for names, for the same reason it won in almost every language since Scheme. You can tell what x means by reading the code around it. A function means the same thing wherever it's called. And a function can't be broken by a caller that happens to use the same variable name.
Why names can't be services
Part 3 kept names in an Effect service, and this is where that stops working. Effect's context resolves requirements where an effect runs, not where it was built. Here's that rule, using a service in place of a variable:
class X extends Context.Service<X, number>()("X") {}
// A "function body" that reads X, defined where X is 1...
const body = Effect.gen(function* () {
return (yield* X) + 0;
});
const defined = Effect.succeed(body).pipe(
Effect.provideService(X, 1),
);
// ...and called where X is 100.
export const called = defined.pipe(
Effect.flatMap((fn) => fn),
Effect.provideService(X, 100),
);
// Effect.runSync(called) is 100: the body saw the caller's X.The effect body was created inside a region where X is 1, and run inside one where X is 100. It sees 100. Effect's context is dynamically scoped, by design.
So if program names lived in services, every closure would see its caller's variables, and f above would return 100. That's the wrong rule for names. But for capabilities, it's exactly the right one.
Capabilities
The question a capability answers isn't "what did the author mean by this name?" It's "what is this run of the program allowed to do, and how?" The answer belongs to whoever runs the program, which is what dynamic resolution provides.
The first capability is output:
// A capability: something the host can do for a program. The
// interpreter asks for it; the host decides what it does.
export class Output extends Context.Service<
Output,
{ readonly print: (line: string) => Effect.Effect<void> }
>()("Output") {}
export const consoleOutput = {
print: (line: string) => Effect.sync(() => console.log(line)),
};
// For tests and sandboxes: remember the lines instead.
export const recordedOutput = () => {
const lines: string[] = [];
const print = (line: string) =>
Effect.sync(() => {
lines.push(line);
});
return { lines, output: { print } };
};The global scope binds the names every program starts with. print is one of them, an ordinary primitive. What printing does is not in the scope; the primitive asks the Output service:
// `print` is a name like any other, bound in the global scope. What
// printing does is up to the Output service.
const print: Primitive["apply"] = (args, span) =>
Effect.gen(function* () {
const [arg, ...extra] = args;
if (!arg || extra.length > 0) {
const got = args.length;
return yield* new WrongArity({ expected: 1, got, span });
}
const output = yield* Output;
yield* output.print(display(arg.value));
return arg.value;
});
export const globals: Scope = {
names: 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],
]),
parent: undefined,
};run starts every program in the global scope, and leaves Output in the type:
export type Failure = Diagnostic | EvalError;
// Programs start in the global scope. Output is still required: the
// host hasn't said where printing goes.
export const run = (
source: string,
evaluator = evaluate,
): Effect.Effect<Value, Failure, Output> =>
parse(source).pipe(
Effect.flatMap((expr) => evaluator(expr, globals)),
);
export const report = (source: string, error: Failure) =>
render(source, { message: error.message, span: error.span });That type is a contract. Try to run the program without saying where output goes, and it doesn't compile:
Effect.runSync(run("(print 1)"));
// Type 'Output' is not assignable to type 'never'.The host provides the capability, and it can provide a different one each time. Here is one program run in two worlds:
// One program, described once. Nothing prints until it runs.
const program = run("(+ (print 1) (print 2))");
// Run it in the real world: 1 and 2 go to the console.
export const loud = program.pipe(
Effect.provideService(Output, consoleOutput),
);
// Run it in a test world: 1 and 2 go into an array.
export const quiet = () => {
const { lines, output } = recordedOutput();
const result = Effect.runSync(
program.pipe(Effect.provideService(Output, output)),
);
return { result, lines };
};quiet() returns the result 3 and the lines ["1", "2"] without touching the console. The tests for this post work that way.
To try it, put Part 2's files in a directory named 02, Part 3's in 03, and this post's in 04, install effect version 4, and run this with Node 24 from inside 04:
import { Effect } from "effect";
import { consoleOutput, Output } from "./capabilities.ts";
import { run } from "./run.ts";
import { display } from "./scope.ts";
const program = run("(((lambda (n) (lambda (x) (+ x n))) 10) 5)");
const value = Effect.runSync(
program.pipe(Effect.provideService(Output, consoleOutput)),
);
console.log(display(value)); // 15The split, in one line
A program can shadow the name print:
((lambda (print) (+ print 1)) 41) ; => 42Inside that function, print is just 41. That's lexical scope doing its job, and it's the author's business. What the program can't do is change what printing does, or print when the host hasn't granted Output. That's the host's business. The two concerns now sit in two separate places in the code: the scope argument and the R slot of the Effect.
What's still missing
Two cracks are left, and they're the subject of the next two acts.
The first is about values. This program parses, and every name in it is bound:
error: + expects numbers, got a
1 | ((lambda (x) (+ x 1)) (quote a))
| ^It fails only when it runs, and the error points inside the function body, at x, rather than at (quote a), the argument that caused the problem. Knowing before running that a function expecting a number has been given a symbol takes a type checker. That starts Act II.
The second is about capabilities. Output is in the type of every program, including (+ 1 2), because the type comes from the TypeScript interpreter, not from the program. The interpreter knows a program might print; it doesn't know which programs do. Making a program's own type say which capabilities it needs is Part 9's job.
Next: Part 5, Types Before Execution. (+ 1 "hello") should be a type error before evaluation.
The code in this post lives in docs/snippets/blog/in-the-beginning/04 and runs in the site's test suite.