¿Cuál es la diferencia entre las clases de tipo de Haskell y las interfaces de Go?

8

Me pregunto si hay una diferencia entre las clases de tipo de Haskell y las interfaces de Go. Ambos definen tipos basados ​​en funciones, de esa manera, que un valor coincide con un tipo, si una función requerida por el tipo se define para el valor.

¿Hay alguna diferencia o son solo dos nombres para la misma cosa?

ceving
fuente

Respuestas:

6

Los dos conceptos son muy, muy similares. En los lenguajes normales de OOP, adjuntamos una vtable (o 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()
 +---+---+---+

Esto nos permite invocar métodos similares a this->vtable.p(this).

En Haskell, la tabla de métodos es más como un argumento oculto implícito:

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

se vería como la función C ++

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

donde Class<A>es una instancia de typeclass Classpara type A. Se invocaría un método como

typeclass_instance->p(value_ptr);

La instancia está separada de los valores. Los valores aún conservan su tipo real. Si bien las clases de tipos permiten cierto polimorfismo, esto no es subtipo de polimorfismo. Eso hace que sea imposible hacer una lista de valores que satisfagan a Class. Por ejemplo, suponiendo que tenemos instance Class Int ...y instance Class String ...no podemos crear un tipo de lista heterogénea como [Class]esa tiene valores como [42, "foo"]. (Esto es posible cuando utiliza la extensión "tipos existenciales", que efectivamente cambia al enfoque Ir).

En Go, un valor no implementa un conjunto fijo de interfaces. En consecuencia, no puede tener un puntero vtable. En su lugar, los punteros a los tipos de interfaz se implementan como punteros gordos que incluyen un puntero a los datos, otro puntero a lo factible:

    `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)

El itable se combina con los datos en un puntero grueso cuando se convierte desde un valor ordinario a un tipo de interfaz. Una vez que tiene un tipo de interfaz, el tipo real de los datos se vuelve irrelevante. De hecho, no puede acceder a los campos directamente sin pasar por métodos o desactivar la interfaz (que puede fallar).

El enfoque de Go para el envío de la interfaz tiene un costo: cada puntero polimórfico es dos veces más grande que un puntero normal. Además, la transmisión de una interfaz a otra implica copiar los punteros del método a una nueva vtable. Pero una vez que hemos construido el itable, esto nos permite enviar llamadas de método a muchas interfaces a bajo costo, algo que sufren los lenguajes tradicionales de OOP. Aquí, m es el número de métodos en la interfaz de destino, yb es el número de clases base:

  • C ++ hace el corte de objetos o necesita perseguir punteros de herencia virtual cuando se convierte, pero luego tiene acceso simple a vtable. O (1) u O (b) costo de conversión, pero envío de método O (1).
  • La máquina virtual de Java Hotspot no tiene que hacer nada al realizar la conversión, pero en la búsqueda del método de interfaz realiza una búsqueda lineal a través de todos los elementos ejecutables implementados por esa clase. O (1) conversión ascendente, pero O (b) envío del método.
  • Python no tiene que hacer nada cuando realiza la conversión, pero utiliza una búsqueda lineal a través de una lista de clases base linealizadas en C3. O (1) upcasting, pero el envío del método O (b²)? No estoy seguro de cuál es la complejidad algorítmica de C3.
  • .NET CLR utiliza un enfoque similar a Hotspot pero agrega otro nivel de indirección en un intento de optimizar el uso de la memoria. O (1) conversión ascendente, pero O (b) envío del método.

La complejidad típica para el envío de métodos es mucho mejor ya que la búsqueda de métodos a menudo se puede almacenar en caché, pero las peores complejidades son bastante horribles.

En comparación, Go tiene conversión ascendente O (1) u O (m), y el envío del método O (1). Haskell no tiene conversión (restringir un tipo con una clase de tipo es un efecto de tiempo de compilación) y el envío del método O (1).

amon
fuente
Gracias por [42, "foo"]. Es un ejemplo vívido.
ceving
2
Aunque esta respuesta está bien escrita y contiene información útil, creo que al centrarse en la implementación en el código compilado, exagera significativamente las similitudes entre las interfaces y las clases de tipos. Con las clases de tipos (y el sistema de tipos de Haskell en general), la mayoría de las cosas interesantes suceden durante la compilación y no se reflejan en el código de máquina final.
KA Buhr
7

Hay varias diferencias

  1. Las clases tipográficas de Haskell se escriben de forma nominativa; debe declarar que Maybees a Monad. Las interfaces Go están tipificadas estructuralmente: si circledeclara area() float64y también lo hace square, ambas están debajo de la interfaz shapeautomáticamente.
  2. Haskell (con extensiones GHC) tiene clases de tipo de parámetros múltiples y (como mi Maybe aejemplo) clases de tipo para tipos de tipo superior. Go no tiene equivalente para estos.
  3. En Haskell, las clases de tipo se consumen con polimorfismo encuadernado que le proporciona restricciones que no se pueden expresar con Go. Por ejemplo + :: Num a => a -> a -> a, lo que garantiza que no intente agregar coma flotante y cuaterniones, es inexpresable en Ir.
Walpen
fuente
¿Es 1. realmente una diferencia o solo le falta azúcar?
ceving
1
Las interfaces Go definen un protocolo para los valores, las clases de tipos de Haskell definen un protocolo para los tipos, esa es también una diferencia bastante importante, diría yo. (. Es por eso que se les llama "clases de tipo", después de todo Clasifican tipos, a diferencia de clases OO (o ir de interfaces), que los valores de clasificar.)
Jörg W Mittag
1
@ceving, definitivamente no es azúcar en el sentido normal: si Haskell saltara a algo como Scala implicits para las clases de tipos, rompería una gran cantidad de código existente.
walpen
@ JörgWMittag Estaré de acuerdo y me gustó su respuesta: estaba tratando de obtener una mayor diferencia desde la perspectiva de los usuarios.
walpen
@walpen ¿Por qué este código de ruptura? Me pregunto cómo podría existir ese código teniendo en cuenta la rigurosidad del sistema de tipos de Haskell.
ceving
4

Son completamente diferentes Las interfaces Go definen un protocolo para los valores, las clases de tipo Haskell definen un protocolo para los tipos. (Por eso se les llama "clases de tipos", después de todo. Clasifican los tipos, a diferencia de las clases OO (o las interfaces de Go), que clasifican los valores).

Las interfaces Go son simplemente aburridas tipologías estructurales, nada más.

Jörg W Mittag
fuente
1
¿Puedes explicarlo? Quizás incluso sin tono condescendiente. Lo que he leído indica que las clases de tipos son polimorfismos ad-hoc comparables a la sobrecarga del operador, que es lo mismo que las interfaces en Go.
ceving
Del tutorial de Haskell : "Al igual que una declaración de interfaz, una declaración de clase de Haskell define un protocolo para usar un objeto"
desde el
2
Del mismo tutorial ( énfasis en negrita mío): "Las clases de tipos [...] nos permiten declarar qué tipos son instancias de qué clase" Las instancias de una interfaz Go son valores , las instancias de una clase de tipo Haskell son tipos . Los valores y los tipos viven en dos mundos completamente separados (al menos en idiomas como Haskell y Go, los idiomas de tipo dependiente como Agda, Guru, Epigram, Idris, Isabelle, Coq, etc.son un asunto diferente).
Jörg W Mittag
Votar porque la respuesta es perspicaz, pero creo que más detalles podrían ayudar. ¿Y qué tiene de aburrido la tipificación estructural? Es bastante raro, y vale la pena celebrarlo en mi opinión.
Max Heiber