  
  [1X2 [33X[0;0YThe [5XGAP[105X[101X[1X kernel programming[133X[101X
  
  
  [1X2.1 [33X[0;0YOverview of the [5XGAP[105X[101X[1X kernel[133X[101X
  
  [33X[0;0YThe [5XGAP[105X kernel consists of more than 150000 lines of [5XC[105X code that:[133X
  
  [30X    [33X[0;6Yprovides the run-time environment and user interface;[133X
  
  [30X    [33X[0;6Yinterprets the [5XGAP[105X language;[133X
  
  [30X    [33X[0;6Yperforms arithmetic operations with basic types of objects;[133X
  
  [30X    [33X[0;6Yspeeds up some time-critical operations.[133X
  
  [33X[0;0YThe [5XGAP[105X kernel code mainly falls into the four main categories:[133X
  
  [31X1[131X   [33X[0;6YImplementations   for  basic  data  types  and  structures  (integers,
        permutations,  finite  field  elements,  etc.), which has to be in the
        kernel for the maximal efficiency.[133X
  
  [31X2[131X   [33X[0;6YLow  level  access  methods  for data objects (lists, ranges, records,
        etc.).[133X
  
  [31X3[131X   [33X[0;6YVarious  methods  for  handling  complex  [5XGAP[105X objects in component and
        positional representation from the kernel.[133X
  
  [31X4[131X   [33X[0;6Y[5XGAP[105X  foundations  such  as  [5XGAP[105X  language,  garbage collector (in what
        follows - GC), etc.[133X
  
  [33X[0;0YThe [5XGAP[105X kernel programming has four levels of sofistication:[133X
  
  [31X1[131X   [33X[0;6YThe simplest form of kernel programming is to add new kernel functions
        for manipulating existing data types.[133X
  
  [31X2[131X   [33X[0;6YUsing  the "data object" type to add new binary data structures to the
        kernel.[133X
  
  [31X3[131X   [33X[0;6YAdding new basic (primitive) data types, such as, for example, [13XFloats[113X.[133X
  
  [31X4[131X   [33X[0;6YModifying the foundations, for example, changing the syntax of the [5XGAP[105X
        language.[133X
  
  [33X[0;0YWe  will cover only first two levels here, while adding new basic data types
  or modifying the foundations are outside the scope of this manual.[133X
  
  
  [1X2.2 [33X[0;0Y"Hello World" example[133X[101X
  
  [33X[0;0YOn  the  [5XGAP[105X  level,  the  kernel  functionality  may  be acessed via kernel
  functions.  You  can recognise such functions because they will be displayed
  as compiled code in the [5XGAP[105X session:[133X
  
  [4X[32X[104X
    [4X[104X
    [4Xgap> Display(TYPE_OBJ);[104X
    [4Xfunction ( obj )[104X
    [4X    <<kernel code>> from src/objects.c:TYPE_OBJ[104X
    [4Xend[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0YLet  us  demonstrate  how  to  add  a kernel function that will print "Hello
  World!".  Such  function has no arguments and returns nothing. To add it, we
  need to perform three basic steps:[133X
  
  [31X1[131X   [33X[0;6YCreate  the [5XC[105X handler, adding to the file [11Xstring.c[111X (this file contains
        the  functions  which  mainly  deal with strings) the [5XC[105X code doing the
        actual  job (see the function [10XPr[110X to print formatted output in the file
        [11Xscanner.c[111X ):[133X
  
  [4X      [32X[104X
          [4X[104X
          [4Xstatic Obj FuncHELLO_WORLD(Obj self)[104X
          [4X{[104X
          [4X    Pr("Hello World!\n", 0, 0);[104X
          [4X    return 0;[104X
          [4X}[104X
          [4X[104X
        [4X[32X[104X
  
        [33X[0;6YThis  code  should  be  placed  somewhere  in the file [11Xstring.c[111X before
        specifying [10XGvarFuncs[110X.[133X
  
  [31X2[131X   [33X[0;6YIn  the same file [11Xstring.c[111X find the list of functions to export called
        [10XGvarFuncs[110X and add to this list a table entry for [10XHELLO_WORLD[110X[133X
  
  [4X      [32X[104X
          [4X[104X
          [4XGVAR_FUNC(HELLO_WORLD, 0, ""),[104X
          [4X[104X
        [4X[32X[104X
  
        [33X[0;6Ycontaining respectively the string specifying the name of the function
        at  the  [5XGAP[105X  level,  the  number  of  arguments,  the string with the
        description  of  arguments,  corresponding  [5XC[105X  handler  and the string
        ([21Xcookie[121X)  specifying  the  location of this handler (see definition of
        the structure [10XStructGVarFunc[110X in the file [11Xsystem.h[111X ).[133X
  
  [31X3[131X   [33X[0;6YCompile the [5XGAP[105X kernel, and now [10XHELLO_WORLD();[110X will work.[133X
  
  [4X      [32X  Example  [32X[104X
          [4X[28X[128X[104X
          [4X[25Xgap>[125X [27XHELLO_WORLD();[127X[104X
          [4X[28XHello World![128X[104X
          [4X[28X[128X[104X
        [4X[32X[104X
  
  
  [1X2.3 [33X[0;0YStructure of the [5XGAP[105X[101X[1X kernel[133X[101X
  
  [33X[0;0YThe  following  picture  is based on the scheme that Martin Schönert drew in
  1995     and     displays    the    structure    of    the    [5XGAP[105X    kernel:
  ------------------------------------------------------------------------------------
  |                                 gap-main                                 |
  |----------------------------------------------------------------------------------|
  |   interpreter/coder/  |  r  |  |  expressions/statements/vars/  |  e  |  |
  funcs/calls/compiler                  |                  a                 |
  |===========================================================================||
  d | | arithmetic: | lists: | calls/opers: | records: | miscellaneous: || e |
  |  *integers | *plain lists | *calls | *plain | *words || r | | *rationals |
  *blists  |  *opers  |  records | *packed vectors || --- | | *finite fields |
  *ranges  |  *types  |  |  *coset enum || s | | *permutations | *list opers |
  *method  |  |  *deep  thought  ||  c  | | *floats | *vectors | selection | |
  *collectors  ||  a  |  |  *cyclotomics  |  *sets | | | *save/load ws || nn |
  |===========================================================================||
  e           |           |           objects          |          r          |
  |----------------------------------------------------------------------------------|
  |                                  gasman                                  |
  |----------------------------------------------------------------------------------|
  |                                  system                                  |
  ------------------------------------------------------------------------------------
  The         2nd         line         of        the        scheme,        the
  "interpreter/coder/expressions/statements/vars/funcs/calls/compiler"   level
  is  essentially  the  [5XGAP[105X runtime system. It takes in [5XGAP[105X code and (possibly
  after  parsing  and  storing  it)  executes it by calling functions from the
  modules  below.  The  GAP  compiler is (a sort of) a drop in replacement for
  this, and there could be others, such as a bytecode generator/interpreter.[133X
  
  [33X[0;0YIn  the region within the thick lines the kernel code sees the same world as
  [5XGAP[105X  code:  it sees objects (including functions), with automatic management
  of  memory occupied by them. The only difference is that the kernel code can
  look, if necessary, inside the binary content of the objects.[133X
  
  [33X[0;0YUnevaluated  expressions  or  fragments of the [5XGAP[105X code never appear in this
  region  and  below  it. Therefore, there are only a few ways to pass control
  back from that level:[133X
  
  [30X    [33X[0;6YCalling a [5XGAP[105X function;[133X
  
  [30X    [33X[0;6YEntering a break loop;[133X
  
  [30X    [33X[0;6YReading a file.[133X
  
  
  [1X2.4 [33X[0;0YGarbage collection in [5XGAP[105X[101X[1X[133X[101X
  
  
  [1X2.4-1 [33X[0;0Y[5XGASMAN[105X[101X[1X[133X[101X
  
  [33X[0;0Y[5XGASMAN[105X is the [5XGAP[105X memory manager. It provides an API dealing with [13XBags[113X which
  are  areas of memory, each with a size and a [10XTNUM[110X (type number) in the range
  0--253 (type numbers are defined in the file [11Xobjects.h[111X; there are some spare
  numbers  reserved for further extensions; types 254 and 255 are reserved for
  [5XGASMAN[105X. See Section [14X2.6[114X for more details).[133X
  
  [33X[0;0YBags  have  stable handles (of [5XC[105X type [10XBag[110X) and can be resized. When the heap
  is  full, inaccessible bags are automatically reclaimed and live bags may be
  moved, but the handles don't change (handle is a pointer to a pointer to the
  actual data). Bag references from [5XC[105X local variables are found automatically,
  and  references  from [5XC[105X static and global variables must be declared. [5XGASMAN[105X
  recovers  unreachable  bags  automatically  -- it knows that bags in [5XC[105X local
  variables  [13Xare[113X  reachable.  From  the  point of GC technicalities, [5XGASMAN[105X is
  generational,  conservative,  compacting (i.e. bags may move, but each has a
  permanent  ID)  and cooperative (i.e. it imposes certain rules on its users)
  memory manager.[133X
  
  [33X[0;0YTo get the type of the bag with the identifier [10Xb[110X, call [10XTNUM_BAG(b)[110X.[133X
  
  [33X[0;0YThe application specifies the type of a bag when it allocates it with [10XNewBag[110X
  and  may  later  change  it  with  [10XRetypeBag[110X  (see  [10XNewBag[110X  and [10XRetypeBag[110X in
  [11Xgasman.h[111X).[133X
  
  [33X[0;0Y[5XGASMAN[105X  needs  to  know the type of a bag so that it knows which function to
  call  to mark all subbags of a given bag (see [10XInitMarkFuncBags[110X below). Apart
  from that [5XGASMAN[105X does not care at all about types.[133X
  
  
  [1X2.4-2 [33X[0;0Y[5XGASMAN[105X[101X[1X Interface[133X[101X
  
  [33X[0;0Y[10XBag[110X is a type definition of some sort of pointer. It may be used as[133X
  
  [4X[32X[104X
    [4X[104X
    [4XBag bag = NewBag(type, size);[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0YCreation  of  a  new  bag may cause garbage collection, and [5XGAP[105X will fail if
  space cannot be allocated.[133X
  
  [33X[0;0YTo reach the data in a bag, call[133X
  
  [4X[32X[104X
    [4X[104X
    [4XBag *ptr = PTR_BAG(bag);[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0Yand keep in mind that the cost of such call is one indirection.[133X
  
  [33X[0;0YThe  [13Xkey  rule[113X  is that you must NOT hold onto this pointer during any event
  which might cause a garbage collection. A common hidden trap is to use[133X
  
  [4X[32X[104X
    [4X[104X
    [4XPTR_BAG(list)[1] = NewBag(t,s);[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0Ybecause  the pointer may be evaluated before the right-hand side evaluation,
  and used after it. Instead of this, you should use[133X
  
  [4X[32X[104X
    [4X[104X
    [4X{[104X
    [4X  Obj temp = NewBag(t,s);[104X
    [4X  PTR_BAG(list)[1] = temp;[104X
    [4X}[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0YThere  is  a second rule: after you assigned a bag identifier [10Xb[110X into a bag [10Xc[110X
  and before the next garbage collection, you must call [10XCHANGED_BAG(c)[110X, unless
  you  know  that  [10Xb[110X  cannot  be  garbage collected (e.g. it is an object like
  [9Xtrue[109X), or [10Xc[110X is the most recently allocated bag of all.[133X
  
  [33X[0;0YOther functions are:[133X
  
  [30X    [33X[0;6Y[10XRetypeBag(  bag, newtnum )[110X changes the type of the bag with identifier
        [10Xbag[110X  to  the  new type [10Xnewtnum[110X. The identifier, the size, and also the
        address of the data area of the bag do not change.[133X
  
  [30X    [33X[0;6Y[10XResizeBag(  bag, newsize )[110X changes the size of the bag with identifier
        [10Xbag[110X  to  the  new  size  [10Xnewsize[110X.  The  identifier of the bag does not
        change, but the address of the data area of the bag may change. If the
        new size is less than the old size, [5XGASMAN[105X throws away any data in the
        bag  beyond the new size. If the new size is larger than the old size,
        it  extends  the  bag.  Note  that  [10XResizeBag[110X  will  perform a garbage
        collection  if  no  free  storage  is  available.  During  the garbage
        collection  the addresses of the data areas of all bags may change. So
        you  must not keep any pointers to or into the data areas of bags over
        calls to [10XResizeBag[110X (see [10XPTR_BAG[110X in [11Xgasman.h[111X).[133X
  
  [30X    [33X[0;6Y[10XInitMarkFuncBags(  type,  mark-func  )[110X(optional) installs the function
        [10Xmark-func[110X  as  marking function for bags of type [10Xtype[110X. The application
        [13Xmust[113X install a marking function for a type before it allocates any bag
        of that type.[133X
  
        [33X[0;6YA marking function returns nothing. It just takes a single argument of
        type  [10XBag[110X and applies the function [10XMarkBag[110X to each bag identifier that
        appears  in  the  bag. During garbage collection marking functions are
        applied  to  each  marked bag (i.e. to all bags that are assumed to be
        still  live),  to  also  mark  their  subbags.  The ability to use the
        correct marking function is the only use that [5XGASMAN[105X has for types.[133X
  
        [33X[0;6Y[10XMarkBag(b)[110X  marks  the  bag  [10Xb[110X  as  live so that it is not thrown away
        during  a garbage collection. It tests if [10Xbag[110X is a valid identifier of
        a bag in the young bags area. If it is not, then [10XMarkBag[110X does nothing,
        so there is no harm in calling it for something that is not actually a
        bag  identifier.  It  is  important that [10XMarkBag[110X should only be called
        from the marking functions installed with [10XInitMarkFuncBags[110X.[133X
  
        [33X[0;6Y[10XMarkBagWeakly[110X is an alternative to [10XMarkBag[110X, intended to be used by the
        marking  functions of weak pointer objects. A bag which is marked both
        weakly and strongly is treated as strongly marked. A bag which is only
        weakly  marked  will  be  recovered  by  garbage  collection,  but its
        identifier  remains,  marked  in  a  way  which  can  be  detected  by
        [10XIsWeakDeadBag[110X.  This  should always be checked before copying or using
        such an identifier.[133X
  
        [33X[0;6Y[5XGASMAN[105X  already  provides  the  following  standard  marking functions
        defined in [11Xgasman.c[111X:[133X
  
        [30X    [33X[0;12Y[10XMarkNoSubBags(  bag )[110X is a marking function for types whose bags
              contain  no  identifier  of  other bags. It does nothing, as its
              name  implies,  and  simply  returns.  For example, the bags for
              large  integers  contain  only  the digits and no identifiers of
              bags.[133X
  
        [30X    [33X[0;12Y[10XMarkOneSubBags( bag )[110X is a marking function for types whose bags
              contain  exactly  one  identifier  of  another  bag as the first
              entry.  It  marks this subbag and returns. For example, bags for
              finite field elements contain exactly one bag identifier for the
              finite field the element belongs to.[133X
  
        [30X    [33X[0;12Y[10XMarkTwoSubBags( bag )[110X is a marking function for types whose bags
              contain  exactly  two identifiers of other bags as the first and
              second  entry such as the binary operations bags. It marks those
              subbags  and  returns.  For  example,  bags for rational numbers
              contain  exactly  two  bag identifiers for the numerator and the
              denominator.[133X
  
        [30X    [33X[0;12Y[10XMarkAllSubBags(  bag  )[110X  is the marking function for types whose
              bags  contain  only identifiers of other bags (for example, bags
              or  lists  contain  only bag identifiers for the elements of the
              list  or  0  if  an entry has no assigned value). [10XMarkAllSubBags[110X
              marks  every  entry  of  such  a  bag.  Note that [10XMarkAllSubBags[110X
              assumes  that all identifiers are at offsets from the address of
              the  data  area  of [10Xbag[110X that are divisible by [10Xsizeof(Bag)[110X. Also,
              since  it  does  not  do any harm to mark something which is not
              actually  a bag identifier, one could use [10XMarkAllSubBags[110X for all
              types  as  long as the identifiers in the data area are properly
              aligned  as  explained  above  (this  would  however  slow  down
              [10XCollectBags[110X).  By  default,  [5XGASMAN[105X  uses  [10XMarkAllSubBagsDefault[110X
              which does exactly this.[133X
  
  
  [1X2.4-3 [33X[0;0YThe GASMAN Interface for Weak Pointer Objects[133X[101X
  
  [33X[0;0YThe  key  support  for  weak  pointers  is  in  the  files  [11Xsrc/gasman.c[111X and
  [11Xsrc/gasman.h[111X.  This  document  assumes  familiarity  with  the  rest  of the
  operation  of GASMAN. A kernel type (tnum) of bags which are intended to act
  as  weak  pointers  to their subobjects must meet three conditions. Firstly,
  the  marking  function  installed  for  that tnum must use [10XMarkBagWeakly[110X for
  those  subbags,  rather  than [10XMarkBag[110X. Secondly, before any access to such a
  subbag,  it  must  be checked with [10XIsWeakDeadBag[110X. If that returns [9Xtrue[109X, then
  the  subbag  has  evaporated  in a recent garbage collection and must not be
  accessed.  Typically  the  reference  to  it  should  be removed. Thirdly, a
  [13Xsweeping  function[113X  must  be  installed  for that tnum which copies the bag,
  removing all references to dead weakly held subbags.[133X
  
  [33X[0;0YThe files [11Xsrc/weakptr.c[111X and [11Xsrc/weakptr.h[111X use this interface to support weak
  pointer objects. Other objects with weak behaviour could be implemented in a
  similar way.[133X
  
  
  [1X2.5 [33X[0;0YInterfaces[133X[101X
  
  [33X[0;0YThe  modules  at  the  bottom  of the picture from the section [14X2.3[114X ([13Xobjects[113X,
  [13Xgasman[113X  and  [13Xsystem[113X),  and white boxes ([13Xarithmetic[113X, [13Xlists[113X, [13Xcalls/operations[113X,
  [13Xrecords[113X) provide interfaces intended for use in the kernel.[133X
  
  [33X[0;0YFor  example [11Xariths.h[111X provides functions like [10XSUM[110X, [10XPROD[110X, [10XAINV[110X, corresponding
  to  the  GAP  operations [10X+[110X, [10X*[110X and unary [10X-[110X. These functions can be applied to
  any  values  (objects)  to perform an appropriate action. Note that there is
  some  overhead  in  using  these  general  functions,  if you know what your
  arguments are, there may be faster ways.[133X
  
  [33X[0;0YAnother  interface  provides [10XELM_LIST[110X, [10XASS_LIST[110X, [10XLEN_LIST[110X, etc. as a general
  interface to any type of list.[133X
  
  [33X[0;0YFunctions  like  these will even work for [5XGAP[105X-level objects whose arithmetic
  or list operations are implemented by installed methods.[133X
  
  [33X[0;0YAdding  a kernel function is easy if it stays in the region within the thick
  lines,  i.e.  it  uses interfaces from white and yellow areas, which provide
  kernel equivalents to the basic GAP functionality.[133X
  
  [33X[0;0YFor  example, the following kernel function will return a list containing an
  object, its square and its cube:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28X[128X[104X
    [4X[28X/*  x -> [x,x^2,x^3]  */[128X[104X
    [4X[28Xstatic Obj FuncFoo1(Obj self, Obj x)[128X[104X
    [4X[28X{[128X[104X
    [4X[28X    Obj x2, x3;[128X[104X
    [4X[28X    Obj list = NEW_PLIST( T_PLIST, 3 );[128X[104X
    [4X[28X    SET_ELM_PLIST( list, 1, x );[128X[104X
    [4X[28X    CHANGED_BAG( list );[128X[104X
    [4X[28X[128X[104X
    [4X[28X    x2 = PROD( x, x );[128X[104X
    [4X[28X    SET_ELM_PLIST( list, 2, x2 );[128X[104X
    [4X[28X    CHANGED_BAG( list );[128X[104X
    [4X[28X[128X[104X
    [4X[28X    x3 = PROD( x2, x );[128X[104X
    [4X[28X    SET_ELM_PLIST( list, 3, x3 );[128X[104X
    [4X[28X    CHANGED_BAG( list );[128X[104X
    [4X[28X[128X[104X
    [4X[28X    SET_LEN_PLIST(list, 3);[128X[104X
    [4X[28X    return list;[128X[104X
    [4X[28X}[128X[104X
    [4X[28X[128X[104X
  [4X[32X[104X
  
  [33X[0;0YIf  speed  is not of utmost importance, then it is usually better to use the
  [10XASS_LIST[110X etc. functions instead of [10XSET_ELM_PLIST[110X and friends, which are more
  low-level  and  easier  to  misuse.  For  example,  they  automatically call
  [10XCHANGED_BAG[110X  and  [10XSET_LEN_PLIST[110X.  Then  the  above example would become this
  instead:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28X[128X[104X
    [4X[28X/*  x -> [x,x^2,x^3]  */[128X[104X
    [4X[28Xstatic Obj FuncFoo2(Obj self, Obj x)[128X[104X
    [4X[28X{[128X[104X
    [4X[28X    Obj x2, x3;[128X[104X
    [4X[28X    Obj list = NEW_PLIST( T_PLIST, 3 );[128X[104X
    [4X[28X    ASS_LIST( list, 1, x );[128X[104X
    [4X[28X[128X[104X
    [4X[28X    x2 = PROD( x, x );[128X[104X
    [4X[28X    ASS_LIST( list, 2, x2 );[128X[104X
    [4X[28X[128X[104X
    [4X[28X    x3 = PROD( x2, x );[128X[104X
    [4X[28X    ASS_LIST( list, 3, x3 );[128X[104X
    [4X[28X[128X[104X
    [4X[28X    return list;[128X[104X
    [4X[28X}[128X[104X
    [4X[28X[128X[104X
  [4X[32X[104X
  
  [33X[0;0YFinally,  if  all  you want to do is produce a list of fixed length, you can
  use the [10XNewPlistFromArgs[110X helper function:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28X[128X[104X
    [4X[28X/*  x -> [x,x^2,x^3]  */[128X[104X
    [4X[28XObj FuncFoo3(Obj self, Obj x)[128X[104X
    [4X[28X{[128X[104X
    [4X[28X    Obj x2 = PROD( x, x );[128X[104X
    [4X[28X    Obj x3 = PROD( x2, x );[128X[104X
    [4X[28X    return NewPlistFromArgs( x, x2, x3 );[128X[104X
    [4X[28X}[128X[104X
    [4X[28X[128X[104X
  [4X[32X[104X
  
  
  [1X2.6 [33X[0;0YObjects and API[133X[101X
  
  [33X[0;0YThe  kernel  representation  of every [5XGAP[105X object is an object of [5XC[105X type [10XObj[110X.
  Objects  are  defined  in  the  file  [11Xobjects.h[111X.  Objects  are actually [13Xbags[113X
  (represented  by  their  handles),  small  integers  and  small finite field
  elements (represented by values that could not be valid handles). [10XBag[110X is the
  type of bag identifiers, defined in the file [11Xsystem.h[111X:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28X[128X[104X
    [4X[28Xtypedef UInt * *        Bag;[128X[104X
    [4X[28X[128X[104X
  [4X[32X[104X
  
  [33X[0;0YEach  bag is identified by its [13Xbag identifier[113X, and no two live bags have the
  same identifier.[133X
  
  [33X[0;0YNote  that the identifier of a bag is different from the address of the data
  area  of  the bag. This address may change during a garbage collection while
  the identifier of a bag never changes. Bags that contain references to other
  bags  must  always  contain  the  identifiers of these other bags, never the
  addresses of the data areas of the bags.[133X
  
  [33X[0;0YNote that bag identifiers are recycled. That means that after a bag dies its
  identifier may be reused for a new bag.[133X
  
  [33X[0;0Y0  is  a  valid  value  of  the  type  [10XBag[110X,  but is guaranteed not to be the
  identifier of any bag.[133X
  
  [33X[0;0YThe ability to distinguish between bags and other objects relies on the fact
  that all bag identifiers are divisible by 4.[133X
  
  [33X[0;0YThere  are  lots  of  kernel API functions providing a uniform interface for
  working with objects:[133X
  
  [30X    [33X[0;6Y[10XTNUM_OBJ[110X  (first  level type), [10XSIZE_OBJ[110X, [10XADDR_OBJ[110X (C pointer to data),
        [10XTYPE_OBJ[110X (full type)[133X
  
  [30X    [33X[0;6Y[10XIS_MUTABLE_OBJ[110X, [10XMakeImmutable[110X, [10XCOPY_OBJ[110X, ...[133X
  
  [30X    [33X[0;6Y[10XPRINT_OBJ[110X[133X
  
  [30X    [33X[0;6Y[10XNEW_PLIST[110X, [10XSET_ELM_PLIST[110X, etc. for creating plain lists[133X
  
  [30X    [33X[0;6Y[10XPROD[110X for arithmetic (see also [10XSUM[110X, [10XDIFF[110X, etc.)[133X
  
  [33X[0;0YThese  functions are flexible: for example, [10XPROD[110X will multiply anything, but
  if  you  know what objects you will have it will be a bit faster to call the
  multiplication directly.[133X
  
  [33X[0;0YTypical  implementation  is  a  table  of functions indexed by [10XTNUM_OBJ[110X. For
  example, this is the definition of [10XPROD[110X in the file [11Xariths.h[111X (you can safely
  ignore the [10XEXPORT_INLINE[110X for now):[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28X[128X[104X
    [4X[28XEXPORT_INLINE Obj PROD(Obj opL, Obj opR)[128X[104X
    [4X[28X{[128X[104X
    [4X[28X    UInt tnumL = TNUM_OBJ(opL);[128X[104X
    [4X[28X    UInt tnumR = TNUM_OBJ(opR);[128X[104X
    [4X[28X    return (*ProdFuncs[tnumL][tnumR])(opL, opR);[128X[104X
    [4X[28X}[128X[104X
    [4X[28X[128X[104X
  [4X[32X[104X
  
  [33X[0;0YAdditionally, [11Xobjects.h[111X also defines symbolic names for TNUMs.[133X
  
  [33X[0;0YThere  are  lots  of other API functions for strings, general lists, calling
  functions, etc.[133X
  
  
  [1X2.6-1 [33X[0;0YImmediate Integers and FFEs[133X[101X
  
  [33X[0;0YThere  are  three  integer  types in GAP: [10XT_INT[110X, [10XT_INTPOS[110X and [10XT_INTNEG[110X. Each
  integer   has  a  unique  representation,  e.g.,  an  integer  that  can  be
  represented as [10XT_INT[110X is never represented as [10XT_INTPOS[110X or [10XT_INTNEG[110X.[133X
  
  [33X[0;0Y[10XT_INT[110X  is the type of those integers small enough to fit into 29 bits (on 32
  bit  systems)  respectively 61 bits (on 64 bit systems). Therefore the value
  range  of this small integers is [22X-2^28...2^28-1[122X respectively [22X-2^60...2^60-1[122X.
  Only these small integers can be used as index expression into sequences.[133X
  
  [33X[0;0YSmall  integers  are  represented by an immediate integer handle, containing
  the value instead of pointing to it, which has the format [10Xss<28 data bits>01[110X
  respectively [10Xss<60 data bits>01[110X.[133X
  
  [33X[0;0YImmediate  integers  handles  carry  the  tag [10XT_INT[110X, i.e. the last bit is 1.
  Thus, the last bit distinguishes immediate integers from other handles which
  point to structures aligned on 4 byte (on 32 bit) respectively 8 byte (on 64
  bit)  boundaries  and therefore have last bit zero. (The bit before the last
  is  reserved as tag to allow extensions of this scheme.) Using immediates as
  pointers and dereferencing them gives address errors.[133X
  
  [33X[0;0YThe  first two bits [10Xss[110X are two copies of the sign bit. That is, the sign bit
  of  immediate  integers  has  a  guard  bit,  that allows quick detection of
  overflow for addition since these two bits must always be equal.[133X
  
  [33X[0;0YFunctions  [10XIS_INTOBJ[110X  and  [10XARE_INTOBJS[110X are used to test if an object (or two
  objects)  is an (immediate) integer object. The functions [10XINTOBJ_INT[110X is used
  to  convert  a [5XC[105X integer to an (immediate) integer object, and [10XINT_INTOBJ[110X is
  used  to  convert  the  (immediate)  integer  object  to  a [5XC[105X integer. These
  functions do NOT check for overflows.[133X
  
  [33X[0;0YThe  other  two  integer  types  are  [10XT_INTPOS[110X  and  [10XT_INTNEG[110X  for  positive
  (respectively,  negative)  integer  values  that  cannot  be  represented by
  immediate integers. See comments in [11Xinteger.c[111X for details.[133X
  
  [33X[0;0YOther  immediate  objects  are  [13Xfinite  field  elements[113X  (FFEs).  The kernel
  supports small finite fields with up to 65536 elements (larger fields can be
  realized  as  polynomial  domains  over  smaller fields). Immediate FFEs are
  represented  in  the  format  [10X<16  bit value><13 bit field ID>010[110X, where the
  least  significant  3  bits  of  such  an  immediate  object are always 010,
  flagging the object as an object of a small finite field.[133X
  
  [33X[0;0YThe  next  13  bits represent the small finite field where the element lies,
  and they are simply an index into a global table of small finite fields.[133X
  
  [33X[0;0YThe most significant 16 bits represent the value of the element.[133X
  
  [33X[0;0YIf  the  value  is  0,  then  the element is the zero from the finite field.
  Otherwise  the  integer  is  the logarithm of this element with respect to a
  fixed generator of the multiplicative group of the finite field plus one. In
  the  following descriptions we denote this generator always with [22Xz[122X, it is an
  element  of  order [22Xord-1[122X, where [22Xord[122X is the order of the finite field. Thus 1
  corresponds  to  [22Xz^1-1  =  z^0 = 1[122X, i.e., the one from the field. Likewise 2
  corresponds to [22Xz^2-1 = z^1 = z[122X, i.e., the root itself.[133X
  
  [33X[0;0YThis  representation makes multiplication very easy, we only have to add the
  values  and  subtract  1  , because [22Xz^a-1 * z^b-1 = z^(a+b-1)-1[122X. Addition is
  reduced  to  multiplication by the formula [22Xz^a + z^b = z^b * (z^a-b+1)[122X. This
  makes it necessary to know the successor [22Xz^a + 1[122X of every value.[133X
  
  [33X[0;0YThe  finite  field bag contains the successor for every nonzero value, i.e.,
  [10XSUCC_FF(<ff>)[<a>][110X  is  the  successor  of  the  element [10X<a>[110X, i.e, it is the
  logarithm  of  [22Xz^a-1  +  1[122X.  This  list is usually called the Zech-Logarithm
  table.  The  zeroth entry in the finite field bag is the order of the finite
  field minus one.[133X
  
  [33X[0;0Y[10XT_INT[110X and [10XT_FFE[110X are reserved [10XTNUM[110Xs for immediate integers and FFEs. [10XTNUM_OBJ[110X
  produces them if needed and otherwise calls [10XTNUM_BAG[110X.[133X
  
  [33X[0;0YThe  kernel  design  allows that other immediate types could be added in the
  future.[133X
  
  
  [1X2.6-2 [33X[0;0YArithmetics[133X[101X
  
  [33X[0;0YArithmetic operations package is implemented in files [11Xariths.h[111X and [11Xariths.c[111X.
  In  particular,  it defines functions like [10XSUM(obj1, obj2)[110X, [10XDIFF[110X, [10XPROD[110X etc.,
  which  accept  (and  may  return)  objects  of any kind, including immediate
  objects. Selection of the appropriate method is handled via calling [10XTNUM_OBJ[110X
  for  arguments  and  then  calling  the appropriate method from the table of
  functions, for example:[133X
  
  [4X[32X[104X
    [4X[104X
    [4XEXPORT_INLINE Obj SUM(Obj opL, Obj opR)[104X
    [4X{[104X
    [4X    UInt tnumL = TNUM_OBJ(opL);[104X
    [4X    UInt tnumR = TNUM_OBJ(opR);[104X
    [4X    return (*SumFuncs[tnumL][tnumR])(opL, opR);[104X
    [4X}[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0YThe default entry of the table of functions just calls back to the [5XGAP[105X level
  to look for the installed methods (see e.g. [10XSumObject[110X in [11Xariths.c[111X), but note
  that kernel methods installed in tables [13XOVERRIDE[113X [5XGAP[105X installed methods.[133X
  
  [33X[0;0YIf  you  expect  to  handle  mainly small integers, then it is significantly
  faster to do:[133X
  
  [4X[32X[104X
    [4X[104X
    [4Xif ( ! ARE_INTOBJS( <opL>, <opR> ) || ! SUM_INTOBJS( <res>, <opL>, <opR> ) )[104X
    [4X    <res> = SUM( <opL>, <opR> );[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0Yinstead of [10X<res> = SUM(<opL>, <opR>)[110X, where [10XSUM_INTOBJS[110X is a function, which
  returns 0 if the answer overflows and a large integer needs to be created.[133X
  
  [33X[0;0YFinally,  note  that  lots of functions in [11Xariths.h[111X called [10XC_<something>[110X are
  used mainly by the compiler.[133X
  
  
  [1X2.6-3 [33X[0;0YFunctions[133X[101X
  
  [33X[0;0YThe  function  call  mechanism  package  is implemented in files [11Xcalls.h[111X and
  [11Xcalls.c[111X.  A  function  object  in  [5XGAP[105X  is  represented by a bag of the type
  [10XT_FUNCTION[110X.  The  bag  for  the  function  [10Xf[110X  contains  eight  pointers fo [5XC[105X
  functions  -  its  handlers.  These  eight  functions  are  for  0,1,2,...,6
  arguments and X arguments respectively, and the [22Xi[122X-th handler can be accessed
  using  the  function  [10XHDLR_FUNC(f,  i)[110X.  This  is  exactly  what  is done by
  functions  [10XCALL_0ARGS[110X,  [10XCALL_1ARGS[110X,  ...,  [10XCALL_6ARGS[110X  and [10XCALL_XARGS[110X, which
  simply  call  the  appropriate  handlers,  passing  the function bag and the
  arguments.  [10XCALL_0ARGS[110X  is for calls passing no arguments, [10XCALL_1ARGS[110X is for
  calls  passing  one  argument, and so on. Thus, the kernel equivalent of the
  GAP  code  [10Xr  :=  f(a,b)[110X  is  [10Xr = CALL_2ARGS(f,a,b)[110X. [10XCALL_XARGS[110X is for calls
  passing more than 6 arguments or for variadic functions, and it requires the
  arguments to be collected in a single plain list.[133X
  
  [33X[0;0YThere  is  a  range of standard handlers that deal with calls to regular [5XGAP[105X
  functions,  to operations, attributes and properties and that also deal with
  [5XGAP[105X variadic functions given as [10Xfunction(arg)[110X.[133X
  
  [33X[0;0YFor  kernel  functions,  the  handler  is the actual function which does the
  work. A typical handler (for 1-argument function) looks like[133X
  
  [4X[32X[104X
    [4X[104X
    [4XObj FuncLength(Obj self, Obj list)[104X
    [4X{[104X
    [4X    return INTOBJ_INT(LEN_LIST(list));[104X
    [4X}[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0YOften the handler has to do some checks on arguments as well. In the example
  above  [10XLEN_LIST[110X  takes  care  of  this  (mainly  because  the jump table for
  [10XLEN_LIST[110X  contains  error  functions  for  non-lists). Every handler must be
  registered  (once) with a unique [21Xcookie[121X by calling [10XInitHandlerFunc( handler,
  cookie  )[110X before it is installed in any function bag. This is needed so that
  it  can  be  identified  when  loading a saved workspace. [3Xcookie[103X should be a
  unique [5XC[105X string, identifying the handler.[133X
  
  [33X[0;0YTo  create  a  function  object,  there  are  three  functions  [10XNewFunction[110X,
  [10XNewFunctionC[110X, and [10XNewFunctionT[110X, defined in the file [11Xcalls.c[111X.[133X
  
  [33X[0;0Y[10XNewFunction(  name,  narg,  nams, hdlr )[110X creates and returns a new function.
  [3Xname[103X  must be a [5XGAP[105X string containing the name of the function. [3Xnarg[103X must be
  the  number of arguments, where -1 indicates a variable number of arguments.
  [3Xnams[103X  must be a [5XGAP[105X list containing the names of the arguments. [3Xhdlr[103X must be
  the  [5XC[105X  function (accepting [3Xself[103X and the [3Xnarg[103X arguments) that will be called
  to execute the function.[133X
  
  [33X[0;0Y[10XNewFunctionC[110X  does  the  same as [10XNewFunction[110X, but expects [3Xname[103X and [3Xnams[103X as [5XC[105X
  strings.  [10XNewFunctionT[110X  also does the same as [10XNewFunction[110X, but has two extra
  arguments that allow to specify the [3Xtype[103X and [3Xsize[103X of the newly created bag.[133X
  
  [33X[0;0YFor example, you can make a function object using the code like this:[133X
  
  [4X[32X[104X
    [4X[104X
    [4Xlenfunc = NewFunctionC("Length", 1, "list", FuncLength);[104X
    [4X[104X
  [4X[32X[104X
  
  
  [1X2.6-4 [33X[0;0YLists[133X[101X
  
  [33X[0;0YThe  [5XGAP[105X  kernel  provides  a generic list interface, which is equivalent to
  using  [10Xlist[i][110X  etc.  in  the library. This interface works for all types of
  lists  known  to GAP, including virtual lists. It has functions like [10XIS_LIST[110X
  (returns  [5XC[105X  Boolean),  [10XLEN_LIST[110X  (returns  [5XC[105X  integer), [10XISB_LIST[110X, [10XELM_LIST[110X,
  [10XELM0_LIST(  <list>,  <pos> ) [110X (returns 0 if <list> has no assigned object at
  position  <pos>) and [10XASS_LIST[110X, defined in the file [11Xlists.h[111X Implementation of
  these functions is done via tables of functions indexed by TNUM.[133X
  
  [33X[0;0YNevertheless,  it  will  be  not much faster to write your [5XC[105X code using such
  functions,  for  example,  to reverse an arbitrary list, than to do the same
  working  in  [5XGAP[105X. However, in case of [13Xplain lists[113X coding in [5XC[105X actually ought
  to produce some speedup.[133X
  
  [33X[0;0YA  plain  list  is  a  list  that may have holes and may contain elements of
  arbitrary  types.  A  plain  list may also have room for elements beyond its
  current  logical  length.  The  last  position  to  which  an element can be
  assigned without resizing the plain list is called the physical length.[133X
  
  [33X[0;0YIf  you  need to create a plain list, use [10XNEW_PLIST(<tnum>,<plength>)[110X, where
  [10X<tnum>[110X  should  be  [10XT_PLIST_<something>[110X, and [10X<plength>[110X is physical length in
  bags. Furthermore, [10XLEN_PLIST[110X gets its logical length, and [10XSET_LEN_PLIST[110X sets
  its logical length. Note that [10XELM_PLIST[110X is faster than [10XELM_LIST[110X.[133X
  
  
  [1X2.6-5 [33X[0;0YData objects[133X[101X
  
  [33X[0;0Y[13XPositional[113X  and  [13XComponent[113X  objects  are  made  from lists and records using
  [10XObjectify[110X.  They  contain  their  [13XType[113X  and  data accessible with [10X![][110X and [10X!.[110X
  operations.[133X
  
  [33X[0;0Y[13XData  objects[113X  also  contain their [13XType[113X, but the data is only accessible via
  kernel  functions.  Data can be anything you like [13Xexcept[113X bag references. The
  garbage  collector  doesn't  see inside them. At a minimum, construction and
  basic  access  functions  need  to  be  written  in the kernel. For example,
  compressed vectors are done this way.[133X
  
  
  [1X2.7 [33X[0;0YRules of Kernel Programming[133X[101X
  
  
  [1X2.7-1 [33X[0;0YThree golden rules[133X[101X
  
  [33X[0;0YThree golden rules of [5XGAP[105X kernel programming:[133X
  
  [31X1[131X   [33X[0;6YReal  [5XC[105X  pointers into objects (returned by [10XADDR_OBJ[110X) must [13Xnot[113X be held
        across anything that could cause a garbage collection ([13XGC[113X).[133X
  
  [31X2[131X   [33X[0;6YIf  you  add  a  new object to another one (e.g. put it in a list) you
        must  call  [10XCHANGED_BAG[110X on the container, otherwise the new object may
        get lost in a GC.[133X
  
  [31X3[131X   [33X[0;6YDon't  use malloc: actually using it a little bit is usually safe, and
        it's safe if you don't ever want to expand the GAP workspace.[133X
  
  
  [1X2.7-2 [33X[0;0YCommon kernel traps[133X[101X
  
  [33X[0;0YMore things can cause a garbage collection than you expect:[133X
  
  [30X    [33X[0;6Yprinting (might be to string stream)[133X
  
  [30X    [33X[0;6Ygeneric list or record access (might be handled by [5XGAP[105X methods)[133X
  
  [30X    [33X[0;6Yinteger arithmetic (might overflow to large integers)[133X
  
  [33X[0;0YBe careful of things like[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28X[128X[104X
    [4X[28XELM_PLIST(l, 3) = something that might cause GC[128X[104X
    [4X[28X[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThis  expands  in  [5XC[105X  to  [10X*((*l)+3)  = something[110X. The compiler is allowed to
  follow  the  inner  *,  then evaluate the right-hand side, then the outer *.
  This will be broken by the garbage collection.[133X
  
  
  [1X2.7-3 [33X[0;0YOne More Bit of GASMAN interface[133X[101X
  
  [33X[0;0YWhen you store a Bag ID in a [5XC[105X global variable, you must declare the address
  of  the  global  to  [5XGASMAN[105X (so the GC knows that the bag is alive). This is
  done by calling [10XInitGlobalBag[110X passing the address and another "cookie" which
  is used by save/load.[133X
  
  [33X[0;0YThere  are  nice  ways to do all the global and handler initializations from
  tables.[133X
  
  
  [1X2.8 [33X[0;0YThe [5XGAP[105X[101X[1X compiler[133X[101X
  
  
  [1X2.8-1 [33X[0;0YCompiling [5XGAP[105X[101X[1X Code[133X[101X
  
  [33X[0;0YThe  [5XGAP[105X compiler converts [5XGAP[105X code into kernel functions. The compiled code
  then  can be loaded into a running kernel (on UNIX or Mac OS). The resulting
  code  still  has  to do lots of checks, so usually it will not be as fast as
  hand-written  [5XC[105X  program.  The performance gain is significant for code that
  spends  a  lot of time in loops, small integer arithmetic, etc., and will be
  not  significant  if code spends most of its time in the kernel or elsewhere
  in library.[133X
  
  [33X[0;0YIn  the  following example we compile the file [11Xfoo.g[111X and then load it during
  the subsequent [5XGAP[105X session:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28X[128X[104X
    [4X[28X$ cat > foo.g[128X[104X
    [4X[28Xfoo := x -> [x,x^2,x^3];[128X[104X
    [4X[28X$ gac -d -C foo.g[128X[104X
    [4X[28X... compilation to C file ...[128X[104X
    [4X[28X$ gac -d foo.g[128X[104X
    [4X[28X... compilation to .so file ...[128X[104X
    [4X[28X$ ls -l foo.so[128X[104X
    [4X[28X-rwxr-xr-x 1 sal 158 4999 2007-09-11 10:19 foo.so*[128X[104X
    [4X[28X$ gap -b[128X[104X
    [4X[28XGAP4, Version: 4.dev of today, ....[128X[104X
    [4X[25Xgap>[125X [27XLoadDynamicModule("./foo.so");[127X[104X
    [4X[25Xgap>[125X [27XPrint(foo);[127X[104X
    [4X[28Xfunction ( x )[128X[104X
    [4X[28X    <<compiled GAP code>> from foo.g:1[128X[104X
    [4X[28Xend[128X[104X
    [4X[25Xgap>[125X [27Xfoo(3);[127X[104X
    [4X[28X[ 3, 9, 27 ][128X[104X
    [4X[28X[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThe compiler code will look as follows:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28X[128X[104X
    [4X[28X/* return [ x, x ^ 2, x ^ 3 ]; */[128X[104X
    [4X[28Xt_1 = NEW_PLIST( T_PLIST, 3 );[128X[104X
    [4X[28XSET_LEN_PLIST( t_1, 3 );[128X[104X
    [4X[28XSET_ELM_PLIST( t_1, 1, a_x );[128X[104X
    [4X[28XCHANGED_BAG( t_1 );[128X[104X
    [4X[28Xt_2 = POW( a_x, INTOBJ_INT(2) );[128X[104X
    [4X[28XSET_ELM_PLIST( t_1, 2, t_2 );[128X[104X
    [4X[28XCHANGED_BAG( t_1 );[128X[104X
    [4X[28Xt_2 = POW( a_x, INTOBJ_INT(3) );[128X[104X
    [4X[28XSET_ELM_PLIST( t_1, 3, t_2 );[128X[104X
    [4X[28XCHANGED_BAG( t_1 );[128X[104X
    [4X[28XSWITCH_TO_OLD_FRAME(oldFrame);[128X[104X
    [4X[28Xreturn t_1;[128X[104X
    [4X[28X[128X[104X
  [4X[32X[104X
  
  [33X[0;0YNote that the original [5XGAP[105X code (more or less) appears as comments.[133X
  
  [33X[0;0YIf  you want to see or modify the intermediate [5XC[105X code, you can also instruct
  the  compiler  to produce only the [5XC[105X files by using the option [10X-C[110X instead of
  [10X-d[110X.[133X
  
  [33X[0;0YThere  are some known problems with [5XC[105X code produced with the [5XGAP[105X compiler on
  32 bit architectures and used on 64 bit architectures (and vice versa).[133X
  
  [33X[0;0YThere  are  more  ways to exploit the [5XGAP[105X compiler apart from just compiling
  the [5XGAP[105X code:[133X
  
  [30X    [33X[0;6YYou  can  compile  your code and then hand-optimize critical sections.
        For  example, you can replace calls to [10XPOW[110X by calls to [10XPROD[110X or even to
        the  product  function  for  particular  kinds of objects. You must be
        aware of a risk of a segmentation fault if you will call your function
        with wrong arguments.[133X
  
  [30X    [33X[0;6YYou  can  use the compiler to generate a shell that can be dynamically
        loaded,  and then fill in your own [5XC[105X code in this shell. This approach
        is used in [5XBrowse[105X, [5XEDIM[105X and [5XIO[105X packages. In this case you must make it
        sure that your code complies with rules.[133X
  
  
  [1X2.8-2 [33X[0;0YSuitability for Compilation[133X[101X
  
  [33X[0;0YTypically  algorithms spend large parts of their runtime only in small parts
  of  the  code. The design of [5XGAP[105X reflects this situation with kernel methods
  for   many   time  critical  calculations  such  as  matrix  or  permutation
  arithmetic.[133X
  
  [33X[0;0YCompiling  an  algorithm whose time critical parts are already in the kernel
  of  course  will  give disappointing results: Compilation will only speed up
  the  parts  that  are  not already in the kernel and if they make us a small
  part of the runtime, the overall gain is small.[133X
  
  [33X[0;0YRoutines  that  benefit  from  compilation  are  those  which  do  extensive
  operations with basic data types, such as lists or small integers.[133X
  
  
  [1X2.8-3 [33X[0;0YCompiling Library Code[133X[101X
  
  [33X[0;0YThis  subsection describes the mechanism used to make [5XGAP[105X recognize compiled
  versions  of  library  files.  Note  that there is no point in compiling the
  whole  library  as  typically only few functions benefit from compilation as
  described in Section [14X2.8-2[114X.[133X
  
  [33X[0;0YAll  library  files  that  come  with  [5XGAP[105X (not the files that belong to [5XGAP[105X
  packages)  are read using the internal function [10XREAD_GAP_ROOT[110X. This function
  then  checks  whether  a  compiled version of the file exists and if its CRC
  number (see [14X'Reference: CrcFile'[114X) matches the file. If it does, the compiled
  version is loaded. Otherwise the file is read. You can start [5XGAP[105X with the [10X-D
  -N[110X option to see information printed about this process.[133X
  
  [33X[0;0YTo   make  [5XGAP[105X  find  the  compiled  versions,  they  must  be  put  in  the
  [11Xbin/[111X[3Xsystemname[103X[11X/compiled[111X  directory  ([3Xsystemname[103X  is  the  name  you gave for
  compilation,  for  example  [11Xi386-ibm-linux-gcc2[111X).  They  have  to  be called
  according  to  the following scheme: Suppose the file is [11Xhumpty/dumpty.gi[111X in
  the    [5XGAP[105X   home   directory.   Then   the   compiled   version   will   be
  [11Xbin/[111X[3Xsystemname[103X[11X/compiled/humpty/gi/dumpty.so[111X.    That   is,   the   directory
  hierarchy  is  mirrored  under  the  [11Xcompiled[111X directory. A further directory
  level  is  added  for the suffix of the file, and the suffix of the compiled
  version of the file is set to [10X.so[110X (as produced by the compiler).[133X
  
  [33X[0;0YFor  example we show how to compile the [11Xcombinat.gi[111X file on a Linux machine.
  Suppose we are in the home directory of the gap distribution.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28Xbin/i386-ibm-linux-gcc2/gac -d lib/combinat.gi[128X[104X
  [4X[32X[104X
  
  [33X[0;0Ycreates  a file [11Xcombinat.so[111X. We now put it in the right place, creating also
  the necessary directories:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[28Xmkdir bin/i386-ibm-linux-gcc2/compiled[128X[104X
    [4X[28Xmkdir bin/i386-ibm-linux-gcc2/compiled/lib[128X[104X
    [4X[28Xmkdir bin/i386-ibm-linux-gcc2/compiled/lib/gi[128X[104X
    [4X[28Xmv combinat.so bin/i386-ibm-linux-gcc2/compiled/lib/gi[128X[104X
  [4X[32X[104X
  
  [33X[0;0YIf  you  now  start  [5XGAP[105X  and  look,  for  example, at the function [2XBinomial[102X
  ([14XReference:  Binomial[114X),  defined  in  [11Xcombinat.gi[111X,  you  see  it  is  indeed
  compiled:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XDisplay(GaussianCoefficient);[127X[104X
    [4X[28Xfunction ( n, k, q )[128X[104X
    [4X[28X    <<compiled GAP code>> from GAPROOT/lib/combinat.g:26[128X[104X
    [4X[28Xend[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThe  command  line  option  [10X-M[110X  disables the loading of compiled modules and
  always reads code from the library.[133X
  
  
  [1X2.9 [33X[0;0YGlobal Variables[133X[101X
  
  
  [1X2.9-1 [33X[0;0YGlobal variables[133X[101X
  
  [33X[0;0YThe  part  of  the  kernel  that  manages global variables, i.e., the global
  namespace,  is  contained in the files [11Xgvars.h[111X and [11Xgvars.c[111X. Global variables
  have  an  internal form, of type [10XGVar[110X (actually an index into a hash table).
  They  may  be obtained with [10XGVar gv = GVarName(<string>);[110X. A global variable
  may be safely held on to across GC (but not across save/load workspace).[133X
  
  [33X[0;0YTo  manipulate  with  global  variables,  you  may use [10XAssGVar(gv, <obj>)[110X or
  [10XValGVar( gv )[110X (returns 0 if unbound, not an error), etc.[133X
  
  
  [1X2.9-2 [33X[0;0YTracking global variables[133X[101X
  
  [33X[0;0YThe [5XC[105X code[133X
  
  [4X[32X[104X
    [4X[104X
    [4XObj Stuff;[104X
    [4XInitCopyGVar( "stuff", &Stuff );[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0Ycauses [10XStuff[110X to track the value of the global named "stuff". When the global
  is changed, the new value will be put in the [5XC[105X variable.[133X
  
  [33X[0;0YA  useful  refinement is [10XInitFopyGVar[110X. This does the same, provided that the
  value  assigned is a function, otherwise the [5XC[105X variable points to a function
  that prints a suitable error message.[133X
  
  [33X[0;0YThese are usually set up during initialization of a kernel module.[133X
  
  
  [1X2.10 [33X[0;0YThe Kernel Module Structure and interface[133X[101X
  
  
  [1X2.10-1 [33X[0;0YThe Kernel Module Structure[133X[101X
  
  [33X[0;0YApart  from  a  very  small  amount  of  glue,  all of the kernel (including
  compiled GAP code) is organised into modules.[133X
  
  [33X[0;0YBasically  each  module  consists  of  one [10X.c[110X file and one [10X.h[110X file. The file
  [11Xgap.c[111X  contains  the  variable  [10XInitFuncsBuiltinModules[110X which is initialized
  with  a  list  of  functions  such  as [10XInitInfoInt[110X. Each such function, when
  called,  returns a data structure describing a module, which typically looks
  as follows:[133X
  
  [4X[32X[104X
    [4X[104X
    [4X/****************************************************************************[104X
    [4X**[104X
    [4X*F  InitInfoInt() . . . . . . . . . . . . . . . . . . table of init functions[104X
    [4X*/[104X
    [4Xstatic StructInitInfo module = {[104X
    [4X    .type = MODULE_BUILTIN,[104X
    [4X    .name = "integer",[104X
    [4X    .initKernel = InitKernel,[104X
    [4X    .initLibrary = InitLibrary,[104X
    [4X};[104X
    [4X[104X
  [4X[32X[104X
  
  [33X[0;0YThe  first  part is just information, but the functions from [10XinitKernel[110X down
  are the key to the interface to kernel modules.[133X
  
  
  [1X2.10-2 [33X[0;0YThe Kernel Module Interface[133X[101X
  
  [33X[0;0YThe  general  rule  is that if a 0 appears, the function is skipped; indeed,
  you may omit entries which are 0.[133X
  
  [33X[0;0YWhen GAP is starting up, it does the following:[133X
  
  [30X    [33X[0;6YCalls  the [10XinitKernel[110X functions of all those modules that have one. If
        any of them return non-zero then it aborts.[133X
  
  [30X    [33X[0;6YThen calls the [10XinitLibrary[110X functions likewise[133X
  
  [30X    [33X[0;6YThen the [10XcheckInit[110X functions[133X
  
  [33X[0;0YThe other three functions relate to save/load workspace:[133X
  
  [30X    [33X[0;6Y[10XpreSave[110X functions are called before saving.[133X
  
  [30X    [33X[0;6Y[10XpostSave[110X functions (in the reverse order) after saving[133X
  
  [30X    [33X[0;6Y[10XpostRestore[110X  functions are called after a workspace has been loaded to
        finish linking up the kernel and workspace.[133X
  
  
  [1X2.10-3 [33X[0;0YSequences of Events[133X[101X
  
  [33X[0;0YNormal GAP startup (no -L)[133X
  
  [30X    [33X[0;6YAll [10XinitKernel[110X methods called (abort on non-zero return)[133X
  
  [30X    [33X[0;6YAll [10XinitLibrary[110X methods called (abort on non-zero return)[133X
  
  [30X    [33X[0;6YAll [10XcheckInit[110X methods called (abort on non-zero return)[133X
  
  [30X    [33X[0;6Y[10Xinit.g[110X read[133X
  
  [33X[0;0YStartup loading a workspace[133X
  
  [30X    [33X[0;6YAll [10XinitKernel[110X methods called (abort on non-zero return)[133X
  
  [30X    [33X[0;6YWorkspace loaded, global bags and handlers linked up[133X
  
  [30X    [33X[0;6YAll [10XpostRestore[110X methods called (abort on non-zero return)[133X
  
  [30X    [33X[0;6YEnter the main loop[133X
  
  
  [1X2.10-4 [33X[0;0YSaving a Workspace[133X[101X
  
  [30X    [33X[0;6YAll [10XpreSave[110X methods called (recover on non-zero return)[133X
  
  [30X    [33X[0;6YFull garbage collection[133X
  
  [30X    [33X[0;6YAfter  this,  workspace must be "clean" -- no non-objects stored where
        objects are expected (eg in plain lists)[133X
  
  [30X    [33X[0;6YSaved workspace file written[133X
  
  [30X    [33X[0;6YAll [10XpostSave[110X methods called in reverse order[133X
  
  
  [1X2.10-5 [33X[0;0YExcerpts from InitKernel from integer.c[133X[101X
  
  [4X[32X[104X
    [4X[104X
    [4X/****************************************************************************[104X
    [4X**[104X
    [4X*V  GVarFuncs . . . . . . . . . . . . . . . . . . list of functions to export[104X
    [4X*/[104X
    [4Xstatic StructGVarFunc GVarFuncs [] = {[104X
    [4X[104X
    [4X    GVAR_FUNC(QUO_INT, 2, "a, b"),[104X
    [4X    GVAR_FUNC(ABS_INT, 1, "n"),[104X
    [4X    . . .[104X
    [4X    { 0 }[104X
    [4X};[104X
    [4X[104X
    [4X/****************************************************************************[104X
    [4X**[104X
    [4X*F  InitKernel( <module> )  . . . . . . . . initialise kernel data structures[104X
    [4X*/[104X
    [4Xstatic Int InitKernel ([104X
    [4X    StructInitInfo *    module )[104X
    [4X{[104X
    [4X    UInt                t1,  t2;[104X
    [4X[104X
    [4X    /* init filters and functions                                          */[104X
    [4X    InitHdlrFiltsFromTable( GVarFilts );[104X
    [4X    InitHdlrFuncsFromTable( GVarFuncs );[104X
    [4X    . . .[104X
    [4X[104X
  [4X[32X[104X
  
  
  [1X2.10-6 [33X[0;0YCommentary[133X[101X
  
  [30X    [33X[0;6YThe   items   in  the  array  of  [10XStructGVarFunc[110X  objects  define  the
        GAP-callable global functions exported by the module[133X
  
  [30X    [33X[0;6Y[10XInitHdlrFuncsFromTable[110X  initializes  all  the  handlers with the given
        cookies[133X
  
  [30X    [33X[0;6YIn the [10XinitLibrary[110X function of the same model, we see this:[133X
  
  [4X      [32X[104X
          [4X[104X
          [4X/****************************************************************************[104X
          [4X**[104X
          [4X*F  InitLibrary( <module> ) . . . . . . .  initialise library data structures[104X
          [4X*/[104X
          [4Xstatic Int InitLibrary ([104X
          [4X    StructInitInfo *    module )[104X
          [4X{[104X
          [4X    /* init filters and functions                                          */[104X
          [4X    InitGVarFiltsFromTable( GVarFilts );[104X
          [4X    InitGVarFuncsFromTable( GVarFuncs );[104X
          [4X    . . .[104X
          [4X[104X
        [4X[32X[104X
  
  [30X    [33X[0;6YThis  call  [10XInitGVarFuncsFromTable[110X creates the actual function objects
        (in the workspace) using [10XNewFunctionC[110X[133X
  
  [30X    [33X[0;6YIt  also  installs  these  objects in global variables and makes those
        variables read-only[133X
  
  
  [1X2.10-7 [33X[0;0YOther Similar Functions[133X[101X
  
  [30X    [33X[0;6YThere are other support functions for module initialization[133X
  
  [30X    [33X[0;6YDefined in [11Xgap.c[111X[133X
  
  [30X    [33X[0;6Y[10XInitHdlr<xxxx>FromTable[110X and [10XInitGVar<xxxx>FromTable[110X exist for filters,
        attributes, properties and operations[133X
  
  [30X    [33X[0;6YStructure definitions are found in [11Xsystem.h[111X[133X
  
  
  [1X2.10-8 [33X[0;0YImporting from the Library[133X[101X
  
  [30X    [33X[0;6YThere  are data structures (e.g. types) and functions (e.g. for method
        selection) that are used by the kernel, but easier written in GAP[133X
  
  [30X    [33X[0;6YThese are mainly in [10X.g[110X files[133X
  
  [30X    [33X[0;6YThey  are  imported  into  the  kernel using [10XImportGVarFromLibrary[110X and
        [10XImportFuncFromLibrary[110X[133X
  
  [30X    [33X[0;6YThese are basically just [10XInitCopyGVar[110X and [10XInitFopyGVar[110X[133X
  
  [30X    [33X[0;6YThey also make the GVars read-only and keep some records[133X
  
  [30X    [33X[0;6YAt  the  end  of  [10Xread1.g[110X  the  GAP function [10XExportToKernelFinished[110X is
        called[133X
  
  [30X    [33X[0;6YThis checks that all the imported GVars have actually been read.[133X
  
  [30X    [33X[0;6YUntil  this  is  done,  some functionality may not be usable yet (e.g.
        [10XTYPE_OBJ[110X).[133X
  
  
  [1X2.10-9 [33X[0;0YInitKernel[133X[101X
  
  [33X[0;0YTypical things to do in [10XinitKernel[110X functions:[133X
  
  [30X    [33X[0;6YCall [10XInitHdlrFuncsFromTable[110X[133X
  
  [30X    [33X[0;6YInstall names for bag types in [10XInfoBags[110X[133X
  
  [30X    [33X[0;6YInstall   marking   functions   for  bag  types  (needed  for  garbage
        collection)[133X
  
  [30X    [33X[0;6YInstall functions in kernel tables for...[133X
  
        [30X    [33X[0;12YSaving[133X
  
        [30X    [33X[0;12YLoading[133X
  
        [30X    [33X[0;12YPrinting[133X
  
        [30X    [33X[0;12YArithmetic operations[133X
  
        [30X    [33X[0;12YType determination[133X
  
        [30X    [33X[0;12YCopying (and MakeImmutable)[133X
  
        [30X    [33X[0;12YList access, length, and associated functions[133X
  
  [30X    [33X[0;6YInitialize GVar copies and fopies and imports[133X
  
  [30X    [33X[0;6YAdd entries to various tables used by the list machinery[133X
  
  [30X    [33X[0;6YDO  NOT  create  ANY  bags  in  the workspace (they would be lost in a
        restore workspace)[133X
  
  
  [1X2.10-10 [33X[0;0YinitLibrary and postRestore[133X[101X
  
  [30X    [33X[0;6YThese functions can create or access structure in the workspace[133X
  
  [30X    [33X[0;6YOften [10XinitLibrary[110X also calls [10XpostRestore[110X[133X
  
  [30X    [33X[0;6YTypical [10XpostRestore[110X activities:[133X
  
        [30X    [33X[0;12Yrunning  [10XGVarName[110X  to  get  the  numbers  of global variables of
              interest[133X
  
        [30X    [33X[0;12Ylikewise [10XRNamName[110X to get the numbers for record field names[133X
  
        [30X    [33X[0;12Ygetting  the length of things like the list of GVars into kernel
              variables[133X
  
  [30X    [33X[0;6Yother [10XInitLibrary[110X activities:[133X
  
        [30X    [33X[0;12YCall  [10XInitGVarFuncsFromTable[110X  and  its  friends,  using the same
              tables that were passed to the [10XInitHdlr[110X functions[133X
  
        [30X    [33X[0;12YCreate any other global variables (not holding functions)[133X
  
        [30X    [33X[0;12YCreate  any  special  functions  (eg ones that have handlers for
              several ariths)[133X
  
  [30X    [33X[0;6YAllocate any scratch areas needed in the workspace[133X
  
