Title: Algebra in Smalltalk: EfiQuations

by Thomas Gagné

EfiQuations is a parcel that can be loaded into a VisualWorks Smalltalk image that provides a mechanism for manipulating algebraic expressions in Smalltalk. Its practical use is for performing arithmetic on weight, measurements, and currencies.

To play with it, download both
    eFinNet-Equations.pcl and
    eFinNet-Equations.pst and optionally
    eFinNet-Equations-SUnit.pcl and
    eFinNet-Equations-SUnit.pst

Why a parser isn't satisfactory

Why create a parser when Smalltalk already has one? Besides, The problem isn't in parsing algebra, it's being able to express it and use its results in normal Smalltalk code. In my supply-chain application there existed multiple places where I needed to calculate values using mixed units--but those units were related to each other. 100lb = 1LB. I didn't want to hardcode the units, their equivalences, or do anything that didn't look like Smalltalk.

If I needed to add $US100 + $CAN100, just like I do when I put each bill into my wallet, I wanted the Smalltalk code to look just as simple:

wallet := #US * 100.
wallet := wallet + #CAN * 100

In the code sample above it's a bit too obvious that I have multiple currencies. When parsing XML it isn't so obvious. 

<wallet>
    <bill denomination="100" currency="CAN"/>
    <bill denomination="100" currency="US"/>
</wallet>

Now, collecting these values into my Smalltalk wallet is relatively simple, using #inject:into: while iterating through wallet's child elements, and using the normal Smalltalk binary operators +, -, *, /, and an additional **.

Explain why using dedicated weights and measurement libraries aren't satisfactory.

Date Changes
February 23-25, 2004

Fixed problem where the expression 0.65s * #US * 100 would throw exception. It now properly resolves to 65.00US. Also, got rid of test for Gemstone.

I got rid off the symbolDictionary in all the expression classes. I decided that solving expresions or converting symbols should be a function of an EfiSymbolDictionary instead of the expression itself. Besides, it was remarkably difficult to make sure the SymbolDictionary perculated through the expression as it got more complex (other operations were done to it). Additionally, I had no model of what to do when two expression with different symbol dictionaries were combined.

isEfiVariable and isEfiValue are both added to Object's instance methods. This makes it easier to deal with mixed expressions.

(#x * #x * #x) now properly evaluates to x^3. An EfiRaised multiplied by its base increments its exponent by one.

Added SUnit tests to make sure nothing breaks when I fix something else or add new rules. It's amazing how quickly the parcel can be tested and new features added without screwing things up.

Added more documentation. See both the Parcel comments and the comments inside EfiExpression.

The parcel no longer requires eFinNet-Base or eFinNet-KernelPatches. The objects EfiExpression, EfiExpressionHolder, EfiSymbol, and EfiSymbolDictionary no longer subclass EfiObject. eFinNet-KernelPatches' FixedPoint's #printOn: (removing trailing exponent $s) was moved to this parcel.
February 9, 2004

EfiRaised (exponents) can now handle multiplications. The following expressions should work.

For any rational number a, and for whole values of m and n, a^m * a^n = a^m+n

(#a**#n) * (#a**#m).
(#a**20) * (#a**30).
(#a**#n) * (#a**30).
(#a**20) * (#a**#m).
(#a**#n) + 3.
(#a**#n) + 3 / (#x - #y).
April 23, 2003
  • 3(x + 5) and 3(x - 5) now properly distribute as (3x + 15) and (3x - 15)
  • Fixed bug in EfiProduct's #- which accidentally did addition instead of subtraction
  • Fixed bug in ByteSymbol which tried to reverse subtractions
  • Fixed bug in ByteSymbol which tried to reverse divisions
April 21, 2003
  • 2x + #x now properly evaluates to 3x instead of 2x + x
  • 2x - #x now properly evaluates to x instead of 1x
  • #x + #x + #x is now 3x instead of 2x + x
  • 3 / (#x + 1) * (#x + 1) now evalutes to 3 instead of throwing an exception
  • (#x + 1) + (#x + 1) now evalutes to 2(x+1)

Introduction

I've always wanted to add apples and oranges, just to prove it can be done. After some thought I realized it's done all the time. If I rename apples x and oranges y then x + y is simply the expression x + y.

Multiplication is even easier in algebra. x * y is usually expressed simply as xy. There's no need to know what x and y are, since there just variables. But what if we renamed the variables to something recognizable, but meaningless all the same. In this case well use 100 and USD. 100 * USD = 100USD. Many people will assume I'm talking about US Dollars, and that I've one hundred of them. But actually all I have is the value 100 multiplied by the variable USD.

The attraction to doing this in Smalltalk is the ability to change the behavior of classes. In Smalltalk the String class can be taught multiplication so that it would be possible to multiple oranges with numbers and add them to apples.

(2 * #orange) + (3 * #apple) "2orange+3apple"

Makes sense, doesn't it? If two oranges and three apples were placed into a grocery bag your four year old can tell you there's two oranges and three apples but most computer types (and other debaters with limited vision) would tell you, "you can't add apples and oranges." Apparently their coexistence in the bag can't penetrate their reality.

One of the benefits of using algebra in programs is the ability for end-users to interpret the results themseles without them having any special meaning inside the program. Something with special meaning means something with extra programming and the whole point of programming is to avoid work. As and example the folloing combinations of numbers of variables simply algebraic expressions with meanings to adults that supercede basic math:

100USD one hundred US dollars
160CAN one hundred sixty Canadian dollars
2TBS two tablespoons
2.54cm = 1in 2.54 centimeters is equal to 1 inch
1doz 12 of something. Usually eggs or roses.

In each example above, the expression on the left is interpreted by the reader as having the meaning on the right. In each case (except the equivalence example) all the program knows about is a product, the result of multiplying the value on the left with the value on the right. When the two values can't be simplified then the expression is considered simplified (did I say this would be complicated?).

Why Smalltalk?

First, it was the language I was using for the project I needed some algebra for. Second, it's a great place to do something like this because Strings and other object normally not associated with math can be taught to do math.

Getting the basics right

The basic classes

In the simple expression "x + y" there are three objects. 'x', 'y', and '+'. In this system, x and y are both operands and + is an operator. The operator stores a left and a right operand. The result of evaluating #x + #y is an EfiAddition which prints itself as x+y.

To make this work EfiQuations extends the ByteSymbol with the methods +, -, *, and /, as well as a method to convert a ByteSymbol to an EfiExpression. This fundamental modification to the class allows symbols to participate fully in mathematical expressions.

Addition and subtraction

Copyright © 2003, Thomas Gagné