Hyperoperations Implementation in Python, Part 3. - Expressions

If you missed Part 1 or 2, see them here:

In this third installment, we'll build on top of the number system developed earlier.

If you are interested is following along with the source, you can see it here: https://github.com/casten/number/blob/main/Expression.py

The previous work allowed us to create numbers and arithmetic functions with nothing more than incrementing, walking along, and combining those operations to create higher orders of arithmetic functions. We started with a number representation based on individual units tracking the number, i.e. a unary representation. 1 was X, 2 was XX, 5 was XXXXX, and so forth.

With addition, subtraction, multiplication, division, and on up, the foundation for elementary counting math was established. The next question was where to go next? Some obvious candidates include negative numbers, fractions, decimals, etc. But I decided to head a slightly different direction for the time being.

Where we left off, we could chain operations and numbers together to perform calculations. An example might be:

zero.inc().inc().mul(zero.inc().inc().pow(zero.inc().inc().inc()))              

Which is not very readable. Using multiple statements and variables we can improve a little.

two = zero.inc().inc()
three = two.inc()
eight = two.pow(three)           

and finally

two.mul(eight)        

which would give 16. We basically have a very difficult to use calculator.

Expressions

The next part I wanted to implement was some support for basic expressions. This means introducing a few new concepts.

The first is variables. We already have numbers and operators. Now we'll add the ability to represent an unknown quantity with a choosable name. This would look something like:

three.mul(X).add(two)        

Of course we can't fully evaluate the expression until we know the value of X. Also, we don't want to use variables from the Python language. These are should be placeholders in a system that we can perform mathematical operations on with our new numbers. Previously we coded up a series of operations using our numbers and operations. But these were just executed by the Python and didn't have any persistent life after the statements were executed. What we need is a way to store our numbers and variables in a sequence of operations to create expressions. For example, say we want to represent the formula for the area of a triangle:

We multiply the height times the base and divide by two. So we want something like:

H.mul(B).div(2)        

We'll introduce the idea of an expression to hold these operations. Additionally we'll add abstractions for variables and operators. It will look something like:

Expression( Value, Operator, Value)        

So let's start with variables for H and B and connect them with a multiply.

Expression( Variable("H"), "mul", Variable("B"))        

But we've still got to divide by two. Let's add that in:

Expression( Variable("H"), "mul", Variable("B"), "div", Two)        

So this is an expression. And this would work. But having to put everything in one Expression statement is sort of a pain. I actually like the simplicity of this, but decided to use a bit of a different scheme to allow things to be constructed in groups, and then chained together. It looks like this (and I'll use the Python syntax here):

exp1 = Expression(Variable("H"))
exp2 = Expression(Variable("B"), Operation("div", Two))        

Which we combine together to with:

tri_area = exp1.chain(Operation("mul"), exp2)        

Which would create the expression:

Expression(Variable("H"), Operation("mul", Expression (Variable("B"), Operation("div", Two)))        

So an Expression consists of a (Value, Operation) with the Operation optional. An Operation is an (Operator, Expression). Which starts the cycle again.

It makes a chain that eventually gets evaluated from left to right. Also, the Value can be either a Number, like Two, or a Variable, like X.

It seems like a lot of pain and doesn't look much different than our previous calculations. But since we have variables now, we can take our built up Expression and plug in values. Plugging in values looks like:

filled_in = tri_area.subst(Variable("H"), Two).subst(Variable("B"), Three)         

I also added in helper function that prints out the expressions in more normal form. Doing so with the Expression filled_in would show:

filled_in.repr_standard()

->   2 * 3 / 2            

To get the final answer, you call simplify:

answer = filled_in.simplify() 
answer.repr_standard()
->  3        

Algebra Type Stuff: Numbers

In addition to performing operations on Number values, the simplify() function can perform another trick. But first let's look at an Expression chain of just numbers:

Expression( one, Operation( "add" , Expression( two, Operation ("mul", Expression (three))))        

The way that simplification of numbers occurs is the following:

We start at the beginning and look at the current type. In this case, it is a number one. We then look to see if there is an operation. If yes, we look at the type of the operand. If we see it is also a number, we can apply the operation and collapse the two Expressions into a result expression. Then we tack on the remainder. Then we start again from the beginning. (We should actually start where we left off, but that's a pretty small optimization.) We repeat the sequence until we get to the end. It should look like:

1. We find one, add and then two. They are both numbers, so we one.add(two). We get Three.
2. Replace one.add(two) with three and get: three.mul(three)
3. We start again and get nine. Now the expression is just the value nine.

Algebra Type Stuff: Variables

We can also perform another type of simplification if we encounter two variables of the same type. For example:

X.add(X).mul(3)        

If we see a variable, an operation and another of the same variable, we can consolidate them and reduce the variable count. However, we are trading one operation for another and we do not have fewer expressions. Take the example from above:

X.add(X) is the same as X.mul(2), so we can do that replacement:

X.add(X).mul(3) = X.mul(2).mul(3)         

But then in this case we luck out and have two numbers next to each other. So we can reduce further:

X.mul(2).mul(3) = X.mul(6)        

Let's do a quick sanity check on this:

let X = 4,  4.add(4).mul(3) = 4+4*3 = 24        

For the reduced version we have

X.mul(6) 
  or 
4.mul(6) = 24!        

One more check for to make sure we didn't get lucky:

let X = 7, 7.add(7).mul(3) = 7+7*3 = 42
7.mul(6) = 42         

We had two of the same variable separated by addition which were promoted to multiplication by two. Which of course makes sense. We had two of them.

If we have two of the same multiplied, then those become squared or to the power of two. Likewise for power and tetration.

For the decremental operators (sub, div, log), the replacement is a collapse to the identities for each. So X - X = 0. The Expression becomes zero. Division and log both become one. In these cases not only do we have one fewer expression, but the variables disappear as well leaving just numbers. Very nice!

To see these in action, have a look at the source. The unit tests show most of the described functions in action.

https://github.com/casten/number/blob/main/Expression.py#L270

For the next article, see: