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.

Explication de la terminologie La linéarisation de la superclasse C3 est appelée C3 car elle :

un graphe de précédence étendue cohérent, la préservation de l'ordre de préséance local, et appliquant un critère de monotonie.

Histoire

Publication en 1996 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é , où Dylan est un langage de programmation qui permet la programmation objet. Dans cet article, il est écrit :

Adoption dans différents langages Il a été adapté à l'implémentation d'Open Dylan en News item on opendylan.org à la suite d'une proposition d'améliorationDylan Enhancement Proposal 3: C3 superclass linearization. Il a été choisi comme algorithme par défaut pour la résolution de méthode dans Python 2.3 (et versions ultérieures)Python 2.3's use of C3 MROTutorial for practical applications of C3 linearization using Python, RakuPerl 6's use of the C3 MRO, Parrot, Solidity et le module de programmation orientée objet de PGF/TikZ . 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.0C3 MRO available in Perl 5.10 and newer. Une implémentation d'extension pour les versions antérieures de Perl 5 nommée Class::C3 existe sur CPANPerl 5 extension for C3 MRO on CPAN .

Guido van Rossum de Python résume ainsi la linéarisation de la superclasse C3 :

Description

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.

Exemple droite|vignette|300x300px| Exemple de graphe de dépendance avec les classes Z, K1, K2, K3, A, B, C, D, E, O. 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. En Python 3 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): passEt maintenant :>>> Z.mro() [Z, K1, C, K3, A, K2, B, D, E, O, <class 'object'>]

En Raku 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)

Références

Catégorie:Programmation orientée objet Catégorie:Pages avec des traductions non relues