Qual é a diferença entre as classes de tipo de Haskell e as interfaces de Go?

8

Gostaria de saber se existe uma diferença entre as classes de tipo de Haskell e as interfaces de Go. Ambos definem tipos com base em funções, dessa maneira, que um valor corresponde a um tipo, se uma função requerida pelo tipo for definida para o valor.

Existem diferenças ou são apenas dois nomes para a mesma coisa?

ceving
fonte

Respostas:

6

Os dois conceitos são muito, muito semelhantes. Em linguagens OOP normais, anexamos uma vtable (ou para interfaces: itable) a cada objeto:

| this
v
+---+---+---+
| V | a | b | the object with fields a, b
+---+---+---+
  |
  v
 +---+---+---+
 | o | p | q | the vtable with method slots o(), p(), q()
 +---+---+---+

Isso nos permite invocar métodos semelhantes a this->vtable.p(this).

Em Haskell, a tabela de métodos é mais como um argumento oculto implícito:

method :: Class a => a -> a -> Int

se pareceria com a função C ++

template<typename A>
int method(Class<A>*, A*, A*)

Onde Class<A>é uma instância de typeclass Classpara type A. Um método seria chamado como

typeclass_instance->p(value_ptr);

A instância é separada dos valores. Os valores ainda mantêm seu tipo real. Embora as classes tipográficas permitam algum polimorfismo, isso não é subtipo de polimorfismo. Isso torna impossível fazer uma lista de valores que satisfaçam a Class. Por exemplo, supondo que tenhamos instance Class Int ...e instance Class String ...não possamos criar um tipo de lista heterogêneo como [Class]esse e que possua valores como [42, "foo"]. (Isso é possível quando você usa a extensão "tipos existenciais", que efetivamente muda para a abordagem Ir).

No Go, um valor não implementa um conjunto fixo de interfaces. Conseqüentemente, ele não pode ter um ponteiro vtable. Em vez disso, ponteiros para tipos de interface são implementados como ponteiros gordos que incluem um ponteiro para os dados, outro ponteiro para a itable:

    `this` fat pointer
    +---+---+
    |   |   |
    +---+---+
 ____/    \_________
v                   v
+---+---+---+       +---+---+
| o | p | q |       | a | b | the data with
+---+---+---+       +---+---+ fields a, b
itable with method
slots o(), p(), q()

this.itable->p(this.data_ptr)

O itable é combinado com os dados em um ponteiro gordo quando você converte de um valor comum para um tipo de interface. Depois de ter um tipo de interface, o tipo real dos dados se torna irrelevante. Na verdade, você não pode acessar os campos diretamente sem passar por métodos ou reduzir a interface (o que pode falhar).

A abordagem da Go ao envio de interfaces tem um custo: cada ponteiro polimórfico é duas vezes maior que um ponteiro normal. Além disso, transmitir de uma interface para outra envolve copiar os ponteiros do método para uma nova vtable. Mas uma vez que construímos o itable, isso nos permite despachar chamadas de método baratas para muitas interfaces, algo com o qual as linguagens tradicionais de POO sofrem. Aqui, m é o número de métodos na interface de destino eb é o número de classes base:

  • O C ++ faz o fatiamento de objetos ou precisa perseguir ponteiros de herança virtual ao converter, mas depois tem acesso simples à vtable. O (1) ou O (b) custo de upcasting, mas O (1) envio de método.
  • A VM Java Hotspot não precisa fazer nada ao fazer upcasting, mas, na consulta do método de interface, faz uma pesquisa linear por todos os itens implementados por essa classe. O (1) upcasting, mas O (b) envio de método.
  • O Python não precisa fazer nada ao fazer upcasting, mas usa uma pesquisa linear por meio de uma lista de classes base linearizadas em C3. O (1) upcasting, mas O (b²) despacho de método? Não tenho certeza qual é a complexidade algorítmica do C3.
  • O .NET CLR usa uma abordagem semelhante ao Hotspot, mas adiciona outro nível de indireção na tentativa de otimizar o uso da memória. O (1) upcasting, mas O (b) envio de método.

A complexidade típica do envio de métodos é muito melhor, pois a pesquisa de métodos geralmente pode ser armazenada em cache, mas as complexidades de pior caso são bastante horríveis.

Em comparação, Go possui upcasting O (1) ou O (m) e envio de método O (1). Haskell não tem upcasting (restringir um tipo com uma classe type é um efeito em tempo de compilação) e O (1) despacham o método.

amon
fonte
Obrigado por [42, "foo"]. É um exemplo vívido.
ceving
2
Embora essa resposta seja bem escrita e contenha informações úteis, acho que, ao focar na implementação no código compilado, ela superestima significativamente as semelhanças entre interfaces e classes de tipo. Com as classes de tipo (e o sistema de tipo Haskell em geral), a maioria das coisas interessantes acontece durante a compilação e não é refletida no código final da máquina.
31517 KA Buhr
7

Existem várias diferenças

  1. As classes de tipo Haskell são digitadas nominativamente - você deve declarar que Maybeé a Monad. As interfaces Go são tipificadas estruturalmente: se circledeclara area() float64e o mesmo acontece square, ambas estão sob a interface shapeautomaticamente.
  2. Haskell (com extensões GHC) têm multi Parâmetro Tipo Classes e (como o meu Maybe aexemplo) Tipo classes para tipos kinded mais elevados. Go não tem equivalente para estes.
  3. No Haskell, as classes de tipo são consumidas com polimorfismo associado, o que fornece restrições inexprimíveis com o Go. Por exemplo + :: Num a => a -> a -> a, o que garante que você não tentará adicionar ponto flutuante e quaternions, é inexprimível no Go.
Walpen
fonte
1. é realmente uma diferença ou apenas falta açúcar?
ceving 20/12/16
1
As interfaces Go definem um protocolo para valores, as classes de tipo Haskell definem um protocolo para os tipos, que também é uma grande diferença, eu diria. (É por isso que eles são chamados de "classes de tipos", afinal. Eles classificam os tipos, diferentemente das classes OO (ou das interfaces de Go), que classificam valores.)
Jörg W Mittag
1
@ ceving, definitivamente não é açúcar no sentido normal: se Haskell pulasse para algo como Scala implica nas classes de tipo, isso quebraria muito código existente.
walpen
@ JörgWMittag Eu concordo lá e gostei da sua resposta: estava tentando entender melhor a diferença da perspectiva dos usuários.
walpen
@walpen Por que esse código de quebra? Eu me pergunto como esse código poderia existir, considerando o rigor do sistema de tipos de Haskell.
ceving 20/12/16
4

Eles são completamente diferentes. As interfaces Go definem um protocolo para valores, as classes de tipo Haskell definem um protocolo para os tipos. (É por isso que eles são chamados de "classes de tipos", afinal. Eles classificam tipos, diferentemente das classes OO (ou interfaces de Go), que classificam valores.)

As interfaces Go são apenas chatas para digitar estruturas antigas, nada mais.

Jörg W Mittag
fonte
1
Você pode explicar isso? Talvez até sem tom condescendente. O que eu li afirma que as classes de tipo são polimorfismos ad-hoc comparáveis ​​à sobrecarga do operador, que é a mesma das interfaces no Go.
ceving 20/12/16
No tutorial Haskell : "Como uma declaração de interface, uma declaração de classe Haskell define um protocolo para usar um objeto"
ceving 20/12/16
2
Nesse mesmo tutorial ( ênfase em negrito ): "As classes de tipo […] nos permitem declarar quais tipos são instâncias de qual classe" As instâncias de uma interface Go são valores , as instâncias de uma classe de tipo Haskell são tipos . Valores e tipos vivem em dois mundos completamente separados (pelo menos em idiomas como Haskell e Go, idiomas de tipo dependente como Agda, Guru, Epigram, Idris, Isabelle, Coq etc. são uma questão diferente).
Jörg W Mittag
Votação porque a resposta é perspicaz, mas acho que mais detalhes podem ajudar. E o que é chato na digitação estrutural ?! É muito raro e vale a pena comemorar na minha opinião.
Max Heiber