Expressions, Statements, and Blocks

Part II focused on how to evaluate a literal expression to a value. Part III extended the language we consider to programs that bound values to names and used those names within expressions. A program built only from those parts returns a single value. This part introduces constructs that do something when they are evaluated: e.g., r := r + 1 changes the value a memory cell holds, a while loop repeats the actions of its body, an if takes one of two branches. Each raises a question the earlier forms never did — what is the value of a construct that does something?

Two answers are in wide use. A language can treat such a construct as a statement: a form executed for its effect, in a category apart from expressions, carrying no value and unable to be used where a value is required. Or it can treat it as an expression like any other, evaluated for a value even when the reason to write it is the effect. The choice runs through the whole language: its grammar, its evaluator, and later its type checker. In this chapter, we detail the choice we make in Bridger.

Effects

An effect is a change a construct makes when it runs that a later step can observe, over and above whatever value the construct computes. Assigning to a memory cell is one: r := e overwrites what the cell holds, and code that reads the cell afterward finds the new value where the old one had been. Printing a line to a screen is an effect; so is reading input from a keyboard or a file, writing a file, and sending or receiving bytes over a network connection. What these share is that running the construct leaves something changed — a cell, the screen, a file, a machine across the network — in a way that persists past the evaluation and sets the run apart from one in which the construct never ran.

Bridger’s built-in effect is mutation. A program changes state by writing a value to a memory cell with r := e, and that cell’s contents are what a later read observes; the cell and the assignment that writes it are the subject of the next chapter. Bridger also includes built-in functions for printing and reading primitive values; however, Bridger does not support reading or writing to files and network connections. This part focuses on creating, modifying, and reading mutable memory cells and the control flow required to compute using these primitives. This chapter examines the question of how to combine constructs for expressing value expressions and effectful computations.

Where languages draw the line

Fortran and Algol 60 drew a firm boundary between the two. An expression — a + b, f(x) — appeared inside a statement, and a statement — an assignment, a loop, a jump — was a different kind of thing: it produced no value and could not appear where a value was expected. A program was a sequence of statements, and expressions were the material they were built from. The conditional came twice over, once in each category: a conditional expression that chose between two values, and an if statement that chose between two courses of action.

Algol 68 lowered the boundary. Its report built a program out of units, each with a value and a type, and gave the value of a construct written for its effect a type of its own, void; an assignment and a loop were units like any other, and a place where a statement had stood became a place holding a void-valued expression (van Wijngaarden et al., 1976). Lisp had been built from expressions since 1960; Algol 68’s contribution was to carry that arrangement into the imperative, block-structured line Fortran and Algol 60 had established, and to name the value a construct leaves behind when its point was the effect. That value, and the decision of where to draw the line between value-expressions and statements, are the focus of the rest of this chapter.

The value of an effectful form

A construct run for its effect still has to fit into a language built from expressions: if it may stand where a value is expected, it has to produce one. The value that carries no information is the one to hand back, since there is nothing to report except that the work was done. Bridger’s unit type, whose single value is written (), plays that part. Assignment r := e yields (); a while loop yields (); an if with no else yields (). Unit arrived in Part II described as the value of a statement; a statement is the kind of form that produces it.

Unit is what lets the expression grammar absorb the effectful forms without a special case. A while loop has a value, so it may appear as a block item, as the right-hand side of a binding, or anywhere else an expression may go; its value happens to be the one that says only “done.” One category of form covers both the computations that report a result and the ones that report their completion.

Where Bridger draws the line

Almost every construct in Bridger is an expression with a value. if, match, while, for, and a block { … } all evaluate to something, so any of them may be used where a value is expected:

let n = if x > 0 { x } else { -x };

binds n to whichever branch is taken. The forms whose purpose is an effect are expressions too, and their value is (). So the statement category, which in Algol 60 held assignments and loops and conditionals, is nearly empty in Bridger — those forms have moved into the expressions.

What remains of a statement lives inside a block. Blocks arrived in Part III as the vehicle for binding; read now as the construct that sequences a program’s steps, a block is a sequence of items followed by an optional trailing expression. Each item is either a let or ref binding, or an expression closed with ;, which runs the expression and discards its value. The trailing expression, written with no ;, is the block’s value; a block with no trailing expression has the value ().

block       ::= '{' { block_item } [ expr ] '}' ;
block_item  ::= let_binding | ref_binding
              | ( if_expr | match_expr | while_expr | for_expr | block ) [ ';' ]
              | expr_stmt ;
expr_stmt   ::= expr ';' ;

The ; is the whole of what makes an expression a statement here: f() in a block is an expression whose value becomes the block’s value if it is last, and f(); is that same expression run for its effect with its value thrown away. The rules that evaluate a block — an item threaded for effect, the trailing expression as the value, an empty block as () — are the ones stated in Part III; they need no addition for this part.

The two forms that stay out of the expression grammar are the let and ref bindings. A binding is an item of a block and never an expression, so

let x = let y = 0;   // does not parse

is rejected: the right-hand side of a let must be an expression, and a let is not one. The line sits there because a binding’s work is to extend the environment over what follows it, and only a block supplies a “what follows.” A bare let x = 5 with no surrounding block would bind x over nothing and have no value to give; keeping it an item of a block is what makes its scope well defined. return stays outside the operator grammar as well — it is an expression, but one that abandons the enclosing function rather than yielding a value in place, and it travels by the same Control path the interpreter already uses for errors.

Building it

The provided evaluator has a single entry, eval_expr, returning a Value; there is no eval_stmt beside it. A block is one arm of that function, and a statement is a shape it walks rather than a thing evaluated to a value of its own:

// A block is statements then an optional trailing expression,
// which is the block's value; a statement is a binding or an
// expression run for its effect.
Expr::Block(Vec<Stmt>, Option<Box<Expr>>, Span)

enum Stmt {
    Let(Name, Option<Ty>, Expr, Span),   // a binding
    Expr(Expr),                          // run for effect
}

A Stmt::Expr(e) evaluates e and drops the value; a Stmt::Let evaluates the right-hand side and extends the environment over the rest of the block, exactly as let does. Because assignment, loops, and conditionals are ordinary expressions, they are evaluated by the same arms that handle 2 + 2, and the evaluator needs no second traversal for a category of forms that produce no value. Drawing the line low collapses two kinds of evaluation into one.

The same economy reaches the type checker in Part VI: one judgment $Γ ⊢ e : τ$ assigns a type to every form, with the effectful ones typed (), where a language with a statement category needs a second judgment for the forms that have no type to assign. Collecting the rules this part contributes is the work of Milestone M3.

The design space

C and Java keep the Algol 60 boundary. An if is a statement with no value, so choosing between two values calls for a separate expression-level form, the conditional operator c ? a : b; the language carries two conditionals because the statement one cannot be used where a value is wanted. Assignment goes the other way: in C a = b is an expression with a value, which is what lets if (x = 0) compile as a test — an assignment mistaken for a comparison. The split forces some forms to be duplicated across the two categories and lets others slip between them.

ML, Ruby, and Rust draw the line low, as Bridger does. In ML an if is an expression and a sequence yields its last value; Ruby lets nearly every construct return a value. Rust is the model Bridger follows most closely: it is expression-oriented, yet a let is a statement, a block’s trailing expression with no ; is the block’s value, and a ; discards. Bridger’s blocks work the same way, down to let being a block item rather than an expression. The Algol 68 arrangement of the previous section is the older member of this family; its void is the role Bridger’s () fills.

What the low line costs is a reader’s expectation that an assignment or a loop is “just a statement”: here each has a value, and a stray while where an Int was wanted is a type error against () rather than a syntax error. What it buys is a single expression grammar, a single evaluator, and a single typing judgment, with the unit type carrying the forms whose only result is that they ran. The bindings are the one place the line is drawn above the expressions, and they are drawn there because a binding means nothing except over a region that follows it.

Concept checks

Assignment r := e evaluates to (). In C, a = b evaluates to the assigned value instead. What does each choice make possible, and why does Bridger's fit its expression orientation?

C’s choice lets an assignment stand anywhere a value is wanted, including a condition, which is why if (x = 0) compiles — an assignment where a comparison was meant, with no complaint from the grammar. Bridger’s := produces () because assignment is written for its effect and unit is the value that reports only that the effect happened; the writer already knows what was assigned, so the assigned value carries no information back. Producing a value keeps := an ordinary expression, so it fits an expression-oriented language, while producing unit rather than the assigned value keeps r := 0 from silently passing where a Bool or an Int was expected — that use is a type error against ().

The block let x = let y = 0; does not parse, even though a let's right-hand side is an expression. Why is a let binding a block item rather than an expression?

A binding’s work is to extend the environment over the part of the block that follows it, so it only has meaning as an item of a block, which is what supplies a “rest of the block” for the name to be in scope over. Written on its own, let y = 0 would bind y over nothing and would have no value to hand back as the right-hand side of the outer let. Keeping bindings out of the expression grammar is what makes a name’s scope exactly the remainder of its block; the right-hand side of a let is an expression, and a let itself is not one.

C has both an if statement and a conditional operator c ? a : b; Bridger has only if. What accounts for the difference?

C’s if is a statement, so it produces no value and cannot be used to choose between two values — let n = if c { a } else { b } has no counterpart written with the if statement. The conditional operator exists to fill that gap: it is an expression-level conditional for exactly the case the statement one cannot serve. Bridger’s if is already an expression, so a single form does both jobs — it chooses a course of action when its branches produce (), and it chooses a value when they produce anything else — and no second conditional is needed.

How does drawing the statement/expression line low affect the evaluator and the type checker, compared with keeping a separate statement category?

With almost every form an expression, the evaluator is one function that returns a value: assignment, loops, and conditionals are handled by the same machinery as arithmetic, and the effectful ones return (). A language with a statement category needs a second path — a way to execute a statement that yields no value — alongside the one that evaluates an expression, and a form that exists in both categories must be handled in both. The same holds for the type checker: one judgment assigns a type to every form, with the effectful forms typed (), where a two-category language needs a separate treatment for the forms that have no type. The unit type is what makes the single path enough, giving the effectful forms a value to carry.

A Practical Introduction to Programming Language Design