Here we’re going to talk about the
eval function, which takes an array of tokens, and either returns the result of the calculation or an error. You may have noticed that I used Polish notation, e.g.,
+ 3 4 in this language, with the expressions delimited by parentheses. The reason for this is two-fold: First, I want to make this into a more full-featured Lisp interpreter one day, and second, for the same reason that Lisp is written in prefix notation – it makes things easy to parse. As wikipedia says:
When Polish notation is used as a syntax for mathematical expressions by programming language interpreters, it is readily parsed into abstract syntax trees and can, in fact, define a one-to-one representation for the same. Because of this, Lisp (see below) and related programming languages define their entire syntax in terms of prefix notation (and others use postfix notation).
We can think of an expression like
(* (+ 2 3) (+ 1 3)) as a tree, with the division operator at the root and
(+ 2 3) and
(+ 1 3) as sub-trees. One major difference in the language I’ve defined from Polish mathematical notation is that I allow an arbitrary number of operands to follow each operator, which is why I need parentheses.
As I mentioned in part one of this series, we can evaluate expressions like this using a Shift-Reduce parser. See part one for a quick example of how a shift reduce parser evaluates an expression.
Today I want to focus on the “reduce” operation. When we reduce part of the parse tree, we re-write it in a simpler form, and put it back where it was. When the whole expression is reduced to a single integer, we’re done. If we end up with something that can’t be reduced to a single integer when we reach the end of our array of tokens, we return an error.
Here’s the first two reduce functions:
Basically, these functions take an array of tokens, unpack them, and then fold them up into a single value, if possible. If this operation succeeds, we push it back onto the stack.
We have essentially the same code for subtraction and division, with one important difference. Can you spot it?
Basically, the difference is that the first item in a subtraction or division reduction is special. Let’s compare subtraction to addition to learn why. Here’s
(+ 2 3 1) as a sum:
sum([3,2,1]). No suppose we want to write the
(- 3 2 1) as a sum. We would need to write
sum([3,-2,-1]). The difference is that every item except the first has its sign changed. For division we would do exactly the same thing, except that for every item except the first we would change N to 1/N, and multiply them.
Let’s also look at this difference in terms of the call to
fold. Fold acts on an array and takes two arguments: an initial value and a function that can combine two elements in the array:
some_array.fold(initial, |last_result, next| /* combine last result and next */);
We need the initial value because we need to fold something up with the first value. (Note: many languages call this function
reduce. C# calls it
Aggregate().) Subtraction and division are more work because they don’t have identity values. For addition, we can use
0 as the initial value of fold, and we won’t throw off future addition. For multiplication, we can use
1. But for subtraction and division, we need to use the first item in the array itself, because there’s no value we can initialize a bunch of subtractions or divisions with that won’t affect the outcome.
Anyway, that’s how I built a basic calculator REPL in Rust. I plan to take a break from this project for a while and contribute to other people’s open source Rust. Hit me up at @willmurphyscode if you’d like me to help with one of yours 🙂
Till next time, happy learning!