Cette section peut paraître plus technique que celles qui précèdent, mais nous pensons qu’il est important de comprendre ce que sont les parents et les coercitions pour utiliser comme il faut les structures algébriques fournies par Sage.
Nous allons voir ici ce que ces notions signifient, mais pas comment les mettre en œuvre pour implémenter une nouvelle structure algébrique. Un tutorial thématique couvrant ce point est disponible ici.
Une première approximation en Python de la notion mathématique d’anneau pourrait consister à définir une classe pour les éléments X de l’anneau concerné, de fournir les méthodes « double-underscore » nécessaires pour donner un sens aux opérations de l’anneau, par exemple __add__, __sub__ et __mul__, et naturellement de s’assurer qu’elles respectent les axiomes de la structure d’anneau.
Python étant un language (dynamiquement) fortement typé, on pourrait s’attendre à devoir implémenter une classe pour chaque anneau. Après tout, Python définit bien un type <int> pour les entiers, un type <float> pour les réels, et ainsi de suite. Mais cette approche ne peut pas fonctionner : il y a une infinité d’anneaux différents, et l’on ne peut pas implémenter une infinité de classes !
Une autre idée est de créer une hiérarchie de classes destinées à implémenter les éléments des structures algébriques usuelles : éléments de groupes, d’anneaux, d’algèbres à division, d’anneaux commutatifs, de corps, d’algèbres, etc.
Mais cela signifie que des éléments d’anneaux franchement différents peuvent avoir le même type.
sage: P.<x,y> = GF(3)[]
sage: Q.<a,b> = GF(4,'z')[]
sage: type(x)==type(a)
True
On pourrait aussi vouloir avoir des classes Python différentes pour fournir plusieurs implémentations d’une même structure mathématique (matrices denses contre matrices creuses par exemple).
sage: P.<a> = PolynomialRing(ZZ)
sage: Q.<b> = PolynomialRing(ZZ, sparse=True)
sage: R.<c> = PolynomialRing(ZZ, implementation='NTL')
sage: type(a); type(b); type(c)
<type 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>
<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse'>
<type 'sage.rings.polynomial.polynomial_integer_dense_ntl.Polynomial_integer_dense_ntl'>
Deux problèmes se posent alors. D’une part, si deux éléments sont instances de la même classe, on s’attend à ce que leur méthode __add__ soit capable de les additionner, alors que ce n’est pas ce que l’on souhaite si les éléments appartiennent en fait à des anneaux différents. D’autre part, si l’on a deux éléments qui appartiennent à des implémentations différentes d’un même anneau, on veut pouvoir les ajouter, et ce n’est pas immédiats s’ils ne sont pas instances de la même classe.
La solution à ces difficultés est fournie par le mécanisme de coercition décrit ci-dessous.
Mais avant tout, il est essentiel que chaque élément « sache » de quoi il est élément. Cette information est donnée par la méthode parent().
sage: a.parent(); b.parent(); c.parent()
Univariate Polynomial Ring in a over Integer Ring
Sparse Univariate Polynomial Ring in b over Integer Ring
Univariate Polynomial Ring in c over Integer Ring (using NTL)
En plus d’une hiérarchie de classes destinée à implémenter les éléments de structures algébriques, Sage fournit une hiérarchie similaire pour les structures elles-mêmes. Ces structures s’appellent en Sage des parents, et leurs classes dérivent d’une même classe de base. Celle-ci a des sous-classes « ensemble », « anneau », « corps », et ainsi de suite, dont la hiérarchie correspond à peu près à celle des concepts mathématiques qu’elles décrivent :
sage: isinstance(QQ,Field)
True
sage: isinstance(QQ, Ring)
True
sage: isinstance(ZZ,Field)
False
sage: isinstance(ZZ, Ring)
True
Or en algèbre, on regroupe les objets qui partagent le même genre de structure algébrique en ce que l’on appelle des catégories. Il y a donc un parallèle approximatif entre la hiérarchie des classes de Sage et la hiérarchie des catégories. Mais cette correspondance n’est pas parfaite, et Sage implémente par ailleurs les catégories en tant que telles :
sage: Rings()
Category of rings
sage: ZZ.category()
Category of euclidean domains
sage: ZZ.category().is_subcategory(Rings())
True
sage: ZZ in Rings()
True
sage: ZZ in Fields()
False
sage: QQ in Fields()
True
Tandis que la hiérarchie des classes est déterminée avant tout par des considérations de programmation, l’infrastructure des catégories cherche plutôt à respecter la structure mathématique. Elle permet de munir les objets d’une catégorie de méthodes et de tests génériques, qui ne dépendent pas de l’implémentation particulière d’un objet donné de la catégorie.
Les parents en tant qu’objets Python doivent être uniques. Ainsi, lorsqu’un anneau de polynômes sur un anneau donné et avec une liste donnée de générateurs est construit, il est conservé en cache et réutilisé par la suite :
sage: RR['x','y'] is RR['x','y']
True
Le type RingElement ne correspond pas parfaitement à la notion mathématique d’élément d’anneau. Par exemple, bien que les matrices carrées appartiennent à un anneau, elles ne sont pas de type RingElement :
sage: M = Matrix(ZZ,2,2); M
[0 0]
[0 0]
sage: isinstance(M, RingElement)
False
Si les parents sont censés être uniques, des éléments égaux d’un parent ne sont pas nécessairement identiques. Le comportement de Sage diffère ici de celui de Python pour certains entiers (pas tous) :
sage: int(1) is int(1) # Python int
True
sage: int(-15) is int(-15)
False
sage: 1 is 1 # Sage Integer
False
Il faut bien comprendre que les éléments d’anneaux différents ne se distinguent généralement pas par leur type, mais par leur parent :
sage: a = GF(2)(1)
sage: b = GF(5)(1)
sage: type(a) is type(b)
True
sage: parent(a)
Finite Field of size 2
sage: parent(b)
Finite Field of size 5
Ainsi, le parent d’un élément est plus important que son type du point de vue algébrique.
Il est parfois possible de convertir un élément d’un certain parent en élément d’un autre parent. Une telle conversion peut être explicite ou implicite. Les conversions implicites sont appelées coercitions.
Le lecteur aura peut-être rencontré les notions de conversion de type et de coercition de type dans le contexte du langage C par exemple. En Sage, il existe aussi des notions de conversion et de coercition, mais elles s’appliquent aux parents et non aux types. Attention donc à ne pas confondre les conversions en Sage avec les conversions de type du C !
Nous nous limitons ici à une brève présentation, et renvoyons le lecteur à la section du manuel de référence consacrée aux coercitions ainsi qu’au tutoriel spécifique pour plus de détails.
On peut adopter deux positions extrêmes sur les opérations arithmétiques entre éléments d’anneaux différents :
ou
Sage adopte un compromis. Si P1 et P2 sont des parents et si p1 est un élément de P1, l’utilisateur peut demander explicitement comment P1 s’interprète dans P2. Cela n’a pas forcément de sens dans tous les cas, et l’interprétation peut n’être définie que pour certains éléments de P1 ; c’est à l’utilisateur de s’assurer que la conversion a un sens. Cela s’appelle une conversion :
sage: a = GF(2)(1)
sage: b = GF(5)(1)
sage: GF(5)(a) == b
True
sage: GF(2)(b) == a
True
Cependant, une conversion implicite (c’est-à-dire automatique) n’est possible que si elle peut se faire systématiquement et de manière cohérente. Il faut ici absolument faire preuve de rigueur.
Une telle conversion implicite s’appelle une coercition. Si une coercition est définie entre deux parents, elle doit coïncider avec la conversion. De plus, les coercitions doivent obéir aux deux conditions suivantes :
Ainsi, bien qu’il soit possible de convertir tout élément de GF(2) en un élément de GF(5), la conversion ne peut être une coercition, puisque il n’existe pas de morphisme d’anneaux de GF(2) dans GF(5).
Le second point — la cohérence des choix — est un peu plus compliqué à expliquer. Illustrons-le sur l’exemple des anneaux de polynômes multivariés. Dans les applications, il s’avère utile que les coercitions respectent les noms des variables. Nous avons donc :
sage: R1.<x,y> = ZZ[]
sage: R2 = ZZ['y','x']
sage: R2.has_coerce_map_from(R1)
True
sage: R2(x)
x
sage: R2(y)
y
En l’absence d’un morphisme d’anneau qui préserve les noms de variable, la coercition entre anneaux de polynômes multivariés n’est pas définie. Il peut tout de même exister une conversion qui envoie les variables d’un anneau sur celle de l’autre en fonction de leur position dans la liste des générateurs :
sage: R3 = ZZ['z','x']
sage: R3.has_coerce_map_from(R1)
False
sage: R3(x)
z
sage: R3(y)
x
Mais une telle conversion ne répond pas aux critères pour être une coercition : en effet, en composant l’application de ZZ['x','y'] dans ZZ['y','x'] avec celle qui préserve les positions de ZZ['y','x'] dans ZZ['a','b'], nous obtiendrions une application qui ne préserve ni les noms ni les positions, ce qui viole la règle de cohérence.
Lorsqu’une coercition est définie, elle est souvent utilisée pour comparer des éléments d’anneaux différents ou pour effectuer des opérations arithmétiques. Cela est commode, mais il faut être prudent en étendant la relation d’égalité == au-delà des frontières d’un parent donné. Par exemple, si == est bien censé être une relation d’équivalence entre éléments d’un anneau, il n’en va pas forcément de même quand on compare des éléments d’anneaux différents. Ainsi, les éléments 1 de ZZ et d’un corps fini sont considérés comme égaux, puisqu’il existe une coercition canonique des entiers dans tout corps fini. En revanche, il n’y a en général pas de coercition entre deux corps finis quelconques. On a donc
sage: GF(5)(1) == 1
True
sage: 1 == GF(2)(1)
True
sage: GF(5)(1) == GF(2)(1)
False
sage: GF(5)(1) != GF(2)(1)
True
De même, on a
sage: R3(R1.1) == R3.1
True
sage: R1.1 == R3.1
False
sage: R1.1 != R3.1
True
Une autre conséquence de la condition de cohérence est que les coercitions ne sont possibles que des anneaux exacts (comme les rationnels QQ) vers les anneaux inexacts (comme les réels à précision donnée RR), jamais l’inverse. En effet, pour qu’une conversion de RR dans QQ puisse être une coercition, il faudrait que la composée de la coercition de QQ dans RR et de cette conversion soit l’identité sur QQ, ce qui n’est pas possible puisque des rationnels distincts peuvent très bien être envoyés sur le même élément de RR :
sage: RR(1/10^200+1/10^100) == RR(1/10^100)
True
sage: 1/10^200+1/10^100 == 1/10^100
False
Lorsque l’on compare des éléments de deux parents P1 et P2, il peut arriver qu’il n’existe pas de coercition entre P1 et P2, mais qu’il y ait un choix canonique de parent P3 tel que P1 et P2 admettent tous deux des coercitions dans P3. Dans ce cas aussi, la coercition a lieu. Un exemple typique de ce mécanisme est l’addition d’un rationnel et d’un polynôme à coefficients entiers, qui produit un polynôme à coefficients rationnels :
sage: P1.<x> = ZZ[]
sage: p = 2*x+3
sage: q = 1/2
sage: parent(p)
Univariate Polynomial Ring in x over Integer Ring
sage: parent(p+q)
Univariate Polynomial Ring in x over Rational Field
Notons qu’en principe, on aurait très bien pu choisir pour P3 le corps des fractions de ZZ['x']. Cependant, Sage tente de choisir un parent commun canonique aussi naturel que possible (ici QQ['x']). Afin que cela fonctionne de façon fiable, Sage ne se contente pas de prendre n’importe lequel lorsque plusieurs candidats semblent aussi naturels les uns que les autres. La manière dont le choix est fait est décrite dans le tutoriel spécifique déjà mentionné.
Dans l’exemple suivant, il n’y a pas de coercition vers un parent commun :
sage: R.<x> = QQ[]
sage: S.<y> = QQ[]
sage: x+y
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '+': 'Univariate Polynomial Ring in x over Rational Field' and 'Univariate Polynomial Ring in y over Rational Field'
En effet, Sage refuse de choisir entre les candidats QQ['x']['y'], QQ['y']['x'], QQ['x','y'] et QQ['y','x'], car ces quatre structures deux à deux distinctes semblent toutes des parents communs naturels, et aucun choix canonique ne s’impose.