> < ^ Date: Mon, 16 Jan 1995 12:23:00 -0700
> < ^ From: Frank Celler <frank.celler@math.rwth-aachen.de >
^ Subject: words in GAP 3.4

Dear Gap-Forum,

Derek Holt asked in his email message:

I want to do a long series of manipulations on words in abstract
generators. I can't decide whether to convert the words to lists of
integers or not.

First of all let me answer Derek's easier questions.

My queries are then
(i) Is there a better way of doing things which I don't know about?

No, there is no secret way (or better way) to deal with words at the moment.
The current implementation is not very satisfactory, i.e., the printing is
quite confusing and the representation as strings of handles instead of
integers makes functions such as 'MappedWord' rather slow.

big difference. In any case, I hope that free monoids will eventually be
supported in GAP, where inverse do not arise.

Yes, GAP 4.1 will, among other free/finitely presented structures, support
free/fp monoids as native data types and address the problems mentioned

Derek continues with a much harder question.

(ii) If not, can I put in plea for the future provision of a
"SubstitutedWord" function which operates on its argument in place,
rather than copying and returning a new word.

GAP 4.1 will have a different garbage collector which will deal more
efficiently with garbage created in processes repeatedly modifying an object
because the storage manager keeps track of recently created objects (i.e.,
it is generational).

However, both storage managers need to copy objects even when trying to
operate in place but changing their size in most cases, because there might
not be enough room to enlarge an object and so it has to be copied to a new
location. This can even be necessary when trying to *shrink* an object,
this is due to the way the storage manager keeps track of free space.

Another reason against modifying objects in place is that one has to copy
each object when calling a library function outside the algorithm because
other library functions might store their arguments as part of their
computation (e.g. a Schreier-Sims will store its arguments as part of the
strong generating set). Modifying objects after calling a library function
might corrupt data structures/results in subtle ways.

On the other hand GAP 4.1 will make it easier to write functions which will
modify words in place, so if one is working in a very closed environment and
one is able to control the problems mentioned above, it will be easier in GAP
4.1 to work in place.

But these are major changes which will not be available before GAP 4.1, which
we don't expect much before the end of this year, so my suggestion is to use
list instead. In GAP 4.1 there will be some more functions for list
manipulations (e.g. SubstituteList, PositionSublist). It is much easier to
integrate these functions into GAP 3.4 and the list interface will survive
the transition to GAP 4.1, while there will be some changes to the user
interface for words because of the problems and confusions created by the GAP
3.x word interface, e.g. the function 'AbstractGenerator' will finally be
replaced by the function 'FreeGroup' which is already used in GAP 3.4.

best wishes

> < [top]