[Edu-sig] computer algebra

[Guido van Rossum]

On Wed, Dec 10, 2008 at 6:47 PM, kirby urner <kirby.urner at gmail.com> wrote:
> So I've been yakking with Ian (tizard.stanford.edu) re the new
> fractions.py, installed in Standard Library per 2.6, saw it demoed at
> a recent user group meeting (PPUG).
>
> Python's __div__ is similar to Mathematica's computer algebra notion
> of division in that you're free to divide any type by any type,
> providing this makes any algebraic sense, using a kind of liberal duck
> typing.
>
> What I mean by that is __div__ by itself doesn't pre-specify anything,
> so if there's a meaningful way to deploy the division operator between
> arguments A, B, then go ahead and do it, write you code accordingly.

Or unmeaningful! Unlike (I presume) Mathematica, Python doesn't mind
if you define a/b as multiplication. Your users might mind though. :-)

> In Java, we could write __div__ in all different ways depending on
> valid type permutations (not that Java has operator overloading, just
> stricter typing at write time means you've gotta post "guards at the
> gate" in your methods).  Python, with late binding, duck typing, won't
> post guards, but you'll still need to write algorithms capable of
> sorting out the possibilities.  Maybe the user throws you a matrix?
> Has an inverse.  OK, so __div__ makes some sense...
>
> fractions.py in contrast, implements the narrow Q type, the rational
> number, defined as p / q where p, q are members of the set integers.
>
> One could imagine a Fraction class that eats two complex numbers, or
> two Decimals.  Computer algebra attaches meaning here, as in both sets
> we're able to define a multiplicative identity such that A / B means A
> * B**(-1) i.e. A * pow(B, -1) i.e. A * (1/B).

It's not so easy though. The specific purpose of the Fraction class is
to always reduce the fraction to a canonical representation using the
GCD algorithm (e.g. 15/12 becomes 5/4), which only applies to
integers.

> So the results of this operation, Fraction(A, B), might be some object
> holding the Decimal or Complex result.  In generic algebra,
> everything's a duck, although conversion between types is possible
> (yes, that sounds nonsensical).
>
> fractions.Fraction, on the other hand, barfs on anything but integers,
> isn't trying to be all divisions to all possible types, isn't
> pretending this is Mathematica or a generic CAS.

Fortunately Python supports a way of overloading binary operators
where it is sufficient if *one* of the operands knows how to deal with
the other. So Fraction(3, 4) * 2j happily returns 1.5j. You don't have
to teach Fraction about Matrix if you can teach Matrix about Fraction.

> Note that I'm not criticizing fractions.py in any way, am so far quite
> happy with it.  I'm simply drawing attention to some fine points.
>
> Related:
>
> When I went to all the trouble to compose two functions, f and g,
> using __mul__, I'd get comments like:  but the "open oh" (another
> symbol) is the "composition operator" i.e. "you're only using *
> because ASCII doesn't include the 'open oh'".
>
> However, I was making a different point:  that in group theory math
> texts, we're proud to use "regular" multiplication and division
> operators for such operations as "compositions of functions" because
> we're thinking __mul__ and __div__ have that generic meaning -- we
> neither need, nor want, the proliferation of symbols the "open oh"
> people think we must need.

There are different schools of thought about this actually. I don't
think pride comes into it. Inventing and using specialized symbols is
often useful in math because it provides more context. If you write "f
* g" the reader would need to know in advance that f and g are
functions or else they wouldn't know what was meant. But if you write
"f o g" then the reader can *infer* that f and g are functions. Python
happens to use the former (overloading based on argument types);
Python's predecessor ABC used the latter (type inferencing based on
operators). Neither is necessarily better than the other.

There are also fields of mathematics where both are used, with a
different meaning; e.g. f o g would mean functional composition while
f * g could mean the function you get by multiplying f(x) and g(x). In
Python:

def open_oh(f, g):
  return lambda x: f(g(x))

def star(f, g):
  return lambda x: f(x) * g(x)

> Note that by "open oh" I'm not talking about "big oh", a different
> notation that I don't think is redundant, agree with Knuth that if
> your calculus book doesn't include it, you're probably in one of those
> computer illiterate schools (ETS slave, whatever).

I think that comment is a little out of line. BTW big Oh is not part
of calculus, it's part of complexity theory, a totally different field
(more relevant to computers than calculus though).

-- 
--Guido van Rossum (home page: http://www.python.org/~guido/)