Subtipo implícito vs explícito

Esta página afirma que

muchos lenguajes no usan subtipos implícitos (equivalencia estructural), prefieren subtipos explícitos / declarados (equivalencia de declaración)

Principalmente he usado lenguajes de programación que usan subtipos explícitos . ¿Cuáles son las ventajas del subtipo implícito, como se describe en las notas anteriores?

pl.programming-languages type-theory Frankie Ribery
fuente

De las preguntas frecuentes, sobre el alcance de este intercambio: "El trabajo en este campo a menudo se distingue por su énfasis en la técnica matemática y el rigor". Estoy votando a favor porque no veo ningún margen de rigor en las respuestas a esta pregunta.

David Eppstein

Lamentablemente, hay mucho más margen de rigor para responder a esta pregunta de lo que inicialmente podría esperar. Muchas personas muy eminentes quemaron gran parte de la lucha de los 90 con preguntas aparentemente triviales sobre el subtipo. Desafortunadamente, es un área con una muy baja relación esfuerzo / recompensa.

Neel Krishnaswami

Sí, hay mucho espacio para las matemáticas y el rigor al responder esta pregunta, o al menos para explicar matemáticamente qué es el subtipo implícito . No estoy seguro de la relación esfuerzo / recompensa.

Noam Zeilberger

Probablemente debería haber dicho que fue "muy difícil", ya que al reflexionar me doy cuenta de que estoy muy interesado en las respuestas.

Neel Krishnaswami

Ok, estoy convencido Quitaría mi voto negativo, pero el sistema no me lo permite.

David Eppstein

Respuestas:

La respuesta corta es "verificar las propiedades adicionales del código existente". La respuesta más larga sigue.

No estoy seguro de que "implícito" vs "explícito" sea una buena terminología. Esta distinción a veces se denomina subtipo "estructural" frente a subtipo "nominal". Luego, también hay una segunda distinción en las posibles interpretaciones del subtipo estructural (descrito en breve). Tenga en cuenta que las tres interpretaciones del subtipo realmente son ortogonales, por lo que no tiene sentido compararlas entre sí, en lugar de comprender los usos de cada una.

La principal distinción operativa al interpretar una relación de subtipo estructural A <: B es si es presenciada por una coerción real con contenido computacional (tiempo de ejecución / tiempo de compilación), o si puede ser presenciada por la coerción de identidad. Si es lo primero, la propiedad teórica importante que debe tener es la "coherencia", es decir, si hay múltiples formas de demostrar que A es un subtipo subestructural de B, cada una de las coacciones que la acompañan deben tener el mismo contenido computacional.

El enlace que proporcionó parece tener en mente la segunda interpretación del subtipo estructural, donde A <: B puede ser testigo de la coerción de identidad. Esto a veces se llama una "interpretación de subconjunto" de subtipo, tomando la visión ingenua de que un tipo representa un conjunto de valores, por lo que A <: B en caso de que cada valor de tipo A sea también un valor de tipo B. También es a veces llamado "mecanografía de refinamiento", y un buen artículo para leer sobre la motivación original es Freeman & Pfenning's tipos de refinamiento de para ML . Para una encarnación más reciente en F #, puede leer Bengston et al, Tipos de refinamiento para implementaciones seguras. La idea básica es tomar un lenguaje de programación existente que puede (o no) tener tipos pero en el que los tipos no garantizan tanto (por ejemplo, solo seguridad de memoria), y considerar una segunda capa de tipos seleccionando subconjuntos de programas con propiedades adicionales más precisas.

(Ahora, diría que la teoría matemática detrás de esta interpretación del subtipo todavía no se entiende tan bien como debería ser, y tal vez sea porque sus usos no son tan apreciados como deberían ser. Un problema es que el "conjunto la interpretación de los tipos de valores "es demasiado ingenua y, por lo tanto, a veces se abandona en lugar de refinarse. Para otro argumento de que esta interpretación del subtipo merece más atención matemática, lea la introducción a Subspaces de Paul Taylor en la dualidad abstracta de piedra" .

Noam Zeilberger
fuente

A \times B \times C <: A \times B

$A \times B \times C <: A \times B$

C

$C$

A

$A$

B

$B$

El trabajo del optimizador es determinar el diseño óptimo de la memoria, por lo que las coacciones que son identidades realmente deberían ser el resultado de la optimización.

Andrej Bauer

solo para aclarar el comentario de Andrej con respecto a mi respuesta, en una interpretación de mecanografía de refinamiento, las relaciones de subtipo siempre son presenciadas por la coerción de identidad por definición , porque los tipos de refinamiento no tienen contenido computacional adicional. En otras palabras, si A y B son dos refinamientos ("subconjuntos" / "propiedades") de un tipo de valores X, A <: B afirma que para cada valor x en X, si x: A, entonces también x: B. Dicha declaración puede verificarse o falsificarse, pero no tiene efecto en tiempo de ejecución, ya que las pruebas de que x: A yx: B no existen en tiempo de ejecución.

Noam Zeilberger

N

$\mathbb{N}$

{x : N | x < 2^{32}}

$\{x:N\;\;|\;\;x < 2^{32}\}$

N

$N$

{x : N | x < 2^{32}}

$\{x:N | x < 2^{32}\}$

N

$N$

{x : N | x < 2^{32}}

$\{x:N | x < 2^{32}\}$

Noam Zeilberger

Esta respuesta es una especie de suplemento mínimo a la excelente respuesta de Noam. Un punto de interés de datos es el destino de los conceptos de C ++, que fracasaron en un intento de unificar las nociones nominales y estructurales de tipo.

Aquí hay una excelente reseña, con enlaces a gran parte de la discusión relevante: http://bartoszmilewski.wordpress.com/2010/06/24/c-concepts-a-postmortem/

Sin embargo, el escrito anterior no discute el problema nominal vs. estructural en ninguna profundidad. Hay otra reseña aquí, que lo hace: http://nerdland.net/2009/07/alas-concepts-we-hardly-knew-ye/

El documento clave que ambos señalan es "Simplificando el uso de conceptos" de Bjarne Stroustrup: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2906.pdf , que entra en la práctica problemas encontrados con cierta profundidad.

En general, la discusión es más pragmática que rigurosa. Sin embargo, ofrece una buena visión de los tipos de compensaciones involucradas en estos temas, especialmente en el contexto de un lenguaje existente de gran tamaño.

sclv
fuente