Preface of GAP 3.1

GAP stands for Groups, Algorithms and Programming. The name was chosen to reflect the aim of the system, which is introduced in this manual.

Until well into the eighties the interest of pure mathematicians in computational group theory was stirred by, but in most cases also confined to the information that was produced by group theoretical software for their special research problems -- and hampered by the uneasy feeling that one was using black boxes of uncontrollable reliability. However the last years have seen a rapid spread of interest in the understanding, design and even implementation of group theoretical algorithms. These are gradually becoming accepted both as standard tools for a working group theoretician, like certain methods of proof, and as worthwhile objects of study, like connections between notions expressed in theorems.

GAP was started as an attempt to meet this interest. Therefore a primary design goal has been to give its user full access to algorithms and the data structures used by them, thus allowing critical study as well as modification of existing methods. We also intend to relieve the user from unwanted technical chores and to assist him in the programming, thus supporting invention and implementation of new algorithms as well as experimentation with them.

We have tried to achieve these goals by a design which in addition makes GAP easily portable, even to computers such as Atari ST and Amiga, and at the same time facilitates the maintenance of GAP with the limited resources of an academic environment.

While I had felt for some time rather strongly the wish for such a truly open system for computational group theory, the concrete idea of GAP was born when, together with a larger group of students, among whom where Johannes Meier, Alice Niemeyer, Werner Nickel and Martin Schönert who eventually wrote the first version of GAP, I had my first contact with the Maple system at the EUROCAL meeting in Linz/Austria in 1985. Maple demonstrated to us the feasibility of a strong and efficient computer algebra system built from a small kernel, with an interpreted library of routines written in a problem-adapted language. The discussion of the plan of a system for computational group theory organized in a similar way started in the fall of 1985, programming only in the second half of 1986. A first version of GAP was operational by the end of 1986. The system was first presented at the Oberwolfach meeting on computational group theory in May 1988. Version 2.4 was the first officially to be given away from Aachen starting in December 1988. The strong interest in this version, in spite of its still rather small collection of group theoretical routines, as well as constructive criticism by many colleagues, confirmed our belief in the general design principles of the system. Nevertheless over three years have gone by until now in April 1992 version 3.1 is released.

A main reason for this much time and the fact that there have not been intermediate releases is that we have found it advisable to make a number of changes to basic data structures until we now hope to have reached a state where we can maintain upward compatibility over further releases, which are planned to follow much more frequently. Of course the time has also been used to extend the scope of the methods implemented in GAP. A rough guess puts the size of the present program library at about eight times the size of that in version 2.4. In spite of this there are still very notable gaps in what I would like to see in GAP.

The system that you are getting now consists of four parts:

  • A comparatively small kernel, written in C, which provides the user with:
    • automatic dynamical storage management, which the user needn't bother about in his programming;
    • a set of time-critical basic functions, e.g. "arithmetic" operations for integers, finite field elements, permutations and words, as well as natural operations for lists and records;
    • an interpreter for the GAP language, which belongs to the Pascal family, but, while allowing additional types for group theoretical objects, does not require type declarations;
    • a set of programming tools for testing, debugging, and timing algorithms.

     
  • A much larger library of GAP functions that implement group theoretical and other algorithms. Since this is written entirely in the GAP language, in contrast to the situation in older group theoretical software, 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 his own and eventually for the benefit of all GAP users. We hope that moreover the structuring of the library using the concept of 'domains' and the techniques used for their handling that have been introduced into GAP 3.1 by Martin Schönert will be further helpful in this respect.
     
  • A library of group theoretical data which already contains e.g. a list of primitive groups of Charles Sims, a list of the 2-groups of order up to 256 of Eamonn O'Brien and a large collection of character tables including all of the Cambridge 'Atlas of Finite Groups', but which we hope to extend further with the help of colleagues who have undertaken larger classifications of groups.
     
  • The documentation. This is available as a file that can either be used for on-line help or be printed out to form this manual. Some advice for using this manual may be helpful. The first chapter 'About GAP' is really an introduction to the use of the system, starting from scratch and, for the beginning, assuming neither much knowledge about group theory nor much versatility in using a computer. Some of the later sections of chapter 1 assume more, however. For instance, the section 'About Character Tables' definitely assumes familiarity with representation theory of finite groups, while in particular the sections 'About the Implementation of Domains' to 'About Defining New Group Elements' address more advanced users who want to extend the system to meet their special needs. The further chapters of the manual give then a full description of the functions presently available in GAP.

The policy for the further development of GAP is to keep the kernel as small as possible, extending the set of basic functions only by very selected ones that have proved to be time-critical and, wherever feasible, of general use. In the interest of the possibility of exchanging functions written in the GAP language the kernel has to be maintained in a single place which in the foreseeable future will be Aachen. On the other hand we hope that the design of GAP will allow the library to grow not only by continued work in Aachen but, as does any other part of mathematics, by exchange of contributions from many sides. Our own plans in this respect in the near future include the removal of present restrictions on the degree of permutations and the size of finite fields, the implementation of some further standard methods for working with finite presentations, such as Reidemeister-Schreier and Tietze transformations, extension of the methods for permutation groups, some further tools for working with character tables, and better interactive means of working with the output of the subgroup lattice program. Some of this has already been implemented and just did not make it for the deadline that we had set for inclusion with this release.

There are five other points to make on further policy:

  • When we began work on GAP the typical user that we had in mind was the one wanting to implement his own algorithmic ideas. While we certainly hope that we still serve such users well it has become clear from the experience of the last years that there are even more users of two different species, on the one hand the established theoretician, sometimes with little experience in the use of computers, who wants an easily understandable tool, on the other hand the student, often quite familiar with computers, who wants to get assistance in learning the theory by being able to do nontrivial examples. We think that in fact GAP can well be used by both, but we realize that for each a special introduction would be desirable. We apologize that we have not had the time yet to write such.
     
  • When we began work on GAP, we designed it as a system for doing group theory. It has already turned out that in fact the design of the system is general enough, and some of its functions are also useful, for doing work in other neighbouring areas. For instance Leonard Soicher has used GAP to develop a system GRAPE for working with graphs. We certainly enjoy seeing this happen, but we want to emphasize that our primary interest is the development of a group theory system and that we do not plan to try to extend it beyond our abilities into a general computer algebra system.
     
  • Rather we hope to provide tools for linking GAP to other systems that represent years of work and experience in areas such as commutative algebra, or, even in the near future, to very efficient special purpose stand-alone programs such as the p-group generation program of Mike Newman and Eamonn O'Brien.
     
  • We invite you to extend GAP. We are willing to make such extensions available through the same channels as GAP in the form of a share library. Of course, we will do this only if the extension can be distributed free of charge like GAP. The copyright for such extensions shall remain with you.
     
  • Finally to answer an often asked question: The GAP language is in principle designed to be compilable. We may one day try writing a compiler for it, but this is not yet under way.

GAP is given away under the conditions that have always been in use between mathematicians, i.e. in particular completely in source and free of charge. We hope that the possibility offered by modern technology of depositing GAP on a number of computers to be fetched from them by 'ftp', will assist us in this policy. We want to emphasize, however, two points. GAP is not public domain software; we want to maintain a copyright that in particular forbids commercialization of GAP. Further we ask that use of GAP be quoted in publications like the use of any other mathematical work, and we would be grateful if we could keep track of where GAP is implemented. Therefore we ask you to notify us if you have got GAP, e.g., by sending a short e-mail message to 'gap@samson.math.rwth-aachen.de'. The simple reason, on top of our curiousity, is that as anybody else in an academic environment we have from time to time to prove that we are doing meaningful work.

We have established a GAP forum, where interested users can discuss GAP related topics by e-mail. In particular this forum is for questions about GAP, general comments, bug reports, and maybe bug fixes. We will read this forum and answer questions and comments, and distribute bug fixes. Of course others are also invited to answer questions, etc. We will also announce future releases of GAP on this forum.

To subscribe send an e-mail message to 'listserv@samson.math.rwth-aachen.de' containing the line 'subscribe gap-forum <your-name>', where <your-name> should be your full name, not your e-mail address. You will receive an acknowledgement, and from then on all e-mail messages sent to 'gap-forum@samson.math.rwth-aachen.de'.

'listserv@samson.math.rwth-aachen.de' also accepts the following requests. 'help' for a short help on how to use 'listserv', 'unsubscribe gap-forum' to unsubscribe, 'recipients gap-forum' to get a list of subscribers, and 'statistics gap-forum' to see how many e-mail messages each subscriber has sent so far.

GAP was started as a joint Diplom project of four students whose names have already been mentioned. Since then about 10 finished Diplom projects have contributed to GAP and further students are presently extending the library in the course of their work for the Diplom as well as other members of Lehrstuhl D and colleagues from other institutes. Their individual contributions to the programs and to the manual are documented in the respective files. To all of them as well as to all who have helped proofreading and improving this manual I want to express my thanks for their engagement and enthusiasm. Very special thanks however go to Martin Schönert. Not only does GAP owe many of its basic design features to his profound knowledge of computer languages and the techniques for their implementation, but in many long discussions he has in the name of future users always been the strongest defender of clarity of the design against my impatience and the temptation for "quick and dirty" solutions.

As with version 2.4 we send this version out hoping for feedback of constructive criticism. Of course we ask to be notified about bugs, but moreover we shall appreciate any suggestion for the improvement of the basic system as well as of the algorithms in the library. Most of all, however, we hope that in spite of such criticism you will enjoy working with GAP.

Aachen, March 31, 1992, Joachim Neubüser.