java - relacionados - polimorfismo sobrecarga y sobreescritura

Polimorfismo paramétrico vs polimorfismo ad-hoc

Question

Me gustaría entender la diferencia clave entre el polimorfismo paramétrico como el polimorfismo de clases / funciones genéricas en los lenguajes Java / Scala / C ++ y el polimorfismo "ad-hoc" en el sistema de tipo Haskell. Estoy familiarizado con el primer tipo de idiomas, pero nunca he trabajado con Haskell.

Más precisamente:

1. ¿En qué se diferencia el algoritmo de inferencia de tipo, por ejemplo, en Java, de la inferencia de tipo en Haskell?
2. Por favor, dame un ejemplo de la situación en la que algo se puede escribir en Java / Scala pero no se puede escribir en Haskell (de acuerdo con las características modulares de estas plataformas también), y viceversa.

Gracias por adelantado.

Answer 1

Según el TAPL , §23.2:

El polimorfismo paramétrico (...) permite escribir una sola pieza "genéricamente", utilizando variables en lugar de tipos reales, y luego crear una instancia con tipos particulares según sea necesario. Las definiciones paramétricas son uniformes: todas sus instancias se comportan igual. (...)

El polimorfismo ad-hoc, por el contrario, permite que un valor polimórfico muestre diferentes comportamientos cuando se "ve" en diferentes tipos. El ejemplo más común de polimorfismo ad-hoc es la sobrecarga, que asocia un único símbolo de función con muchas implementaciones; el compilador (o el sistema de tiempo de ejecución, dependiendo de si la resolución de sobrecarga es estática o dinámica) elige una implementación adecuada para cada aplicación de la función, según los tipos de los argumentos.

Entonces, si se consideran etapas sucesivas de la historia, Java oficial no genérica (también conocida como pre J2SE 5.0 , antes de septiembre de 2004) tenía un polimorfismo ad-hoc, por lo que se podía sobrecargar un método , pero no un polimorfismo paramétrico, por lo que no se podía t escribe un método genérico . Luego puedes hacer ambas cosas, por supuesto.

En comparación, desde sus comienzos en 1990 , Haskell era paramétricamente polimórfico, lo que significa que usted podría escribir:

swap :: (A; B) -> (B; A)
swap (x; y) = (y; x)

donde A y B son variables de tipo pueden ser instanciadas a todos los tipos, sin suposiciones.

Pero no existía una construcción preexistente que ofrezca un polimorfismo ad-hoc , que tiene la intención de permitirle escribir funciones que se apliquen a varios , pero no a todos los tipos. Las clases de tipo se implementaron como una forma de lograr este objetivo.

Le permiten describir una clase (algo parecido a una interfaz Java), dando la firma de tipo de las funciones que quiere implementar para su tipo genérico. Luego puede registrar algunas (y con suerte, varias ) instancias que coincidan con esta clase. Mientras tanto, puedes escribir un método genérico como:

between :: (Ord a)  a -> a -> a -> Bool
between x y z = x ≤ y ^ y ≤ z

donde Ord es la clase que define la función (_ ≤ _) . Cuando se utiliza, (between "abc" "d" "ghi") se resuelve estáticamente para seleccionar la instancia correcta para las cadenas (en lugar de, por ejemplo, enteros), exactamente en el momento en que la sobrecarga del método (Java) lo haría.

Puede hacer algo similar en Java con comodines delimitados . Pero la diferencia clave entre Haskell y Java en ese frente es que solo Haskell puede hacer que el diccionario pase automáticamente : en ambos idiomas, dadas dos instancias de Ord T , digamos b0 y b1 , puede construir una función f que tome esas como argumentos y produzca la instancia para el tipo de pareja (b0, b1) , utilizando, por ejemplo, el orden lexicográfico. Diga ahora que le han dado (("hello", 2), ((3, "hi"), 5)) . En Java, debe recordar las instancias de string e int , y pasar la instancia correcta (hecha de cuatro aplicaciones de f !) Para aplicar between ese objeto. Haskell puede aplicar la compositionality y descubrir cómo construir la instancia correcta dadas solo las instancias básicas y el constructor f (esto se extiende a otros constructores, por supuesto).

Ahora, en lo que respecta a la inferencia de tipos (y probablemente esta sea una pregunta distinta), para ambos idiomas es incompleta , en el sentido de que siempre se puede escribir un programa sin anotaciones para el cual el compilador no podrá determinar el tipo.

1. para Haskell, esto se debe a que tiene un polimorfismo impredicative (también conocido como de primera clase), para el cual la inferencia de tipo es indecidible. Tenga en cuenta que en ese punto, Java se limita al polimorfismo de primer orden (algo en lo que Scala se expande).

2. para Java, esto se debe a que admite la subtipificación contravariante .

Pero esos idiomas difieren principalmente en el rango de declaraciones de programa a las que se aplica la inferencia de tipo en la práctica, y en la importancia dada a la corrección de los resultados de inferencia de tipo.

1. Para Haskell, la inferencia se aplica a todos los términos "no altamente polimórficos" y hace un esfuerzo serio para devolver resultados sólidos basados ​​en extensiones publicadas de un algoritmo conocido:

   • En esencia, la inferencia de Haskell se basa en Hindley-Milner , que le da resultados completos tan pronto como al inferir el tipo de una aplicación, las variables de tipo (por ejemplo, A y B en el ejemplo anterior) solo pueden crearse con una instancia no polimórfica tipos (estoy simplificando, pero este es esencialmente el polimorfismo de estilo ML que se puede encontrar en, por ejemplo, Ocaml).
   • un GHC reciente se asegurará de que se requiera una anotación de tipo solo para una vinculación de let o λ-abstraction que tenga un tipo que no sea de Damas-Milner .
   • Haskell ha tratado de mantenerse relativamente cerca de este núcleo inferible incluso en sus extensiones más peludas (por ejemplo, GADTs ). En cualquier caso, las extensiones propuestas casi siempre vienen en un documento con una prueba de la corrección de la inferencia de tipo extendida.

2. Para Java, la inferencia de tipo se aplica de una manera mucho más limitada de todos modos:

   Antes del lanzamiento de Java 5, no había inferencia de tipo en Java. De acuerdo con la cultura del lenguaje Java, el programador debe declarar explícitamente el tipo de cada variable, método y objeto dinámicamente asignado . Cuando genéricos (clases y métodos parametrizados por tipo) se introdujeron en Java 5, el lenguaje retuvo este requisito para variables, métodos y asignaciones . Pero la introducción de métodos polimórficos (parametrizados por tipo) dictaba que (i) el programador proporciona los argumentos de tipo de método en cada sitio de llamada de método polimórfico o (ii) el lenguaje admite la inferencia de argumentos de tipo de método. Para evitar crear una carga administrativa adicional para los programadores, los diseñadores de Java 5 eligieron realizar una inferencia de tipo para determinar los argumentos de tipo para las llamadas al método polimórfico . ( source , énfasis mío)

   El algoritmo de inferencia es esencialmente el de GJ , pero con una adición un somewhat source de comodines como una source tardía (Tenga en cuenta que no estoy actualizado sobre las posibles correcciones realizadas en J2SE 6.0, sin embargo). La gran diferencia conceptual en el enfoque es que la inferencia de Java es local , en el sentido de que el tipo inferido de una expresión depende solo de las restricciones generadas por el sistema de tipo y en los tipos de sus sub-expresiones, pero no en el contexto.

   Tenga en cuenta que la línea del partido con respecto a la inferencia de tipo incompleta ya veces incorrecta es relativamente relajada. Según la especificación :

   Tenga en cuenta también que la inferencia de tipo no afecta la solidez de ninguna manera. Si los tipos inferidos son absurdos, la invocación arrojará un error de tipo. El algoritmo de inferencia tipo debe verse como una heurística, diseñada para perfdorm en la práctica. Si no puede inferir el resultado deseado, se pueden usar paramneters de tipo explícito en su lugar.

Answer 2

Una discusión completa de lo que significa el polimorfismo paramétrico y el polimorfismo ad-hoc y en qué medida están disponibles en Haskell y en Java es largo; Sin embargo, sus preguntas concretas pueden abordarse de manera mucho más simple:

¿Cómo se diferencia el algoritmo de inferencia de tipo, por ejemplo, en Java, de la inferencia de tipo en Haskell?

Por lo que sé, Java no hace inferencia tipo. Entonces la diferencia es que Haskell lo hace.

Por favor, dame un ejemplo de la situación en la que algo se puede escribir en Java / Scala pero no se puede escribir en Haskell (de acuerdo con las características modulares de estas plataformas también), y viceversa.

Un ejemplo muy simple de algo que Haskell puede hacer y que Java no puede es definir maxBound :: Bounded a => a . No sé lo suficiente de Java para señalar algo que puede hacer que Haskell no puede.

Answer 3

El polimorfismo paramétrico significa que no nos importa el tipo, implementaremos la función de la misma forma para cualquier tipo. Por ejemplo, en Haskell:

length :: [a] -> Int
length [] = 0          
length (x:xs) = 1 + length xs

No nos importa cuál sea el tipo de elementos de la lista, solo nos importa cuántos hay.

El polimorfismo ad-hoc (también conocido como sobrecarga de métodos) , sin embargo, significa que utilizaremos una implementación diferente dependiendo del tipo de parámetro.

Aquí hay un ejemplo en Haskell. Digamos que queremos definir una función llamada makeBreakfast .

Si el parámetro de entrada es Eggs , quiero que makeBreakfast devuelva un mensaje sobre cómo hacer huevos.

Si el parámetro de entrada es Pancakes , quiero que makeBreakfast devuelva un mensaje sobre cómo hacer panqueques.

Crearemos una clase de tipos llamada BreakfastFood que implementa la función makeBreakfast . La implementación de makeBreakfast será diferente dependiendo del tipo de entrada para makeBreakfast .

class BreakfastFood food where
  makeBreakfast :: food -> String

instance BreakfastFood Eggs where
  makeBreakfast = "First crack ''em, then fry ''em"

instance BreakfastFood Toast where
  makeBreakfast = "Put bread in the toaster until brown"

De acuerdo con los conceptos de John Mitchell en lenguajes de programación ,

La diferencia clave entre el polimorfismo paramétrico y la sobrecarga (también conocido como polimorfismo ad-hoc) es que las funciones polimórficas paramétricas utilizan un algoritmo para operar en argumentos de muchos tipos diferentes, mientras que las funciones sobrecargadas pueden usar un algoritmo diferente para cada tipo de argumento.