As an exercise to learn more about Rust, I decided to write a calculator program. It’s able to evaluate arbitrary numerical expressions (i.e. 2 * 3^5 / 3), as well as simple algebraic expressions (i.e. 3x + 5x). These articles will document some of the hurdles that I ran into, as well as the solutions that I came up with. Well, let’s not linger any longer and jump right in!

Defining the AST

After creating the project files with cargo, let’s start by defining the abstract syntax tree that represents each numerical expression. An easy way to do that is to come up with some sample expressions that we want to evaluate, such as

  • 1 + 1 - 2
  • 3 * 2
  • 5 / 3
  • (1 + 1) * 2
  • 3x + 5x

Based on the first example, it seems like we’ll need a term to represent a constant, as well as a term to represent a sum. Subtraction (i.e 2 - 1) is special case of a sum with a negative term, so we don’t have to add a term for it. Next, we’ll need terms for multiplication and division. We can’t just use one term for both like we can for addition and subtraction, since it’s possible to multiply by zero but not divide by zero. Let’s go ahead and sketch out the initial enum:

enum Expr {
    Const(f64),
    Sum(f64, f64),
    Product(f64, f64),
    Quotient(f64, f64)
}

There’s a problem with this representation, though; we can’t express chained operations like 1 + 1 * 2. We’ll have to modify the enum to hold Expr instead. The simplest approach may be to replace the f64s in Sum, Product, and Quotient with Expr:

enum Expr {
    Const(f64),
    Sum(Expr, Expr),
    Product(Expr, Expr),
    Quotient(Expr, Expr)
}

Unfortunately, this fails to compile:

error[E0072]: recursive type `Expr` has infinite size

A Sum could contain infinitely many Sums, for example, so it would be impossible for Rust to determine how large an Expr would be. Instead, we’ll have to use references inside of each recursive term. We could write &Expr, but then we’d have to manage a lot of lifetimes. Instead, let’s use Box:

enum Expr {
    Const(f64),
    Sum(Box<Expr>, Box<Expr>),
    Product(Box<Expr>, Box<Expr>),
    Quotient(Box<Expr>, Box<Expr>)
}

Great, it compiles! Let’s try it out by writing out 1 + 1 and 1 + 1 * 2:

let one_plus_one =
    Expr::Sum(
        Box::new(Expr::Const(1.0)),
	Box::new(Expr::Const(1.0))
    );

let one_plus_one_times_two = 
    Expr::Sum(
        Box::new(Expr::Const(1.0)),
	Box::new(
	    Expr::Product(
	        Box::new(Expr::Const(1.0)),
	        Box::new(Expr::Const(2.0))
	    )
	)
    );

Unfortunately, it requires a lot of boilerplate, but it works. After adding #[derive(Debug)] above the Expr enum, we can print out an Expr e.g. println!("{:?}", one_plus_one).

Implementing a DSL

It’d be nice if we could write out calculations directly in our code. That’s sounds like a good case for writing a macro, but let’s try something simpler instead: making a DSL. The greatest inconvenience is probably the fact that we have to box each term in a sum or product. Let’s write a few helper functions to automatically do the boxing for us. Implementation should be very straightforward:

impl Expr { // In this section, we'll just focus on sum and product
    fn sum(lh: Expr, rh: Expr) -> Expr {
        Expr::Sum(Box::new(lh), Box::new(rh))
    }

    fn product(lh: Expr, rh: Expr) -> Expr {
        Expr::Product(Box::new(lh), Box::new(rh))
    }
}

Now, instead of writing Expr::Sum(Box::new(...), Box::new(...)), we could just write Expr::product(Expr::Const(1), Expr::Const(2)). This is already much better, but let’s take it a step further: let’s aim for something like Expr::sum(1, Expr::product(1, 2)). We don’t want to just limit our parameters to Expr, but we also want to include f64. We can achieve that by using a type parameter with a trait bound on it:

fn sum<L, R>(lh: L, rh: R) -> Expr where L: Into<Expr>, R: Into<Expr> {
    Expr::Sum(Box::new(lh.into()), Box::new(rh.into()))
}

fn product<L, R>(lh: L, rh: R) -> Expr where L: Into<Expr>, R: Into<Expr> {
    Expr::Product(Box::new(lh.into()), Box::new(rh.into()))
}

The Into trait lets us use a type T as a parameter given that we implement an into function which converts from a T to the target type (which, in our case, is Expr). In the case of the above function, we’ll use L and R instead of a single T, since the left and right hand parameters could have different types, like in Expr::sum(1, Expr::sum(1, 2)).

Speaking of which, we can’t write an expression using f64 directly without implementing Into<Expr> for f64. However, it seems more natural to implement a From<f64> for Expr (which provides an Into instance for free) instead, since we want to convert from an f64 to an Expr.

impl From<f64> for Expr {
    fn from(x: f64) -> Expr {
        Expr::Const(x)
    }
}

We can now write out sum and product with a mix of f64 and Expr. Let’s rewrite one_plus_one and one_plus_one_times_two and add an even more complicated expression:

let one_plus_one = Expr::sum(1.0, Expr::Const(1.0));
let one_plus_one_times_two = Expr::sum(1.0, Expr::product(1.0, 2.0));

let complicated_expr =
    Expr::sum(Expr::product(1.0, 2.0), Expr::product(3.0, 4.0));

Bonus: Natural-looking Expressions

Going even further, we could make it possible to use the +, -, *, and / operators in our code. All we have to do is implement the Add, Sub, Mul, and Div traits, respectively, by specifying the resulting type (which, in our case, is Expr) and implementing a function corresponding to the operation. All we have to do is call the functions that we’ve already written. The impl for Add is shown below; the others are similar.

use std::ops::{Add, Sub, Mul, Div};
impl Add for Expr {
    type Output = Expr;
    fn add(self, other: Expr) -> Expr {
        Expr::sum(self, other)
    }
}

Now, we can simplify complicated_expr to

Expr::product(1.0, 2.0) + Expr::product(3.0, 4.0)

We can’t just write 1.0 * 2.0 + 3.0 * 4.0, since Rust will simply evaluate that to a f64. In any case, additional simplication won’t really help readability, so let’s stop here (we could always try to write a macro, though. Maybe next time).

What’s Next

I’ve shown how to compose an AST for a calculator in Rust. I didn’t implement the DSL for Quotient, but it should be similar to implementing Add and Product. Of course, simply defining our data structure isn’t very interesting—we want to be able to do something with it! In the next post in the series, I’ll explore how to evaluate our expressions and turn the calculator into an actual calculator.