"En sistemas orientados a objetos con herencia múltiple, se debe utilizar algún mecanismo para resolver conflictos cuando se heredan diferentes definiciones de la misma propiedad de múltiples superclases". [1] La linealización de superclases C3 es un algoritmo utilizado principalmente para obtener el orden en el que se deben heredar los métodos en presencia de herencia múltiple . En otras palabras, el resultado de la linealización de superclases C3 es un Orden de Resolución de Métodos ( MRO ) determinista.
La linealización de la superclase C3 se llama C3 porque "es consistente con tres propiedades": [1]
Se publicó por primera vez en la conferencia OOPSLA de 1996, en un artículo titulado "A Monotonic Superclass Linearization for Dylan ". [1] Se adaptó a la implementación de Open Dylan en enero de 2012 [2] tras una propuesta de mejora. [3] Se ha elegido como el algoritmo predeterminado para la resolución de métodos en Python 2.3 (y más reciente), [4] [5] Raku , [6] Parrot , [7] Solidity y el módulo de programación orientada a objetos de PGF/TikZ . [8] También está disponible como una alternativa, MRO no predeterminada en el núcleo de Perl 5 a partir de la versión 5.10.0. [9] Existe una implementación de extensión para versiones anteriores de Perl 5 denominada Class::C3en CPAN . [10]
Guido van Rossum de Python resume la linealización de la superclase C3 de la siguiente manera: [11]
Básicamente, la idea detrás de C3 es que si se escriben todas las reglas de ordenamiento impuestas por las relaciones de herencia en una jerarquía de clases compleja, el algoritmo determinará un ordenamiento monótono de las clases que las satisfaga a todas. Si no se puede determinar dicho ordenamiento, el algoritmo fallará.
La linealización de una superclase C3 es la suma de la clase más una fusión única de las linealizaciones de sus padres y una lista de los padres en sí. La lista de padres como último argumento del proceso de fusión conserva el orden de precedencia local de las clases de padres directos.
La fusión de las linealizaciones de los padres y la lista de padres se realiza seleccionando el primer encabezado de las listas que no aparece en la cola (todos los elementos de una lista excepto el primero) de ninguna de las listas. Tenga en cuenta que un encabezado bueno puede aparecer como el primer elemento en varias listas al mismo tiempo, pero está prohibido que aparezca en cualquier otro lugar. El elemento seleccionado se elimina de todas las listas en las que aparece como encabezado y se agrega a la lista de salida. El proceso de selección y eliminación de un encabezado bueno para extender la lista de salida se repite hasta que se agoten todas las listas restantes. Si en algún momento no se puede seleccionar ningún encabezado bueno, porque los encabezados de todas las listas restantes aparecen en cualquier cola de las listas, entonces la fusión es imposible de calcular debido a ordenaciones inconsistentes de dependencias en la jerarquía de herencia y no existe ninguna linealización de la clase original.
Un enfoque ingenuo de divide y vencerás para calcular la linealización de una clase puede invocar el algoritmo de forma recursiva para encontrar las linealizaciones de las clases padre para la subrutina de fusión. Sin embargo, esto dará como resultado una recursión de bucle infinito en presencia de una jerarquía de clases cíclica. Para detectar dicho ciclo y romper la recursión infinita (y reutilizar los resultados de cálculos anteriores como una optimización), la invocación recursiva debe estar protegida contra el reingreso de un argumento anterior por medio de una memoria caché o memorización .
Este algoritmo es similar a encontrar un orden topológico .
Dado
clase O clase A extiende O clase B extiende O clase C extiende O clase D extiende O clase E extiende O clase K1 extiende C , A , B clase K3 extiende A , D clase K2 extiende B , D , E clase Z extiende K1 , K3 , K2 La linealización de Z se calcula como
L ( O ) := [ O ] // la linealización de O es trivialmente la lista singleton [O], porque O no tiene padres L ( A ) := [ A ] + merge ( L ( O ) , [ O ]) // la linealización de A es A más la fusión de las linealizaciones de sus padres con la lista de padres... = [ A ] + merge ([ O ] , [ O ]) = [ A , O ] // ...que simplemente antepone A a la linealización de su padre único L ( B ) := [ B , O ] // las linealizaciones de B, C, D y E se calculan de forma similar a la de A L ( C ) := [ C , O ] L ( D ) := [ D , O ] L ( E ) := [ E , O ] L ( K1 ) := [ K1 ] + merge ( L ( C ) , L ( B ) , L ( A ) , [ C , A , B ]) // primero, encuentre la linealización de los padres de K1, L(C), L(B) y L(A), y fusionelos con la lista padre [C, A, B] = [ K1 ] + merge ([ C , O ] , [ B , O ] , [ A , O ] , [ C , A , B ]) // la clase C es un buen candidato para el primer paso de fusión, porque solo aparece como el encabezado de la primera y la última lista = [ K1 , C ] + merge ([ O ] , [ B , O ] , [ A , O ] , [ A , B ]) // la clase O no es un buen candidato para el siguiente paso de fusión, porque también aparece en las colas de las listas 2 y 3, la clase B tampoco es buena; pero la clase A es un buen candidato = [ K1 , C , A ] + merge ([ O ] , [ B , O ] , [ O ] , [ B ]) // la clase B es un buen candidato; la clase O todavía aparece en la cola de la lista 2 = [ K1 , C , A , B ] + merge ([ O ] , [ O ] , [ O ]) // finalmente, la clase O es un candidato válido, lo que también agota todas las listas restantes = [ K1 , C , A , B , O ] L ( K3 ) := [ K3 ] + merge ( L ( A ) , L ( D ) , [ A , D ]) = [ K3 ] + merge ([ A , O ] , [ D , O ] , [ A , D ]) // select A = [ K3 , A ] + merge ([ O ] , [ D , O ] , [ D ]) // falla O, select D = [ K3 , A , D ] + merge ([ O ] , [ O ]) // select O = [ K3 , A , D , O ] L ( K2 ) := [ K2 ] + fusionar ( L ( B ) , L ( D ) , L ( E ) , [ B , D , E ]) = [ K2 ] + fusionar ([ B , O ] , [ D , O ] , [ E , O ] , [ B , D , E ]) // seleccionar B = [ K2 , B ] + fusionar ([ O ] , [ D , O ] , [ E , O ] , [ D , E ]) // falla O, seleccionar D = [ K2 , B , D ] + fusionar ([ O ] , [ O ] , [ E , O ] , [ E ]) // falla O, seleccionar E = [ K2 , B , D , E ] + fusionar ([ O ] , [ O ] , [ O ]) // seleccionar O = [ K2 , B , D , E , O ] L ( Z ) := [ Z ] + fusionar ( L ( K1 ) , L ( K3 ) , L ( K2 ) , [ K1 , K3 , K2 ]) = [ Z ] + fusionar ( [ K1 , C , A , B , O ] , [ K3 , A , D , O ] , [ K2 , B , D , E , O ] , [ K1 , K3 , K2 ]) // seleccione K1 = [ Z , K1 ] + fusionar ([ C , A , B , O ] , [ K3 , A , D , O ] , [ K2 , B , D , E , O ] , [ K3 , K2 ]) // seleccione C = [ Z , K1 , C ] + fusionar ([ A , B , O ] , [ K3 , A , D , O ] , [ K2 , B , D , E , O ] , [ K3 , K2 ]) // falla A, selecciona K3 = [ Z , K1 , C , K3 ] + fusionar ([ A , B , O ] , [ A , D , O ] , [ K2 , B , D , E , O ] , [ K2 ]) // seleccionar A = [ Z , K1 , C , K3 , A ] + fusionar ([ B , O ] , [ D , O ] , [ K2 , B , D , E , O ] , [ K2 ]) // falla B, falla D, selecciona K2 = [ Z , K1 , C , K3 , A , K2 ] + fusionar ([ B , O ] , [ D , O ] , [ B , D , E , O ]) // selecciona B = [ Z , K1 , C , K3 , A , K2 , B ] + fusionar ([ O ] , [ D , O ] , [ D , E , O ]) // falla O, selecciona D = [ Z , K1 , C , K3 , A , K2 , B , D ] + fusionar ([ O ] , [ O ] , [ E , O ]) // falla O, selecciona E = [ Z , K1 , C , K3 , A , K2 , B , D , E ] + fusionar ([ O ] , [ O ] , [ O ]) // seleccione O = [ Z , K1 , C , K3 , A , K2 , B , D , E , O ] // listo. Primero, una metaclase para permitir una representación corta de los objetos por nombre en lugar del valor REPR de la clase predeterminada:
clase Tipo ( type ): def __repr__ ( cls ): # Hará que repr(O) sea "O" en lugar de "<__main__.O>", # y lo mismo para cualquier subclase de O. return cls . __name__clase O ( objeto , metaclase = Tipo ): pasarA continuación, definimos nuestras clases base:
Clase A ( O ): aprobadoClase B ( O ): aprobadoClase C ( O ): aprobadoClase D ( O ): aprobadoClase E ( O ): aprobadoLuego construimos el árbol de herencia:
Clase K1 ( C , A , B ): aprobadoClase K3 ( A , D ): aprobadoClase K2 ( B , D , E ): aprobadoClase Z ( K1 , K3 , K2 ): aprobadoY ahora:
>>> Z . mro () [Z, K1, C, K3, A, K2, B, D, E, O, <clase 'objeto'>]Raku utiliza la linealización C3 para las clases de forma predeterminada:
clase A {} clase B {} clase C {} clase D {} clase E {} clase K1 es C es A es B {} clase K3 es A es D {} clase K2 es B es D es E {} clase Z es K1 es K3 es K2 {} digamos Z .^ mro ; # SALIDA: ((Z) (K1) (C) (K3) (A) (K2) (B) (D) (E) (Cualquiera) (Mu))( Anyy Muson los tipos de los que heredan todos los objetos Raku, por lo que Anyreemplaza a O)
{{cite conference}}: CS1 maint: multiple names: authors list (link)