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

3. Attributes in Mathematica

Let us look at another example. Suppose we are given a list of n objects and want to construct all permutations of k objects from them. Again, we shall look for an algebraic program to realize this task. Let us consider an example where and the objects are . Then, as before, we see that we would get an answer by taking the terms of the expansion of

except that this time we do not want the multiplication to be commutative. Mathematica has the following function.

However it knows very few rules so if we are lazy we might just clear the Orderless attribute from Times and do something like this.

As before, this will not work for numbers instead of symbols. However, we could easily deal with this problem by mapping Hold on the list and then applying ReleaseHold at the end. Another problem is that we temporarily cleared the Orderless attribute of Times, which is generally not considered a very good idea and may produce unexpected results. In this case there were no such surprises. However, a general algebraic version of the code is both simpler and much more efficient.

Here we see a characteristic difference between Mathematica and specialized programs for dealing with abstract algebraic structures like rings, groups, and so on. Such programs tend to be object oriented and contain structures like groups or rings as some form of data types. Mathematica does not have objects or types that correspond to groups or rings, but contains functions and attributes that let one implement distributivity, commutativity, associativity, and so forth in a functional way. As a bonus, we can find uses for them in more general programming that are not strictly concerned with abstract algebraic structures.

As we have seen, distributivity is implemented in Mathematica through the function Distribute. How about the other fundamental algebraic notions, commutativity and associativity? These are essentially implemented as a so-called "Attributes" of functions Orderless and Flat. Understanding these attributes (as well as OneIdentity, which does not have a simple algebraic motivation) is the foundation of algebraic programming.

The attribute Orderless in a function is usually said to correspond to the mathematical notion of commutativity. This is indeed true, but one has to be careful with the interpretation of "correspond." Many functions that are "mathematically" commutative do not have the attribute Orderless. Such is the case with the logical function Or. From the mathematical viewpoint the function is commutative.

However, Orderless is not an attribute of Or.

We can see the effect this has on pattern matching.

The reason is not mathematical but has to do with performance and the way logical functions are used in programming, where one actually may wish to exploit the order of evaluation. The arguments of are evaluated in order, and True will be returned the moment one of them is found to be true. This may be a substantial timesaver. Also, consider the following example, which I owe to Daniel Lichtblau.

We can see that the following two evaluations will produce different behavior.

In other words: we have to pay attention to order when pattern matching even though || is in fact a commutative operation. This can be exploited in programming both to increase efficiency and to avoid generating unnecessary errors.

On the other hand, it is precisely the effect of the "algebraic" attributes Orderless, Flat, and OneIdentity on pattern matching that makes algebraic programming a surprisingly powerful technique.

Let us then consider these remaining algebraic attributes, Flat and OneIdentity, which together with the function Distribute and the Orderless attribute, play the central roles in algebraic programming.

The attribute Flat, corresponds to the mathematical property of associativity. Of course, as usual there is more to it than just that.

In order to understand the effect of the algebraic attributes on pattern matching we shall use the Mathematica function ReplaceList. Indeed, this function, together with Distribute and the algebraic attributes, is the most useful Mathematica command in algebraic programming.

Let us try using ReplaceList to understand the effect of the Flat attribute on pattern matching.

We start by taking a function f with no attributes and consider the following replacement rule.

Not surprisingly there was no match. Now give f the attribute Flat.

Let us repeat the previous attempt.

Note what happened. The function was now rewritten using "associativity" in two ways, as and . The rule was then applied but only at the top level. Now suppose we give f the attribute OneIdentity in addition to Flat.

You see that all expressions of the type f[x] were replaced just by . Of course this happens only when pattern matching. If you enter

you still get just f[x], not .

Indeed:

The useful function ReplaceAllList works like ReplaceList but also works on all subexpressions.

Let us now look at another example of algebraic programming. Of course, the most natural use of algebraic programming is solving algebra problems. So let us first consider an associativity problem.

Q: Suppose is a nonassociative noncommutative product of any number of elements. Find all the distinct ways of multiplying four elements using that would be equal if were associative.

We use a function f, to which we assign the attributes Flat and OneIdentity.

This sort of thing is in fact quite useful in various areas of mathematics. Later we shall give just one application of exactly this idea to solving a rather well-known puzzle that is frequently asked on symbolic algebra email lists.