This repository has been archived by the owner on Jan 30, 2023. It is now read-only.
-
-
Notifications
You must be signed in to change notification settings - Fork 7
/
primer.py
1661 lines (1237 loc) · 60.7 KB
/
primer.py
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
r"""
Elements, parents, and categories in Sage: a (draft of) primer
.. contents::
:depth: 2
Abstract
========
The purpose of categories in Sage is to translate the mathematical
concept of categories (category of groups, of vector spaces, ...)
into a concrete software engineering design pattern for:
- organizing and promoting generic code
- fostering consistency across the Sage library (naming
conventions, doc, tests)
- embedding more mathematical knowledge into the system
This design pattern is largely inspired from Axiom and its
followers (Aldor, Fricas, MuPAD, ...). It differs from those by:
- blending in the Magma inspired concept of Parent/Element
- being built on top of (and not into) the standard Python object
oriented and class hierarchy mechanism. This did not require
changing the language, and could in principle be implemented in
any language supporting the creation of new classes dynamically.
The general philosophy is that *Building mathematical information
into the system yields more expressive, more conceptual and, at
the end, easier to maintain and faster code* (within a programming
realm; this would not necessarily apply to specialized libraries
like gmp!).
One line pitch for mathematicians
---------------------------------
Categories in Sage provide a library of interrelated bookshelves, with
each bookshelf containing algorithms, tests, documentation, or some
mathematical facts about the objects of a given category (e.g. groups).
One line pitch for programmers
------------------------------
Categories in Sage provide a large hierarchy of abstract classes for
mathematical objects. To keep it maintainable, the inheritance
information between the classes is not hardcoded but instead
reconstructed dynamically from duplication free semantic information.
Introduction: Sage as a library of objects and algorithms
=========================================================
The Sage library, with more than one million lines of code,
documentation, and tests, implements:
- Thousands of different kinds of objects (classes):
Integers, polynomials, matrices, groups, number fields, elliptic
curves, permutations, morphisms, languages, ... and a few racoons ...
- Tens of thousands methods and functions:
Arithmetic, integer and polynomial factorization, pattern matching
on words, ...
Some challenges
---------------
- How to organize this library?
One needs some bookshelves to group together related objects and algorithms.
- How to ensure consistency?
Similar objects should behave similarly::
sage: Permutations(5).cardinality()
120
sage: GL(2,2).cardinality()
6
sage: A=random_matrix(ZZ,6,3,x=7)
sage: L=LatticePolytope(A.rows())
sage: L.npoints() # oops! # random
37
- How to ensure robustness?
- How to reduce duplication?
Example: binary powering::
sage: m = 3
sage: m^8 == m*m*m*m*m*m*m*m == ((m^2)^2)^2
True
::
sage: m=random_matrix(QQ, 4, algorithm='echelonizable', rank=3, upper_bound=60)
sage: m^8 == m*m*m*m*m*m*m*m == ((m^2)^2)^2
True
We want to implement binary powering only once, as *generic* code
that will apply in all cases.
A bit of help from abstract algebra
===================================
The hierarchy of categories
---------------------------
What makes binary powering work in the above examples? In both cases,
we have *a set* endowed with a *multiplicative binary operation* which
is *associative*. Such a set is called a *semigroup*, and binary
powering works generally for any semigroup.
Sage knows about semigroups::
sage: Semigroups()
Category of semigroups
and sure enough, binary powering is defined there::
sage: m._pow_.__module__
'sage.categories.semigroups'
That's our bookshelf! And it's used in many places::
sage: GL(2,ZZ) in Semigroups()
True
sage: NN in Semigroups()
True
For a less trivial bookshelf we can consider euclidean rings: once we
know how to do euclidean division in some set `R`, we can compute
gcd's in `R` generically using the Euclidean algorithm.
We are in fact very lucky: abstract algebra provides us right away
with a large and robust set of bookshelves which is the result of
centuries of work of mathematicians to identify the important
concepts. This includes for example::
sage: Sets()
Category of sets
sage: Groups()
Category of groups
sage: Rings()
Category of rings
sage: Fields()
Category of fields
sage: HopfAlgebras(QQ)
Category of hopf algebras over Rational Field
Each of the above is called a *category*. It typically specifies what
are the operations on the elements, as well as the axioms satisfied by
those operations. For example the category of groups specifies that a
group is a set endowed with a binary operation (the multiplication)
which is associative and admits a unit and inverses.
Each set in Sage knows which bookshelf of generic algorithms it can
use, that is to which category it belongs::
sage: G = GL(2,ZZ)
sage: G.category()
Category of groups
In fact a group is a semigroup, and Sage knows about this::
sage: Groups().is_subcategory(Semigroups())
True
sage: G in Semigroups()
True
Altogether, our group gets algorithms from a bunch of bookshelves::
sage: G.categories()
[Category of groups, Category of monoids, Category of semigroups,
...,
Category of magmas,
Category of sets, ...]
Those can be viewed graphically::
sage: g = Groups().category_graph()
sage: g.set_latex_options(format="dot2tex")
sage: view(g, tightpage=True) # not tested
In case ``dot2tex`` is not available, you can use instead::
sage: g.show(vertex_shape=None, figsize=20)
Here is an overview of all categories in Sage::
sage: g = sage.categories.category.category_graph()
sage: g.set_latex_options(format="dot2tex")
sage: view(g, tightpage=True) # not tested
Wrap-up: generic algorithms in Sage are organized in a hierarchy of
bookshelves modelled upon the usual hierarchy of categories provided
by abstract algebra.
.. _category-primer-parents-elements-categories:
Elements, Parents, Categories
-----------------------------
.. RUBRIC:: Parent
A *parent* is a Python instance modelling a set of mathematical
elements together with its additional (algebraic) structure.
Examples include the ring of integers, the group `S_3`, the set of
prime numbers, the set of linear maps between two given vector
spaces, and a given finite semigroup.
These sets are often equipped with additional structure: the set
of all integers forms a ring. The main way of encoding this
information is specifying which categories a parent belongs to.
It is completely possible to have different Python instances
modelling the same set of elements. For example, one might want
to consider the ring of integers, or the poset of integers under
their standard order, or the poset of integers under divisibility,
or the semiring of integers under the operations of maximum and
addition. Each of these would be a different instance, belonging
to different categories.
For a given model, there should be a unique instance in Sage
representing that parent::
sage: IntegerRing() is IntegerRing()
True
.. RUBRIC:: Element
An *element* is a Python instance modelling a mathematical element
of a set.
Examples of element include `5` in the integer ring, `x^3 - x` in
the polynomial ring in `x` over the rationals, `4 + O(3^3)` in the
3-adics, the transposition `(1 2)` in `S_3`, and the identity
morphism in the set of linear maps from `\QQ^3` to `\QQ^3`.
Every element in Sage has a parent. The standard idiom in Sage
for creating elements is to create their parent, and then provide
enough data to define the element::
sage: R = PolynomialRing(ZZ, name='x')
sage: R([1,2,3])
3*x^2 + 2*x + 1
One can also create elements using various methods on the parent
and arithmetic of elements::
sage: x = R.gen()
sage: 1 + 2*x + 3*x^2
3*x^2 + 2*x + 1
Unlike parents, elements in Sage are not necessarily unique::
sage: ZZ(5040) is ZZ(5040)
False
Many parents model algebraic structures, and their elements
support arithmetic operations. One often further wants to do
arithmetic by combining elements from different parents: adding
together integers and rationals for example. Sage supports this
feature using coercion (see :mod:`sage.structure.coerce` for more
details).
It is possible for a parent to also have simultaneously the
structure of an element. Consider for example the monoid of all
finite groups, endowed with the Cartesian product operation.
Then, every finite group (which is a parent) is also an element of
this monoid. This is not yet implemented, and the design details
are not yet fixed but experiments are underway in this direction.
.. TODO:: Give a concrete example, typically using :class:`ElementWrapper`.
.. RUBRIC:: Category
A *category* is a Python instance modelling a mathematical category.
Examples of categories include the category of finite semigroups,
the category of all (Python) objects, the category of
`\ZZ`-algebras, and the category of Cartesian products of
`\ZZ`-algebras::
sage: FiniteSemigroups()
Category of finite semigroups
sage: Objects()
Category of objects
sage: Algebras(ZZ)
Category of algebras over Integer Ring
sage: Algebras(ZZ).CartesianProducts()
Category of Cartesian products of algebras over Integer Ring
Mind the 's' in the names of the categories above;
``GroupAlgebra`` and ``GroupAlgebras`` are distinct things.
Every parent belongs to a collection of categories. Moreover,
categories are interrelated by the *super categories*
relation. For example, the category of rings is a super category
of the category of fields, because every field is also a ring.
A category serves two roles:
- to provide a model for the mathematical concept of a category
and the associated structures: homsets, morphisms, functorial
constructions, axioms.
- to organize and promote generic code, naming conventions,
documentation, and tests across similar mathematical structures.
.. RUBRIC:: CategoryObject
Objects of a mathematical category are not necessarily parents.
Parent has a superclass that provides a means of modeling such.
For example, the category of schemes does not have a faithful
forgetful functor to the category of sets, so it does not make
sense to talk about schemes as parents.
.. RUBRIC:: Morphisms, Homsets
As category theorists will expect, *Morphisms* and *Homsets* will
play an ever more important role, as support for them will
improve.
----
Much of the mathematical information in Sage is encoded as relations
between elements and their parents, parents and their categories, and
categories and their super categories::
sage: 1.parent()
Integer Ring
sage: ZZ
Integer Ring
sage: ZZ.category()
Join of Category of euclidean domains
and Category of infinite enumerated sets
and Category of metric spaces
sage: ZZ.categories()
[Join of Category of euclidean domains
and Category of infinite enumerated sets
and Category of metric spaces,
Category of euclidean domains, Category of principal ideal domains,
Category of unique factorization domains, Category of gcd domains,
Category of integral domains, Category of domains,
Category of commutative rings, Category of rings, ...
Category of magmas and additive magmas, ...
Category of monoids, Category of semigroups,
Category of commutative magmas, Category of unital magmas, Category of magmas,
Category of commutative additive groups, ..., Category of additive magmas,
Category of infinite enumerated sets, Category of enumerated sets,
Category of infinite sets, Category of metric spaces,
Category of topological spaces, Category of sets,
Category of sets with partial maps,
Category of objects]
sage: g = EuclideanDomains().category_graph()
sage: g.set_latex_options(format="dot2tex")
sage: view(g, tightpage=True) # not tested
A bit of help from computer science
===================================
Hierarchy of classes
--------------------
How are the bookshelves implemented in practice?
Sage uses the classical design paradigm of Object Oriented Programming
(OOP). Its fundamental principle is that any object that a program is
to manipulate should be modelled by an *instance* of a *class*. The
class implements:
- a *data structure*: which describes how the object is stored,
- *methods*: which describe the operations on the object.
The instance itself contains the data for the given object, according
to the specified data structure.
Hence, all the objects mentioned above should be instances of some
classes. For example, an integer in Sage is an instance of the class
:class:`Integer` (and it knows about it!)::
sage: i = 12
sage: type(i)
<type 'sage.rings.integer.Integer'>
Applying an operation is generally done by *calling a method*::
sage: i.factor()
2^2 * 3
sage: x = var('x')
sage: p = 6*x^2 + 12*x + 6
sage: type(p)
<type 'sage.symbolic.expression.Expression'>
sage: p.factor()
6*(x + 1)^2
sage: R.<x> = PolynomialRing(QQ, sparse=True)
sage: pQ = R ( p )
sage: type(pQ)
<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse_field'>
sage: pQ.factor()
(6) * (x + 1)^2
sage: pZ = ZZ['x'] ( p )
sage: type(pZ)
<type 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>
sage: pZ.factor()
2 * 3 * (x + 1)^2
Factoring integers, expressions, or polynomials are distinct tasks,
with completely different algorithms. Yet, from a user (or caller)
point of view, all those objects can be manipulated alike. This
illustrates the OOP concepts of *polymorphism*, *data abstraction*,
and *encapsulation*.
Let us be curious, and see where some methods are defined. This can be
done by introspection::
sage: i._mul_?? # not tested
For plain Python methods, one can also just ask in which module they
are implemented::
sage: i._pow_.__module__
'sage.categories.semigroups'
sage: pQ._mul_.__module__
'sage.rings.polynomial.polynomial_element_generic'
sage: pQ._pow_.__module__
'sage.categories.semigroups'
We see that integers and polynomials have each their own
multiplication method: the multiplication algorithms are indeed
unrelated and deeply tied to their respective datastructures. On the
other hand, as we have seen above, they share the same powering method
because the set `\ZZ` of integers, and the set `\QQ[x]` of
polynomials are both semigroups. Namely, the class for integers and
the class for polynomials both derive from an *abstract class* for
semigroup elements, which factors out the *generic* methods like
``_pow_``. This illustrates the use of *hierarchy of classes* to share
common code between classes having common behaviour.
OOP design is all about isolating the objects that one wants to model
together with their operations, and designing an appropriate hierarchy
of classes for organizing the code. As we have seen above, the design
of the class hierarchy is easy since it can be modelled upon the
hierarchy of categories (bookshelves). Here is for example a piece of
the hierarchy of classes for an element of a group of permutations::
sage: P = Permutations(4)
sage: m = P.an_element()
sage: for cls in m.__class__.mro(): print cls
<class 'sage.combinat.permutation.StandardPermutations_n_with_category.element_class'>
<class 'sage.combinat.permutation.StandardPermutations_n.Element'>
<class 'sage.combinat.permutation.Permutation'>
...
<class 'sage.categories.groups.Groups.element_class'>
<class 'sage.categories.monoids.Monoids.element_class'>
...
<class 'sage.categories.semigroups.Semigroups.element_class'>
...
On the top, we see concrete classes that describe the data structure
for matrices and provide the operations that are tied to this data
structure. Then follow abstract classes that are attached to the
hierarchy of categories and provide generic algorithms.
The full hierarchy is best viewed graphically::
sage: g = class_graph(m.__class__)
sage: g.set_latex_options(format="dot2tex")
sage: view(g, tightpage=True) # not tested
Parallel hierarchy of classes for parents
-----------------------------------------
Let us recall that we do not just want to compute with elements of
mathematical sets, but with the sets themselves::
sage: ZZ.one()
1
sage: R = QQ['x,y']
sage: R.krull_dimension()
2
sage: A = R.quotient( R.ideal(x^2 - 2) )
sage: A.krull_dimension() # todo: not implemented
Here are some typical operations that one may want to carry on various
kinds of sets:
- The set of permutations of 5, the set of rational points of an
elliptic curve: counting, listing, random generation
- A language (set of words): rationality testing, counting elements,
generating series
- A finite semigroup: left/right ideals, center, representation theory
- A vector space, an algebra: Cartesian product, tensor product, quotient
Hence, following the OOP fundamental principle, parents should also be
modelled by instances of some (hierarchy of) classes. For example, our
group `G` is an instance of the following class::
sage: G = GL(2,ZZ)
sage: type(G)
<class 'sage.groups.matrix_gps.linear.LinearMatrixGroup_gap_with_category'>
Here is a piece of the hierarchy of classes above it::
sage: for cls in G.__class__.mro(): print cls
<class 'sage.groups.matrix_gps.linear.LinearMatrixGroup_gap_with_category'>
...
<class 'sage.categories.groups.Groups.parent_class'>
<class 'sage.categories.monoids.Monoids.parent_class'>
<class 'sage.categories.semigroups.Semigroups.parent_class'>
...
Note that the hierarchy of abstract classes is again attached to
categories and parallel to that we had seen for the elements. This is
best viewed graphically::
sage: g = class_graph(m.__class__)
sage: g.relabel(lambda x: x.replace("_","\_"))
sage: g.set_latex_options(format="dot2tex")
sage: view(g, tightpage=True) # not tested
.. NOTE::
This is a progress upon systems like Axiom or MuPAD where a parent
is modelled by the class of its elements; this oversimplification
leads to confusion between methods on parents and elements, and
makes parents special; in particular it prevents potentially
interesting constructions like "groups of groups".
Sage categories
===============
Why this business of categories? And to start with, why don't we just
have a good old hierarchy of classes ``Group``, ``Semigroup``,
``Magma``, ... ?
Dynamic hierarchy of classes
----------------------------
As we have just seen, when we manipulate groups, we actually
manipulate several kinds of objects:
- groups
- group elements
- morphisms between groups
- and even the category of groups itself!
Thus, on the group bookshelf, we want to put generic code for each of
the above. We therefore need three, parallel hierarchies of abstract
classes:
- Group, Monoid, Semigroup, Magma, ...
- GroupElement, MonoidElement, SemigroupElement, MagmaElement, ...
- GroupMorphism, SemigroupElement, SemigroupMorphism, MagmaMorphism, ...
(and in fact many more as we will see).
We could implement the above hierarchies as usual::
class Group(Monoid):
# generic methods that apply to all groups
class GroupElement(MonoidElement):
# generic methods that apply to all group elements
class GroupMorphism(MonoidMorphism):
# generic methods that apply to all group morphisms
And indeed that's how it was done in Sage before 2009, and there are
still many traces of this. The drawback of this approach is
duplication: the fact that a group is a monoid is repeated three times
above!
Instead, Sage now uses the following syntax, where the :class:`Groups`
bookshelf is structured into units with *nested classes*::
class Groups(Category):
def super_categories(self):
return [Monoids(), ...]
class ParentMethods:
# generic methods that apply to all groups
class ElementMethods:
# generic methods that apply to all group elements
class MorphismMethods:
# generic methods that apply to all group morphisms (not yet implemented)
class SubcategoryMethods:
# generic methods that apply to all subcategories of Groups()
With this syntax, the information that a group is a monoid is
specified only once, in the :meth:`Category.super_categories`
method. And indeed, when the category of inverse unital magmas was
introduced, there was a *single point of truth* to update in order to
reflect the fact that a group is an inverse unital magma::
sage: Groups().super_categories()
[Category of monoids, Category of inverse unital magmas]
The price to pay (there is no free lunch) is that some magic is
required to construct the actual hierarchy of classes for parents,
elements, and morphisms. Namely, ``Groups.ElementMethods`` should be
seen as just a bag of methods, and the actual class
``Groups().element_class`` is constructed from it by adding the
appropriate super classes according to
``Groups().super_categories()``::
sage: Groups().element_class
<class 'sage.categories.groups.Groups.element_class'>
sage: Groups().element_class.__bases__
(<class 'sage.categories.monoids.Monoids.element_class'>,
<class 'sage.categories.magmas.Magmas.Unital.Inverse.element_class'>)
We now see that the hierarchy of classes for parents and elements is
parallel to the hierarchy of categories::
sage: Groups().all_super_categories()
[Category of groups,
Category of monoids,
Category of semigroups,
...
Category of magmas,
Category of sets,
...]
sage: for cls in Groups().element_class.mro(): print cls
<class 'sage.categories.groups.Groups.element_class'>
<class 'sage.categories.monoids.Monoids.element_class'>
<class 'sage.categories.semigroups.Semigroups.element_class'>
...
<class 'sage.categories.magmas.Magmas.element_class'>
...
sage: for cls in Groups().parent_class.mro(): print cls
<class 'sage.categories.groups.Groups.parent_class'>
<class 'sage.categories.monoids.Monoids.parent_class'>
<class 'sage.categories.semigroups.Semigroups.parent_class'>
...
<class 'sage.categories.magmas.Magmas.parent_class'>
...
Another advantage of building the hierarchy of classes dynamically is
that, for parametrized categories, the hierarchy may depend on the
parameters. For example an algebra over `\QQ` is a `\QQ`-vector space,
but an algebra over `\ZZ` is not (it is just a `\ZZ`-module)!
.. NOTE::
At this point this whole infrastructure may feel like
overdesigning, right? We felt like this too! But we will see later
that, once one gets used to it, this approach scales very
naturally.
From a computer science point of view, this infrastructure
implements, on top of standard multiple inheritance, a dynamic
composition mechanism of mixin classes (:wikipedia:`Mixin`),
governed by mathematical properties.
For implementation details on how the hierarchy of classes for
parents and elements is constructed, see :class:`Category`.
.. _category-primer-subcategory:
On the category hierarchy: subcategories and super categories
-------------------------------------------------------------
We have seen above that, for example, the category of sets is a super
category of the category of groups. This models the fact that a group
can be unambiguously considered as a set by forgetting its group
operation. In object-oriented parlance, we want the relation "a group
*is a* set", so that groups can directly inherit code implemented on
sets.
Formally, a category ``Cs()`` is a *super category* of a category
``Ds()`` if Sage considers any object of ``Ds()`` to be an object of
``Cs()``, up to an implicit application of a canonical functor from
``Ds()`` to ``Cs()``. This functor is normally an inclusion of
categories or a forgetful functor. Reciprocally, ``Ds()`` is said to
be a *subcategory* of ``Cs()``.
.. WARNING::
This terminology deviates from the usual mathematical definition
of *subcategory* and is subject to change. Indeed, the forgetful
functor from the category of groups to the category of sets is not
an inclusion of categories, as it is not injective: a given set
may admit more than one group structure. See :trac:`16183` for
more details. The name *supercategory* is also used with a
different meaning in certain areas of mathematics.
Categories are instances and have operations
--------------------------------------------
Note that categories themselves are naturally modelled by instances
because they can have operations of their own. An important one is::
sage: Groups().example()
General Linear Group of degree 4 over Rational Field
which gives an example of object of the category. Besides illustrating
the category, the example provides a minimal template for implementing
a new object in the category::
sage: S = Semigroups().example(); S
An example of a semigroup: the left zero semigroup
Its source code can be obtained by introspection::
sage: S?? # not tested
This example is also typically used for testing generic methods. See
:meth:`Category.example` for more.
Other operations on categories include querying the super categories
or the axioms satisfied by the operations of a category::
sage: Groups().super_categories()
[Category of monoids, Category of inverse unital magmas]
sage: Groups().axioms()
frozenset({'Associative', 'Inverse', 'Unital'})
or constructing the intersection of two categories, or the smallest
category containing them::
sage: Groups() & FiniteSets()
Category of finite groups
sage: Algebras(QQ) | Groups()
Category of monoids
Specifications and generic documentation
----------------------------------------
Categories do not only contain code but also the specifications of the
operations. In particular a list of mandatory and optional methods to
be implemented can be found by introspection with::
sage: Groups().required_methods()
{'element': {'optional': ['_mul_'], 'required': []},
'parent': {'optional': [], 'required': ['__contains__']}}
Documentation about those methods can be obtained with::
sage: G = Groups()
sage: G.element_class._mul_? # not tested
sage: G.parent_class.one? # not tested
See also the :func:`abstract_method` decorator.
.. WARNING::
Well, more precisely, that's how things should be, but there is
still some work to do in this direction. For example, the inverse
operation is not specified above. Also, we are still missing a
good programmatic syntax to specify the input and output types of
the methods. Finally, in many cases the implementer must provide
at least one of two methods, each having a default implementation
using the other one (e.g. listing or iterating for a finite
enumerated set); there is currently no good programmatic way to
specify this.
Generic tests
-------------
Another feature that parents and elements receive from categories is
generic tests; their purpose is to check (at least to some extent)
that the parent satisfies the required mathematical properties (is my
semigroup indeed associative?) and is implemented according to the
specifications (does the method ``an_element`` indeed return an
element of the parent?)::
sage: S = FiniteSemigroups().example(alphabet=('a', 'b'))
sage: TestSuite(S).run(verbose = True)
running ._test_an_element() . . . pass
running ._test_associativity() . . . pass
running ._test_cardinality() . . . pass
running ._test_category() . . . pass
running ._test_elements() . . .
Running the test suite of self.an_element()
running ._test_category() . . . pass
running ._test_eq() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
pass
running ._test_elements_eq_reflexive() . . . pass
running ._test_elements_eq_symmetric() . . . pass
running ._test_elements_eq_transitive() . . . pass
running ._test_elements_neq() . . . pass
running ._test_enumerated_set_contains() . . . pass
running ._test_enumerated_set_iter_cardinality() . . . pass
running ._test_enumerated_set_iter_list() . . . pass
running ._test_eq() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
running ._test_some_elements() . . . pass
Tests can be run individually::
sage: S._test_associativity()
Here is how to access the code of this test::
sage: S._test_associativity?? # not tested
Here is how to run the test on all elements::
sage: L = S.list()
sage: S._test_associativity(elements=L)
See :class:`TestSuite` for more information.
Let us see what happens when a test fails. Here we redefine the
product of `S` to something definitely not associative::
sage: S.product = lambda x, y: S("("+x.value +y.value+")")
And rerun the test::
sage: S._test_associativity(elements=L)
Traceback (most recent call last):
...
File ".../sage/categories/semigroups.py", line ..., in _test_associativity
tester.assert_((x * y) * z == x * (y * z))
...
AssertionError: False is not true
We can recover instantly the actual values of ``x``, ``y``, ``z``, that is,
a counterexample to the associativity of our broken semigroup, using post
mortem introspection with the Python debugger ``pdb`` (this does not
work yet in the notebook)::
sage: import pdb
sage: pdb.pm() # not tested
> /opt/sage-5.11.rc1/local/lib/python/unittest/case.py(424)assertTrue()
-> raise self.failureException(msg)
(Pdb) u
> /opt/sage-5.11.rc1/local/lib/python2.7/site-packages/sage/categories/semigroups.py(145)_test_associativity()
-> tester.assert_((x * y) * z == x * (y * z))
(Pdb) p x, y, z
('a', 'a', 'a')
(Pdb) p (x * y) * z
'((aa)a)'
(Pdb) p x * (y * z)
'(a(aa))'
Wrap-up
-------
- Categories provide a natural hierarchy of bookshelves to organize
not only code, but also specifications and testing tools.
- Everything about, say, algebras with a distinguished basis is
gathered in :class:`AlgebrasWithBasis` or its super categories.
This includes properties and algorithms for elements, parents,
morphisms, but also, as we will see, for constructions like
Cartesian products or quotients.
- The mathematical relations between elements, parents, and categories
translate dynamically into a traditional hierarchy of classes.
- This design enforces robustness and consistency, which is
particularly welcome given that Python is an interpreted language
without static type checking.
Case study
==========
In this section, we study an existing parent in detail; a good followup is to
go through the :mod:`sage.categories.tutorial` or the thematic tutorial on
coercion and categories ("How to implement new algebraic structures in Sage")
to learn how to implement a new one!
We consider the example of finite semigroup provided by the category::
sage: S = FiniteSemigroups().example(); S
An example of a finite semigroup: the left regular band generated by ('a', 'b', 'c', 'd')
sage: S? # not tested
Where do all the operations on ``S`` and its elements come from?
::
sage: x = S('a')
``_repr_`` is a technical method which comes with the data structure
(:class:`ElementWrapper`); since it's implemented in Cython, we need
to use Sage's introspection tools to recover where it's implemented::
sage: x._repr_.__module__
sage: sage.misc.sageinspect.sage_getfile(x._repr_)
'.../sage/structure/element_wrapper.pyx'
``__pow__`` is a generic method for all finite semigroups::
sage: x.__pow__.__module__
'sage.categories.semigroups'
``__mul__`` is a default implementation from the :class:`Magmas`
category (a *magma* is a set with an inner law `*`, not necessarily
associative)::
sage: x.__mul__.__module__
'sage.categories.magmas'
It delegates the work to the parent (following the advice: if you do
not know what to do, ask your parent)::
sage: x.__mul__?? # not tested
``product`` is a mathematical method implemented by the parent::
sage: S.product.__module__
'sage.categories.examples.finite_semigroups'
``cayley_graph`` is a generic method on the parent, provided by the
:class:`FiniteSemigroups` category::
sage: S.cayley_graph.__module__
'sage.categories.semigroups'
``multiplication_table`` is a generic method on the parent, provided
by the :class:`Magmas` category (it does not require associativity)::
sage: S.multiplication_table.__module__
'sage.categories.magmas'
Consider now the implementation of the semigroup::
sage: S?? # not tested
This implementation specifies a data structure for the parents and the
elements, and makes a promise: the implemented parent is a finite
semigroup. Then it fulfills the promise by implementing the basic
operation ``product``. It also implements the optional method
``semigroup_generators``. In exchange, `S` and its elements receive
generic implementations of all the other operations. `S` may override
any of those by more efficient ones. It may typically implement the
element method ``is_idempotent`` to always return ``True``.
A (not yet complete) list of mandatory and optional methods to be
implemented can be found by introspection with::
sage: FiniteSemigroups().required_methods()
{'element': {'optional': ['_mul_'], 'required': []},
'parent': {'optional': ['semigroup_generators'],
'required': ['__contains__']}}
``product`` does not appear in the list because a default implementation
is provided in term of the method ``_mul_`` on elements. Of course, at
least one of them should be implemented. On the other hand, a default
implementation for ``__contains__`` is provided by :class:`Parent`.
Documentation about those methods can be obtained with::
sage: C = FiniteSemigroups().element_class
sage: C._mul_? # not tested
See also the :func:`~sage.misc.abstract_method.abstract_method` decorator.
Here is the code for the finite semigroups category::
sage: FiniteSemigroups?? # not tested
Specifying the category of a parent
===================================
Some parent constructors (not enough!) allow to specify the desired
category for the parent. This can typically be used to specify
additional properties of the parent that we know to hold a priori. For
example, permutation groups are by default in the category of finite
permutation groups (no surprise)::