Recursive Expressions
Interpreters, Iteration 16

User Stories

Handling recursive expressions takes more work in the front end of an interpreter than the back end. So you'll get to tackle a couple user stories all at once.

Every operator (so far) is left associative, so this will solve the associativity issue. The reason for limiting this to just one operator is to avoid the issue of precedence.

What if you want to override the default precedence or associativity?

Since precedence and associativity are handled by the front end, much of the features indicated by these stories are solved for you.

Acceptance Tests

Your Job

So what are you responsible to do for these stories? Look at why your CIAT tests are failing. To understand those error messages, you should first explore how the expressions get parsed.

Take 1 + 2 + 3. Expressions that need to be evaluated last will be at the top of an abstract parse tree (or a tree intermediate representation). In this case, adding 3 is done last after 1 + 2 is evaluated. As TIR code:

new OperatorETIR(
  new OperatorETIR(new IntegerETIR(1), ADD, new IntegerETIR(2)),
  ADD,
  new IntegerETIR(3)
  )

Consider 1 + 2 * 3. The front end parses this so that the 2 * 3 is done first (lower in the tree):

new OperatorETIR(
  new IntegerETIR(1),
  ADD,
  new OperatorETIR(new IntegerETIR(2), MULTIPLY, new IntegerETIR(3))
  )

Consider all the expressions you wrote in your CIAT tests. What TIRs are they turned into?

Now consider what your operator algorithms do: they pass the left and right children to the algorithm without processing them. That is, for 1 + 2 * 3, the addition algorithm is given the integer 1 and the expression 2*3. The addition algorithm is ready for integers and strings, but other operator expressions?!

So the addition algorithm should evaluate the left and right subtrees? Well, you have four methods in the addition algorithm which would have to do this. And you have several other operators, and they'll need to evaluate the subtrees, too.

Go to the source of the problem: the interpreter!

Mocks to the Rescue

Didn't know you needed rescuing, huh?

Consider this: you need to make sure that the interpreter evaluates the left and right subtrees of an operator expression. To test this properly with real TIR objects, you'd have to write assertions for all the different variations: different operators, different types of subexpressions, different depths of trees. I can't imagine doing this effectively with fewer than a dozen or more assertions, some with some really obnoxious TIRs!

So how does one test that the interpreter interprets the left and right subtrees? This is an issue for the test method in HobbesInterpreterTest. The mock objects for the subtrees are created, put into the OperatorETIR under test, and then are expected to be passed to the operator algorithm.

The operator algorithm's behavior is expected (anticipated) with this call:

EasyMock.expect(algorithm.compute(left, right)).andReturn(result);

It's now a little more complicated. You now need to expect the subtrees to be interpreted. Let's express this in English:

The left subtree should be interpreted, and that result should be used in evaluating the operator.

Now, in code:

EasyMock.expect(left.accept(myInterpreter)).andReturn(leftResult);

So much packed into one line of code!

Let's fix these things. The first thing to fix is the expectation on left. You've written the expectation as left.accept(myInterpreter); in the interpreter itself, left comes from the operator expression, and the interpreter is called this. Modulus some names: operator.getLeft().accept(this).

Whatever this returns should be used in the algorithm.compute() call (instead of the left subtree).

If some of your CIAT tests don't red bar, write some that do. The problem is that the right subtree needs to be evaluated.

Recap

Embrace the workflow you just went through.

First, you wrote high-level tests for more complex arithmetic computations. These tests told you what had to be fixed. (If you didn't get a front end from me, they would have complained about the front end, and then they would have complained about the operator algorithms.)

Second, you imagined (with the help of this writeup) what needed to happen: the left and right subtrees needed to be interpreted.

Third, the responsibility of interpretation belongs to HobbesInterpreter, so you went to HobbesInterpreterTest.

Fourth, what should operator interpretation really do? You encoded these expectations in the test. This allowed you to design a solution.

Fifth, you implemented the computations to get the tests to pass.