> < ^ Date: Fri, 21 Apr 1995 11:34:00 +0100 (WET)
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: Survey: Substitution in GAP, etc.
Lewis McCarthy wrote in his e-mail message of 1995/04/15

As part of my Master's research (in Computer Science), I have been
studying ways of performing substitutions of one term for another in a
GAP expression. Having had some experience with Maple, I was initially
surprised to discover that GAP provides no analogue of the "subs"
function in Maple.

I think I now understand the reasons no such facility exists.

Let me clarify it for the sake of those who have no experience with
Maple.

In Maple there is basically just one type of objects: expressions.
That is the objects one deals with in Maple consist of numbers, symbols,
function applications, and are composed through algebraic operations
such as addition, multiplication. Those objects correspond very
closely to the written representation.

In this context it makes sense to ``substitute'' one term by another.
Note however, that this process is a purely lexical substitution.
This leads to behaviour that is sometimes surprising.
For example suppose you have a polynomial <f> in Z[x].
To replace <x> with <y>+1 you can simply write 'subs( x=y+1, f )'.
On the other hand suppose that <f> is a multiple of <x>^2.
To replace <x>^2 with <y>+1 you *cannot* write 'subs( x^2=y+1, f )',
because Maple will not recognize that <x>^4 is (<x>^2)^2
(you could write 'subs( x=(y+1)^(1/2), f )').

In GAP on the other hand there are many different types of objects:
permutations, matrices, elements of cyclotomic fields, and so on.
Those objects are not composed from simpler objects (from GAP's point of
view). And the correspondence to the written representation is sometimes
not that easy.

In this context it makes no sense to ``substitute''. At least not in the
Maple sense. A substitution is basically something that happens to the
(written) representation. This is fine in Maple where the distance
between the written representation and the actual object is small. But
in GAP this distance is sometimes rather large.

Our philosophy is to view such a transformation as something that happens
to the object, not to its representation. And we think that the correct
mathematical concept for this are homomorphisms.

Lewis continued

In designing some limited substitution facilities, however, I've
envisioned some kinds of substitutions which may well be feasible, but
not actually useful to anyone. So (getting to the point of this message
at last !) I would like to hear from other users of GAP, and other
symbolic math systems, about this question. What kinds of substitutions
do you find useful in GAP (et al.) ? What kinds of substitutions are
possible but not helpful (or even meaningful) to you in other systems ?
Please describe cases of substitutions you would like to perform in GAP,
and the approach you've taken to handling them.

I would like to add the following questions. Can you view your problem
in terms of homomorphisms? What homomorphisms would you need to solve
your problem?

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]