chap2.txt

  
  2 A First Session with GAP
  
  This  tutorial introduces you to the GAP system. It is written with users in
  mind who have just managed to start GAP for the first time on their computer
  and  want  to  learn  the  basic facts about GAP by playing around with some
  instructive  examples.  Therefore,  this  tutorial  contains  at many places
  examples consisting of several lines of input (which you should type on your
  terminal)  followed  by  the corresponding output ( which GAP produces as an
  answer to your input).
  
  We  encourage  you  to actually run through these examples on your computer.
  This  will  support your feeling for GAP as a tool, which is the leading aim
  of  this  tutorial. Do not believe any statement in it as long as you cannot
  verify it for your own version of GAP. You will learn to distinguish between
  small  deviations  of  the  behavior  of  your personal GAP from the printed
  examples and serious nonsense.
  
  Since  the  printing routines of GAP are in some sense machine dependent you
  will  for  instance  encounter  a different layout of the printed objects in
  different  environments. But the contents should always be the same. In case
  you  encounter serious nonsense it is highly recommended that you send a bug
  report to mailto:[email protected].
  
  The  examples in this tutorial should explain everything you have to know in
  order  to  be  able  to  use  GAP.  The  reference  manual then gives a more
  systematic   treatment  of  the  various  types  of  objects  that  GAP  can
  manipulate.  It seems desirable neither to start this systematic course with
  the  most  elementary (and most boring) structures, nor to confront you with
  all  the  complex  data  types  before  you  know how they are composed from
  elementary  structures.  For  this reason this tutorial wants to provide you
  with  a  basic  understanding  of GAP objects, on which the reference manual
  will  then  build  when  it  explains  everything in detail. So after having
  mastered  this  tutorial, you can immediately plunge into the exciting parts
  of  GAP  and  only read detailed information about elementary things (in the
  reference manual) when you really need them.
  
  Each  chapter  of  this  tutorial  contains a section with references to the
  reference manual at the end.
  
  
  2.1 Starting and Leaving GAP
  
  If  the  program is correctly installed then you usually start GAP by simply
  typing  gap  at  the  prompt of your operating system followed by the Return
  key, sometimes this is also called the Newline key.
  
    Example  
    $ gap
  
  
  GAP answers your request with its beautiful banner and then it shows its own
  prompt gap> asking you for further input. (You can avoid the banner with the
  command  line  option  -b;  more  command  line  options  are  described  in
  Section 'Reference: Command Line Options'.)
  
    Example  
    gap> 
  
  
  The  usual  way to end a GAP session is to type quit; at the gap> prompt. Do
  not omit the semicolon!
  
    Example  
    gap> quit;
    $ 
  
  
  On  some  systems  you  could  type  Ctrl-D to yield the same effect. In any
  situation  GAP  is  ended  by  typing  Ctrl-C twice within a second. Here as
  always,  a  combination  like  Ctrl-D means that you have to press the D key
  while you hold down the Ctrl key.
  
  On  some  systems  (for  example the Apple Macintosh) minor changes might be
  necessary.  This  is  explained  in  GAP  installation instructions (see the
  INSTALL file in the GAP root directory, or the GAP website).
  
  In  most  places  whitespace  characters (i.e. Spaces, Tabs and Returns) are
  insignificant  for  the  meaning of GAP input. Identifiers and keywords must
  however  not contain any whitespace. On the other hand, sometimes there must
  be  whitespace  around  identifiers  and keywords to separate them from each
  other  and  from  numbers. We will use whitespace to format more complicated
  commands for better readability.
  
  A  comment  in  GAP starts with the symbol # and continues to the end of the
  line.  Comments  are  treated like whitespace by GAP. We use comments in the
  printed  examples  in  this  tutorial  to  explain certain lines of input or
  output.
  
  
  2.2 Loading Source Code from a File
  
  The  most  convenient  way of creating larger pieces of GAP code is to write
  them  to  some  text file. For this purpose you can simply use your favorite
  text  editor.  You  can load such a file into GAP using the Read (Reference:
  Read) function:
  
    Example  
    gap> Read("../../GAPProgs/Example.g");
  
  
  You  can  either  give the full absolute path name of the source file or its
  relative  path  name  from  the GAP root directory (the directory containing
  bin/, doc/, lib/, etc.).
  
  
  2.3 The Read Evaluate Print Loop
  
  GAP is an interactive system. It continuously executes a read evaluate print
  loop.  Each  expression  you type at the keyboard is read by GAP, evaluated,
  and then the result is shown.
  
  The  interactive  nature  of  GAP  allows  you  to type an expression at the
  keyboard  and see its value immediately. You can define a function and apply
  it  to  arguments  to  see  how  it works. You may even write whole programs
  containing lots of functions and test them without leaving the program.
  
  When  your program is large it will be more convenient to write it on a file
  and  then  read  that  file into GAP. Preparing your functions in a file has
  several  advantages. You can compose your functions more carefully in a file
  (with  your  favorite  text editor), you can correct errors without retyping
  the  whole  function and you can keep a copy for later use. Moreover you can
  write  lots of comments into the program text, which are ignored by GAP, but
  are  very  useful  for  human readers of your program text. GAP treats input
  from  a file in the same way that it treats input from the keyboard. Further
  details can be found in section Read (Reference: Read).
  
  A  simple  calculation  with GAP is as easy as one can imagine. You type the
  problem  just  after the prompt, terminate it with a semicolon and then pass
  the problem to the program with the Return key. For example, to multiply the
  difference  between 9 and 7 by the sum of 5 and 6, that is to calculate (9 -
  7)  *  (5 + 6), you type exactly this last sequence of symbols followed by ;
  and Return.
  
    Example  
    gap> (9 - 7) * (5 + 6);
    22
    gap> 
  
  
  Then  GAP  echoes  the  result 22 on the next line and shows with the prompt
  that  it  is ready for the next problem. Henceforth, we will no longer print
  this additional prompt.
  
  If  you  make  a  mistake while typing the line, but before typing the final
  Return,  you  can  use the Delete key (or sometimes Backspace key) to delete
  the  last  typed character. You can also move the cursor back and forward in
  the  line with Ctrl-B and Ctrl-F and insert or delete characters anywhere in
  the   line.   The   line   editing   commands   are   fully   described   in
  section 'Reference: Line Editing'.
  
  If  you did omit the semicolon at the end of the line but have already typed
  Return,  then  GAP has read everything you typed, but does not know that the
  command  is complete. The program is waiting for further input and indicates
  this  with  a  partial prompt >. This problem is solved by simply typing the
  missing  semicolon on the next line of input. Then the result is printed and
  the normal prompt returns.
  
    Example  
    gap> (9 - 7) * (5 + 6)
    > ;
    22
  
  
  So the input can consist of several lines, and GAP prints a partial prompt >
  in  each  input line except the first, until the command is completed with a
  semicolon. (GAP may already evaluate part of the input when Return is typed,
  so  for  long  calculations it might take some time until the partial prompt
  appears.) Whenever you see the partial prompt and you cannot decide what GAP
  is  still  waiting  for,  then  you have to type semicolons until the normal
  prompt  returns.  In every situation the exact meaning of the prompt gap> is
  that the program is waiting for a new problem.
  
  But even if you mistyped the command more seriously, you do not have to type
  it  all  again. Suppose you mistyped or forgot the last closing parenthesis.
  Then  your  command  is  syntactically  incorrect  and  GAP  will notice it,
  incapable of computing the desired result.
  
    Example  
    gap> (9 - 7) * (5 + 6;
    Syntax error: ) expected
    (9 - 7) * (5 + 6;
                    ^
  
  
  Instead  of the result an error message occurs indicating the place where an
  unexpected  symbol  occurred  with  an  arrow sign ^ under it. As a computer
  program  cannot  know what your intentions really were, this is only a hint.
  But  in  this  case  GAP is right by claiming that there should be a closing
  parenthesis  before  the  semicolon.  Now you can type Ctrl-P to recover the
  last  line  of input. It will be written after the prompt with the cursor in
  the  first  position. Type Ctrl-E to take the cursor to the end of the line,
  then  Ctrl-B to move the cursor one character back. The cursor is now on the
  position of the semicolon. Enter the missing parenthesis by simply typing ).
  Now  the line is correct and may be passed to GAP by hitting the Return key.
  Note  that  for  this action it is not necessary to move the cursor past the
  last character of the input line.
  
  Each  line  of  commands  you type is sent to GAP for evaluation by pressing
  Return  regardless  of  the  position of the cursor in that line. We will no
  longer mention the Return key from now on.
  
  Sometimes  a  syntax  error  will  cause  GAP to enter a break loop. This is
  indicated  by  the special prompt brk>. If another syntax error occurs while
  GAP  is  in  a break loop, the prompt will change to brk_02>, brk_03> and so
  on.  You  can leave the current break loop and exit to the next outer one by
  either  typing quit; or by hitting Ctrl-D. Eventually GAP will return to its
  normal state and show its normal prompt gap> again.
  
  
  2.4 Constants and Operators
  
  In  an  expression  like  (9 - 7) * (5 + 6) the constants 5, 6, 7, and 9 are
  being composed by the operators +, * and - to result in a new value.
  
  There   are  three  kinds  of  operators  in  GAP,  arithmetical  operators,
  comparison  operators,  and logical operators. You have already seen that it
  is  possible to form the sum, the difference, and the product of two integer
  values.  There  are  some  more  operators applicable to integers in GAP. Of
  course  integers  may  be  divided  by  each  other,  possibly  resulting in
  noninteger rational values.
  
    Example  
    gap> 12345/25;
    2469/5
  
  
  Note that the numerator and denominator are divided by their greatest common
  divisor   and  that  the  result  is  uniquely  represented  as  a  division
  instruction.
  
  The next self-explanatory example demonstrates negative numbers.
  
    Example  
    gap> -3; 17 - 23;
    -3
    -6
  
  
  The  exponentiation  operator  is written as ^. This operation in particular
  might  lead  to  very  large  numbers.  This is no problem for GAP as it can
  handle numbers of (almost) any size.
  
    Example  
    gap> 3^132;
    955004950796825236893190701774414011919935138974343129836853841
  
  
  The mod operator allows you to compute one value modulo another.
  
    Example  
    gap> 17 mod 3;
    2
  
  
  Note  that  there  must be whitespace around the keyword mod in this example
  since  17mod3  or  17mod would be interpreted as identifiers. The whitespace
  around  operators  that do not consist of letters, e.g., the operators * and
  -, is not necessary.
  
  GAP  knows  a  precedence  between  operators  that  may  be  overridden  by
  parentheses.
  
    Example  
    gap> (9 - 7) * 5 = 9 - 7  * 5;
    false
  
  
  Besides  these arithmetical operators there are comparison operators in GAP.
  A  comparison  results in a boolean value which is another kind of constant.
  The  comparison  operators  =,  <>,  <,  <=,  >  and  >=, test for equality,
  inequality,  less than, less than or equal, greater than and greater than or
  equal, respectively.
  
    Example  
    gap> 10^5 < 10^4;
    false
  
  
  The  boolean values true and false can be manipulated via logical operators,
  i. e., the unary operator not and the binary operators and and or. Of course
  boolean values can be compared, too.
  
    Example  
    gap> not true; true and false; true or false;
    false
    false
    true
    gap> 10 > 0 and 10 < 100;
    true
  
  
  Another  important  type  of  constants  in  GAP  are permutations. They are
  written in cycle notation and they can be multiplied.
  
    Example  
    gap> (1,2,3);
    (1,2,3)
    gap> (1,2,3) * (1,2);
    (2,3)
  
  
  The  inverse  of  the permutation (1,2,3) is denoted by (1,2,3)^-1. Moreover
  the  caret  operator  ^  is  used  to determine the image of a point under a
  permutation and to conjugate one permutation by another.
  
    Example  
    gap> (1,2,3)^-1;
    (1,3,2)
    gap> 2^(1,2,3);
    3
    gap> (1,2,3)^(1,2);
    (1,3,2)
  
  
  The  various  other constants that GAP can deal with will be introduced when
  they are used, for example there are elements of finite fields such as Z(8),
  and complex roots of unity such as E(4).
  
  The last type of constants we want to mention here are the characters, which
  are  simply  objects  in  GAP  that  represent arbitrary characters from the
  character  set of the operating system. Character literals can be entered in
  GAP by enclosing the character in singlequotes '.
  
    Example  
    gap> 'a';
    'a'
    gap> '*';
    '*'
  
  
  There  are no operators defined for characters except that characters can be
  compared.
  
  In this section you have seen that values may be preceded by unary operators
  and  combined  by  binary  operators  placed between the operands. There are
  rules  for  precedence  which may be overridden by parentheses. A comparison
  results  in  a  boolean  value.  Boolean  values  are  combined  via logical
  operators.  Moreover  you  have  seen  that GAP handles numbers of arbitrary
  size.  Numbers  and  boolean  values are constants. There are other types of
  constants  in GAP like permutations. You are now in a position to use GAP as
  a simple desktop calculator.
  
  
  2.5 Variables versus Objects
  
  The  constants  described  in  the  last  section  are  specified by certain
  combinations  of digits and minus signs (in the case of integers) or digits,
  commas  and  parentheses  (in  the case of permutations). These sequences of
  characters always have the same meaning to GAP. On the other hand, there are
  variables, specified by a sequence of letters and digits (including at least
  one letter), and their meaning depends on what has been assigned to them. An
  assignment  is  done  by  a  GAP  command  sequence_of_letters_and_digits :=
  meaning,  where  the sequence on the left hand side is called the identifier
  of  the  variable  and  it serves as its name. The meaning on the right hand
  side  can be a constant like an integer or a permutation, but it can also be
  almost  any  other  GAP  object. From now on, we will use the term object to
  denote something that can be assigned to a variable.
  
  There  must  be  no  whitespace  between  the  : and the = in the assignment
  operator.  Also  do  not  confuse  the  assignment  operator with the single
  equality sign = which in GAP is only used for the test of equality.
  
    Example  
    gap> a:= (9 - 7) * (5 + 6);
    22
    gap> a;
    22
    gap> a * (a + 1);
    506
    gap> a = 10;
    false
    gap> a:= 10;
    10
    gap> a * (a + 1);
    110
  
  
  After  an  assignment  the  assigned  object is echoed on the next line. The
  printing  of  the  object  of  a statement may be in every case prevented by
  typing a double semicolon.
  
    Example  
    gap> w:= 2;; 
  
  
  After  the  assignment  the  variable evaluates to that object if evaluated.
  Thus  it  is possible to refer to that object by the name of the variable in
  any situation.
  
  This is in fact the whole secret of an assignment. An identifier is bound to
  an  object  and  from  this moment points to that object. Nothing more. This
  binding  is changed by the next assignment to that identifier. An identifier
  does not denote a block of memory as in some other programming languages. It
  simply  points to an object, which has been given its place in memory by the
  GAP  storage  manager.  This place may change during a GAP session, but that
  doesn't bother the identifier. The identifier points to the object, not to a
  place in the memory.
  
  For the same reason it is not the identifier that has a type but the object.
  This  means on the other hand that the identifier a which now is bound to an
  integer  object may in the same session point to any other object regardless
  of its type.
  
  Identifiers  may  be sequences of letters and digits containing at least one
  letter.  For example abc and a0bc1 are valid identifiers. But also 123a is a
  valid  identifier  as  it  cannot  be  confused  with  any number. Just 1234
  indicates  the  number  1234  and  cannot  be at the same time the name of a
  variable.
  
  Since  GAP  distinguishes  upper  and  lower  case,  a1 and A1 are different
  identifiers. Keywords such as quit must not be used as identifiers. You will
  see more keywords in the following sections.
  
  In  the  remaining part of this manual we will ignore the difference between
  variables,  their names (identifiers), and the objects they point to. It may
  be  useful  to  think  from time to time about what is really meant by terms
  such as the integer w.
  
  There  are  some predefined variables coming with GAP. Many of them you will
  find  in  the  remaining  chapters  of this manual, since functions are also
  referred to via identifiers.
  
  You  can get an overview of all GAP variables by entering NamesGVars(). Many
  of  these  are  predefined.  If you are interested in the variables you have
  defined yourself in the current GAP session, you can enter NamesUserGVars().
  
    Example  
    gap> NamesUserGVars();
    [ "a", "w" ]
  
  
  This  seems  to  be the right place to state the following rule: The name of
  every  global variable in the GAP library starts with a capital letter. Thus
  if you choose only names starting with a small letter for your own variables
  you  will  not attempt to overwrite any predefined variable. (Note that most
  of the predefined variables are read-only, and trying to change their values
  will result in an error message.)
  
  There are some further interesting variables one of which will be introduced
  now.
  
  Whenever  GAP  returns an object by printing it on the next line this object
  is assigned to the variable last. So if you computed
  
    Example  
    gap> (9 - 7) * (5 + 6);
    22
  
  
  and  forgot  to assign the object to the variable a for further use, you can
  still do it by the following assignment.
  
    Example  
    gap> a:= last;
    22
  
  
  Moreover there are variables last2 and last3, you can guess their values.
  
  In  this  section  you  have  seen how to assign objects to variables. These
  objects  can  later  be  accessed  through  the  name  of  the variable, its
  identifier.  You  have  also  encountered  the  useful  concept  of the last
  variables  storing  the latest returned objects. And you have learned that a
  double semicolon prevents the result of a statement from being printed.
  
  
  2.6 Objects vs. Elements
  
  In  the last section we mentioned that every object is given a certain place
  in  memory by the GAP storage manager (although that place may change in the
  course  of  a  GAP  session).  In this sense, objects at different places in
  memory  are  never equal, and if the object pointed to by the variable a (to
  be  more  precise,  the  variable  with identifier a) is equal to the object
  pointed  to  by  the variable b, then we should better say that they are not
  only   equal   but  identical.  GAP  provides  the  function  IsIdenticalObj
  (Reference: IsIdenticalObj) to test whether this is the case.
  
    Example  
    gap> a:= (1,2);; IsIdenticalObj( a, a );
    true
    gap> b:= (1,2);; IsIdenticalObj( a, b );
    false
    gap> b:= a;; IsIdenticalObj( a, b );
    true
  
  
  As  the above example indicates, GAP objects a and b can be unequal although
  they  are  equal from a mathematical point of view, i.e., although we should
  have  a  =  b.  It  may  be that the objects a and b are stored in different
  places  in memory, or it may be that we have an equivalence relation defined
  on  the  set  of  objects under which a and b belong to the same equivalence
  class.  For  example,  if  a  = x^3 and b = x^{-5} are words in the finitely
  presented group ⟨ x ∣ x^2 = 1 ⟩, we would have a = b in that group.
  
  GAP uses the equality operator = to denote such a mathematical equality, not
  the  identity of objects. Hence we often have a = b although IsIdenticalObj(
  a, b ) = false. The operator = defines an equivalence relation on the set of
  all GAP objects, and we call the corresponding equivalence classes elements.
  Phrasing  it differently, the same element may be represented by various GAP
  objects.
  
  Non-trivial  examples  of elements that are represented by different objects
  (objects  that  really  look  different,  not ones that are merely stored in
  different  memory  places)  will  occur  only  when  we  will be considering
  composite objects such as lists or domains.
  
  
  2.7 About Functions
  
  A  program  written  in the GAP language is called a function. Functions are
  special  GAP  objects. Most of them behave like mathematical functions. They
  are  applied to objects and will return a new object depending on the input.
  The  function  Factorial (Reference: Factorial), for example, can be applied
  to an integer and will return the factorial of this integer.
  
    Example  
    gap> Factorial(17);
    355687428096000
  
  
  Applying a function to arguments means to write the arguments in parentheses
  following  the  function.  Several arguments are separated by commas, as for
  the function Gcd (Reference: Gcd) which computes the greatest common divisor
  of two integers.
  
    Example  
    gap> Gcd(1234, 5678);
    2
  
  
  There  are  other  functions that do not return an object but only produce a
  side  effect,  for  example changing one of their arguments. These functions
  are  sometimes  called  procedures. The function Print (Reference: Print) is
  only called for the side effect of printing something on the screen.
  
    Example  
    gap> Print(1234, "\n");
    1234
  
  
  In order to be able to compose arbitrary text with Print (Reference: Print),
  this  function  itself will not produce a line break after printing. Thus we
  had another newline character "\n" printed to start a new line.
  
  Some functions will both change an argument and return an object such as the
  function  Sortex  (Reference:  Sortex)  that  sorts  a  list and returns the
  permutation  of  the  list  elements  that  it  has  performed. You will not
  understand  right  now  what it means to change an object. We will return to
  this subject several times in the next sections.
  
  A  comfortable  way to define a function yourself is the maps-to operator ->
  consisting  of  a  minus  sign and a greater sign with no whitespace between
  them.  The  function cubed which maps a number to its cube is defined on the
  following line.
  
    Example  
    gap> cubed:= x -> x^3;
    function( x ) ... end
  
  
  After the function has been defined, it can now be applied.
  
    Example  
    gap> cubed(5);
    125
  
  
  More complicated functions, especially functions with more than one argument
  cannot  be  defined  in  this  way.  You  will see how to write your own GAP
  functions in Section 4.1.
  
  In this section you have seen GAP objects of type function. You have learned
  how  to apply a function to arguments. This yields as result a new object or
  a  side  effect.  A  side  effect  may  change  an argument of the function.
  Moreover  you  have  seen  an  easy way to define a function in GAP with the
  maps-to operator.
  
  
  2.8 Help
  
  The  content  of  the  GAP  manuals is also available as on-line help. A GAP
  session  loads  a  long  list  of index entries. This typically contains all
  chapter  and  section headers, all names of documented functions, operations
  and so on, as well as some explicit index entries defined in the manuals.
  
  The format of a query is as follows.
  
  ?[book:][?]topic
  
  A  simple  example  would  be to type ?help at the GAP prompt. If there is a
  single section with index entry topic then this is displayed directly.
  
  If there are several matches you get an overview like in the example below.
  
    Example  
    gap> ?sets
    Help: several entries match this topic - type ?2 to get match [2]
    
    [1] Tutorial: Sets
    [2] Reference: Sets
    [3] Reference: sets
    [4] Reference: Sets of Subgroups
    [5] Reference: setstabilizer
  
  
  GAP's manuals consist of several books, which are indicated before the colon
  in  the  list above. A help query can be restricted to one book by using the
  optional book: part. For example ?tut : sets will display the first of these
  help  sections.  More  precisely,  the  parts  of  the string book which are
  separated by white space are interpreted as beginnings of the first words in
  the  name  of  the  book.  Try ?books to see the list of available books and
  their names.
  
  The   search  for  a  matching  topic  (and  optional  book)  is  done  case
  insensitively.  If  there  is  another  ? before the topic, then a substring
  search  for  topic is performed on all index entries. Otherwise the parts of
  topic which are separated by white space are considered as beginnings of the
  first words in an index entry.
  
  White space is normalized in the search string (and the index entries).
  
  Examples.  All  the  following  queries lead to the chapter of the reference
  manual which explains the use of GAP's help system in more detail.
  
    Example  
    gap> ?Reference: The Help System
    gap> ?  REF : t h s
    gap> ?ref:?  help   system 
  
  
  The  query  ??sets  shows all help sections in all books whose index entries
  contain the substring sets.
  
  As  mentioned  in the example above a complete list of commands for the help
  system  is  available  in  Section ?Ref:  The  Help  System of the reference
  manual.  In  particular  there  are  commands  to  browse  through  the help
  sections,  see ?Ref:  Browsing  through  the  Sections and there is a way to
  influence   the   way   how  the  help  sections  are  displayed,  see ?Ref:
  SetHelpViewer.  For  example  you  can  use an external pager program, a Web
  browser, dvi-previewer and/or pdf-viewer for reading GAP's online help.
  
  
  2.9 Further Information introducing the System
  
  For  large  amounts of input data, it might be advisable to write your input
  first  into a file, and then read this into GAP; see Read (Reference: Read),
  Edit (Reference: Edit) for this.
  
  The definition of the GAP syntax can be looked up in Chapter 'Reference: The
  Programming Language'. A complete list of command line editing facilities is
  found  in  Section 'Reference: Line Editing'. The break loop is described in
  Section 'Reference: Break Loops'.
  
  Operators  are explained in more detail in Sections 'Reference: Expressions'
  and  'Reference:  Comparisons'. You will find more information about boolean
  values  in  Chapters 'Reference:  Booleans'  and 'Reference: Boolean Lists'.
  Permutations   are   described   in  Chapter 'Reference:  Permutations'  and
  characters in Chapter 'Reference: Strings and Characters'.
  
  Variables  and  assignments  are  described  in  more  detail in 'Reference:
  Variables'  and  'Reference:  Assignments'.  A  complete list of keywords is
  contained in 'Reference: Keywords'.
  
  More   about   functions   can   be  found  in 'Reference:  Function  Calls'
  and 'Reference: Procedure Calls'.