A Rule-based Revolution

Organizing Mathematical Knowledge as a Rule-based Decision Tree

Albert D. Rich, Applied Logician
Hawaii Island, July 2015

I am the author of 3 implementations of the muLisp artificial intelligence development system, and coauthor of the muMath and Derive computer algebra systems. However, I am convinced my current research will be by far my most important and enduring contribution to the fields of math and computer science.

Since the beginning of recorded history, mathematicians have been amassing mathematical truths at an ever greater rate and into ever more esoteric realms. However, this vast amount of knowledge has not been systematically organized so the precise formula required to solve a particular problem can easily be found. It's like leaves scattered on a lawn, rather than organized into a heavily branched tree with each leaf attached to the appropriate limb.

It's Feasible

I am convinced much of mathematical knowledge can be organized into a rule-based decision tree that is unique and optimal. Others have proposed similar such grandiose programs, but the rule-based paradigm actually makes it possible to accomplish it. And this is not just armchair speculation.

Over my almost 40-year career implementing computer algebra systems, I am driven to the realization that rule-based systems are the optimal way to get optimal results. This is not limited to my current focus: indefinite integration. muMath and Derive are general purpose programs able to solve a broad range of problems. Throughout their development these systems gained knowledge by the addition of new rules and the generalization of existing ones.

David Stoutemyer and I began the design and implementation of muMath in the late 1970s. From the earliest versions, despite being limited to a 64 kilobyte address space, the system provided a mechanism for assigning rules to the property lists of functions and operators. When an expression was being evaluated, the property list of its top-level function or operator was searched to see if there was a rule specifically for the expression's second-level function or operator. If so, the rule was applied and the process repeated recursively until no more rules applied.

Although crude by today's standards, this two-level pattern matching mechanism was used extensively in the implementation of muMath. Also its modularity and simplicity allowed users to add their own rules to the system. Derive was also heavily dependent on rules to simplify, solve and integrate expressions; but the rules were "hard wired" in programming code. Although more powerful than muMath, Derive was often criticized for not allowing users to define their own rules for built-in functions and operators.

Computer hardware and software are highly ephemeral, so the mathematical knowledge in muMath and Derive will soon be lost. After development of Derive was terminated prematurely in 2005, I was determined to find a way to pass on the accumulated knowledge in such systems that would survive changing technology.

To that end, I began implementing a Rule-Based Integrator, nicknamed Rubi. Currently it consists of over 6000 integration rules organized into a decision tree that uniquely determines the appropriate rule to apply to a given integrand. Stored as a simple directed graph, this decision tree is what distinguishes Rubi from the program code used by its predecessors to select rules.

Indefinite integration accounts for only a tiny fraction of all mathematical knowledge. However, based on my experience implementing muMath and Derive, I see no reason why much of the rest of mathematics cannot be organized as a rule-based decision tree as well. Certainly much of analysis including equation solving, expression simplification, differentiation, summation, limits, etc. can be automated using this paradigm.

It's Desirable

So assuming a discipline of mathematics can be reduced to a rule-based decision tree, is it worth the considerable effort required? My experience implementing Rubi clearly indicates the answer is a resounding yes! The benefits include:

All the integration rules, test suite problems and results demonstrating the above benefits are freely available on Rubi's website.

It's Real

Finally it should be noted that Rubi is an ever improving, but imperfect, model of the actual integration decision tree existing in some Platonic sense. In the same way, software simulating a hurricane is just an imperfect model of the actual hurricane blowing in the physical world. So Rubi may be just a model, but she's a darn good-looking one.

Not only does an optimal integration decision tree exist, it is unique. Time and again, in order to achieve optimal antiderivatives for integrands of a given form, I was forced to restructure Rubi's decision tree and/or discover new rules. Often this repetitive process severely tested my deeply held belief that an optimal set of rules for integrating expressions must exist. But eventually the process always did converge, leaving me no choice in the design of the decision tree.

Rubi provides proof-of-concept of the utility of organizing mathematical knowledge in the form of a rule-based decision tree. Hopefully it will convince others in the math and computer science communities to join the rule-based revolution, and explore whether it is applicable to their field of interest as well.

The above is a preprint of an article to appear in the 25th anniversary issue of the Derive Newsletter published by the Derive & CAS-TI User Group.

Rubi home