%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W preface.tex GAP documentation Joachim Neubueser
%%
%H @(#)$Id: preface.tex,v 4.35 2002/05/02 07:50:41 sal Exp $
%%
%Y Copyright (C) 1997, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
%%
%% This file contains the preface of the GAP manual.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Preface}
Welcome to {\GAP}. This preface serves not only to introduce this
manual, ``the {\GAP} Tutorial'', but also as an introduction to the
system as a whole, and in particular to version 4 release 3 (or {\GAP}
4.3 for short).
{\GAP} stands for *Groups, Algorithms and Programming*. The name was
chosen to reflect the aim of the system, which is introduced in this
tutorial manual. Since that choice, the system has become somewhat
broader, and you will also find information about algorithms and
programming for other algebraic structures, such as semigroups and
algebras.
There are four further manuals in addition to this one: the ``Reference
Manual'' containing detailed documentation of the mathematical
functionality of {\GAP}; ``Extending GAP'' containing some tutorial
material on various aspects of {\GAP} programming; ``Programming in
GAP 4'' containing detailed documentation of various aspects of the
system of interest mainly to programmers; and ``New Features for
Developers'' containing details of some newly introduced features
which we may wish to change in a future release and so do not want to
include in the main reference manual. Some of the functionality
of the system and a number of contributed extensions are provided as
``{\GAP} packages'' and each of these has its own manual. This
preface, however, serves as an introduction to the whole system.
Subsequent sections of this preface explain the structure of the
system and the arrangements for the attribution of credit for
authorship and maintenance of the system; acknowledge those who have
made particular contributions to this and previous releases and
outline the changes from earlier versions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The GAP System}
{\GAP} is a *free*, *open* and *extensible* software package for
computation in discrete abstract algebra. The terms ``free'' and
``open'' describe the conditions under which the system is distributed --
in brief, it is *free of charge* (except possibly for the immediate costs
of delivering it to you), you are *free to pass it on* within certain
limits, and all of the workings of the system are *open for you to
examine and change*. Details of these conditions can be found
%display{tex}
in the Copyright Notice of the previous page.
%display{nontex}
%in "ref:Copyright".
%enddisplay
The system is ``extensible'' in that you can write your own programs in
the {\GAP} language, and use them in just the same way as the programs
which form part of the system (the ``library''). Indeed, we actively
support the contribution, refereeing and distribution of extensions to
the system, in the form of ``{\GAP} packages''. Further details of this
can be found in chapter "ref:GAP Packages" in the Reference Manual, and
on our World Wide Web site.
Development of {\GAP} began at Lehrstuhl D f\accent127ur Mathematik,
RWTH-Aachen, under the leadership of Prof.~Joachim Neub\accent127user
in 1985. Version 2.4 was released in 1988 and version 3.1 in 1992.
The final full release of {\GAP} 3, version 3.4, was made in 1994. In
1997, Prof.~Neub\accent127user retired, and overall coordination of
{\GAP} development, now very much an international effort, was
transferred to St Andrews. A complete internal redesign and almost
complete rewrite of the system, which was already in progress in
Aachen, was completed and following five, increasingly usable,
beta-test releases, version 4.1, released July 1999, was the first
version of the rewritten system to be released without any restriction
for general use. Version 4.2 followed in spring 2000 and, this
version, {\GAP} 4.3 is being released in May 2002.
More information on the motivation and development of {\GAP} to date,
can be found on our Web pages in a section entitled ``Release history
and Prefaces''.
For those readers who have used an earlier version of {\GAP}, an
overview of the changes from {\GAP}~4.2, and a brief summary of
changes from {\GAP 3} is given in section "Changes from Earlier
Versions" below.
The system that you are getting now consists of a ``core system'' and
a number of packages. The core system consists of four main parts.
\beginlist%ordered
\item{1.}
A *kernel*, written in C, which provides the user with
\itemitem{--}%unordered
automatic dynamic storage management, which the user needn't bother
about in his programming;
\itemitem{--}
a set of time-critical basic functions, e.g. ``arithmetic'',
operations for integers, finite fields, permutations and words, as
well as natural operations for lists and records;
\itemitem{--}
an interpreter for the {\GAP} language, an untyped
imperative programming language with functions as first class objects
and some extra built-in data types such as permutations and finite
field elements. The language supports a form of object-oriented
programming, similar to that supported by languages like C++ and
Java but with some important differences.
\itemitem{--}
a small set of system functions allowing the {\GAP} programmer to handle
files and execute external programs in a uniform way, regardless of
the particular operating system in use.
\itemitem{--}
a set of programming tools for testing, debugging, and timing
algorithms.
\itemitem{--}
a ``read-eval-view'' style user interface.
\item{2.}
A much larger *library of {\GAP} functions* that
implement algebraic and other algorithms. Since this is written
entirely in the {\GAP} language, the {\GAP} language is both the
main implementation language and the user language of the system.
Therefore the user can as easily as the original programmers
investigate and vary algorithms of the library and add new ones to
it, first for own use and eventually for the benefit of all {\GAP}
users.
\item{3.}
A *library of group theoretical data* which contains
various libraries of groups, including the library of small groups
(containing all groups of order at most 2000, except those of order
1024) and others. Large libraries of ordinary and Brauer character
tables and Tables of Marks are included as packages.
\item{4.}
The *documentation*. This is available as on-line help, as
printable files in various formats and as HTML for viewing
with a Web browser.
\endlist
Also included with the core system are some test files and a few
small utilities which we hope you will find useful.
*{\GAP} packages* are self-contained extensions to the core system. A
package contains {\GAP} code and its own documentation and may also
contain data files or external programs to which the {\GAP} code
provides an interface. These packages may be loaded into {\GAP} using
the `RequirePackage' command, and both the package and its
documentation are then available just as if they were parts of the
core system. Some packages may be loaded automatically, when {\GAP} is
started, if they are present. Some packages, because they depend on
external programs, may only be available on the operating systems
where those programs are available (usually UNIX). You should note
that, while the packages included with this release are the most
recent versions ready for release at this time, new packages and new
versions may be released at any time and can be easily installed in
your copy of {\GAP}.
With {\GAP} 4.3, there are two packages (the library of ordinary and
Brauer character tables, and the library of tables of marks) which
contain functionality developed from parts of the {\GAP} 4.2 core
system. These have been moved into packages for ease of maintenance
and to allow new versions to be released independently of new releases
of the core system. The library of small groups should also be
regarded as a package, although it does not currently use the standard
`RequirePackage' mechanism. Other packages (included in separate
archives for download) contain functionality which has never been part
of the core system.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Authorship and Maintenance}
Previous versions of {\GAP} have simply included the increasingly long
list of all of the authors of the system with no indication as to who
contributed what. In {\GAP} 4.3 we have introduced a new concept:
*modules*, to allow us to report the authorship of the system in more
detail. A module is a part of {\GAP} which provides identifiable
functionality and has reasonably clean interfaces with the rest of the
system (usually it consists of separate files). Each module has its
own lists of authors and maintainers, which are not necessarily the
same. A preliminary list of modules and their attributions appears in
this manual. Note that we are still in the process of identifying
modules within the system, so large parts of the system do not yet
fall into any module. Since also we all collaborate closely in
designing, developing and debugging the system, it should not be
assumed that the list of modules in this manual represents all of
everyone's contribution, or that it lists everyone who made any
contribution at all to each module.
All {\GAP} packages are also considered to be modules and have their
own authors and maintainers. It should however be noted that some
packages provide interfaces between {\GAP} and an external program, a
copy of which is included for convenience, and that, in these cases,
we do not claim that the module authors or maintainers wrote, or
maintain, this external program. Similarly, some modules and packages
include large data libraries that may have been computed by many
people. We try to make clear in each case what credit is attributable
to whom.
We have, for some time, operated a refereeing system for contributed
packages, both to ensure the quality of the software we distribute,
and to provide recognition for the authors. We now consider this to be
a refereeing system for modules, and we would note, in particular
that, although it does not use the standard package interface, the
library of small groups has been refereed and accepted on exactly the
same basis as the accepted packages.
We also include with this distribution, in a separate archive, a
number of packages which have not (yet) gone through our refereeing
process. Some may be accepted in the future, in other cases the
authors have chosen not to submit them. More information can be found
on our World Wide Web site, see section "Further Information about
GAP".
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Acknowledgements}
Very many people have worked on, and contributed to, {\GAP} over the
years since its inception. On our Web site you will find the prefaces
to the previous releases, each of which acknowledges people who have
made special contributions to that release. Even so, it is appropriate
to mention here Joachim Neub\accent127user whose vision of a free,
open and extensible system for computational algebra inspired {\GAP}
in the first place, and Martin Sch\accent127onert, who was the
technical architect of {\GAP} 3 and {\GAP} 4.
In the two years since the release of version 4.2, {\GAP} development
has become a more and more widely distributed operation, and
increasingly dependent on hard voluntary work by developers not solely
or mainly employed to work on {\GAP}, nevertheless, the development
process has remained constructive and friendly, even when wrangling
over difficult technical decisions, or sensitive questions of
attribution and credit and I must express my huge gratitude to
everyone involved for this.
The list of modules which appears in this manual now gives a partial
idea of the contributions of different people, but I should like to
mention some people who have made important contributions to the
development process over the last two years that do not show up there:
Alexander Hulpke has remained a tower of strength, with unparalleled
oversight of many parts of the library, despite now having a teaching
post; Thomas Breuer continues to develop many areas of the system, and
to play a vital role in clarifying our underlying concepts, despite
now working in industry; Frank L\accent127ubeck and Max
Neunh\accent127offer have brought much fresh insight to bear on the
design of crucial parts of the system, and also done a lot of the
ensuing work; Greg Gamble and Volkmar Felsch have both brought
enormous persistence to correcting very many details of the
documentation, improving error messages and generally polishing the
system; and very many others have contributed ideas, insight and hard
work to produce this release. Senior colleagues, especially Joachim
Neub\accent127user, Edmund Robertson, and Charlie Wright, continue to
provide encouragement support and constructive criticism.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Changes from Earlier Versions}
The main changes between {\GAP} 4.2 and {\GAP} 4.3 are:
*Potentially Incompatible Changes*
\beginlist%unordered
\item{--}
There have been many adjustments to the arithmetic of lists (including
matrices and vectors). These include performance enhancements in many
areas, and also extended, and more precisely documented, rules for the
results of arithmetic operations applied to lists, including rules for
the mutability of the results. The main visible consequences of this
are that a lot of operations that previously gave errors now give
results, but, in a few unusual cases, the mutability status, or even
the value, of the results may be different. More specifically:
\itemitem{\*}
The scope of the arithmetic operations is extended to some objects for
which it is currently undefined, or unimplemented.
\itemitem{\*}
The mutability of the results of unary arithmetic operations such
as unary -, multiplication by zero, and raising to the power 0 or
-1, applied to immutable lists has changed. See section
"ref:Arithmetic for Lists" for details.
\itemitem{\*}
The behaviour under multiplication of lists of nesting depth three or
more is changed.
\item{--} Finitely-presented monoids have been added to the system as
objects in their own right. Dividing a free monoid by a list of
relations now produced a finitely-presented monoid, whereas previously
it produced a finitely-presented semigroup.
\item{--} A number of documented functions which have been renamed, or
whose functionality is now unnecessary or better achieved in other
ways have been declared ``obsolescent'' and will be removed in {\GAP}
4.4. These functions have been moved to the file `obsolete.g' in the
{\GAP} library. Perhaps the best known of these functions are the
permutation group functions with the old `Operation' names (such as
`OperationHomomorphism'. These all have replacements like
`ActionHomomorphism' with `Action' names.
\endlist
These changes are, in some respects, departures from our policy of
maintaining upwards compatibility of documented functions between
releases. In the first case, we felt that the old behaviour was
sufficiently inconsistent, illogical, and impossible to document that
we had no alternative but to change it. In the second case the change
was necessary to introduce new functionality. The planned and phased
removal of a few unnecessary functions or symonyms is needed to avoid
becoming buried in ``legacy'' interfaces, but we remain committed to
our policy of maintaining upwards compatibility whenever sensibly possible.
*Changes to Mathematical Functionality*
\beginlist%unordered
\item{--}
The performance of several routines has been substantially improved (e.g.
File I/O, large degree permutation groups, finite field matrices, matrix
groups, double cosets, permutation group homomorphisms, Solvable quotient,
Knuth-Bendix)
\item{--}
Many bugs have been fixed. This release thus incorporates the contents
of all the bugfixes which were released for {\GAP} 4.2. It also fixes
a number of bugs discovered since the last bugfix.
\item{--}
The functionality for finitely presented groups has been improved, including
the addition of effective support for homomorphisms for finitely presented groups.
\item{--}
Routines for the calculation of the Schur multiplier and a
Schur Cover of finite permutation groups are now available.
\item{--}
An implementation of Dixon's method for computing ordinary representations of groups has been added.
\item{--}
The methods for decomposing a group element as a word in given generators and for
computing a presentation of a given group have been substantially enhanced.
\item{--}
More general methods to form group products are available.
\item{--}
Generators for orthogonal groups of odd dimension in characteristic 2 have been added.
\item{--}
Methods for `NrConjugacyClasses' have been added for many classical groups.
\item{--}
Errors in the (theoretical) classification of irreducible solvable matrix
groups have been resolved.
\item{--}
A special representation for univariate rational functions was added.
\item{--}
Straight line program elements have been added.
\item{--}
The built-in MeatAxe now can treat the so-called ``bad case'' well.
\item{--}
The list of Conway polynomials for finite fields has been extended.
\endlist
*Changes to the Data Libraries*
\beginlist%unordered
\item{--}
The library of transitive permutation groups has been extended from degree
23 to degree 31.
\item{--}
The library of irreducible maximal finite integral matrix groups has
been extended from degree 24 to degree 31.
\item{--}
The library of character tables and the library of tables of marks
have been moved into packages for easier maintenance and upgrade. Some
new tables have been added.
\endlist
*Changes to the System*
\beginlist%unordered
\item{--}
Limitations on the length of integers and strings that can be read
into {\GAP} have been removed, integers can also be read in in
hexadecimal format.
\item{--}
The ability to read and write binary strings has been added.
\item{--}
A filename starting with a tilde now refers by default to the home
directory.
\item{--}
The online help interface has been greatly improved. Further help viewers have been added (in
particular viewers for `dvi' and `pdf' files).
\item{--}
The Windows installation has been simplified for the case where you
are installing GAP in its standard location.
\item{--}
Utilities for editing {\GAP} files with `vim' or `emacs' are provided.
\item{--}
The `-K' option can be used to limit the amount of workspace used.
\item{--}
New interfaces allow more control of the user interface, for instance
colouring the `gap>' prompt, or modifying break loop behaviour.
\item{--}
A `continue' statement has been added to the {\GAP} language,
analagous to that in C
\item{--}
Numerous unreliable or potentially confusing C constructions reported
by various C compilers have been removed. The system now compiles with
few or no warnings on all the compilers we could test.
\endlist
The most important changes between {\GAP} 4.1 and {\GAP} 4.2 were:
\beginlist%unordered
\item{--}
A much extended and improved library of small groups as well as
associated IdGroup routines.
\item{--}
The primitive groups library has been made more independent of the
rest of GAP, some errors were corrected.
\item{--}
New (and often much faster) infrastructure for orbit computation, based on a
general ``dictionary'' abstraction.
\item{--}
New functionality for dealing with representations of algebras, and
in particular for semisimple Lie algebras.
\item{--}
New functionality for binary relations on arbitrary sets, magmas and
semigroups.
\item{--}
Bidirectional streams, allowing an external process to be started and then
controlled ``interactively'' by GAP
\item{--}
A prototype implementation of algorithms using general subgroup chains.
\item{--}
Changes in the behaviour of vectors over small finite fields.
\item{--}
A fifth book ``New features for Developers'' has been added to the GAP manual.
\item{--}
Numerous bug fixes and performance improvements
\endlist
The changes between the final release of {\GAP} 3 (version 3.4.4) and
{\GAP} 4 are wide-ranging. The general philosophy of the
changes is two-fold. Firstly, many assumptions in the design of
{\GAP} 3 revealed its authors' primary interest in group theory, and
indeed in finite group theory. Although much of the {\GAP} 4 library
is concerned with groups, the basic design now allows extension to
other algebraic structures, as witnessed by the inclusion of
substantial bodies of algorithms for computation with semigroups and
Lie algebras. Secondly, as the scale of the system, and the number of
people using and contributing to it has grown, some aspects of the
underlying system have proved to be restricting, and these have been
improved as part of comprehensive re-engineering of the system. This
has included the new method selection system, which underpins the
library, and a new, much more flexible, {\GAP} package interface.
Details of these changes can be found in chapter "Migrating to GAP 4" of
this manual. It is perhaps worth mentioning a few points here.
Firstly, much remains unchanged, from the perspective of the mathematical
user:
\beginlist%unordered
\item{--}
The syntax of that part of the {\GAP} language that most users need
for investigating mathematical problems.
\item{--}
The great majority of function names.
\item{--}
Data libraries and the access to them.
\endlist
A number of visible aspects have changed:
\beginlist%unordered
\item{--}
Some function names that need finer specifications now that there are
more structures available in {\GAP}.
\item{--}
The access to information already obtained about a mathematical
structure. In {\GAP}~3 such information about a group could be looked
up by directly inspecting the group record, whereas in {\GAP}~4
functions must be used to access such information.
\endlist
Behind the scenes, much has changed:
\beginlist%unordered
\item{--} A new kernel, with improvements in memory management and in
the language interpreter, as well as new features such as saving of
workspaces and the possibility of compilation of {\GAP} code into C.
\item{--} A new structure to the library, based upon a new type and
method selection system, which is able to support a broader range of
algebraic computation and to make the structure of the library simpler
and more modular.
\item{--}
New and faster algorithms in many mathematical areas.
\item{--}
Data structures and algorithms for new mathematical objects, such as
algebras and semigroups.
\item{--}
A new and more flexible structure for the {\GAP} installation
and documentation, which means, for example, that a {\GAP} package and
its documentation can be installed and be fully usable without any changes
to the {\GAP} system.
\endlist
A very few features of {\GAP}~3 are not yet available in {\GAP}~4.
\beginlist%unordered
\item{--}
Not all of the {\GAP}~3 packages have yet been converted
for use with {\GAP}~4 (although several new packages are available
only in {\GAP}~4).
\item{--} The Galois group determination algorithms which were
implemented in the {\GAP}~3 library are not present in {\GAP}~4.
\item{--} The algorithms for the factorization of polynomials over
algebraic number fields which were implemented in the {\GAP}~3 library
are not present in {\GAP}~4.
\item{--} The library of crystallographic groups which was present in
{\GAP}~3 is now part of a {\GAP}~4 package `crystcat'.
\endlist
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Further Information about GAP}
\atindex{web sites!for GAP}{@web sites!for GAP}
Information about {\GAP} is best obtained from the {\GAP} Web pages that
you find on:
\URL{http://www.gap-system.org}
and its mirrors at:
\URL{http://www.math.rwth-aachen.de/~GAP} and
\URL{http://www.ccs.neu.edu/mirrors/GAP}
Further mirrors may be announced from time to time. There you will
find, amongst other things
\beginlist%unordered
\item{--} directions to the FTP sites from which you can download the
current {\GAP} distribution, any bugfixes, all accepted {\GAP} packages,
and a selection of other contributions.
\item{--} the {\GAP} manual and an archive of the `gap-forum' mailing
list, formatted for reading with a Web browser, and indexed for
searching.
\item{--} information about {\GAP} developers, and about the email
addresses available for comment, discussion and support.
\endlist
\index{email addresses}\indextt{gap-trouble!email address}
I would particularly ask you to note five things:
\beginlist%unordered
\item{--} Any bugfixes which may have been made since this release.
\item{--} The {\GAP} Forum -- an email discussion forum for comments,
discussions or questions about {\GAP}. You must subscribe to the list
before you can post to it, see the Web page for details.
\item{--} The email address \Mailto{gap-trouble@dcs.st-and.ac.uk} to which you
are asked to send any questions or bug reports which do not seem likely
to be of interest to the whole {\GAP} Forum. Section~"ref:If Things Go Wrong"
in the Reference Manual tells you what to include in a bug report.
\item{--} The email address \Mailto{gap@dcs.st-and.ac.uk} to which we ask you
send a brief message when you install {\GAP}.
\item{--} The correct form of citation of {\GAP}, which we ask you use
whenever you publish scientific results obtained using {\GAP}.
\endlist
It finally remains for me to wish you all pleasure and success in using
{\GAP}, and to invite your constructive comment and criticism.
St Andrews May 2002\hfill Steve Linton
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E preface.tex . . . . . . . . . . . . . . . . . . . . . . . . ends here