# GAP's Type System I

## by Markus Pfeiffer

The following posts are somewhat inspired by my talk at the CoDiMa training school in Edinburgh. The Jupyter notebooks that I used are available as ipynbipynb htmlhtml pdfpdf

I figured that the talk was very dense, so I will expand it a bit more into multiple blog posts.

My current plan is to describe the technicalities of the GAP type system, but also do a reasonably self-contained post that describes a practical approach to making the best use of GAP’s type system.

Please note that I will usually be using the latest master branch of GAP, or even patches that I came up with while writing these posts. Usually while writing I notice that GAP’s output is not helpful, and so I change it. If you have a suggestion or question, send me an email!

Lets get started.

## GAP4’s Types, Fam­i­lies, and Fil­ters

With every programming language one learns one of the things one has to learn are some internals that help explaining why a program behaves the way it does.

One of those things is the Type System that the language of choice implements, and for GAP the type system is quite peculiar.

Every object in GAP has a type. If you’re wondering what is and what isn’t an object, you can test this by trying to assign it to a variable:

1
2
3x := 5;
y := Group((1,2,3));
z := if;

In GAP 4 a type is a pair consisting of a family and a filter, and the first thing to keep in mind is that

• Fam­i­lies par­ti­tion the set of all ob­jects,
• Fil­ters form a hi­er­ar­chy on ob­jects

If we want to find the type of an object in GAP, we can use the function TypeObj

1
2
3
4
5
6gap> Type­Obj(1);
<Type: (Cy­clo­tomics­Fam­i­ly, [ Is­Int, Is­Rat, Is­Cyc, ... ])>
gap> Type­Obj([1,2,3]);
<Type: (Col­lec­tions­Fam­i­ly(...), [ Is­Mu­ta­ble, Is­Copy­able, Is­List, ... ])>
gap> Type­Obj(Group((1,2,3)));
<Type: (Col­lec­tions­Fam­i­ly(...), [ Is­Com­po­nent­Ob­ject­Rep, Is­At­trib­ute­Stor­ing­Rep, Is­List­Or­Col­lec­tion, ... ])>

There is also a way to get more verbose information about a type:

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84gap> Dis­play(Type­Obj(1));
fam­i­ly:
Col­lec­tions­Fam­i­ly(...)
fil­ters:
Is­Com­po­nent­Ob­ject­Rep
Is­At­trib­ute­Stor­ing­Rep
Is­List­Or­Col­lec­tion
Is­Col­lec­tion
Is­Fi­nite
Tester(Is­Fi­nite)
Can­Eas­i­ly­Com­pare­El­e­ments
Tester(Can­Eas­i­ly­Com­pare­El­e­ments)
Can­Eas­i­ly­Sort­El­e­ments
Tester(Can­Eas­i­ly­Sort­El­e­ments)
Can­Com­pute­Size
Is­Du­pli­cate­Free
Tester(Is­Du­pli­cate­Free)
Is­ExtLEle­ment
Cat­e­go­ry­Col­lec­tions(Is­ExtLEle­ment)
Is­Ex­tREle­ment
Cat­e­go­ry­Col­lec­tions(Is­Ex­tREle­ment)
Cat­e­go­ry­Col­lec­tions(Is­Mul­ti­pli­ca­tive­El­e­ment)
Cat­e­go­ry­Col­lec­tions(Is­Mul­ti­pli­ca­tive­El­e­ment­With­One)
Cat­e­go­ry­Col­lec­tions(Is­Mul­ti­pli­ca­tive­El­e­ment­With­In­verse)
Cat­e­go­ry­Col­lec­tions(Is­As­so­cia­tive­El­e­ment)
Cat­e­go­ry­Col­lec­tions(Is­Fi­nite­Or­der­El­e­ment)
Is­Gen­er­al­ized­Do­main
Cat­e­go­ry­Col­lec­tions(Is­Perm)
Is­Mag­ma
Is­Mag­ma­With­One
Is­Mag­ma­With­In­vers­es­If­Nonze­ro
Is­Mag­ma­With­In­vers­es
Tester(Gen­er­a­tors­Of­Mag­ma­With­In­vers­es)
Is­Gen­er­a­tors­Of­Mag­ma­With­In­vers­es
Tester(Is­Gen­er­a­tors­Of­Mag­ma­With­In­vers­es)
Is­As­so­cia­tive
Tester(Is­As­so­cia­tive)
Is­Com­mu­ta­tive
Tester(Is­Com­mu­ta­tive)
Tester(Mul­ti­pli­ca­tive­Neu­tral­El­e­ment)
Is­Gen­er­a­tors­Of­Semi­group
Tester(Is­Gen­er­a­tors­Of­Semi­group)
Is­Sim­ple­Semi­group
Tester(Is­Sim­ple­Semi­group)
Is­Reg­u­lar­Semi­group
Tester(Is­Reg­u­lar­Semi­group)
Is­In­verse­Semi­group
Tester(Is­In­verse­Semi­group)
Is­Com­plete­ly­Reg­u­lar­Semi­group
Tester(Is­Com­plete­ly­Reg­u­lar­Semi­group)
Is­Com­plete­ly­Sim­ple­Semi­group
Tester(Is­Com­plete­ly­Sim­ple­Semi­group)
Is­Group­As­Semi­group
Tester(Is­Group­As­Semi­group)
Is­Monoid­As­Semi­group
Tester(Is­Monoid­As­Semi­group)
Is­Or­tho­dox­Semi­group
Tester(Is­Or­tho­dox­Semi­group)
Is­Cyclic
Tester(Is­Cyclic)
Is­Fi­nite­ly­Gen­er­at­ed­Group
Tester(Is­Fi­nite­ly­Gen­er­at­ed­Group)
Is­Sub­set­Lo­cal­ly­Fi­nite­Group
Tester(Is­Sub­set­Lo­cal­ly­Fi­nite­Group)
Can­Eas­i­ly­Test­Mem­ber­ship
Can­Eas­i­ly­Com­pute­With­In­de­pen­dent­Gens­Abelian­Group
Can­Com­pute­Size­Any­Sub­group
Knows­How­To­De­com­pose
Tester(Knows­How­To­De­com­pose)
Is­Nilpo­tent­Group
Tester(Is­Nilpo­tent­Group)
Is­Su­per­solv­able­Group
Tester(Is­Su­per­solv­able­Group)
Is­Mono­mi­al­Group
Tester(Is­Mono­mi­al­Group)
Is­Solv­able­Group
Tester(Is­Solv­able­Group)
Is­Poly­cyclic­Group
Tester(Is­Poly­cyclic­Group)
Can­Eas­i­ly­Com­pute­Pcgs
Can­Com­pute­Fit­ting­Free
Is­Nilpo­tent­By­Fi­nite
Tester(Is­Nilpo­tent­By­Fi­nite)

That output is quite daunting, but it reflects the current knowledge that GAP has about the object.

## Fam­i­lies

The idea behind families in GAP is to describe relationships between objects, and which operations can be applied between them. For example it makes little sense to try and multiply an integer by a permutation.

Families are created at runtime. For example when we create a finitely presented group, GAP creates a family of elements for that specific group.

 1
2
3
4
5
6
7
8
9
10
11gap> F := Free­Group(2);;
gap> G := F / [ F.1^2, F.2^2 ];
<fp group on the gen­er­a­tors [ f1, f2 ]>
gap> Fam­i­ly­Obj(Reprensen­ta­tive(G));
<Fam­i­ly: "Fam­i­ly­El­e­ments­Fp­Group">
gap> H := F / [ F.1^3, F.2 * F.1, F.1^5 ];
<fp group on the gen­er­a­tors [ f1, f2 ]>
gap> Fam­i­ly­Obj(Rep­re­sen­ta­tive(H));
<Fam­i­ly: "Fam­i­ly­El­e­ments­Fp­Group">
gap> Fam­i­ly­Obj(Rep­re­sen­ta­tive(G)) = Fam­i­ly­Obj(Rep­re­sen­ta­tive(H));
false

## Fil­ters

We’ll get back to families later, for now the more interesting bit is the filter.

A filter is

• an el­e­men­tary fil­ter, or
• a con­junc­tion of el­e­men­tary fil­ters

All elementary filters in a GAP session are identified by a unique integer, and a filter is thus represented as a (bit-)list of elementary filters.

Filters are special unary predicates on all objects. By convention most filters’ names begin with Is, with the exception of some filters whose name starts with Has.

The list of filters that return true for any given object in a GAP session can actually expand. This is to say that in GAP objects can change their type during their lifetime.

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21gap> Is­Ob­ject(1);
true
gap> Is­Ob­ject((1,2,3));
true
gap> Is­Int((1,2,3));
false
gap> Is­Int;
<Cat­e­go­ry "Is­Int">
gap> G := Group((1,2), (3,4));;
gap> Is­Mag­ma(G);
true;
gap> f := Is­Mag­ma and Is­Ring;
gap> f(G);
false
gap> Po­si­tion­Sub­list(Dis­play­String(Type­Obj(G)), "Is­Com­mu­ta­tive");
fail
gap> Is­Com­mu­ta­tive(G);
true
gap> Po­si­tion­Sub­list(Dis­play­String(Type­Obj(G)), "Is­Com­mu­ta­tive");
1084

The above code does cheat a little bit. I leave it as an exercise to find out why.

## Next time

Filters can roughly be classified as Categories, Representations, Properties and Others. In the next post we will first find out about Categories and Representations. These filters are set when an object is created, and don’t change during its lifetime. This is in contrast with properties and other filters which can change.