Como a herança difere da subtipagem?

15

Na perspectiva da linguagem de programação, o que significa subtipo? Ouvi dizer que "herança não é subtipagem". Então, quais são as diferenças entre herança e subtipagem?

RoboAlex
fonte
6
Gostaria de saber se esta questão (e outras semelhantes) podem ser redirecionadas para o novo site cs.SE quando ele entra na versão beta pública?
precisa
1
Bem-vindo ao cstheory, um site de perguntas e respostas para perguntas em nível de pesquisa em ciência da computação teórica (TCS). Sua pergunta não parece ser uma pergunta em nível de pesquisa no TCS. Consulte as Perguntas frequentes para obter mais informações sobre o significado disso e sugestões de sites que podem dar boas-vindas à sua pergunta. Por fim, se sua pergunta estiver encerrada por estar fora do escopo e você acredita que pode editá-la para torná-la uma questão de nível de pesquisa, sinta-se à vontade para fazê-lo. O fechamento não é permanente e as perguntas podem ser reabertas. Consulte as Perguntas frequentes para obter mais informações.
Kaveh
3
@UdayReddy: Nenhuma pergunta não foi trivial na primeira resposta, mas devemos tomar uma decisão do ponto de vista moderno. O mesmo argumento que o seu implicaria que a pergunta sobre o algoritmo de Dijkstra está no tópico porque o primeiro artigo fala sobre isso e nada mais.
Tsuyoshi Ito
3
@TsuyoshiIto A analogia não é apropriada porque o primeiro artigo de Dijkstra resolveu o problema, enquanto o primeiro artigo de Cardelli aqui criou o problema. Ainda assim, entendo que não medimos o estado da arte com base no primeiro artigo. Permitam-me assegurar-lhe que as diferenças entre herança e subtipagem não representam um problema resolvido, e espero que o assunto seja debatido por mais 20 anos, pelo menos. O questionador pode ser aconselhado a fazer alguns trabalhos de casa adicionais e editar a pergunta para esclarecer os problemas no nível da pesquisa.
Uday Reddy
3
De qualquer forma, é fácil apontar o OP para o artigo de Cook et al. Com o mesmo nome: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.8635
Andreas Rossberg

Respostas:

18

[Não pensei profundamente nos problemas dos sistemas de tipos orientados a objetos, mas direi o que sei para iniciar a discussão.]

Nós dizemos que é um subtipo de B se tudo Uma -typed valores podem ser usados em todos os contextos onde B -typed valores são esperadas. Ou, dito de outra forma, A -typed valores podem "mascarar" como B -typed valores.UMABUMABUMAB

Se esse mascaramento não apresenta problemas com a verificação de tipo, ou seja, a inserção de valores do tipo nos quais são necessários valores do tipo B continua a digitar o cheque, chamamos de "subtipo estrutural" . Se não houver problemas com o comportamento, ou seja, esse plug-in não altera o comportamento esperado, então chamamos de "subtipo comportamental" . (O "comportamento esperado" terá que ser formalizado separadamente e muitas noções de comportamento serão possíveis.)UMAB

A subtipagem estrutural não garante a subtipagem comportamental porque a estrutura de um tipo pode corresponder por motivos acidentais. No entanto, definir o comportamento esperado não é fácil. Portanto, muitas linguagens de programação usam um ponto intermediário, em que o usuário deve declarar qual tipo é um subtipo. Isso é chamado de "subtipagem nominal" . Veja a pergunta sobre subtipagem implícita vs explícitapara uma discussão sobre esta questão. A idéia é que o programador tenha que garantir subtipos comportamentais para todos os subtipos declarados usando sua própria engenhosidade. O idioma não pode oferecer nenhuma ajuda. No entanto, todos os subtipos declarados devem ter pelo menos subtipos estruturais. Caso contrário, o programa falharia ao digitar check. O idioma pode ajudar a garantir isso. (Algumas linguagens de programação não possuem sistemas de tipos bons o suficiente para garantir isso em tempo de compilação. Nesse caso, a falha de tipo seria detectada em tempo de execução ou talvez resultados incorretos pudessem ser produzidos. Tais buracos de tipo são obviamente indesejáveis.)

Quando se define subclasses em programas orientados a objetos, normalmente se adiciona campos (ou métodos) publicamente visíveis. Na maioria das linguagens de programação, essas subclasses são consideradas subtipos nominais . A questão é se eles também são subtipos estruturais . Se não forem, isto é, a linguagem de programação permite declarar subtipos nominais que não são estruturais, então haverá buracos de tipo na linguagem de programação.

Em casos simples, adicionar campos funciona bem. O tipo da superclasse espera menos campos que o tipo da subclasse. Portanto, se você conectar uma instância de uma subclasse em que uma instância da sueprclass é esperada, o programa simplesmente ignorará os campos adicionais fornecidos e nada dará errado.

No entanto, se a superclasse ou subclasse tiver métodos que usam argumentos do mesmo tipo que ela ou retornam resultados do mesmo tipo que ela, surgirão problemas. Então, o tipo de interface da subclasse não é um subtipo estrutural daquele da superclasse. As linguagens de programação amplamente usadas como tipo de segurança, como Java, não permitem essas subclasses. Portanto, eles restringem o idioma para obter segurança de tipo. Diz-se que a linguagem de programação Eiffel sacrificou a segurança de tipo para obter flexibilidade . Se alguém projeta um sistema de tipo forte que retém a flexibilidade, deve abandonar o princípio de que as subclasses dão origem a subtipos. Daí o título do artigo "Herança não é subtipada". Os autores propõem uma noção diferente de subtipo de ordem superior, que funciona em seu lugar. Kim Bruce também tem uma proposta intimamente relacionada, chamada "correspondência", que obtém o mesmo efeito. Veja esta apresentação . Também é útil um documento de posição de Andrew Black.

Provavelmente a comunidade semântica é a culpada por ignorar amplamente o problema. Tradicionalmente, consideramos isso um problema prático de engenharia de sistemas de tipos que tem pouco interesse teórico. Se não for esse o caso, e de fato houver alguma semântica na área, espero que as outras pessoas as mencionem.

Uday Reddy
fonte
1
Talvez também valha a pena mencionar que existem idiomas reais por aí que dissociaram com êxito o subtipo de herança, por exemplo, o Ocaml em seu sistema de objetos.
Andreas Rossberg
@AndreasRossberg De fato, o OCaml não estava no meu quadro quando escrevi essa resposta. Suponho que o OCaml não tenha subtipagem nominal. Portanto, alguns desses problemas não surgiriam. Mas existe a possibilidade de que os tipos possam coincidir acidentalmente, mesmo que o comportamento não aconteça, e o sistema de tipos não poderá ajudar a detectar erros desse tipo.
Uday Reddy