<!--

  kernel.xml           GAP documentation

  Copyright (C) 2005,  The GAP Group

Here we give an introduction to the &GAP; kernel programming.

-->

<Chapter Label="Chap-Kernel">
<Heading>The &GAP; kernel programming</Heading>

<Section Label="Sect-Kinds">
<Heading>Overview of the &GAP; kernel</Heading>

The &GAP; kernel consists of more than 150000 lines of &C; code that:
<List>
<Item>provides the run-time environment and user interface;</Item>
<Item>interprets the &GAP; language;</Item>
<Item>performs arithmetic operations with basic types of objects;</Item>
<Item>speeds up some time-critical operations.</Item>
</List>

The &GAP; kernel code mainly falls into the four main categories:

<Enum>
<Item>Implementations for basic data types and structures
(integers, permutations, finite field elements, etc.),
which has to be in the kernel for the maximal efficiency.</Item>
<Item>Low level access methods for data objects (lists, ranges, records, etc.).</Item>
<Item>Various methods for handling complex &GAP; objects in component
and positional representation from the kernel.</Item>
<Item>&GAP; foundations such as &GAP; language, garbage collector (in what follows - GC), etc.</Item>
</Enum>

The &GAP; kernel programming has four levels of sofistication:
<Enum>
<Item>The simplest form of kernel programming is to add new kernel functions
for manipulating existing data types.</Item>
<Item>Using the "data object" type to add new binary data structures to the kernel.</Item>
<Item>Adding new basic (primitive) data types, such as, for example, <E>Floats</E>.</Item>
<Item>Modifying the foundations, for example, changing the syntax of the &GAP; language.</Item>
</Enum>

We will cover only first two levels here, while adding new basic data types
or modifying the foundations are outside the scope of this manual.

</Section>

<Section Label="Sect-HelloWorld">
<Heading>"Hello World" example</Heading>

On the &GAP; level, the kernel functionality may be accessed via kernel
functions. You can recognise such functions because they will be displayed
as compiled code in the &GAP; session:

<Listing>
<![CDATA[
gap> Display(TYPE_OBJ);
function ( obj )
    <<kernel code>> from src/objects.c:TYPE_OBJ
end
]]>
</Listing>

Let 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:

<Enum>

<Item>
Create the &C; handler, adding to the file <F>string.c</F>
(this file contains the functions which mainly deal with strings)
the &C; code doing the actual job (see the function <C>Pr</C> to print
formatted output in the file <F>scanner.c</F> ):
<Listing>
<![CDATA[
static Obj FuncHELLO_WORLD(Obj self)
{
    Pr("Hello World!\n", 0, 0);
    return 0;
}
]]>
</Listing>
This code should be placed somewhere in the file <F>string.c</F>
before specifying <C>GvarFuncs</C>.
</Item>

<Item>
In the same file <F>string.c</F> find the list of functions to export
called <C>GvarFuncs</C> and add to this list a table entry for <C>HELLO_WORLD</C>
<Listing>
<![CDATA[
GVAR_FUNC_0ARGS(HELLO_WORLD),
]]>
</Listing>
containing respectively the string specifying the name of the function at the &GAP;
level, the number of arguments, the string with the description of arguments,
corresponding &C; handler and the string (<Q>cookie</Q>) specifying the location
of this handler (see definition of the structure <C>StructGVarFunc</C>
in the file <F>system.h</F> ).
</Item>

<Item>
Compile the &GAP; kernel, and now <C>HELLO_WORLD();</C> will work.
<Log>
<![CDATA[
gap> HELLO_WORLD();
Hello World!
]]>
</Log>
</Item>

</Enum>

</Section>

<Section Label="Sect-BigPicture">
<Heading>Structure of the &GAP; kernel</Heading>

The following picture is based on the scheme that Martin Schönert drew in 1995
and displays the structure of the &GAP; kernel:

<Alt Only="LaTeX">
\centerline{\resizebox{130mm}{!}{\includegraphics{bigpic.pdf}}}
</Alt>

<Alt Only="HTML">
&lt;img src="bigpic.jpg" align="left" />
</Alt>

<Alt Only="Text">
------------------------------------------------------------------------------------
|                                 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                                          |
------------------------------------------------------------------------------------
</Alt>

The 2nd line of the scheme,
the "interpreter/coder/expressions/statements/vars/funcs/calls/compiler" level
is essentially the &GAP; runtime system. It takes in &GAP; 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.
<P/>

In the region within the thick lines the kernel code sees the same world as &GAP;
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.
<P/>

Unevaluated expressions or fragments of the &GAP; code never appear in this
region and below it. Therefore, there are only a few ways to
pass control back from that level:
<List>
<Item>Calling a &GAP; function;</Item>
<Item>Entering a break loop;</Item>
<Item>Reading a file.</Item>
</List>

</Section>


<Section Label="Sect-Gasman">
<Heading>Garbage collection in &GAP;</Heading>

<Subsection Label="Subsect-Gasman">
<Heading>&GASMAN;</Heading>

&GASMAN; is the &GAP; memory manager.
It provides an API dealing with <E>Bags</E> which are
areas of memory, each with a size and a <C>TNUM</C> (type number)
in the range 0--253 (type numbers are defined in the file <F>objects.h</F>;
there are some spare numbers reserved for further extensions; types 254 and 255
are reserved for &GASMAN;. See Section
<Ref Sect="Sect-Objects" /> for more details).
<P/>

Bags have stable handles
(of &C; type <C>Bag</C>) 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 &C; local variables are found automatically, and
references from &C; static and global variables must be declared.
&GASMAN; recovers unreachable bags automatically -- it knows that bags in &C;
local variables <E>are</E> reachable. From the point of GC technicalities, &GASMAN;
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.
<P/>

To get the type of the bag with the identifier <C>b</C>, call <C>TNUM_BAG(b)</C>.
<P/>

The application specifies the type of a bag when it allocates it with <C>NewBag</C>
and may later  change it with <C>RetypeBag</C> (see  <C>NewBag</C> and <C>RetypeBag</C>
in <F>gasman.h</F>).
<P/>

&GASMAN; 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 <C>InitMarkFuncBags</C> below).
Apart from that &GASMAN; does not care at all about types.

</Subsection>


<Subsection Label="Subsect-Gasman-Interface">
<Heading>&GASMAN; Interface</Heading>

<C>Bag</C> is a type definition of some sort of pointer. It may be used as

<Listing>
<![CDATA[
Bag bag = NewBag(type, size);
]]>
</Listing>

Creation of a new bag may cause garbage collection, and &GAP;
will fail if space cannot be allocated.
<P/>
To reach the data in a bag, call

<Listing>
<![CDATA[
Bag *ptr = PTR_BAG(bag);
]]>
</Listing>

and keep in mind that the cost of such call is one indirection.
<P/>

The <E>key rule</E> 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

<Listing>
<![CDATA[
PTR_BAG(list)[1] = NewBag(t,s);
]]>
</Listing>

because the pointer may be evaluated before the right-hand side evaluation,
and used after it. Instead of this, you should use

<Listing>
<![CDATA[
{
  Obj temp = NewBag(t,s);
  PTR_BAG(list)[1] = temp;
}
]]>
</Listing>

There is a second rule: after you assigned a bag identifier <C>b</C>
into a bag <C>c</C> and before the next garbage collection,
you must call <C>CHANGED_BAG(c)</C>, unless
you know that <C>b</C> cannot be garbage collected (e.g. it
is an object like <K>true</K>), or <C>c</C> is the most recently
allocated bag of all.
<P/>

Other functions are:
<List>
<Item>
<C>RetypeBag( bag, newtnum )</C> changes the type of the bag with identifier
<C>bag</C> to the new type <C>newtnum</C>. The identifier, the size, and also
the  address of the data area of the bag do not change.
</Item>
<Item>
<C>ResizeBag( bag, newsize )</C> changes the size of the bag with identifier
<C>bag</C> to the new size <C>newsize</C>.  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, &GASMAN; 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 <C>ResizeBag</C> 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 <C>ResizeBag</C> (see <C>PTR_BAG</C>
in <F>gasman.h</F>).
</Item>
<Item>
<C>InitMarkFuncBags( type, mark-func )</C>(optional) installs the function <C>mark-func</C>
as marking function for bags of type <C>type</C>. The application <E>must</E>
install  a  marking function for a  type before it allocates  any  bag  of  that type.
<P/>
A marking function returns nothing. It just takes a single argument of type <C>Bag</C>
and applies the function <C>MarkBag</C> 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 &GASMAN; has for types.
<P/>
<C>MarkBag(b)</C> marks the bag <C>b</C> as live so that it is not thrown away during
a garbage collection. It tests if <C>bag</C> is a valid identifier of a bag  in the young
bags  area.  If it is not,  then <C>MarkBag</C> does nothing, so there is no
harm in  calling it for  something   that is not actually  a  bag identifier.
It is important that <C>MarkBag</C> should only be called from the marking
functions installed with <C>InitMarkFuncBags</C>.
<P/>
<C>MarkBagWeakly</C> is an alternative to <C>MarkBag</C>, 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
<C>IsWeakDeadBag</C>. This should  always be checked before copying or
using such an identifier.
<P/>
&GASMAN; already provides the following standard
marking functions defined in <F>gasman.c</F>:
<List>
<Item>
<C>MarkNoSubBags( bag )</C> 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.
</Item>
<Item>
<C>MarkOneSubBags( bag )</C> 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.
</Item>
<Item>
<C>MarkTwoSubBags( bag )</C> 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.
</Item>
<Item>
<C>MarkAllSubBags( bag )</C> 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). <C>MarkAllSubBags</C>
marks every entry of such a bag.  Note
that <C>MarkAllSubBags</C> assumes that  all  identifiers are at offsets  from
the    address of the  data area   of  <C>bag</C>   that  are divisible   by
<C>sizeof(Bag)</C>.  Also, since it does not do   any harm to  mark
something which is not actually a bag identifier, one could use
<C>MarkAllSubBags</C> for all  types  as long as  the identifiers  in the data
area are  properly aligned as  explained above (this  would however slow
down <C>CollectBags</C>). By default, &GASMAN; uses <C>MarkAllSubBagsDefault</C>
which does exactly this.
</Item>
</List>
</Item>
</List>

</Subsection>

<Subsection Label="The GASMAN Interface for Weak Pointer Objects">
<Heading>The GASMAN Interface for Weak Pointer Objects</Heading>

The key support for weak pointers is in the files <F>src/gasman.c</F> and
<F>src/gasman.h</F>.
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
<C>MarkBagWeakly</C> for those subbags, rather than <C>MarkBag</C>.
Secondly, before any access to such a subbag, it must be checked with
<C>IsWeakDeadBag</C>.
If that returns <K>true</K>, 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 <E>sweeping function</E> must be installed for that tnum
which copies the bag, removing all references to dead weakly held subbags.
<P/>
The files <F>src/weakptr.c</F> and <F>src/weakptr.h</F> use this interface
to support weak pointer objects.
Other objects with weak behaviour could be implemented in a similar way.

</Subsection>

</Section>


<Section Label="Sect-Interfaces">
<Heading>Interfaces</Heading>

The modules at the bottom of the picture from the section
<Ref Sect="Sect-BigPicture" /> (<E>objects</E>, <E>gasman</E> and
<E>system</E>), and white boxes (<E>arithmetic</E>, <E>lists</E>,
<E>calls/operations</E>, <E>records</E>)
provide interfaces intended for use in the kernel.
<P/>

For example <F>ariths.h</F> provides functions like
<C>SUM</C>, <C>PROD</C>, <C>AINV</C>,
corresponding to the GAP operations <C>+</C>, <C>*</C> and unary <C>-</C>.
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.
<P/>

Another interface provides <C>ELM_LIST</C>, <C>ASS_LIST</C>,
<C>LEN_LIST</C>, etc. as a general interface to any type of list.
<P/>

Functions like these will even work for &GAP;-level objects whose
arithmetic or list operations are implemented by installed methods.
<P/>

Adding 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.
<P/>

For example, the following kernel function will return a list containing an
object, its square and its cube:

<Log>
<![CDATA[
/*  x -> [x,x^2,x^3]  */
static Obj FuncFoo1(Obj self, Obj x)
{
    Obj x2, x3;
    Obj list = NEW_PLIST( T_PLIST, 3 );
    SET_ELM_PLIST( list, 1, x );
    CHANGED_BAG( list );

    x2 = PROD( x, x );
    SET_ELM_PLIST( list, 2, x2 );
    CHANGED_BAG( list );

    x3 = PROD( x2, x );
    SET_ELM_PLIST( list, 3, x3 );
    CHANGED_BAG( list );

    SET_LEN_PLIST(list, 3);
    return list;
}
]]>
</Log>

If speed is not of utmost importance, then it is usually better
to use the <C>ASS_LIST</C> etc. functions instead of <C>SET_ELM_PLIST</C>
and friends, which are more low-level and easier to misuse. For example,
they automatically call <C>CHANGED_BAG</C> and <C>SET_LEN_PLIST</C>.
Then the above example would become this instead:

<Log>
<![CDATA[
/*  x -> [x,x^2,x^3]  */
static Obj FuncFoo2(Obj self, Obj x)
{
    Obj x2, x3;
    Obj list = NEW_PLIST( T_PLIST, 3 );
    ASS_LIST( list, 1, x );

    x2 = PROD( x, x );
    ASS_LIST( list, 2, x2 );

    x3 = PROD( x2, x );
    ASS_LIST( list, 3, x3 );

    return list;
}
]]>
</Log>

Finally, if all you want to do is produce a list of
fixed length, you can use the <C>NewPlistFromArgs</C> helper function:

<Log>
<![CDATA[
/*  x -> [x,x^2,x^3]  */
Obj FuncFoo3(Obj self, Obj x)
{
    Obj x2 = PROD( x, x );
    Obj x3 = PROD( x2, x );
    return NewPlistFromArgs( x, x2, x3 );
}
]]>
</Log>


</Section>


<Section Label="Sect-Objects">
<Heading>Objects and API</Heading>

The kernel representation of every &GAP; object is an object of &C; type <C>Obj</C>.
Objects are defined in the file <F>objects.h</F>.
Objects are actually <E>bags</E> (represented by their handles),
small integers and small finite field elements (represented by values
that could not be valid handles).

<C>Bag</C> is the type of bag identifiers, defined in the file <F>system.h</F>:
<Example>
<![CDATA[
typedef UInt * *        Bag;
]]>
</Example>
Each bag is identified by its <E>bag identifier</E>,
and no two live bags have the same identifier.
<P/>

Note 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.
<P/>

Note that bag identifiers are recycled.  That means that after a bag dies
its identifier may be reused for a new bag.
<P/>

0 is a valid value of the type <C>Bag</C>, but is guaranteed  not to be  the
identifier of any bag.
<P/>

The ability to distinguish between bags and other objects relies on the fact
that all bag identifiers are divisible by 4.
<P/>

There are lots of kernel API functions providing a uniform interface
for working with objects:
<List>
<Item>
<C>TNUM_OBJ</C> (first level type), <C>SIZE_OBJ</C>,
<C>ADDR_OBJ</C> (C pointer to data), <C>TYPE_OBJ</C> (full type)
</Item>
<Item>
<C>IS_MUTABLE_OBJ</C>, <C>MakeImmutable</C>, <C>COPY_OBJ</C>, ...
</Item>
<Item>
<C>PRINT_OBJ</C>
</Item>
<Item>
<C>NEW_PLIST</C>, <C>SET_ELM_PLIST</C>, etc. for creating plain lists
</Item>
<Item>
<C>PROD</C> for arithmetic (see also <C>SUM</C>, <C>DIFF</C>, etc.)
</Item>
</List>
These functions are flexible: for example, <C>PROD</C> will multiply anything,
but if you know what objects you will have it will be a bit faster to call
the multiplication directly.
<P/>
Typical implementation is a table of functions indexed by <C>TNUM_OBJ</C>.
For example, this is the definition of <C>PROD</C> in the file <F>ariths.h</F>
(you can safely ignore the <C>EXPORT_INLINE</C> for now):

<Example>
<![CDATA[
EXPORT_INLINE Obj PROD(Obj opL, Obj opR)
{
    UInt tnumL = TNUM_OBJ(opL);
    UInt tnumR = TNUM_OBJ(opR);
    return (*ProdFuncs[tnumL][tnumR])(opL, opR);
}
]]>
</Example>

Additionally, <F>objects.h</F> also defines symbolic names for TNUMs.
<P/>
There are lots of other API functions for strings, general lists, calling
functions, etc.


<Subsection Label="Subsect-Integers">
<Heading>Immediate Integers and FFEs</Heading>

There are three integer types in GAP: <C>T_INT</C>, <C>T_INTPOS</C> and
<C>T_INTNEG</C>. Each integer has a unique representation, e.g., an integer
that  can  be represented as <C>T_INT</C> is never represented as <C>T_INTPOS</C>
or <C>T_INTNEG</C>.
<P/>

<C>T_INT</C> 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 <M>-2^{28}...2^{28}-1</M>
respectively <M>-2^{60}...2^{60}-1</M>.
Only these small integers can be used as index expression into sequences.
<P/>

Small integers are represented by an immediate integer handle, containing
the value instead of pointing  to  it,  which  has  the  format
<C>ss&lt;28 data bits>01</C> respectively <C>ss&lt;60 data bits>01</C>.
<P/>

Immediate integers handles carry the tag <C>T_INT</C>, 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.
<P/>

The first two bits <C>ss</C> 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.
<P/>

Functions <C>IS_INTOBJ</C> and <C>ARE_INTOBJS</C> are used to test if an object
(or two objects) is an (immediate) integer object.
The functions <C>INTOBJ_INT</C> is used to convert a &C; integer to an (immediate)
integer object, and <C>INT_INTOBJ</C> is used to convert the (immediate) integer
object to a &C; integer. These functions do NOT check for overflows.
<P/>

The other two integer types are <C>T_INTPOS</C> and <C>T_INTNEG</C> for
positive (respectively, negative) integer values  that  cannot  be
represented  by  immediate  integers. See comments in <F>integer.c</F>
for details.
<P/>

Other immediate objects are <E>finite field elements</E> (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 <C>&lt;16 bit value>&lt;13 bit field ID>010</C>,
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.
<P/>

The 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.
<P/>

The most significant 16 bits represent the value of the element.
<P/>

If 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 <M>z</M>,
it is an element of order <M>ord-1</M>, where <M>ord</M> is the order of the finite field.
Thus 1 corresponds to <M>z^{1-1} = z^0 = 1</M>, i.e., the  one from the field.
Likewise 2 corresponds to <M>z^{2-1} = z^1 = z</M>, i.e., the root itself.
<P/>

This representation  makes multiplication very easy,  we only have to add
the values and subtract 1 , because  <M>z^{a-1} * z^{b-1} = z^{(a+b-1)-1}</M>.
Addition is reduced to multiplication by the formula
<M>z^a +  z^b = z^b * (z^{a-b}+1)</M>.
This makes it necessary to know the successor <M>z^a + 1</M> of every value.
<P/>

The  finite field  bag contains  the  successor for  every nonzero value,
i.e., <C>SUCC_FF(&lt;ff>)[&lt;a>]</C> is  the successor of  the element
<C>&lt;a></C>, i.e, it is the  logarithm  of <M>z^{a-1} + 1</M>.
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.
<P/>

<C>T_INT</C> and <C>T_FFE</C> are reserved <C>TNUM</C>s for immediate
integers and FFEs. <C>TNUM_OBJ</C> produces them if needed and otherwise
calls <C>TNUM_BAG</C>.
<P/>

The kernel design allows that other immediate types could be added in the
future.
</Subsection>


<Subsection Label="Subsect-Arithmetics">
<Heading>Arithmetics</Heading>

Arithmetic operations package is implemented in files
<F>ariths.h</F> and <F>ariths.c</F>. In particular,
it defines functions like <C>SUM(obj1, obj2)</C>, <C>DIFF</C>, <C>PROD</C> etc.,
which accept (and may return) objects of any kind, including immediate objects.
Selection of the appropriate method is handled via calling <C>TNUM_OBJ</C> for
arguments and then calling the appropriate method from the table of functions,
for example:
<Listing>
<![CDATA[
EXPORT_INLINE Obj SUM(Obj opL, Obj opR)
{
    UInt tnumL = TNUM_OBJ(opL);
    UInt tnumR = TNUM_OBJ(opR);
    return (*SumFuncs[tnumL][tnumR])(opL, opR);
}
]]>
</Listing>
The default entry of the table of functions just calls back to the &GAP; level
to look for the installed methods (see e.g. <C>SumObject</C> in <F>ariths.c</F>),
but note that kernel methods installed in tables <E>OVERRIDE</E> &GAP;
installed methods.
<P/>
If you expect to handle mainly small integers, then it is significantly faster to do:
<Listing>
<![CDATA[
if ( ! ARE_INTOBJS( <opL>, <opR> ) || ! SUM_INTOBJS( <res>, <opL>, <opR> ) )
    <res> = SUM( <opL>, <opR> );
]]>
</Listing>
instead of <C>&lt;res> = SUM(&lt;opL>, &lt;opR>)</C>, where
<C>SUM_INTOBJS</C> is a function, which returns 0 if the answer overflows
and a large integer needs to be created.
<P/>
Finally, note that lots of functions in <F>ariths.h</F> called <C>C_&lt;something></C>
are used mainly by the compiler.

</Subsection>


<Subsection Label="Subsect-Functions">
<Heading>Functions</Heading>

The function call mechanism package is implemented in files <F>calls.h</F>
and <F>calls.c</F>. A function object in &GAP; is represented by a bag of
the type <C>T_FUNCTION</C>. The bag for the function <C>f</C> contains eight
pointers fo &C; functions - its handlers. These eight functions are for
0,1,2,...,6 arguments and X arguments respectively, and the <M>i</M>-th handler
can be accessed using the function <C>HDLR_FUNC(f, i)</C>. This is exactly what
is done by functions <C>CALL_0ARGS</C>, <C>CALL_1ARGS</C>, ..., <C>CALL_6ARGS</C> and
<C>CALL_XARGS</C>, which simply call the appropriate handlers, passing the
function bag and the arguments. <C>CALL_0ARGS</C> is for calls passing no arguments,
<C>CALL_1ARGS</C> is  for  calls passing one argument, and so on.
Thus, the kernel
equivalent of the GAP code <C>r := f(a,b)</C> is <C>r = CALL_2ARGS(f,a,b)</C>.
<C>CALL_XARGS</C> 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.
<P/>
There is a range of standard handlers that deal with calls to regular &GAP;
functions, to operations, attributes and properties and that also deal with
&GAP; variadic functions given as <C>function(arg)</C>.
<P/>
For kernel functions, the handler is the actual function which does the work.
A typical handler (for 1-argument function) looks like
<Listing>
<![CDATA[
Obj FuncLength(Obj self, Obj list)
{
    return INTOBJ_INT(LEN_LIST(list));
}
]]>
</Listing>
Often the handler has to do some checks on arguments as well. In the example
above <C>LEN_LIST</C> takes care of this (mainly because the jump table
for <C>LEN_LIST</C> contains error functions for non-lists).
Every handler must be registered (once) with a unique <Q>cookie</Q> by
calling <C>InitHandlerFunc( handler, cookie )</C> before it is installed in any
function bag. This is needed so that it can be identified when loading a
saved workspace.  <A>cookie</A> should be a  unique &C; string, identifying the
handler.
<P/>
To create a function object, there are three functions
<C>NewFunction</C>, <C>NewFunctionC</C>, and <C>NewFunctionT</C>,
defined in the file <F>calls.c</F>.
<P/>
<C>NewFunction( name, narg, nams, hdlr )</C>
creates and returns a new function.  <A>name</A> must be  a  &GAP;
string containing the name of the function. <A>narg</A> must be the number of
arguments, where -1 indicates a variable number of arguments. <A>nams</A> must be
a &GAP; list containing the names  of  the  arguments.  <A>hdlr</A>  must  be  the
&C; function (accepting <A>self</A> and  the  <A>narg</A> arguments)  that  will  be
called to execute the function.
<P/>
<C>NewFunctionC</C> does the same as <C>NewFunction</C>,
but  expects  <A>name</A>  and <A>nams</A> as &C; strings.
<C>NewFunctionT</C> also does the same as <C>NewFunction</C>,
but has two extra arguments that allow to specify  the
<A>type</A> and <A>size</A> of the newly created bag.
<P/>
For example, you can make a function object using the code like this:
<Listing>
<![CDATA[
lenfunc = NewFunctionC("Length", 1, "list", FuncLength);
]]>
</Listing>

</Subsection>


<Subsection Label="Subsect-Lists">
<Heading>Lists</Heading>

The &GAP; kernel provides a generic list interface,
which is equivalent to using <C>list[i]</C>
etc. in the library. This interface works for all types
of lists known to GAP, including virtual lists. It has
functions like
<C>IS_LIST</C> (returns &C; Boolean),
<C>LEN_LIST</C> (returns &C; integer),
<C>ISB_LIST</C>, <C>ELM_LIST</C>,
<C>ELM0_LIST( &lt;list>, &lt;pos> ) </C>
(returns 0 if &lt;list> has no assigned  object at position &lt;pos>)
and
<C>ASS_LIST</C>,
defined in the file <F>lists.h</F>
Implementation of these functions is done via tables of functions indexed by TNUM.
<P/>
Nevertheless, it will be not much faster to write your &C; code using such functions,
for example, to reverse an arbitrary list, than to do the same working in &GAP;.
However, in case of <E>plain lists</E> coding
in &C; actually ought to produce some speedup.
<P/>
A  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.
<P/>
If you need to create a plain list, use
<C>NEW_PLIST(&lt;tnum>,&lt;plength>)</C>,
where <C>&lt;tnum></C> should be <C>T_PLIST_&lt;something></C>,
and <C>&lt;plength></C> is physical length in bags. Furthermore,
<C>LEN_PLIST</C> gets its logical length, and
<C>SET_LEN_PLIST</C> sets its logical length. Note that
<C>ELM_PLIST</C> is faster than <C>ELM_LIST</C>.

</Subsection>


<Subsection Label="Subsect-Data-Objects">
<Heading>Data objects</Heading>

<E>Positional</E> and <E>Component</E> objects are made from lists and
records using <C>Objectify</C>. They contain their <E>Type</E> and data
accessible with <C>![]</C> and <C>!.</C> operations.
<P/>

<E>Data objects</E> also contain their <E>Type</E>, but the data is only
accessible via kernel functions. Data can be anything you like <E>except</E>
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.

</Subsection>

</Section>



<Section Label="Sect-Rules">
<Heading>Rules of Kernel Programming</Heading>

<Subsection Label="Sect-GoldenRules">
<Heading>Three golden rules</Heading>

Three golden rules of &GAP; kernel programming:
<Enum>
<Item>
Real &C; pointers into objects (returned by <C>ADDR_OBJ</C>) must <E>not</E>
be held across anything that could cause a garbage collection (<E>GC</E>).
</Item>
<Item>
If you add a new object to another one (e.g. put it in a list) you must call
<C>CHANGED_BAG</C> on the container, otherwise the new object may get lost in a GC.
</Item>
<Item>
Don'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.
</Item>
</Enum>

</Subsection>


<Subsection Label="Subsect-Traps">
<Heading>Common kernel traps</Heading>

More things can cause a garbage collection than you expect:
<List>
<Item>printing (might be to string stream)</Item>
<Item>generic list or record access (might be handled by &GAP; methods)</Item>
<Item>integer arithmetic (might overflow to large integers)</Item>
</List>
Be careful of things like
<Log>
<![CDATA[
ELM_PLIST(l, 3) = something that might cause GC
]]>
</Log>
This expands in &C; to <C>*((*l)+3) = something</C>.
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.

</Subsection>

<Subsection Label="Subsect-MoreGasman">
<Heading>One More Bit of GASMAN interface</Heading>

When you store a Bag ID in a &C; global variable, you must declare
the address of the global to &GASMAN; (so the GC knows that the bag is
alive). This is done by calling <C>InitGlobalBag</C> passing the address
and another "cookie" which is used by save/load.
<P/>
There are nice ways to do all the global and handler
initializations from tables.

</Subsection>

</Section>

<Section Label="Sect-compiler">
<Heading>The &GAP; compiler</Heading>

<Subsection Label="Compiling GAP Code">
<Heading>Compiling &GAP; Code</Heading>

The &GAP; compiler converts &GAP; 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 &C; 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.
<P/>

In the following example we compile the file <F>foo.g</F> and then
load it during the subsequent &GAP; session:

<Log>
<![CDATA[
$ cat > foo.g
foo := x -> [x,x^2,x^3];
$ gac -d -C foo.g
... compilation to C file ...
$ gac -d foo.g
... compilation to .so file ...
$ ls -l foo.so
-rwxr-xr-x 1 sal 158 4999 2007-09-11 10:19 foo.so*
$ gap -b
GAP4, Version: 4.dev of today, ....
gap> LoadDynamicModule("./foo.so");
gap> Print(foo);
function ( x )
    <<compiled GAP code>> from foo.g:1
end
gap> foo(3);
[ 3, 9, 27 ]
]]>
</Log>

The compiler code will look as follows:

<Log>
<![CDATA[
/* return [ x, x ^ 2, x ^ 3 ]; */
t_1 = NEW_PLIST( T_PLIST, 3 );
SET_LEN_PLIST( t_1, 3 );
SET_ELM_PLIST( t_1, 1, a_x );
CHANGED_BAG( t_1 );
t_2 = POW( a_x, INTOBJ_INT(2) );
SET_ELM_PLIST( t_1, 2, t_2 );
CHANGED_BAG( t_1 );
t_2 = POW( a_x, INTOBJ_INT(3) );
SET_ELM_PLIST( t_1, 3, t_2 );
CHANGED_BAG( t_1 );
SWITCH_TO_OLD_FRAME(oldFrame);
return t_1;
]]>
</Log>

Note that the original &GAP; code (more or less) appears as comments.
<P/>

If you want to see or modify the intermediate &C; code, you can also instruct
the compiler to produce only the &C; files by using the option <C>-C</C>
instead of <C>-d</C>.
<P/>

There are some known problems with &C; code produced with the
&GAP; compiler on 32 bit architectures and used on 64 bit architectures
(and vice versa).
<P/>

There are more ways to exploit the &GAP; compiler apart from just compiling
the &GAP; code:
<List>
<Item>You can compile your code and then hand-optimize critical sections.
For example, you can replace calls to <C>POW</C> by calls to <C>PROD</C> 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.
</Item>
<Item>
You can use the compiler to generate a shell that can be dynamically loaded,
and then fill in your own &C; code in this shell. This approach is used
in <Package>Browse</Package>, <Package>EDIM</Package> and <Package>IO</Package>
packages. In this case you must make it sure that your code complies with rules.
</Item>
</List>

</Subsection>


<!-- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -->
<Subsection Label="Suitability for Compilation">
<Heading>Suitability for Compilation</Heading>

Typically algorithms spend large parts of their runtime only in small parts
of the code. The design of &GAP; reflects this situation with kernel
methods for many time critical calculations such as matrix or permutation
arithmetic.
<P/>
Compiling 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.
<P/>
Routines that benefit from compilation are those which do extensive
operations with basic data types, such as lists or small integers.

</Subsection>

</Section>


<Section Label="Sect-GVars">
<Heading>Global Variables</Heading>

<Subsection Label="Subsect-GVars">
<Heading>Global variables</Heading>

The part of the kernel that  manages global variables, i.e., the global
namespace, is contained in the files <F>gvars.h</F> and <F>gvars.c</F>.
Global variables have an internal form, of type <C>GVar</C>
(actually an index into a hash table).
They may be obtained with <C>GVar gv = GVarName(&lt;string>);</C>.
A global variable may be safely held on to across GC (but not across
save/load workspace).
<P/>
To manipulate with global variables, you may use
<C>AssGVar(gv, &lt;obj>)</C> or
<C>ValGVar( gv )</C> (returns 0 if unbound, not an error), etc.

</Subsection>

<Subsection Label="Subsect-TrackGVars ">
<Heading>Tracking global variables</Heading>

The &C; code

<Listing>
<![CDATA[
Obj Stuff;
InitCopyGVar( "stuff", &Stuff );
]]>
</Listing>

causes <C>Stuff</C> to track the value of the global named
"stuff". When the global is changed, the new value will be put in
the &C; variable.
<P/>
A useful refinement is <C>InitFopyGVar</C>. This does the same,
provided that the value assigned is a function, otherwise the &C;
variable points to a function that prints a suitable error message.
<P/>
These are usually set up during initialization of a kernel module.

</Subsection>

</Section>

<Section Label="Sect-Kernel-Modules">
<Heading>The Kernel Module Structure and interface</Heading>

<Subsection Label="Subsect-Kernel-Modules-Structure">
<Heading>The Kernel Module Structure</Heading>

Apart from a very small amount of glue, all of the kernel
(including compiled GAP code) is organised  into modules.
<P/>

Basically each module consists of one <C>.c</C> file and one <C>.h</C> file.

The file <F>gap.c</F> contains the variable <C>InitFuncsBuiltinModules</C>
which is initialized with a list of functions such as <C>InitInfoInt</C>.

Each such function, when called, returns a data structure describing a module,
which typically looks as follows:
<Listing>
<![CDATA[
/****************************************************************************
**
*F  InitInfoInt() . . . . . . . . . . . . . . . . . . table of init functions
*/
static StructInitInfo module = {
    .type = MODULE_BUILTIN,
    .name = "integer",
    .initKernel = InitKernel,
    .initLibrary = InitLibrary,
};
]]>
</Listing>
The first part is just information, but the functions from
<C>initKernel</C> down are the key to the interface to kernel modules.

</Subsection>

<Subsection Label="Subsect-Kernel-Modules-Interface">
<Heading>The Kernel Module Interface</Heading>

The general rule is that if a 0 appears, the function is skipped;
indeed, you may omit entries which are 0.<P/>

When GAP is starting up, it does the following:
<List>
<Item>Calls the <C>initKernel</C> functions of all those modules that have
one. If any of them return non-zero then it aborts.</Item>
<Item>Then calls the <C>initLibrary</C> functions likewise</Item>
<Item>Then the <C>checkInit</C> functions</Item>
</List>

The other three functions relate to save/load workspace:
<List>
<Item><C>preSave</C> functions are called before saving.</Item>
<Item><C>postSave</C> functions (in the reverse order) after saving</Item>
<Item><C>postRestore</C> functions are called after a workspace has been
loaded to finish linking up the kernel and workspace.</Item>
</List>

</Subsection>

<Subsection Label="Subsect-SeqEvents">
<Heading>Sequences of Events</Heading>

Normal GAP startup (no -L)
<List>
<Item>All <C>initKernel</C> methods called (abort on non-zero return)</Item>
<Item>All <C>initLibrary</C> methods called (abort on non-zero return)</Item>
<Item>All <C>checkInit</C> methods called (abort on non-zero return)</Item>
<Item><C>init.g</C> read</Item>
</List>

Startup loading a workspace
<List>
<Item>All <C>initKernel</C> methods called (abort on non-zero return)</Item>
<Item>Workspace loaded, global bags and handlers linked up</Item>
<Item>All <C>postRestore</C> methods called (abort on non-zero return)</Item>
<Item>Enter the main loop</Item>
</List>

</Subsection>

<Subsection Label="Subsect-Workspace">
<Heading>Saving a Workspace</Heading>

<List>
<Item>All <C>preSave</C> methods called (recover on non-zero return)</Item>
<Item>Full garbage collection</Item>
<Item>After this, workspace must be "clean" -- no non-objects
stored where objects are expected (eg in plain lists)</Item>
<Item>Saved workspace file written</Item>
<Item>All <C>postSave</C> methods called in reverse order</Item>
</List>

</Subsection>

<Subsection Label="Subsect-Excerpts">
<Heading>Excerpts from InitKernel from integer.c</Heading>

<Listing>
<![CDATA[
/****************************************************************************
**
*V  GVarFuncs . . . . . . . . . . . . . . . . . . list of functions to export
*/
static StructGVarFunc GVarFuncs [] = {

    GVAR_FUNC_2ARGS(QUO_INT, a, b),
    GVAR_FUNC_1ARGS(ABS_INT, n),
    . . .
    { 0 }
};

/****************************************************************************
**
*F  InitKernel( <module> )  . . . . . . . . initialise kernel data structures
*/
static Int InitKernel (
    StructInitInfo *    module )
{
    UInt                t1,  t2;

    /* init filters and functions                                          */
    InitHdlrFiltsFromTable( GVarFilts );
    InitHdlrFuncsFromTable( GVarFuncs );
    . . .
]]>
</Listing>

</Subsection>


<Subsection Label="Subsect-Commentary">
<Heading>Commentary</Heading>

<List>
<Item>The items in the array of <C>StructGVarFunc</C> objects define
the GAP-callable global functions exported by the module</Item>
<Item><C>InitHdlrFuncsFromTable</C> initializes all the handlers with
the given cookies</Item>
<Item>In the <C>initLibrary</C> function of the same model, we see this:

<Listing>
<![CDATA[
/****************************************************************************
**
*F  InitLibrary( <module> ) . . . . . . .  initialise library data structures
*/
static Int InitLibrary (
    StructInitInfo *    module )
{
    /* init filters and functions                                          */
    InitGVarFiltsFromTable( GVarFilts );
    InitGVarFuncsFromTable( GVarFuncs );
    . . .
]]>
</Listing>
</Item>

<Item>This call <C>InitGVarFuncsFromTable</C> creates the actual
function objects (in the workspace) using <C>NewFunctionC</C></Item>
<Item>It also installs these objects in global variables and makes
those variables read-only</Item>
</List>

</Subsection>


<Subsection Label="Subsect-OtherFunctions">
<Heading>Other Similar Functions</Heading>

<List>
<Item>There are other support functions for module initialization</Item>
<Item>Defined in <F>gap.c</F></Item>
<Item><C>InitHdlr&lt;xxxx>FromTable</C> and <C>InitGVar&lt;xxxx>FromTable</C> exist for filters, attributes, properties and operations</Item>
<Item>Structure definitions are found in <F>system.h</F></Item>
</List>

</Subsection>

<Subsection Label="Subsect-Import">
<Heading>Importing from the Library</Heading>

<List>
<Item>There are data structures (e.g. types) and functions (e.g. for method selection) that are used by the kernel, but easier written in GAP</Item>
<Item>These are mainly in <C>.g</C> files</Item>
<Item>They are imported into the kernel using <C>ImportGVarFromLibrary</C> and <C>ImportFuncFromLibrary</C></Item>
<Item>These are basically just <C>InitCopyGVar</C> and <C>InitFopyGVar</C></Item>
<Item>They also make the GVars read-only and keep some records</Item>
<Item>At the end of <C>read1.g</C> the GAP function <C>ExportToKernelFinished</C> is called</Item>
<Item>This checks that all the imported GVars have actually been read.</Item>
<Item>Until this is done, some functionality may not be usable yet (e.g. <C>TYPE_OBJ</C>).</Item>
</List>

</Subsection>


<Subsection Label="Subsect-InitKernel">
<Heading>InitKernel</Heading>

Typical things to do in <C>initKernel</C> functions:

<List>
<Item>Call <C>InitHdlrFuncsFromTable</C></Item>
<Item>Install names for bag types in <C>InfoBags</C></Item>
<Item>Install marking functions for bag types (needed for garbage collection)</Item>
<Item>Install functions in kernel tables for...
    <List>
    <Item>Saving</Item>
    <Item>Loading</Item>
    <Item>Printing</Item>
    <Item>Arithmetic operations</Item>
    <Item>Type determination</Item>
    <Item>Copying (and MakeImmutable)</Item>
    <Item>List access, length, and associated functions</Item>
    </List>
</Item>
<Item>Initialize GVar copies and fopies and imports</Item>
<Item>Add entries to various tables used by the list machinery</Item>
<Item>DO NOT create ANY bags in the workspace (they would be lost in a restore workspace)</Item>
</List>

</Subsection>

<Subsection Label="Subsect-postRestore">
<Heading>initLibrary and postRestore</Heading>

<List>

<Item>These functions can create or access structure in the workspace</Item>
<Item>Often <C>initLibrary</C> also calls <C>postRestore</C></Item>
<Item>Typical <C>postRestore</C> activities:
    <List>
    <Item>running <C>GVarName</C> to get the numbers of global variables of interest</Item>
    <Item>likewise <C>RNamName</C> to get the numbers for record field names</Item>
    <Item>getting the length of things like the list of GVars into kernel variables</Item>
    </List>
</Item>
<Item>other <C>InitLibrary</C> activities:
    <List>
    <Item>Call <C>InitGVarFuncsFromTable</C> and its friends, using the same tables that were passed to the <C>InitHdlr</C> functions</Item>
    <Item>Create any other global variables (not holding functions)</Item>
    <Item>Create any special functions (eg ones that have handlers for several ariths)</Item>
    </List>
</Item>
<Item>Allocate any scratch areas needed in the workspace</Item>
</List>

</Subsection>

</Section>

</Chapter>
