# Creating a Calculator in Rust, Part 1

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 `f64`

s 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 `Sum`

s, 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.