Milestone M4

Functions, Closures, and Static Scope

Part V made functions values. A lambda evaluates to a closure that holds its parameters, its body, and the environment it was written in; a call runs that body in the captured environment extended with the arguments; and because the body looks names up where the function was defined, Bridger is statically scoped. This milestone puts the two forms into the evaluator.

It is also the first milestone at which a whole Bridger program runs. Execution starts by calling main, and a call is one of the arms you write here, so until now there has been no way to reach a program’s body. New on the provided side are the pieces around that call: the driver that sets up the program’s environment and calls main, the counter that bounds how deeply calls nest, and the prelude’s native primitives, which your calls dispatch to.

To-dos

grep -rn 'todo_m4!' src lists two arms left as holes after M3:

// src/interp/eval.rs — the two M4 arms of eval_expr
Expr::Lambda(..) => todo_m4!("E-Lam"),
Expr::Call(..)   => todo_m4!("E-App (dispatch Bridger vs. Native closure)"),

Lambda is short. Call carries most of this milestone: it is where a closure meets its arguments, where the call depth is counted, and where the return channel you built at M3 is finally caught.

Milestone specification

Each form this milestone adds, the rule that gives it meaning, and the cases that leave it stuck:

Form	Rule	Stuck when
`\|x, y\| e`	`E-Lam`	—
`f(e1, …, en)`	`E-App`	`f` is not a function; the argument count differs from the parameter count; calls nest more than 100 000 deep

The rules are in First-class functions and Evaluating function calls; this table is the checklist your evaluator is measured against. A call of a prelude primitive is stuck in the ways the prelude lists for it, and those cases are provided.

Four contracts hold across the two arms:

A lambda evaluates nothing. Its body runs only when the closure is called, so a lambda whose body would be stuck is still a value.
A call evaluates in a fixed order: the operator first, then the arguments from left to right. An operator that is not a function is stuck before any argument is evaluated.
A body runs in the closure’s environment, extended with one binding per parameter. The environment of the caller plays no part; that is what makes the language statically scoped.
A return stops at its call. The Control::Return that M3’s return raises is caught by the nearest enclosing call and becomes that call’s value; a Control::Raise passes through calls unchanged.

Implementing Milestone M4

Destructure each arm’s .. into the fields you need:

Variant	Fields	Covers
`Expr::Lambda`	`(Vec<LambdaParam>, Box<Expr>, Span)`	parameters, body
`Expr::Call`	`(Box<Expr>, Vec<Expr>, Span)`	operator, arguments, the whole call’s span

The value a lambda produces and the tools a call needs are all provided, and the content chapters show them: the Closure enum and LambdaParam in First-class functions, and Env::extend, the two error variants, enter_call, leave_call, and eval_prelude in Evaluating function calls. Those sections describe each arm step by step, following E-Lam’s and E-App’s premises in order. What follows adds what a test will hold you to.

Lambda builds a Closure::Bridger from the parameter names, a copy of the body, and the env the arm was given, and returns it as a Value::Closure. A parameter’s type annotation is for the type checker of Part VI and is dropped here.
Call with an operator that is not a Value::Closure is NotAFunction, with found filled in by type_of. With a Closure::Native, it hands the argument values to eval_prelude. With a Closure::Bridger, a count mismatch is ArityMismatch, expected being the parameter count and found the argument count. Both errors carry the span of the whole call.
The frame count must balance. enter_call comes before the body and leave_call after it, whatever the body’s outcome. A body that ends in Control::Return or Control::Raise arrives as an Err, and applying ? to the body’s result before calling leave_call would leave on exactly those paths without decrementing the count — and, for Return, without catching it. Take the body’s result as a value, call leave_call, and then decide what the result means.

map, filter, and fold are native, but the function they are handed usually is not. The prelude calls it by evaluating an ordinary call expression through your Call arm, so a pipeline such as map(xs, |x: Int| x * 10) exercises your arm once per element, with the same arity check and the same return handling as a call written in the program.

Running a program

From this milestone on, the interpreter runs programs from a file. cargo run builds the bridger binary and passes it the arguments after --:

$ cat fact.brg
fn fact(n: Int) -> Int = if n == 0 { 1 } else { n * fact(n - 1) };
fn main() { println(fact(5)); }

$ cargo run -q --features m4 -- fact.brg
120

The provided driver, eval_program, does the work between loading the file and running main. It binds every prelude primitive and every top-level fn into the program’s root environment, with each fn a closure over that root — the arrangement that lets top-level functions call themselves and one another, described in Recursion and higher-order functions. It then evaluates the global lets, each one after the globals it reads, and reports a cycle among them as an error. Last, it evaluates the call main() through your Call arm. No static checks run yet; the type checker joins at Milestone M5.

A program that uses closures and a prelude function prints what println wrote:

$ cat adders.brg
fn make_adder(k: Int) -> fn(Int) -> Int = |x: Int| x + k;

fn main() {
    let add5 = make_adder(5);
    println(add5(10));
    println(map([1, 2, 3], make_adder(100)));
}

$ cargo run -q --features m4 -- adders.brg
15
[101, 102, 103]

The program’s input is standard input, read whole when it does not come from a terminal, so a program that reads can be fed with a pipe:

$ cat sum.brg
fn main() {
    let a = read_int();
    let b = read_int();
    println(a + b);
}

$ echo "3 4" | cargo run -q --features m4 -- sum.brg
7

A program that gets stuck stops with a diagnostic: the error’s message, and the source with the expression that got stuck underlined. The exit status is 1, where a program that ran exits with 0. Here a call passes one argument to a function of two:

$ cat arity.brg
fn area(w: Int, h: Int) -> Int = w * h;

fn main() {
    println(area(3));
}

$ cargo run -q --features m4 -- arity.brg
  × takes 2 argument(s), given 1
   ╭─[arity.brg:4:13]
 3 │ fn main() {
 4 │     println(area(3));
   ·             ───┬───
   ·                ╰── here
 5 │ }
   ╰────

And here is the let-bound lambda from recursion and higher-order functions, which cannot see its own name:

$ cat selfref.brg
fn main() {
    let fact = |n: Int| if n == 0 { 1 } else { n * fact(n - 1) };
    println(fact(5));
}

$ cargo run -q --features m4 -- selfref.brg
  × unbound variable `fact`
   ╭─[selfref.brg:2:52]
 1 │ fn main() {
 2 │     let fact = |n: Int| if n == 0 { 1 } else { n * fact(n - 1) };
   ·                                                    ──┬─
   ·                                                      ╰── here
 3 │     println(fact(5));
   ╰────

The rendering is provided; what it shows comes from your arms. The message is the one for the RuntimeError variant your arm returned, and the underline is the span it attached: ArityMismatch from your Call arm with the span of the whole call, and UnboundVariable from the Var arm you wrote at M2, with the span of the name. A wrong span underlines the wrong code, which is why the tests check the span of every error along with its variant.

Worked examples

An expression, and the value it evaluates to:

(|x: Int| x + 1)(4)                         ⇓ 5

let y = 10;
let f = |x: Int| x + y;
f(5)                                        ⇓ 15   (y from the lambda's env)

(|f: fn(Int) -> Int| f(3))(|x: Int| x * 2)  ⇓ 6    (a function as an argument)

(|| { return 7; 9 })()                      ⇓ 7    (the call catches the return)

map([1, 2, 3], |x: Int| x * 10)             ⇓ [10, 20, 30]

Expressions with no value, which halt the run:

(|x: Int, y: Int| 0)(1)        ⇓ stuck  (ArityMismatch: expected 2, found 1)
5()                            ⇓ stuck  (NotAFunction: found Int)

And a whole program that gets stuck partway through, because each level of sum_to holds a frame until the level below it returns:

fn sum_to(n: Int) -> Int = if n == 0 { 0 } else { n + sum_to(n - 1) };
fn main() { println(sum_to(1000000)); }
                               ⇓ stuck  (StackOverflow at the call sum_to(n - 1))

How to know it works

cargo m4 runs the provided milestone M4 tests and, because the milestones are cumulative, the M3, M2, and M1 tests with them. The M4 tests come in two kinds. The first builds an Expr by hand, as the earlier milestones’ tests do, with the new builders lambda and call. The second loads a program from source and runs it through eval_program, checking the value main returns, the text it printed, or the error it got stuck on:

// (|x| x + 1)(4)  ⇓  5
let f = lambda(&["x"], binary(Add, var("x", 1), int(1, 2), 3), 0);
assert_eq!(value_of(&call(f, vec![int(4, 4)], 5)), Value::Int(5));

// a whole program: main's value, and what it printed
let (v, out) = run_program("fn main() -> () { print(42); }");

The whole-program tests reach parts of the driver as well as your arms: globals initialized in dependency order, a cycle among globals reported as an error, the read_* family consuming input. None of those needs code of yours beyond Lambda and Call, but none of them can pass until a call works, since every program starts with one.

Fill the arms, run cargo m4, and repeat until every M4 test — and every M3, M2, and M1 test — passes. Then run a program or two of your own with cargo run.

Seeing the contrast

The milestone asks for static scope only. To see what the other discipline would do, the static and dynamic scope chapter describes an optional experiment on a finished evaluator: run a call’s body in the caller’s environment, watch the closure examples diverge, and change it back.

Design problems

Bridger has no let rec. Suppose you added let rec f = |x| e, in whose right-hand side f is in scope. Why can your Block arm not implement it with Env::extend alone, and what are two ways it could be done?

The closure for |x| e has to capture an environment that already contains f, bound to that same closure. Env::extend returns a new scope containing a value you already have, so either order fails: extend first, and there is no closure yet to bind f to; build the closure first, and the environment it captured has no f, which is exactly why a let-bound lambda cannot call itself (environments). The binding has to be made before its value exists and filled in afterwards. One way is the one the provided driver uses for top-level functions: a scope whose bindings can be added after the scope is shared, so the closure captures the scope and the scope then receives the closure. Env provides that only for the program’s root, through add_function, which the driver calls and your arms do not. The other way needs nothing new from Env: treat let rec f = |x| e as the knot through the store from recursion and higher-order functions — allocate a cell, bind f to it, build the closure, write it into the cell — at the cost of reading f through deref, which a let rec would have to insert wherever f is used.

Suppose a Call arm by mistake extended the caller's environment with the parameters instead of the closure's. Most of the examples on this page still produce the same values. Write a short whole program whose output shows the mistake, and say which property of the program is responsible.

fn make_adder(k: Int) -> fn(Int) -> Int = |x: Int| x + k;

fn main() {
    let add5 = make_adder(5);
    println(add5(1));            // 6; with the caller's env, stuck: no k
}

The lambda’s body mentions k, a name bound only in the call of make_adder, and the lambda is called after that call has returned. With the closure’s environment, k is found where the lambda was written, and the program prints 6. With the caller’s environment, the body looks for k in main, which has no k, and the program is stuck with an unbound variable. A test that catches the mistake needs a function whose body uses a free name bound somewhere other than at the call site. In the examples above, the free names (y in f, the top-level functions) are visible from the caller as well, so both disciplines agree on them. Static and dynamic scope gives a program, twice(add_x, 10), where the two disciplines both produce a value and disagree on it.

Write compose_all, which takes a list of fn(Int) -> Int and returns their composition, using fold and no recursion of your own. What does it return for the empty list, and in which order are the functions applied?

fn id(x: Int) -> Int = x;
fn compose(f: fn(Int) -> Int, g: fn(Int) -> Int) -> fn(Int) -> Int =
    |x: Int| f(g(x));

fn compose_all(fs: [fn(Int) -> Int]) -> fn(Int) -> Int = fold(fs, id, compose);

compose_all([inc, dbl])(5)     // 11
compose_all([dbl, inc])(5)     // 12
compose_all([])(5)             // 5

with inc and dbl adding one and doubling. The accumulator of the fold is a function, starting at id; each step composes the function so far with the next element, so [inc, dbl] becomes compose(compose(id, inc), dbl), which applies dbl first: inc(dbl(5)) is 11. The function written last in the list runs first, as in $f \circ g$ . The empty list returns id, the function that composing with leaves unchanged, in the same role 0 plays for a sum. fold’s combining function is compose itself, a top-level fn passed by name.

With times(f, n) = fold(range(0, n), id, |acc, i| compose(f, acc)), the expression times(inc, 150000) evaluates to a function without trouble, and calling that function with 0 is a StackOverflow. Explain both halves.

fn times(f: fn(Int) -> Int, n: Int) -> fn(Int) -> Int =
    fold(range(0, n), id, |acc: fn(Int) -> Int, i: Int| compose(f, acc));

let big = times(inc, 150000);  // fine
big(0)                         // StackOverflow inside compose's lambda

Building big is a loop. fold is native and opens no frames of its own; it calls the combining lambda once per element, and each call returns, with a new closure, before the next begins. At no point are two of those calls in progress, so the depth never exceeds a few frames. The result is a chain of 150 000 closures, each holding f and the closure before it in its environment, and building it costs memory but no depth. Calling big(0) walks that chain. The outermost closure computes f(g(x)), so it must call g — the next closure in the chain — and wait for its result before calling f. Every closure in the chain is in progress at once, one frame each, and the count passes the limit of 100 000 well before the end. With n below the limit, as in times(inc, 10)(0), the call returns 10. The closures do what the recursive sum_to did, holding one pending operation per level, although the program that built them contains no recursive function.

Keyboard shortcuts

A Practical Introduction to Programming Language Design