Linealización C3

En informática , la linealización de superclase C3 es un algoritmo que se utiliza principalmente para obtener el orden en el que los métodos deben heredarse en presencia de herencia múltiple . En otras palabras, la salida de la linealización de la superclase C3 es un orden de resolución de método determinista ( MRO ).

La linealización de la superclase C3 da como resultado tres propiedades importantes:

• un gráfico de precedencia extendido consistente ,
• preservación del orden de precedencia local, y
• ajustando el criterio de la monotonicidad.

Se publicó por primera vez en la conferencia OOPSLA de 1996 , en un artículo titulado "Una linealización de superclase monótona para Dylan ". ^[1] Se adaptó a la implementación de Open Dylan en enero de 2012 ^[2] tras una propuesta de mejora. ^[3] Ha sido 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 Programación Orientada a Objetos de PGF / TikZ módulo. ^[8] También está disponible como un MRO alternativo no predeterminado en el núcleo de Perl 5comenzando con la versión 5.10.0. ^[9] Existe una implementación de extensión para versiones anteriores de Perl 5 named Class::C3en CPAN . ^[10]

Guido van Rossum de Python resume así la linealización de la superclase C3: ^[11]

Básicamente, la idea detrás de C3 es que si escribe todas las reglas de ordenación impuestas por las relaciones de herencia en una jerarquía de clases compleja, el algoritmo determinará una ordenación monótona de las clases que las satisfaga todas. Si tal orden no se puede determinar, el algoritmo fallará.

Descripción

Este artículo puede resultar confuso o poco claro para los lectores . Por favor ayude a aclarar el artículo . Puede haber una discusión sobre esto en la página de discusión . ( Abril de 2018 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

La linealización de superclase C3 de una clase es la suma de la clase más una combinació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 principales directas.

La combinación de linealizaciones de padres y 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 una buena cabecera puede aparecer como primer elemento en varias listas al mismo tiempo, pero está prohibido aparecer en cualquier otro lugar. El elemento seleccionado se elimina de todas las listas donde aparece como encabezado y se agrega a la lista de salida. El proceso de seleccionar y eliminar un buen encabezado para ampliar la lista de salida se repite hasta que se agotan todas las listas restantes. Si en algún momento no se puede seleccionar un buen encabezado, 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 linealización de la clase original.

Un enfoque ingenuo de dividir y conquistar para calcular la linealización de una clase puede invocar el algoritmo de forma recursiva para encontrar las linealizaciones de las clases principales para la subrutina de combinación. Sin embargo, esto dará como resultado una recursividad de bucle infinito en presencia de una jerarquía de clases cíclica. Para detectar tal ciclo y romper la recursividad infinita (y reutilizar los resultados de los cálculos anteriores como una optimización), la invocación recursiva debe protegerse contra la reentrada de un argumento anterior por medio de una memoria caché o memorización .

Este algoritmo es similar a encontrar un orden topológico .

Ejemplo

Dado

Un gráfico de dependencia para el ejemplo de linealización C3.

clase Ola clase A se extiende a Ola clase B se extiende a Oclase C extiende Ola clase D se extiende a Ola clase E se extiende a Ola clase K1 se extiende A, B, Cla clase K2 se extiende a D, B, Ela clase K3 se extiende a D, Ala clase Z se extiende a K1, K2, K3

la linealización de Z se calcula como

L (O): = [O] // la linealización de O es trivialmente la lista de singleton [O], porque O no tiene padresL (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] + fusionar ([O], [O]) = [A, O] // ... que simplemente antepone A a la linealización de su padre únicoL (B): = [B, O] // Las linealizaciones de B, C, D y E se calculan de forma similar a la de AL (C): = [C, O]L (D): = [D, O]L (E): = [E, O]L (K1): = [K1] + merge (L (A), L (B), L (C), [A, B, C]) // primero, encuentra las linealizaciones de los padres de K1, L (A) , L (B) y L (C), y fusionarlos con la lista principal [A, B, C] = [K1] + merge ([A, O], [B, O], [C, O], [A, B, C]) // la clase A es un buen candidato para el primer paso de combinación, porque solo aparece como encabezado de la primera y última lista = [K1, A] + merge ([O], [B, O], [C, O], [B, C]) // la clase O no es un buen candidato para el siguiente paso de combinación, porque también aparece en las colas de las listas 2 y 3; pero la clase B es un buen candidato = [K1, A, B] + fusionar ([O], [O], [C, O], [C]) // la clase C es un buen candidato; la clase O todavía aparece al final de la lista 3 = [K1, A, B, C] + merge ([O], [O], [O]) // finalmente, la clase O es un candidato válido, que también agota todas las listas restantes = [K1, A, B, C, O]L (K2): = [K2] + fusionar (L (D), L (B), L (E), [D, B, E]) = [K2] + fusionar ([D, O], [B, O], [E, O], [D, B, E]) // seleccionar D = [K2, D] + fusionar ([O], [B, O], [E, O], [B, E]) // falla O, seleccione B = [K2, D, B] + fusionar ([O], [O], [E, O], [E]) // falla O, seleccione E = [K2, D, B, E] + fusionar ([O], [O], [O]) // seleccionar O = [K2, D, B, E, O]L (K3): = [K3] + fusionar (L (D), L (A), [D, A]) = [K3] + fusionar ([D, O], [A, O], [D, A]) // seleccionar D = [K3, D] + fusionar ([O], [A, O], [A]) // falla O, seleccione A = [K3, D, A] + fusionar ([O], [O]) // seleccionar O = [K3, D, A, O]L (Z): = [Z] + fusionar (L (K1), L (K2), L (K3), [K1, K2, K3]) = [Z] + fusionar ([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3]) / / seleccione K1 = [Z, K1] + fusionar ([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3]) // falla A, seleccione K2 = [Z, K1, K2] + fusionar ([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3]) // falla A, falla D, seleccione K3 = [Z, K1, K2, K3] + fusionar ([A, B, C, O], [D, B, E, O], [D, A, O]) // falla A, selecciona D = [Z, K1, K2, K3, D] + fusionar ([A, B, C, O], [B, E, O], [A, O]) // seleccionar A = [Z, K1, K2, K3, D, A] + fusionar ([B, C, O], [B, E, O], [O]) // seleccionar B = [Z, K1, K2, K3, D, A, B] + fusionar ([C, O], [E, O], [O]) // seleccionar C = [Z, K1, K2, K3, D, A, B, C] + fusionar ([O], [E, O], [O]) // falla O, seleccione E = [Z, K1, K2, K3, D, A, B, C, E] + fusionar ([O], [O], [O]) // seleccionar O = [Z, K1, K2, K3, D, A, B, C, E, O] // hecho

Ejemplo demostrado en Python 3

Primero, una metaclase para permitir una representación corta de los objetos por nombre en lugar de, por ejemplo ,:<class '__main__.A'>

clase  Tipo ( tipo ):  def  __repr__ ( cls ):  return  cls . __nombre__clase  O ( objeto ,  metaclase = Tipo ):  pasar

Luego construimos el árbol de herencia.

clase  A ( O ):  pasarclase  B ( O ):  pasarclase  C ( O ):  pasaclase  D ( O ):  pasarclase  E ( O ):  pasaclase  K1 ( A ,  B ,  C ):  pasaclase  K2 ( D ,  B ,  E ):  pasaclase  K3 ( D ,  A ):  pasaclase  Z ( K1 ,  K2 ,  K3 ):  pasa

Y ahora:

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

Ejemplo demostrado en Raku

Raku usa la linealización C3 para las clases de forma predeterminada:

clase  A {} clase  B {} clase  C {} clase  D {} clase  E {} clase  K1  es  A  es  B  es  C {} clase  K2  es  D  es  B  es  E {} clase  K3  es  D  es  A {} clase  Z  es  K1  es  K2  es  K3 {} digamos  Z. ^ mro ;# SALIDA: ((Z) (K1) (K2) (K3) (D) (A) (B) (C) (E) (Cualquiera) (Mu))

(los Anyy Muson los tipos de los que heredan todos los objetos Raku)

Referencias

1. "Una linealización de superclase monótona para Dylan". Actas de la conferencia OOPSLA '96 . Prensa ACM . 1996-06-28. págs. 69–82. CiteSeerX  10.1.1.19.3910 . doi : 10.1145 / 236337.236343 . ISBN 0-89791-788-X.
2. Noticia en opendylan.org
3. Propuesta de mejora de Dylan 3: linealización de la superclase C3
4. Uso de Python 2.3 de C3 MRO
5. Tutorial para aplicaciones prácticas de linealización C3 usando Python
6. Uso de Perl 6 del C3 MRO
7. "Parrot usa C3 MRO" . Archivado desde el original el 8 de febrero de 2007 . Consultado el 6 de diciembre de 2006 .
8. Tantau, Till (29 de agosto de 2015). El Manual de TikZ y PGF (PDF) (3.0.1a ed.). pag. 956 . Consultado el 14 de agosto de 2017 .
9. C3 MRO disponible en Perl 5.10 y más reciente
10. Extensión de Perl 5 para C3 MRO en CPAN
11. van Rossum, Guido (23 de junio de 2010). "Orden de resolución del método" . La historia de Python . Consultado el 18 de enero de 2018 .