Make A Language

Part Six: Blocks

6 October 2020

By the end of this post, Eldiro will have blocks. By block, I mean the Rust meaning, not one from any other programming language.1

What is a block, anyway?

In Rust (and Eldiro, once they are implemented), blocks are a way to group a bunch of bindings together and ensure that they are not accessible from outside the block. For example, foo and bar aren’t accessible outside the curly braces.

{
    let foo = 100;
    let bar = "hello";
}

What makes blocks interesting, though, is how, when evaluated, the value of the entire block is the value of its last expression. For example, the value of this block is 2:

{
    let one = 1;
    one + one
}

Because blocks are expressions, we can use them anywhere where an expression can be used. Consider this real-world example of reading a line from STDIN:

let mut input = String::new();
std::io::stdin().read_line(&mut input)?;

We need to explicitly declare input to be mutable. This protects us from accidentally mutating something that should never be changed. Let’s say that input is one of these cases – we don’t want to alter the user’s input, so it should really be immutable. We can’t remove the mut from input though, because we are mutating it by reading in the line from STDIN.

One possible solution to this problem is to use a block:

let input = {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s)?;
    s
};

input has the same value as before, but now it’s immutable. We have restricted the mutability to the inside of the block, thereby potentially preventing mistakes.

This is just one example of the usage of blocks – as you may imagine, they are a useful language feature to have.

Parsing blocks

Like always, we will begin with a parser. Create a module called block by adding pub mod block; to lib.rs and creating the file src/block.rs. Let’s get started with a test:

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn parse_empty_block() {
        assert_eq!(Block::new("{}"), Ok(("", Block { exprs: Vec::new() })));
    }
}

Let’s define Block:

use crate::expr::Expr;

#[derive(Debug, PartialEq)]
pub struct Block {
    pub exprs: Vec<Expr>,
}

Notice anything strange here? In our previous Rust examples, blocks could contain both expressions and binding definitions. If we go by the definition above, though, blocks can only contain expressions. The solution to this issue is that blocks actually contain statements, which, in Eldiro’s case, means an enum that can either contain a binding definition or an expression.

A detour into statements

Add pub mod stmt; to lib.rs and open src/stmt.rs in your editor. Let’s write two tests to make sure that statements can parse both expressions and binding definitions.

use crate::binding_def::BindingDef;
use crate::expr::Expr;

#[cfg(test)]
mod tests {
    use super::*;
    use crate::expr::{Number, Op};

    #[test]
    fn parse_binding_def() {
        assert_eq!(
            Stmt::new("let a = 10"),
            Ok((
                "",
                Stmt::BindingDef(BindingDef {
                    name: "a".to_string(),
                    val: Expr::Number(Number(10)),
                }),
            )),
        );
    }

    #[test]
    fn parse_expr() {
        assert_eq!(
            Stmt::new("1+1"),
            Ok((
                "",
                Stmt::Expr(Expr::Operation {
                    lhs: Number(1),
                    rhs: Number(1),
                    op: Op::Add,
                }),
            )),
        );
    }
}

This doesn’t compile, though, because BindingDef’s fields are not public. Let’s go to binding_def.rs and make them pub:

#[derive(Debug, PartialEq)]
pub struct BindingDef {
    pub name: String,
    pub val: Expr,
}

Cool! We now need to write Stmt’s definition:

// stmt.rs

#[derive(Debug, PartialEq)]
pub enum Stmt {
    BindingDef(BindingDef),
    Expr(Expr),
}

Now we can write the parser, which makes use of backtracking:

impl Stmt {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        BindingDef::new(s)
            .map(|(s, binding_def)| (s, Self::BindingDef(binding_def)))
            .or_else(|_| Expr::new(s).map(|(s, expr)| (s, Self::Expr(expr))))
    }
}

It may look intimidating, but what this is doing is parsing a binding definition and, if successful, turning that into a Stmt::BindingDef. If it’s unsuccessful, it instead tries to parse an Expr and, if that was successful, turns that into a Stmt::Expr.

Back to blocks

Now that we have statements, we can go back to block.rs and replace expressions with statements:

use crate::stmt::Stmt;

#[derive(Debug, PartialEq)]
pub struct Block {
    pub stmts: Vec<Stmt>,
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn parse_empty_block() {
        assert_eq!(Block::new("{}"), Ok(("", Block { stmts: Vec::new() })));
    }
}

Let’s define Block::new in the simplest way that makes the test pass:

use crate::utils;

// snip

impl Block {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        let s = utils::tag("{}", s)?;

        Ok((s, Block { stmts: Vec::new() }))
    }
}
$ cargo t -q
running 30 tests
..............................
test result: ok. 30 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Blocks can contain whitespace:

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn parse_empty_block_with_whitespace() {
        assert_eq!(Block::new("{   }"), Ok(("", Block { stmts: Vec::new() })));
    }
}

Making this work is easy: strip away the whitespace between the two braces:

impl Block {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        let s = utils::tag("{", s)?;
        let (s, _) = utils::extract_whitespace(s);
        let s = utils::tag("}", s)?;

        Ok((s, Block { stmts: Vec::new() }))
    }
}
$ cargo t -q
running 31 tests
...............................
test result: ok. 31 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Let’s now try parsing a block with a single statement:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::expr::{Expr, Number};

    // snip

    #[test]
    fn parse_block_with_one_stmt() {
        assert_eq!(
            Block::new("{ 5 }"),
            Ok((
                "",
                Block {
                    stmts: vec![Stmt::Expr(Expr::Number(Number(5)))],
                },
            )),
        );
    }
}

The easiest way to make the test pass is to try parsing just one statement, and, if it fails, use an empty vector of statements:

impl Block {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        let s = utils::tag("{", s)?;
        let (s, _) = utils::extract_whitespace(s);

        let (s, stmts) = if let Ok((s, stmt)) = Stmt::new(s) {
            (s, vec![stmt])
        } else {
            (s, Vec::new())
        };

        let (s, _) = utils::extract_whitespace(s);
        let s = utils::tag("}", s)?;

        Ok((s, Block { stmts }))
    }
}

It works:

$ cargo t -q
running 32 tests
................................
test result: ok. 32 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Let’s now write a test for multiple statements:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::binding_def::BindingDef;
    use crate::expr::{Expr, Number};

    // snip

    #[test]
    fn parse_block_with_multiple_stmts() {
        assert_eq!(
            Block::new(
                "{
    let a = 10
    let b = a
    b
}",
            ),
            Ok((
                "",
                Block {
                    stmts: vec![
                        Stmt::BindingDef(BindingDef {
                            name: "a".to_string(),
                            val: Expr::Number(Number(10)),
                        }),
                        Stmt::BindingDef(BindingDef {
                            name: "b".to_string(),
                            val: ?, // what do we put here?
                        }),
                        Stmt::Expr(?), // and here?
                    ],
                },
            )),
        );
    }
}

What do we write where those question marks are? We’re meant to put something of the type Expr, but what we have there is a BindingUsage. It looks like we’ve forgotten (I take full responsibility) to make BindingUsages expressions!

Let’s quickly fix the error that came up when we tried to use BindingUsage’s private field name in that test:

// binding_usage.rs

#[derive(Debug, PartialEq)]
pub struct BindingUsage {
    pub name: String,
}

Making BindingUsage and Block expressions

Let’s re-organise binding_usage and block to be inside of the expr module – after all, binding usages and blocks are expressions.

$ mkdir src/expr/
$ mv src/binding_usage.rs src/expr/
$ mv src/block.rs src/expr/

Then move pub mod binding_usage; and pub mod block; from lib.rs into expr.rs. To keep things nice and tidy, let’s change the imports in crate::expr::block::tests to be like this:

#[cfg(test)]
mod tests {
    // change this:
    use super::*;
    use crate::binding_def::BindingDef;
    use crate::expr::{Expr, Number};

    // to this:
    use super::super::{Expr, Number};
    use super::*;
    use crate::binding_def::BindingDef;

    // The rest of the tests stay here.
}

This way, if we ever decide to move the expr module somewhere else, the imports won’t break.

Let’s jump back to expr.rs and add tests for parsing expressions and blocks so that we can be sure we’ve integrated the parsers correctly.

pub mod binding_usage;
pub mod block;

use crate::utils;
use crate::val::Val;
use binding_usage::BindingUsage;
use block::Block;

// snip

#[cfg(test)]
mod tests {
    use super::*;
    use crate::stmt::Stmt;

    // snip

    #[test]
    fn parse_binding_usage() {
        assert_eq!(
            Expr::new("bar"),
            Ok((
                "",
                Expr::BindingUsage(BindingUsage {
                    name: "bar".to_string(),
                }),
            )),
        );
    }

    #[test]
    fn parse_block() {
        assert_eq!(
            Expr::new("{ 200 }"),
            Ok((
                "",
                Expr::Block(Block {
                    stmts: vec![Stmt::Expr(Expr::Number(Number(200)))],
                }),
            )),
        );
    }

    // snip
}

We now need to update Expr’s definition to match:

#[derive(Debug, PartialEq)]
pub enum Expr {
    Number(Number),
    Operation { lhs: Number, rhs: Number, op: Op },
    BindingUsage(BindingUsage),
    Block(Block),
}

We also need to update Expr::new so that it tries to parse binding usages and blocks:

impl Expr {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        Self::new_operation(s)
            .or_else(|_| Self::new_number(s))
            .or_else(|_| {
                BindingUsage::new(s)
                    .map(|(s, binding_usage)| (s, Self::BindingUsage(binding_usage)))
            })
            .or_else(|_| Block::new(s).map(|(s, block)| (s, Self::Block(block))))
    }

    // snip
}

Getting back to work

Let’s go back to that massive test we were writing for parsing blocks – the one with the question marks. Now, we can fill in those two fields with Expr::BindingUsages:

#[cfg(test)]
mod tests {
    use super::super::{BindingUsage, Expr, Number};
    use super::*;
    use crate::binding_def::BindingDef;

    // snip

    #[test]
    fn parse_block_with_multiple_stmts() {
        assert_eq!(
            Block::new(
                "{
    let a = 10
    let b = a
    b
}",
            ),
            Ok((
                "",
                Block {
                    stmts: vec![
                        Stmt::BindingDef(BindingDef {
                            name: "a".to_string(),
                            val: Expr::Number(Number(10)),
                        }),
                        Stmt::BindingDef(BindingDef {
                            name: "b".to_string(),
                            val: Expr::BindingUsage(BindingUsage {
                                name: "a".to_string(),
                            }),
                        }),
                        Stmt::Expr(Expr::BindingUsage(BindingUsage {
                            name: "b".to_string(),
                        })),
                    ],
                },
            )),
        );
    }
}

How are we going to make this test pass? Let’s take a look at how we are currently parsing blocks:

impl Block {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        let s = utils::tag("{", s)?;
        let (s, _) = utils::extract_whitespace(s);

        let (s, stmts) = if let Ok((s, stmt)) = Stmt::new(s) {
            (s, vec![stmt])
        } else {
            (s, Vec::new())
        };

        let (s, _) = utils::extract_whitespace(s);
        let s = utils::tag("}", s)?;

        Ok((s, Block { stmts }))
    }
}

The solution is to create a loop that continuously updates s and keeps pushing to a Vec<Stmt> until parsing a Stmt fails:

impl Block {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        let s = utils::tag("{", s)?;
        let (s, _) = utils::extract_whitespace(s);

        let mut s = s;
        let mut stmts = Vec::new();

        while let Ok((new_s, stmt)) = Stmt::new(s) {
            s = new_s;
            stmts.push(stmt);
        }

        let (s, _) = utils::extract_whitespace(s);
        let s = utils::tag("}", s)?;

        Ok((s, Block { stmts }))
    }
}

We can’t check if we’re right, though, as we have a compilation error elsewhere in the project. The problem is in Expr::eval; more specifically, Rust is complaining that we haven’t handled the cases of evaluating binding usages or blocks. For now, we’ll tell Rust that those are a work-in-progress, and that we’ll come back to it later:

// expr.rs

impl Expr {
    // snip

    pub(crate) fn eval(&self) -> Val {
        match self {
            Self::Number(Number(n)) => Val::Number(*n),
            Self::Operation { lhs, rhs, op } => {
                let Number(lhs) = lhs;
                let Number(rhs) = rhs;

                let result = match op {
                    Op::Add => lhs + rhs,
                    Op::Sub => lhs - rhs,
                    Op::Mul => lhs * rhs,
                    Op::Div => lhs / rhs,
                };

                Val::Number(result)
            }
            _ => todo!(),
        }
    }
}

Let’s see if it works:

$ cargo t -q
running 35 tests
...........F.......................
failures:

---- expr::block::tests::parse_block_with_multiple_stmts stdout ----
thread 'expr::block::tests::parse_block_with_multiple_stmts' panicked at 'assertion failed: `(left == right)`
  left: `Err("expected }")`,
 right: `Ok(("", Block { stmts: [BindingDef(BindingDef { name: "a", val: Number(Number(10)) }), BindingDef(BindingDef { name: "b", val: BindingUsage(BindingUsage { name: "a" }) }), Expr(BindingUsage(BindingUsage { name: "b" }))] }))`', src/expr/block.rs:60:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    expr::block::tests::parse_block_with_multiple_stmts

test result: FAILED. 34 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

Oof! Let’s add in a debug print to see where we went wrong:

impl Block {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        let s = utils::tag("{", s)?;
        let (s, _) = utils::extract_whitespace(s);

        let mut s = dbg!(s); // here
        let mut stmts = Vec::new();

        while let Ok((new_s, stmt)) = Stmt::new(s) {
            s = new_s;
            stmts.push(stmt);
        }

        let (s, _) = utils::extract_whitespace(s);
        let s = utils::tag("}", s)?;

        Ok((s, Block { stmts }))
    }
}

Let’s run the tests again:

running 35 tests
.......F...........................
failures:

---- expr::block::tests::parse_block_with_multiple_stmts stdout ----
[src/expr/block.rs:14] s = "\n    let a = 10\n    let b = a\n    b\n}"
thread 'expr::block::tests::parse_block_with_multiple_stmts' panicked at 'assertion failed: `(left == right)`
  left: `Err("expected }")`,
 right: `Ok(("", Block { stmts: [BindingDef(BindingDef { name: "a", val: Number(Number(10)) }), BindingDef(BindingDef { name: "b", val: BindingUsage(BindingUsage { name: "a" }) }), Expr(BindingUsage(BindingUsage { name: "b" }))] }))`', src/expr/block.rs:60:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    expr::block::tests::parse_block_with_multiple_stmts

test result: FAILED. 34 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

Ahah! Take a look at that newline at the start of s. You’d expect that the utils::extract_whitespace call right before the debug print would’ve stripped that off, but it didn’t. This is because utils::extract_whitespace only deals with spaces, not newlines. Let’s fix this (don’t forget to remove the debug print!):

// utils.rs

// snip

const WHITESPACE: &[char] = &[' ', '\n'];

pub(crate) fn extract_whitespace(s: &str) -> (&str, &str) {
    take_while(|c| WHITESPACE.contains(&c), s)
}

pub(crate) fn extract_whitespace1(s: &str) -> Result<(&str, &str), String> {
    take_while1(
        |c| WHITESPACE.contains(&c),
        s,
        "expected whitespace".to_string(),
    )
}

// snip

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn extract_newlines_or_spaces() {
        assert_eq!(extract_whitespace(" \n   \n\nabc"), ("abc", " \n   \n\n"));
    }

    #[test]
    fn do_not_extract_spaces1_when_input_does_not_start_with_them() {
        assert_eq!(
            extract_whitespace1("blah"),
            Err("expected whitespace".to_string()),
        );
    }

    // snip
}

Let’s run our tests and see how we went:

$ cargo t -q
running 36 tests
......F....F........................
failures:

---- expr::block::tests::parse_block_with_multiple_stmts stdout ----
thread 'expr::block::tests::parse_block_with_multiple_stmts' panicked at 'assertion failed: `(left == right)`
  left: `Err("expected }")`,
 right: `Ok(("", Block { stmts: [BindingDef(BindingDef { name: "a", val: Number(Number(10)) }), BindingDef(BindingDef { name: "b", val: BindingUsage(BindingUsage { name: "a" }) }), Expr(BindingUsage(BindingUsage { name: "b" }))] }))`', src/expr/block.rs:60:9

---- binding_def::tests::cannot_parse_binding_def_without_space_after_let stdout ----
thread 'binding_def::tests::cannot_parse_binding_def_without_space_after_let' panicked at 'assertion failed: `(left == right)`
  left: `Err("expected whitespace")`,
 right: `Err("expected a space")`', src/binding_def.rs:63:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    binding_def::tests::cannot_parse_binding_def_without_space_after_let
    expr::block::tests::parse_block_with_multiple_stmts

test result: FAILED. 34 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out

Not again; that same bug from before is still there! The second failure is easy to fix, though – it’s an old error message that we just updated:

// binding_def.rs

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn cannot_parse_binding_def_without_space_after_let() {
        assert_eq!(
            BindingDef::new("letaaa=1+2"),
            Err("expected a space".to_string()),
        );
    }
}

Run the tests!

$ cargo t -q
running 36 tests
.........F..........................
failures:

---- expr::block::tests::parse_block_with_multiple_stmts stdout ----
thread 'expr::block::tests::parse_block_with_multiple_stmts' panicked at 'assertion failed: `(left == right)`
  left: `Err("expected }")`,
 right: `Ok(("", Block { stmts: [BindingDef(BindingDef { name: "a", val: Number(Number(10)) }), BindingDef(BindingDef { name: "b", val: BindingUsage(BindingUsage { name: "a" }) }), Expr(BindingUsage(BindingUsage { name: "b" }))] }))`', src/expr/block.rs:60:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    expr::block::tests::parse_block_with_multiple_stmts

test result: FAILED. 35 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

Great! One down, one to go. To try and squash this last bug, let’s add a couple more debug prints:

// block.rs

impl Block {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        let s = utils::tag("{", s)?;
        let (s, _) = utils::extract_whitespace(s);

        let mut s = dbg!(s); // here
        let mut stmts = Vec::new();

        while let Ok((new_s, stmt)) = Stmt::new(s) {
            s = dbg!(new_s); // here
            stmts.push(stmt);
            dbg!(&stmts); // and here
        }

        let (s, _) = utils::extract_whitespace(s);
        let s = utils::tag("}", s)?;

        Ok((s, Block { stmts }))
    }
}

I wonder what we’ll see …

$ cargo t -q
running 36 tests
...................F................
failures:

---- expr::block::tests::parse_block_with_multiple_stmts stdout ----
[src/expr/block.rs:14] s = "let a = 10\n    let b = a\n    b\n}"
[src/expr/block.rs:18] new_s = "\n    let b = a\n    b\n}"
[src/expr/block.rs:20] &stmts = [
    BindingDef(
        BindingDef {
            name: "a",
            val: Number(
                Number(
                    10,
                ),
            ),
        },
    ),
]
thread 'expr::block::tests::parse_block_with_multiple_stmts' panicked at 'assertion failed: `(left == right)`
  left: `Err("expected }")`,
 right: `Ok(("", Block { stmts: [BindingDef(BindingDef { name: "a", val: Number(Number(10)) }), BindingDef(BindingDef { name: "b", val: BindingUsage(BindingUsage { name: "a" }) }), Expr(BindingUsage(BindingUsage { name: "b" }))] }))`', src/expr/block.rs:61:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    expr::block::tests::parse_block_with_multiple_stmts

test result: FAILED. 35 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

Ah, I think I’ve figured it out: we never strip off the whitespace between statements, causing Stmt::new to error out on the next iteration of the loop, which exits the loop. We then remove the leading whitespace, leaving utils::tag to stumble across let, rather than the expected }.

Here’s the fix:

impl Block {
    pub fn new(s: &str) -> Result<(&str, Self), String> {
        let s = utils::tag("{", s)?;
        let (s, _) = utils::extract_whitespace(s);

        let mut s = s;
        let mut stmts = Vec::new();

        while let Ok((new_s, stmt)) = Stmt::new(s) {
            s = new_s;
            stmts.push(stmt);

            let (new_s, _) = utils::extract_whitespace(s);
            s = new_s;
        }

        let (s, _) = utils::extract_whitespace(s);
        let s = utils::tag("}", s)?;

        Ok((s, Block { stmts }))
    }
}
$ cargo t -q
running 36 tests
....................................
test result: ok. 36 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Fantastic!

Evaluating blocks

Now that we’re done with parsing blocks, we can move on to evaluating them. Open up expr.rs and scroll down to that todo!() we added earlier:

impl Expr {
    pub(crate) fn eval(&self) -> Val {
        match self {
            Self::Number(Number(n)) => Val::Number(*n),
            Self::Operation { lhs, rhs, op } => {
                let Number(lhs) = lhs;
                let Number(rhs) = rhs;

                let result = match op {
                    Op::Add => lhs + rhs,
                    Op::Sub => lhs - rhs,
                    Op::Mul => lhs * rhs,
                    Op::Div => lhs / rhs,
                };

                Val::Number(result)
            }
            _ => todo!(),
        }
    }
}

That wildcard pattern (_) catches both Expr::BindingUsage and Expr::Block; let’s add a test for evaluating Expr::BindingUsage first:

pub mod binding_usage;
pub mod block;

use crate::env::Env;
use crate::utils;
use crate::val::Val;
use binding_usage::BindingUsage;
use block::Block;

// snip

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn eval_binding_usage() {
        let mut env = Env::default();
        env.store_binding("ten".to_string(), Val::Number(10));

        assert_eq!(
            Expr::BindingUsage(BindingUsage {
                name: "ten".to_string(),
            })
            .eval(&env),
            Ok(Val::Number(10)),
        );
    }
}

Remember that the eval method needs to have access to an Env so that it can obtain the values of bindings, and that it needs to return a Result in case the binding being used doesn’t exist. Both of these things aren’t true for the current implementation of Expr::eval.

Let’s make Expr::eval take a reference to an Env and return a Result:

impl Expr {
    pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
        match self {
            Self::Number(Number(n)) => Ok(Val::Number(*n)),
            Self::Operation { lhs, rhs, op } => {
                let Number(lhs) = lhs;
                let Number(rhs) = rhs;

                let result = match op {
                    Op::Add => lhs + rhs,
                    Op::Sub => lhs - rhs,
                    Op::Mul => lhs * rhs,
                    Op::Div => lhs / rhs,
                };

                Ok(Val::Number(result))
            }
            _ => todo!(),
        }
    }
}

We now need to update all of Expr::eval’s tests:

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn eval_add() {
        assert_eq!(
            Expr::Operation {
                lhs: Number(10),
                rhs: Number(10),
                op: Op::Add,
            }
            .eval(&Env::default()),
            Ok(Val::Number(20)),
        );
    }

    #[test]
    fn eval_sub() {
        assert_eq!(
            Expr::Operation {
                lhs: Number(1),
                rhs: Number(5),
                op: Op::Sub,
            }
            .eval(&Env::default()),
            Ok(Val::Number(-4)),
        );
    }

    #[test]
    fn eval_mul() {
        assert_eq!(
            Expr::Operation {
                lhs: Number(5),
                rhs: Number(6),
                op: Op::Mul,
            }
            .eval(&Env::default()),
            Ok(Val::Number(30)),
        );
    }

    #[test]
    fn eval_div() {
        assert_eq!(
            Expr::Operation {
                lhs: Number(200),
                rhs: Number(20),
                op: Op::Div,
            }
            .eval(&Env::default()),
            Ok(Val::Number(10)),
        );
    }

    // snip
}

The change to Expr::eval’s signature has caused some other errors, too:

$ cargo c
    Checking eldiro v0.1.0 (/home/me/src/eldiro)
error[E0061]: this function takes 1 argument but 0 arguments were supplied
  --> src/binding_def.rs:34:55
   |
34 |         env.store_binding(self.name.clone(), self.val.eval());
   |                                                       ^^^^- supplied 0 arguments
   |                                                       |
   |                                                       expected 1 argument
   | 
  ::: src/expr.rs:73:5
   |
73 |     pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
   |     ----------------------------------------------------------- defined here

error[E0308]: mismatched types
  --> src/binding_def.rs:34:46
   |
34 |         env.store_binding(self.name.clone(), self.val.eval());
   |                                              ^^^^^^^^^^^^^^^ expected enum `val::Val`, found enum `std::result::Result`
   |
   = note: expected enum `val::Val`
              found enum `std::result::Result<val::Val, std::string::String>`

error: aborting due to 2 previous errors

Looks like we have to update BindingDef::eval:

impl BindingDef {
    // snip

    pub(crate) fn eval(&self, env: &mut Env) -> Result<(), String> {
        env.store_binding(self.name.clone(), self.val.eval(env)?);
        Ok(())
    }
}

Eldiro compiles now, so let’s run the tests:

$ cargo t -q
running 37 tests
..............F......................
failures:

---- expr::tests::eval_binding_usage stdout ----
thread 'expr::tests::eval_binding_usage' panicked at 'not yet implemented', src/expr.rs:89:18
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    expr::tests::eval_binding_usage

test result: FAILED. 36 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

Oops! I totally forgot about that todo!(). Let’s add a specific case to the match in Expr::eval for Expr::BindingUsage:

impl Expr {
    // snip

    pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
        match self {
            Self::Number(Number(n)) => Ok(Val::Number(*n)),
            Self::Operation { lhs, rhs, op } => {
                let Number(lhs) = lhs;
                let Number(rhs) = rhs;

                let result = match op {
                    Op::Add => lhs + rhs,
                    Op::Sub => lhs - rhs,
                    Op::Mul => lhs * rhs,
                    Op::Div => lhs / rhs,
                };

                Ok(Val::Number(result))
            }
            Self::BindingUsage(binding_usage) => binding_usage.eval(env),
            _ => todo!(),
        }
    }
}

I wonder if it all works …

$ cargo t -q
running 37 tests
.....................................
test result: ok. 37 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Great! The only thing that’s left is to implement evaluation for blocks.

Actually evaluating blocks

Let’s remove that todo!() in Expr::eval for good, and instead call an imaginary method on Block:

impl Expr {
    // snip

    pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
        match self {
            Self::Number(Number(n)) => Ok(Val::Number(*n)),
            Self::Operation { lhs, rhs, op } => {
                let Number(lhs) = lhs;
                let Number(rhs) = rhs;

                let result = match op {
                    Op::Add => lhs + rhs,
                    Op::Sub => lhs - rhs,
                    Op::Mul => lhs * rhs,
                    Op::Div => lhs / rhs,
                };

                Ok(Val::Number(result))
            }
            Self::BindingUsage(binding_usage) => binding_usage.eval(env),
            Self::Block(block) => block.eval(env),
        }
    }
}

We should write a simple test in this file to ensure that everything is integrating properly:

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn eval_block() {
        assert_eq!(
            Expr::Block(Block {
                stmts: vec![Stmt::Expr(Expr::Number(Number(10)))],
            })
            .eval(&Env::default()),
            Ok(Val::Number(10)),
        );
    }
}

Now that that’s done, we can implement the imaginary method from before. But first, we should write a simple test so that we have something to guide us:

// block.rs

use crate::env::Env;
use crate::stmt::Stmt;
use crate::utils;
use crate::val::Val;

// snip

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn eval_empty_block() {
        assert_eq!(
            Block { stmts: Vec::new() }.eval(&Env::default()),
            Ok(?),
        );
    }
}

What do we want that ? to be? In Rust, the value of an empty block is (), also known as the unit or the empty tuple. Eldiro doesn’t have tuples yet, so the easiest option for now is to add a Unit variant to Val:

// val.rs

#[derive(Debug, Clone, PartialEq)]
pub enum Val {
    Number(i32),
    Unit,
}

Although this is intentionally adding the Billion Dollar Mistake to the language, eventually it’ll be removed and replaced with an empty tuple.

Now that that’s in place, we can remove the ? from our test and replace it with Val::Unit:

// block

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn eval_empty_block() {
        assert_eq!(
            Block { stmts: Vec::new() }.eval(&Env::default()),
            Ok(Val::Unit),
        );
    }
}

What’s the easiest way to make this test pass?

impl Block {
    // snip

    pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
        Ok(Val::Unit)
    }
}

This does make this one specific test pass, but the test we wrote earlier with the block containing the number 10 is failing:

$ cargo t -q
running 39 tests
..................F....................
failures:

---- expr::tests::eval_block stdout ----
thread 'expr::tests::eval_block' panicked at 'assertion failed: `(left == right)`
  left: `Ok(Unit)`,
 right: `Ok(Number(10))`', src/expr.rs:254:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    expr::tests::eval_block

test result: FAILED. 38 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

Let’s write a test just like that, but in block.rs, so we can see all the test cases for evaluating blocks in one place:2

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn eval_block_with_one_expr() {
        assert_eq!(
            Block {
                stmts: vec![Stmt::Expr(Expr::Number(Number(25)))],
            }
            .eval(&Env::default()),
            Ok(Val::Number(25)),
        );
    }
}

This fails in the same way that crate::expr::tests::eval_block does:

$ cargo t -q
running 40 tests
......F.....F...........................
failures:

---- expr::block::tests::eval_block_with_one_expr stdout ----
thread 'expr::block::tests::eval_block_with_one_expr' panicked at 'assertion failed: `(left == right)`
  left: `Ok(Unit)`,
 right: `Ok(Number(25))`', src/expr/block.rs:110:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- expr::tests::eval_block stdout ----
thread 'expr::tests::eval_block' panicked at 'assertion failed: `(left == right)`
  left: `Ok(Unit)`,
 right: `Ok(Number(10))`', src/expr.rs:254:9


failures:
    expr::block::tests::eval_block_with_one_expr
    expr::tests::eval_block

test result: FAILED. 38 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out

A neat way to make both of these tests pass is to use .last() on the vector of statements that Block contains, combined with an Option combinator to handle the case when the Block is empty:

impl Block {
    // snip

    pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
        self.stmts.last().map_or(Ok(Val::Unit), |stmt| match stmt {
            Stmt::BindingDef(_) => todo!(),
            Stmt::Expr(expr) => expr.eval(env),
        })
    }
}
$ cargo t -q
running 40 tests
........................................
test result: ok. 40 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Cool, that works. We now need to add a test to see if the block maintains the evaluation environment as binding definitions are added:

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn eval_block_with_binding_def_and_usage() {
        assert_eq!(
            Block {
                stmts: vec![
                    Stmt::BindingDef(BindingDef {
                        name: "one".to_string(),
                        val: Expr::Number(Number(1)),
                    }),
                    Stmt::Expr(Expr::BindingUsage(BindingUsage {
                        name: "one".to_string(),
                    })),
                ],
            }
            .eval(&Env::default()),
            Ok(Val::Number(1)),
        );
    }
}

The critical part here is that Block::eval takes an immutable reference to the evaluation environment – in other words, we are preventing a bug where the block can affect the value of bindings outside it by making use of Rust’s borrowing rules. How are we going to evaluate binding definitions (which need a mutable reference to the Env) if we don’t have mutable access to the evaluation environment, though?

The solution is to create a new, independent Env inside of Block::eval. This way any bindings created inside of the block are isolated, and we have full permission to create mutable references as we please. Here’s a pretty messy implementation:

impl Block {
    // snip

    pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
        if self.stmts.is_empty() {
            return Ok(Val::Unit);
        }

        let mut env = Env::default();

        let stmts_except_last = &self.stmts[..self.stmts.len() - 1];
        for stmt in stmts_except_last {
            match stmt {
                Stmt::BindingDef(binding_def) => binding_def.eval(&mut env)?,
                Stmt::Expr(expr) => {
                    expr.eval(&env)?;
                }
            }
        }

        // We can unwrap safely here because we have already checked whether self.stmts is empty.
        let last = self.stmts.last().unwrap();

        match last {
            Stmt::BindingDef(binding_def) => {
                binding_def.eval(&mut env)?;
                Ok(Val::Unit)
            }
            Stmt::Expr(expr) => expr.eval(&env),
        }
    }
}

We check first if the block is empty; if it is, we return early with Val::Unit; otherwise, we go on to loop through all the statements in the block but the last, and evaluate them. The last statement is treated specially, because its value is the value of the entire block. This does all indeed work correctly:

$ cargo t -q
running 41 tests
.........................................
test result: ok. 41 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

But the code is repetitive and isn’t clean. Take a look, for example, at the match inside the for loop and at the end of the function: they are similar, and could be abstracted into a function. Let’s extract it into Stmt::eval:

// stmt.rs

use crate::binding_def::BindingDef;
use crate::env::Env;
use crate::expr::Expr;
use crate::val::Val;

// snip

impl Stmt {
    // snip

    pub(crate) fn eval(&self, env: &mut Env) -> Result<Val, String> {
        match self {
            Self::BindingDef(binding_def) => {
                binding_def.eval(env)?;
                Ok(Val::Unit)
            }
            Self::Expr(expr) => expr.eval(env),
        }
    }
}

Let’s write a pair of tests to make sure this works:

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn eval_binding_def() {
        assert_eq!(
            Stmt::BindingDef(BindingDef {
                name: "whatever".to_string(),
                val: Expr::Number(Number(-10)),
            })
            .eval(&mut Env::default()),
            Ok(Val::Unit),
        );
    }

    #[test]
    fn eval_expr() {
        assert_eq!(
            Stmt::Expr(Expr::Number(Number(5))).eval(&mut Env::default()),
            Ok(Val::Number(5)),
        );
    }
}

We can now go back to Block::eval and make use of Stmt::eval:

impl Block {
    // snip

    pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
        if self.stmts.is_empty() {
            return Ok(Val::Unit);
        }

        let mut env = Env::default();

        let stmts_except_last = &self.stmts[..self.stmts.len() - 1];
        for stmt in stmts_except_last {
            stmt.eval(&mut env)?;
        }

        // We can unwrap safely here because we have already checked whether self.stmts is empty.
        self.stmts.last().unwrap().eval(&mut env)
    }
}

Let’s run the tests to see if we’ve broken anything:

$ cargo t -q
running 43 tests
...........................................
test result: ok. 43 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Nope! It’s all in working order.

I’m not happy with the test suite, though. I think that we need two more tests; specifically, we need a test to check that a block of only binding definitions has a value of Val::Unit, and we also need a test to check that the last statement of the block becomes the value of the entire block.

Here are the tests to add:

#[cfg(test)]
mod tests {
    use super::super::{BindingUsage, Expr, Number, Op};
    use super::*;
    use crate::binding_def::BindingDef;

    // snip

    #[test]
    fn eval_block_with_multiple_binding_defs() {
        assert_eq!(
            Block {
                stmts: vec![
                    Stmt::BindingDef(BindingDef {
                        name: "foo".to_string(),
                        val: Expr::Number(Number(5)),
                    }),
                    Stmt::BindingDef(BindingDef {
                        name: "bar".to_string(),
                        val: Expr::Number(Number(4)),
                    }),
                    Stmt::BindingDef(BindingDef {
                        name: "baz".to_string(),
                        val: Expr::Number(Number(3)),
                    }),
                ],
            }
            .eval(&Env::default()),
            Ok(Val::Unit),
        );
    }

    #[test]
    fn eval_block_with_multiple_exprs() {
        assert_eq!(
            Block {
                stmts: vec![
                    Stmt::Expr(Expr::Number(Number(100))),
                    Stmt::Expr(Expr::Number(Number(30))),
                    Stmt::Expr(Expr::Operation {
                        lhs: Number(10),
                        rhs: Number(7),
                        op: Op::Sub,
                    }),
                ],
            }
            .eval(&Env::default()),
            Ok(Val::Number(3)),
        );
    }
}

It turns out that both of these tests pass with the current implementation, which is convenient:

$ cargo t -q
running 45 tests
.............................................
test result: ok. 45 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Inheriting bindings from parent env

Have you noticed that the env parameter of Block::eval is unused?

When a block is evaluated, it should still be able to access all the bindings from the environment it is being evaluated with. For example:

let foo = 2
let bar = {
    let baz = foo
    baz
}

foo, which comes from the ‘parent’ Env, is being accessed from within the block.

Let’s write a test to ensure that Eldiro has this behaviour:

// block.rs

#[cfg(test)]
mod tests {
    // snip

    #[test]
    fn eval_block_using_bindings_from_parent_env() {
        let mut env = Env::default();
        env.store_binding("foo".to_string(), Val::Number(2));

        assert_eq!(
            Block {
                stmts: vec![
                    Stmt::BindingDef(BindingDef {
                        name: "baz".to_string(),
                        val: Expr::BindingUsage(BindingUsage {
                            name: "foo".to_string(),
                        }),
                    }),
                    Stmt::Expr(Expr::BindingUsage(BindingUsage {
                        name: "baz".to_string(),
                    })),
                ],
            }
            .eval(&env),
            Ok(Val::Number(2)),
        );
    }
}

We haven’t accounted for accessing bindings from the parent Env in the current Block::eval implementation, so the test fails:

$ cargo t -q
running 46 tests
..........F...................................
failures:

---- expr::block::tests::eval_block_using_bindings_from_parent_env stdout ----
thread 'expr::block::tests::eval_block_using_bindings_from_parent_env' panicked at 'assertion failed: `(left == right)`
  left: `Err("binding with name ‘foo’ does not exist")`,
 right: `Ok(Number(2))`', src/expr/block.rs:198:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    expr::block::tests::eval_block_using_bindings_from_parent_env

test result: FAILED. 45 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

The fix for this is incredibly simple: rather than creating an empty environment to evaluate the block’s statements in, we clone the environment that was passed into Block::eval:

impl Block {
    // snip

    pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
        if self.stmts.is_empty() {
            return Ok(Val::Unit);
        }

        // Doesn’t compile because Env doesn’t implement Clone.
        let mut env = env.clone();

        let stmts_except_last = &self.stmts[..self.stmts.len() - 1];
        for stmt in stmts_except_last {
            stmt.eval(&mut env)?;
        }

        // We can unwrap safely here because we have already checked whether self.stmts is empty.
        self.stmts.last().unwrap().eval(&mut env)
    }
}

There is a better way, though: instead of duplicating the values of all the bindings in the parent environment, we can store a reference to the parent environment inside of Env:

// env.rs

#[derive(Debug, PartialEq, Default)]
pub(crate) struct Env<'parent> {
    bindings: HashMap<String, Val>,
    parent: Option<&'parent Self>,
}

parent is an Option because at the top of the chain of nested blocks there is an Env that does not have a parent. This can be referred to as the ‘root’.

We need to adjust the implementation of Env::get_binding_value to recursively ask its parent for the value of a binding, so that, when we get the value of a binding, we keep searching up the chain until we either find the binding, or reach the root, at which point we can return an error.

impl<'parent> Env<'parent> {
    // snip

    pub(crate) fn get_binding_value(&self, name: &str) -> Result<Val, String> {
        self.get_binding_value_without_error_msg(name)
            .ok_or_else(|| format!("binding with name ‘{}’ does not exist", name))
    }

    fn get_binding_value_without_error_msg(&self, name: &str) -> Option<Val> {
        self.bindings.get(name).cloned().or_else(|| {
            self.parent
                .and_then(|parent| parent.get_binding_value_without_error_msg(name))
        })
    }
}

We also need a way to create a ‘child’ environment from a parent:

impl<'parent> Env<'parent> {
    pub(crate) fn create_child(&'parent self) -> Self {
        Self {
            bindings: HashMap::new(),
            parent: Some(self),
        }
    }

    // snip
}

We can now update Block::eval to create a child environment from the environment that is passed into the method:

impl Block {
    // snip

    pub(crate) fn eval(&self, env: &Env) -> Result<Val, String> {
        if self.stmts.is_empty() {
            return Ok(Val::Unit);
        }

        let mut child_env = env.create_child();

        let stmts_except_last = &self.stmts[..self.stmts.len() - 1];
        for stmt in stmts_except_last {
            stmt.eval(&mut child_env)?;
        }

        // We can unwrap safely here because we have already checked whether self.stmts is empty.
        self.stmts.last().unwrap().eval(&mut child_env)
    }
}

As usual, we’ll finish off this post by running the tests:

$ cargo t -q
running 46 tests
..............................................
test result: ok. 46 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Thanks for reading! In the next post we’ll create a REPL for Eldiro. This will both allow for some immediate feedback during development, as well as fixing all those warnings about unused functions we’ve been seeing for so long.


  1. Ruby, for example, also has the idea of a block, that coincidentally is different from the Rust meaning. ↩︎

  2. The tests in crate::expr don’t count, because those are only there to test that we’ve integrated Block::eval with Expr::eval. ↩︎