Number (part 2)

Following on from my previous article on Number, an open-source numeric library in Scala, I will discuss the mechanism of lazy expression evaluation. Before reading this, you might want to take a look at Composable Scala Matchers because the expression matchers are implemented using that library.

The trouble with eager evaluation of expressions is that we can easily lose precision when it could be avoided. For example, suppose we want to know the value of (√3+1)(√3–1). If we do this using plain numbers, for example with the following code:

val root3 = Number(3).sqrt
val two = (root3 add one) multiply (root3 add negate(one))

The rendering of root3 and two will be 1.7320508075688772[27] and 1.9999999999999996(63), respectively. Of course, that second number is recognizably two if we test its sameness with two(see Number, part 1 for the same method).

import Field._
val ok = implicitly[Fuzzy[Field]].same(0.8)(two, Number.two)

Nevertheless, it is slightly disconcerting to see all of those 9s even though, as Mathologer tells us, 9.999… really is equal to 10.

So, how do we get the answer to be just two? We use expressions (lazy evaluation of numeric values):

val root3= Expression(3).sqrt
val root3PlusOne = root3 plus Expression.one
val root3MinusOne = root3 plus Expression(negate(one))

// Note the use of an implicit converter from Expression to Number.
val two: Number = root3PlusOne * root3MinusOne

The intermediate results (root3PlusOne and root3MinusOne) are rendered, when implicitly converted to Number, as 2.7320508075688770(33) and 0.7320508075688772(16) respectively. But when we convert two to a String, we see exactly what we should: 2.

How does that little bit of magic happen? It’s through the use of ExpressionMatchers, one of the classes of Number. It starts with the materialize method of Expression which results in a Field (the super-trait of Number and Complex). This in turn invokes a method simplifyAndEvaluate which is defined as part of ExpressionMatchers. The logic is that, if it matches on a simplification of the expression, then it evaluates that simplification (hopefully as an exact number). Otherwise, it just evaluates the expression, which may be a fuzzy number.

Let’s take a look at the expression tree for the expression above:

Expression Tree for (√3+1)(√3–1)

The simplifier method has different logic for the three types of expression: AtomicExpression (a leaf nodes: light yellow in the picture), BiFunction (a dyadic function: light green in the picture) and Function (a monadic function: light blue in the picture). The general idea is that any exact bifunction expression, for example 1 + 2, will be simplified by replacing it with its exact value of 3 (an AtomicExpression). More complex expressions can also be simplified— perhaps by collecting terms from cousin nodes in the expression tree. Trivial substitutions, such as x for x * 1, or 0 for x – x, are also made (where x is any expression). Any sub-expression that is simplified, albeit not to an exact expression, is passed through simplifier again in case further simplifications can be made. Currently, the logic only goes two levels deep (sufficient for our root3 exercise above), unless a series of operations with the same operator (for example Sum or Product) are found, in which case these are all grouped together and simplified if possible.

Monadic functions, for example ln e^x, can also be simplified, in this case to the expression x.

Basically, the rules of algebra are followed in this simplification process. When all other simplifications have been made, it can be productive to expand all terms to the form a + b + c… This is what happens in the case of (√3+1)(√3–1). The expression expands to √3 √3 + √3 –√3 –1. Regardless of the order of terms in this expansion, √3 –√3 will be replaced by 0, then 0 –1 will be replaced by –1. √3 √3 is replaced by 3 and 3 –1 is replaced by 2.

Each of the matchers takes as input an instance of some type, T, and returns a MatchResult[R] where T and R are parametric types. For many of the matchers, T or R or both evaluate to Expression. MatchResult[R] has two usual cases: Match[R] and Miss[String, T]. Additionally, there’s an Error case. It’s important that only actual matches are passed into simplifier again, otherwise and infinite loop (and stack overflow) will occur.

There are a few other little conveniences here and there like the Expression.apply method which takes a Field or an Int and yields an appropriate constant expression. There is also an implicit converter (in the companion object of Number) from Expression to Number, which invokes materializer. And there is ExpressionOps, an implicit class which allows an Expression to combine, using the operators +, *, etc., with other expressions, as well as Fields and Ints.

It is also possible to parse an expression from a character String. Such an expression can be represented via infix notation (using the Expression.parse method) or reverse Polish notation (using the Mill.parse method). Mill is an implementation of a stack of Expressions and operators. Each of these parsers is somewhat limited as of V1.0.10.

In part 3, I will talk about the details of the numeric calculations and, in particular, the design which allows for some irrational and transcendental numbers to be represented exactly.