Volume 9, Issue 2

Articles
In and Out
Trott's Corner
New Products
New Publications
Calendar
News Bulletins
New Resources
Classifieds

Editorial Policy
Staff
Submissions
Subscriptions
Back Issues
Contact Information

Algebraic Programming in Mathematica

1. What is Algebraic Programming?

I first came across the expression "the algebraic method in programming" (or algebraic programming for short) in the context of Mathematica in the book by Ilan Vardi [1]. By algebraic programming, Vardi meant solving programming problems by using concepts of abstract algebra, such as distributivity, commutativity, and associativity. Vardi gives some examples of algebraic programming. One of these is a solution to the following problem.

Q: Write a program that will produce all possible subsets of a given set (list) of symbols, for example .

Vardi makes the observation that the answer to the problem is contained in the following algebraic formula.

This formula depends only on the algebraic property of distributivity of multiplication and the existence of a unit. Indeed, Mathematica makes it possible to solve the problem directly by converting the last formula.

We can write a function that will apply this method to any set of symbols. Note, however, that this program will not work if we use a list of numbers!

This attractive method can be used to produce unexpected solutions to surprisingly many problems. However, this is not actually what Vardi meant by "algebraic programming." In fact one might call this approach "naive algebraic programming." It is naive because it makes use of specific algebraic functions rather than the general algebraic principles on which they are built. Here is a "sophisticated" algebraic program due to Vardi that achieves the same result.

Not surprisingly, the second program not only works with symbols and numbers, but is also considerably faster than the first.

The main reason is that the second program is more "abstract," in the sense that it makes fewer assumptions and has to perform fewer checks. Essentially it applies the principle of "distributivity" in the widest possible sense. In general, algebraic computations using functions like Times, Expand, and so forth involve extensive sorting of intermediate expressions before they are brought to a canonical form. From the point of view of efficiency, it is much better to operate with lists because no evaluation or canonicalization ever happens, and lists can contain anything.