O algoritmo de linearização C3 para resolução de métodos em várias linguagens OO de herança múltipla: procurando uma justificativa para alguns detalhes da implementação

7

De acordo com esta descrição da ordem de resolução de método do Python (mro), também conhecida como linearização C3 , o algoritmo pode ser descrito recursivamente da seguinte forma:

L(O) = <O>
L(C) = <C> + merge(L(B1),..., L(Bn), <B1,...,Bn>)

Onde

  • O é a classe da qual toda classe herda.
  • Cé uma classe que herda diretamente de B1, ... ,, Bnnesta ordem.
  • <e >são delimitadores de lista.
  • + é o operador de concatenação de lista.
  • merge mescla seus argumentos de lista em uma única lista, da maneira a ser descrita abaixo.

O texto acima pode ser reformulado em palavras (citadas no documento Python acima):

a linearização de C é a soma de C mais a mescla das linearizações dos pais e a lista dos pais.

O mergealgoritmo é descrito da seguinte forma (essencialmente citado no documento Python, mas ligeiramente reformulado):

Considere o cabeçalho da primeira lista, ou seja, L (B1) [0]: se for um cabeçalho bom , ou seja, se não estiver na cauda adequada de qualquer uma das outras listas, adicione-o à linearização de C e remova-o de todas as listas na mesclagem. Caso contrário, considere o cabeçalho da próxima lista, etc. Repita até que não haja mais aulas ou boas cabeças. No último caso, é impossível construir a mesclagem.

O exemplo a seguir é dado como uma ilustração. Suponha que Aherda diretamente Be C, nessa ordem, e suponha que as linearizações de Be Csejam

L(B) = <B, D, E, O>
L(C) = <C, D, F, O>

Então Aa linearização é

L(A) = <A> + merge(<B,D,E,O>, <C,D,F,O>, <B,C>)
     = <A, B> + merge(<D,E,O>, <C,D,F,O>, <C>)
     = <A, B, C> + merge(<D,E,O>, <D,F,O>)
     = <A, B, C, D> + merge(<E,O>, <F,O>)
     = <A, B, C, D, E> + merge(<O>, <F,O>)
     = <A, B, C, D, E, F> + merge(<O>, <O>)
     = <A, B, C, D, E, F, O>

Minha pergunta é: em termos da descrição original do algoritmo, para que serve servir <B1,...,Bn>como argumento a lista de pais diretos merge? O algoritmo produzirá resultados diferentes se esse argumento for omitido?

algorithms programming-languages type-theory object-oriented Evan Aad
fonte

Respostas:

5

Sem a última lista:

merge(<B,D,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

Com a última lista:

merge(<B,D,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,O>, <C,F,O>, <D,O>, <C,D>) =
  <B,C> + merge(<D,O>, <F,O>, <D,O>, <D>) =
  <B,C,D,F,O>

Sem a última lista:

merge(<B,D,C,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

Com a última lista:

merge(<B,D,C,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,C,O>, <C,F,O>, <D,O>, <C,D>) =
  no-merge

Intuitivamente, a última lista força o resultado final a ser compatível com o pedido <B1,...,Bn>. Isso pode alterar a ordem ou fazer com que a mesclagem falhe.

chi
fonte