.net - suma - ¿Qué son los tipos de fila? ¿Son tipos de datos algebraicos?

suma de dos listas en haskell (3)

Completaré la excelente respuesta de PatJ con su ejemplo, escrito usando clases.

Dadas las clases a continuación:

class t1 = object method a = 42 method b = "Hello world" end class t2 = object method a = 1337 method b = false end

Y los objetos a continuación:

let o1 = new t1 let o2 = new t2

Puedes escribir lo siguiente:

let print_a t = print_int t#a;; val print_a : < a : int; .. > -> unit = <fun> print_a o1;; 42 - : unit = () print_a o2;; 1337 - : unit = ()

Puedes ver el tipo de fila en la firma de print_a . La < a : int; .. > < a : int; .. > es un tipo que literalmente significa "cualquier objeto que tenga al menos un método con firma int " .

A menudo escucho que F # carece de soporte para los tipos de fila OCaml, lo que hace que el lenguaje sea más poderoso que F #.

¿Qué son? ¿Son tipos de datos algebraicos, como tipos de suma (uniones discriminadas) o tipos de productos (tuplas, registros)? ¿Y es posible escribir tipos de fila en otros dialectos, como F #?

En primer lugar, tenemos que arreglar la terminología. No existe el "tipo de fila" ^† , al menos en la teoría de tipos y especialmente en el sistema de tipos de OCaml. Existe un "polimorfismo de fila" y lo discutiremos a continuación ⁰ .

El polimorfismo de hileras es una forma de polimorfismo. OCaml proporciona dos tipos de polimorfismo: paramétrico y de fila, y carece de los otros dos: ad hoc e inclusión (también conocido como subtipo) ¹ .

En primer lugar, ¿qué es el polimoprismo ? En el contexto de los sistemas de tipos, el polimorfismo permite que un solo término tenga varios tipos. El problema aquí es que el tipo de palabra en sí está muy sobrecargado en la comunidad de informática y lenguaje de programación. Entonces, para minimizar la confusión, simplemente reintrodúzcala aquí, para estar en la misma página ² . Un tipo de término generalmente denota alguna aproximación de la semántica del término. Donde la semántica podría ser tan simple como un conjunto de valores equipados con un conjunto de operaciones o algo más complejo, como efectos, anotaciones y teorías arbitrarias. En general, la semántica denota un conjunto de todos los comportamientos posibles de un término. Un sistema de tipos ^‡ denota un conjunto de reglas, que permite algunas construcciones de lenguaje y no permite que otros se basen en sus tipos. Es decir, verifica que las composiciones de los términos se comporten correctamente. Por ejemplo, si hay una construcción de aplicación de función en un lenguaje, el sistema de tipos permitirá una aplicación solo para aquellos argumentos que tengan tipos que coincidan con los tipos de parámetros. Y ahí es donde entra en juego el polimorfismo. En los sistemas de tipo monomórfico, esta coincidencia podría ser de uno a uno, es decir, literal. Los sistemas de tipos polimórficos proporcionan mecanismos para especificar algunas expresiones regulares que coincidirán con una familia de tipos. Por lo tanto, diferentes tipos de polimorfismo son simplemente diferentes tipos de expresiones regulares que puede usar para denotar la familia de tipos.

Ahora veamos diferentes tipos de polimorfismo desde esta perspectiva. Por ejemplo, el polimorfismo paramétrico es como un punto en expresiones regulares. Por ejemplo, ''a list es . list . list : eso significa que coincidimos literalmente con list y un parámetro del tipo de list podría ser cualquier tipo. El polimorfismo de fila es un operador estrella, por ejemplo, <quacks : unit; ..> <quacks : unit; ..> es lo mismo que <quacks : unit; .*> <quacks : unit; .*> . Y significa que coincide con cualquier tipo que quacks y hace lo que sea ³ . Hablando de subtipos nominales, en este caso, tenemos clases nominales (también conocidas como clases de caracteres en expresiones regulares), y especificamos una familia de tipos con el nombre de su clase base. Por ejemplo, duck es como [:duck:]* y cualquier valor que esté correctamente registrado como miembro de clase coincide con este tipo (a través de la herencia de clase y el nuevo operador) ⁴ . Finalmente, el polimorfismo ad hoc también es nominal y se asigna a clases de caracteres en expresiones regulares. La principal diferencia aquí es que la noción de tipo en el polimorfismo ad hoc no se aplica a un valor, sino al nombre. Por lo tanto, un nombre, como el nombre de una función o el operador + , puede tener múltiples definiciones (implementaciones) que deben registrarse de manera estática utilizando algún mecanismo de lenguaje (por ejemplo, sobrecargar a un operador, implementar un método, etc.). Por lo tanto, el polimorfismo ad-hoc es solo un caso especial de subtipo nominal.

Ahora, cuando tengamos claridad, podemos discutir qué nos da el polimorfismo de hileras. El polimorfismo de hileras es una característica de los sistemas de tipo estructural (también conocido como tipificación de pato en lenguajes tipificados dinámicamente) en contraste con los sistemas de tipo nominal, que proporcionan un polimorfismo de subtipo. En general, como hemos comentado anteriormente, nos permite especificar un tipo como "cualquier cosa que reproduzca" en lugar de "cualquier cosa que implemente la interfaz IDuck". Así que sí, por supuesto, puede hacer lo mismo con la tipificación nominal definiendo la interfaz duck y registrando explícitamente todas las implementaciones como instancias de esta interfaz utilizando algunos mecanismos inherit o implements . Pero el principal problema aquí es que su jerarquía está sellada, es decir, necesita cambiar su código para registrar una implementación en una interfaz recién creada. Eso rompe el principio abierto / cerrado y dificulta la reutilización del código. Otro problema con el subtipo nominal es que, a menos que su jerarquía forme una red (es decir, para dos clases, siempre hay un límite superior mínimo), no puede implementar la inferencia de tipos en ella ⁵ .

Otras lecturas

Objective ML: Una extensión efectiva orientada a objetos para ML - una descripción completa del tema.
François Pottier y Didier Rémy. La esencia de la inferencia tipo ML. En Benjamin C. Pierce, editor, Temas avanzados en tipos y lenguajes de programación, MIT Press, 2005. - Consulte la sección 10.8 para una explicación muy detallada y detallada de las filas.
Inferencia de tipo simple para el polimorfismo estructural : para una explicación detallada de la interacción entre el polimorfismo estructural y de fila en presencia de inferencia de tipo.

⁰⁾ Como se señaló en los comentarios de @nekketsuuu, estaba usando la terminología un poco voluntarista, ya que mi intención era dar una idea de alto nivel y fácil de entender, sin profundizar en los detalles. He revisado el post desde entonces, para hacerlo un poco más estricto.

¹⁾ Sin embargo, OCaml proporciona clases con herencia y una noción de subtipo, aún no es un subtipo de polimorfismo según la definición común, ya que no es nominal. Debería venir más claro del resto de la respuesta.

²⁾ Solo estoy arreglando la terminología, no estoy diciendo que mi definición sea correcta. Mucha gente piensa que el tipo denota una representación de un valor, e históricamente esto es correcto.

³⁾ Quizás una mejor expresión regular sería <.*; quacks : unit; .*> <.*; quacks : unit; .*> <.*; quacks : unit; .*> pero creo que tienes la idea.

⁴⁾ Por lo tanto, OCaml no tiene subtipo de polimorfismo, aunque tiene una noción de subtipo. Cuando especifique un tipo, no coincidirá con el subtipo, solo coincidirá literalmente, y debe usar un operador de conversión ascendente explícita para hacer que un valor de tipo T sea aplicable en un contexto donde se espera super(T) . Entonces, aunque hay subtipos en OCaml no se trata de polimorfismo.

⁵⁾ Y aunque el requisito de celosía no parece imposible, en la vida real es difícil imponer esta restricción en las jerarquías, o si se impone, la precisión de la inferencia de tipo siempre estará vinculada con la precisión de la jerarquía de tipos. Así que en la práctica, no funciona, cf. Scala

^† (omita esta nota en una primera lectura) Aunque en OCaml existen variables de fila que se utilizan para incrustar el polimorfismo de fila en la inferencia de tipo OCaml que solo tiene polimorfismo paramétrico.

^‡) A menudo, la palabra tipificación se usa de manera intercambiable con el sistema de tipos para referirse a un conjunto particular de reglas en el sistema de tipos general. Por ejemplo, a veces decimos "OCaml tiene escritura de filas" para denotar el hecho de que el sistema de tipo OCaml proporciona reglas para el "polimorfismo de filas".

Los tipos de fila son raros. Y muy potente.

Los tipos de fila se utilizan para implementar objetos y variantes polimórficas en OCaml.

Pero primero, esto es lo que no podemos hacer sin tipos de filas:

type t1 = { a : int; b : string; } type t2 = { a : int; c : bool; } let print_a x = print_int x.a let ab = { a = 42; b = "foo"; } let ac = { a = 123; c = false; } let () = print_a ab; print_a ac

Por supuesto, este código se negará a compilar, porque print_a debe tener un tipo único: t1 o t2 , pero no ambos. Sin embargo, en algunos casos, podemos querer ese comportamiento exacto. Para eso son los tipos de filas. Eso es lo que hacen: un tipo más "flexible".

En OCaml, hay dos usos principales de los tipos de fila: objects y variantes polimórficas . En términos de álgebra, los objetos le dan "producto de fila" y variantes polimórficas "suma de fila".

Lo que hay que tener en cuenta acerca de los tipos de filas es que puede terminar con algunos subtipos por declarar, y contrarrestar la escritura intuitiva y la semántica (especialmente en las clases de casos).

Puedes consultar este papel para más detalles.