Linéarisation C3 — Wikipédia

Un article de Wikipédia, l'encyclopédie libre.

La mise en forme de cet article est à améliorer (septembre 2022).

La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».

Comment faire ?

Les points d'amélioration suivants sont les cas les plus fréquents. Le détail des points à revoir est peut-être précisé sur la page de discussion.

• Les titres sont pré-formatés par le logiciel. Ils ne sont ni en capitales, ni en gras.
• Le texte ne doit pas être écrit en capitales (les noms de famille non plus), ni en gras, ni en italique, ni en « petit »…
• Le gras n'est utilisé que pour surligner le titre de l'article dans l'introduction, une seule fois.
• L'italique est rarement utilisé : mots en langue étrangère, titres d'œuvres, noms de bateaux, etc.
• Les citations ne sont pas en italique mais en corps de texte normal. Elles sont entourées par des guillemets français : « et ».
• Les listes à puces sont à éviter, des paragraphes rédigés étant largement préférés. Les tableaux sont à réserver à la présentation de données structurées (résultats, etc.).
• Les appels de note de bas de page (petits chiffres en exposant, introduits par l'outil «  Source ») sont à placer entre la fin de phrase et le point final^{[comme ça]}.
• Les liens internes (vers d'autres articles de Wikipédia) sont à choisir avec parcimonie. Créez des liens vers des articles approfondissant le sujet. Les termes génériques sans rapport avec le sujet sont à éviter, ainsi que les répétitions de liens vers un même terme.
• Les liens externes sont à placer uniquement dans une section « Liens externes », à la fin de l'article. Ces liens sont à choisir avec parcimonie suivant les règles définies. Si un lien sert de source à l'article, son insertion dans le texte est à faire par les notes de bas de page.
• La présentation des références doit suivre les conventions bibliographiques. Il est recommandé d'utiliser les modèles {{Ouvrage}}, {{Chapitre}}, {{Article}}, {{Lien web}} et/ou {{Bibliographie}}. Le mode d'édition visuel peut mettre en forme automatiquement les références.
• Insérer une infobox (cadre d'informations à droite) n'est pas obligatoire pour parachever la mise en page.

Pour une aide détaillée, merci de consulter Aide:Wikification.

Si vous pensez que ces points ont été résolus, vous pouvez retirer ce bandeau et améliorer la mise en forme d'un autre article.

En programmation informatique, et plus précisément en programmation objet, la linéarisation de la superclasse C3 est un algorithme utilisé principalement pour obtenir l'ordre dans lequel les méthodes doivent être héritées en présence d'un héritage multiple. En d'autres termes, la sortie de la linéarisation de la superclasse C3 est un ordre de résolution de méthode (MRO pour Method Resolution Order en anglais) déterministe.

La linéarisation de la superclasse C3 est appelée C3 car elle « est cohérente avec trois propriétés^[1] » :

• un graphe de précédence étendue cohérent^[Quoi ?],
• la préservation de l'ordre de préséance local^[Quoi ?], et
• appliquant un critère de monotonie^[Lequel ?].

La linéarisation de la superclasse C3 a été publié pour la première fois lors de la conférence OOPSLA de 1996, dans un article intitulé A Monotonic Superclass Linearization for Dylan^[1], où Dylan est un langage de programmation qui permet la programmation objet. Dans cet article, il est écrit :

« Dans les systèmes orientés objet avec héritage multiple, un mécanisme doit être utilisé pour résoudre les conflits lors de l'héritage de différentes définitions de la même propriété à partir de plusieurs superclasses. »^[1]

Il a été adapté à l'implémentation d'Open Dylan en janvier 2012 ^[2] à la suite d'une proposition d'amélioration^[3]. Il a été choisi comme algorithme par défaut pour la résolution de méthode dans Python 2.3 (et versions ultérieures)^[4],[5], Raku^[6], Parrot^[7], Solidity et le module de programmation orientée objet de PGF/TikZ^[8] . Il est également disponible en tant que MRO alternatif, non par défaut, dans le cœur de Perl 5 à partir de la version 5.10.0^[9]. Une implémentation d'extension pour les versions antérieures de Perl 5 nommée Class::C3 existe sur CPAN^[10] .

Guido van Rossum de Python résume ainsi la linéarisation de la superclasse C3^[11] :

« Fondamentalement, l'idée derrière C3 est que si vous écrivez toutes les règles d'ordonnancement imposées par les relations d'héritage dans une hiérarchie de classes complexe, l'algorithme déterminera un ordonnancement monotone des classes qui les satisfait toutes. Si un tel ordre ne peut être déterminé, l'algorithme échouera. »

La linéarisation de la superclasse C3 d'une classe est la somme de la classe plus une fusion unique des linéarisations de ses parents et une liste des parents elle-même. La liste des parents comme dernier argument du processus de fusion préserve l'ordre de priorité local des classes parentes directes.

La fusion des linéarisations des parents et de la liste des parents se fait en sélectionnant la première tête des listes qui n'apparaît pas dans la queue (tous les éléments d'une liste sauf le premier) d'aucune des listes. Notez qu'une bonne tête peut apparaître comme premier élément dans plusieurs listes en même temps, mais il est interdit d'apparaître ailleurs. L'élément sélectionné est supprimé de toutes les listes où il apparaît en tant qu'en-tête et ajouté à la liste de sortie. Le processus de sélection et de suppression d'une bonne tête pour étendre la liste de sortie est répété jusqu'à ce que toutes les listes restantes soient épuisées. Si, à un moment donné, aucune bonne tête ne peut être sélectionnée, car les têtes de toutes les listes restantes apparaissent dans n'importe quelle queue des listes, la fusion est alors impossible à calculer en raison d'ordres incohérents de dépendances dans la hiérarchie d'héritage et de l'absence de linéarisation de l'original. classe existe.

Une approche naïve de division pour régner pour calculer la linéarisation d'une classe peut invoquer l'algorithme de manière récursive pour trouver les linéarisations des classes parentes pour le sous-programme de fusion. Cependant, cela se traduira par une récursivité en boucle infinie en présence d'une hiérarchie de classes cyclique. Pour détecter un tel cycle et casser la récursivité infinie (et réutiliser les résultats des calculs précédents comme optimisation), l'invocation récursive doit être protégée contre la ré-entrée d'un argument précédent au moyen d'un cache ou d'une mémorisation.

Cet algorithme est similaire à la recherche d'un ordre topologique dans un graphe orienté acyclique^{[réf. nécessaire]}.

Dans cette section, nous allons considérer le graphe de dépendance dans la figure de droite. Les sommets Z, K1, K2, K3, A, B, C, D, E, O sont des classes. Dans la figure, il y a une flèche, lorsqu'une classe hérite d'une autre. Par exemple, la flèche Z → K1 indique que la classe Z hérite de K1. Il y a de l'héritage multiple : par exemple Z hérite de K1, K2 et K3.

Tout d'abord, une métaclasse pour permettre une représentation courte des objets par leur nom au lieu, par exemple, <class '__main__.A'> <class '__main__.A'> :

class Type(type):
    def __repr__(cls):
        return cls.__name__
class O(object, metaclass=Type): pass

Ensuite, nous construisons l'arbre d'héritage.

class A(O): pass
class B(O): pass
class C(O): pass
class D(O): pass
class E(O): pass
class K1(C, A, B): pass
class K3(A, D): pass
class K2(B, D, E): pass
class Z(K1, K3, K2): pass

Et maintenant :

>>> Z.mro()
[Z, K1, C, K3, A, K2, B, D, E, O, <class 'object'>]

Le langage de programmation Raku utilise la linéarisation C3 pour les classes par défaut :

class A {}
class B {}
class C {}
class D {}
class E {}
class K1 is C is A is B {}
class K3 is A is D {}
class K2 is B is D is E {}
class Z is K1 is K3 is K2 {}
say Z.^mro; # OUTPUT: ((Z) (K1) (C) (K3) (A) (K2) (B) (D) (E) (Any) (Mu))

(les Any et Mu sont les types dont tous les objets Raku héritent)

• Portail de la programmation informatique