¿Por qué no ser tipeado de forma dependiente?

161

He visto varias fuentes hacerse eco de la opinión de que "Haskell se está convirtiendo gradualmente en un lenguaje de tipo dependiente". La implicación parece ser que con más y más extensiones de lenguaje, Haskell se está desviando en esa dirección general, pero aún no está allí.

Básicamente hay dos cosas que me gustaría saber. La primera es, simplemente, lo que significa "ser un lenguaje escrito-dependientemente" en realidad significa ? (Ojalá sin ser demasiado técnico al respecto).

La segunda pregunta es ... ¿cuál es el inconveniente? Quiero decir, la gente sabe que vamos en esa dirección, por lo que debe haber alguna ventaja. Y, sin embargo, todavía no estamos allí, por lo que debe haber algún inconveniente que impida que la gente siga todo el camino. Tengo la impresión de que el problema es un fuerte aumento de la complejidad. Pero, sin comprender realmente qué es la escritura dependiente, no estoy seguro.

Lo que sé es que cada vez que comienzo a leer sobre un lenguaje de programación de tipo dependiente, el texto es completamente incomprensible ... Presumiblemente ese es el problema. (?)

Orquídea matemática
fuente
10
En pocas palabras, puede escribir tipos que dependen de términos (cálculos). Esto es suficiente para especificar tipos sobre cada aspecto de su programa y, por lo tanto, significa que el sistema de tipos es capaz de especificar el programa completo. El problema es que debido a que los tipos dependen de los cálculos, la verificación de tipos es mucho más difícil de hacer (imposible en general).
GManNickG
27
@GManNickG: la verificación de tipos es totalmente posible. La inferencia de tipos es otra cuestión, pero nuevamente las diversas extensiones de GHC han abandonado hace mucho tiempo la idea de que debería ser posible inferir todos los tipos.
CA McCann
77
Si entiendo correctamente, el inconveniente es que hacer un tipeo dependiente correcto (por ejemplo, de una manera que sea utilizable y bien fundada) es difícil , y aún no sabemos cómo.
Próxima tormenta
1
@CAMcCann: Sí, mi error.
GManNickG
44
No creo que nadie haya señalado el único gran inconveniente pragmático: escribir pruebas de que todo su código es correcto es bastante tedioso. Debido a que no puede hacer automáticamente la inferencia de tipos (corresponde a la demostración de teoremas en una lógica "hella poderosa"), debe escribir anotaciones para su programa en forma de pruebas. Obviamente, esto se vuelve molesto y difícil de hacer después de un tiempo, especialmente para la magia monádica más elaborada que la gente suele hacer en Haskell. Lo más cercano que estamos llegando en estos días son los idiomas que hacen la mayor parte de esto por nosotros o nos dan un buen conjunto de primitivas.
Kristopher Micinski

Respuestas:

21

La escritura dependiente es realmente solo la unificación del valor y los niveles de tipo, por lo que puede parametrizar valores en tipos (ya es posible con clases de tipos y polimorfismo paramétrico en Haskell) y puede parametrizar tipos en valores (no, estrictamente hablando, aún posible en Haskell , aunque se DataKindsacerca mucho).

Editar: Aparentemente, a partir de este momento, me equivoqué (vea el comentario de @ pigworker). Conservaré el resto de esto como un registro de los mitos que me han alimentado. :PAGS


El problema con pasar a una escritura totalmente dependiente, por lo que he escuchado, es que rompería la restricción de fase entre los niveles de tipo y valor que permite que Haskell se compile en un código de máquina eficiente con tipos borrados. Con nuestro nivel actual de tecnología, un lenguaje de tipo dependiente debe pasar por un intérprete en algún momento (ya sea inmediatamente o después de ser compilado a un bytecode de tipo dependiente o similar).

Esto no es necesariamente una restricción fundamental, pero no conozco personalmente ninguna investigación actual que parezca prometedora a este respecto, pero que aún no se ha convertido en GHC. Si alguien más sabe más, estaría feliz de ser corregido.

Llama de Ptharien
fuente
46
Lo que dices es casi completamente falso. No te culpo por completo: repite los mitos estándar como un hecho. El lenguaje de Edwin Brady, Idris, realiza el borrado de tipo (porque ningún comportamiento en tiempo de ejecución depende de los tipos) y genera una codificación de supercombinador levantada lambda bastante estándar a partir de la cual se genera el código utilizando técnicas de máquina G estándar.
trabajador porcino
3
Como nota al margen, alguien recientemente me señaló este documento . Por lo que puedo decir, haría que Haskell fuera de tipo dependiente (es decir, el lenguaje de nivel de tipo sería de tipo dependiente), que es lo más cercano que puedo ver en un futuro cercano.
Llama de Ptharien
8
Sí, ese documento muestra la forma de hacer que los tipos dependan de cosas de nivel de tipo (y eliminar la distinción tipo / tipo). Un seguimiento plausible, ya en discusión, es permitir tipos de funciones dependientes reales, pero restringir sus argumentos al fragmento del lenguaje que puede existir tanto en las capas de valor como de tipo (ahora no trivial gracias a la promoción del tipo de datos). Eso eliminaría la necesidad de la construcción singleton que actualmente hace que "fingirlo" sea más complejo de lo deseable. Nos estamos acercando cada vez más a la realidad.
trabajador porcino
13
Hay muchas preguntas pragmáticas, adaptando tipos dependientes a Haskell. Una vez que tenemos esta forma restringida de espacio de función dependiente, aún nos enfrentamos a la pregunta de cómo agrandar el fragmento del lenguaje de valores que está permitido a nivel de tipo, y cuál debería ser su teoría de la ecuación (como queremos que 2 + 2 ser 4 y tal). Hay muchos problemas complicados (p. Ej., Inferior) que desde el principio los lenguajes tipeados de forma dependiente diseñan desde el principio.
pigworker
2
@pigworker ¿Hay un subconjunto limpio de Haskell que sea total? Si es así, ¿no podríamos usar eso para el "fragmento del lenguaje que puede existir tanto en las capas de valor como de tipo"? Si no, ¿qué se necesitaría para producir uno?
Llama de Ptharien
223

Haskell mecanografiado dependientemente, ¿ahora?

Haskell es, en pequeña medida, un lenguaje de tipo dependiente. Existe una noción de datos de nivel de tipo, ahora se escribe con mayor sensatez gracias a ella DataKinds, y hay algunos medios ( GADTs) para dar una representación en tiempo de ejecución a los datos de nivel de tipo. Por lo tanto, los valores de material en tiempo de ejecución se muestran efectivamente en tipos , que es lo que significa que un idioma se tipee de forma dependiente.

Los tipos de datos simples se promueven al nivel de clase, de modo que los valores que contienen se pueden usar en tipos. De ahí el ejemplo arquetípico

data Nat = Z | S Nat

data Vec :: Nat -> * -> * where
  VNil   :: Vec Z x
  VCons  :: x -> Vec n x -> Vec (S n) x

se hace posible, y con él, definiciones como

vApply :: Vec n (s -> t) -> Vec n s -> Vec n t
vApply VNil         VNil         = VNil
vApply (VCons f fs) (VCons s ss) = VCons (f s) (vApply fs ss)

lo cual es bueno. Tenga en cuenta que la longitud nes algo puramente estático en esa función, asegurando que los vectores de entrada y salida tengan la misma longitud, aunque esa longitud no desempeñe ningún papel en la ejecución de vApply. Por el contrario, es mucho más complicado (es decir, imposible) implementar la función que hace ncopias de un determinado x(que sería purepara vApply's <*>)

vReplicate :: x -> Vec n x

porque es vital saber cuántas copias hacer en tiempo de ejecución. Ingresa singletons.

data Natty :: Nat -> * where
  Zy :: Natty Z
  Sy :: Natty n -> Natty (S n)

Para cualquier tipo promocionable, podemos construir la familia singleton, indexada sobre el tipo promocionado, habitada por duplicados en tiempo de ejecución de sus valores. Natty nes el tipo de copias en tiempo de ejecución del nivel de tipo n :: Nat. Ahora podemos escribir

vReplicate :: Natty n -> x -> Vec n x
vReplicate Zy     x = VNil
vReplicate (Sy n) x = VCons x (vReplicate n x)

Entonces, tiene un valor de nivel de tipo unido a un valor de tiempo de ejecución: inspeccionar la copia en tiempo de ejecución refina el conocimiento estático del valor de nivel de tipo. A pesar de que los términos y los tipos están separados, podemos trabajar de forma dependiente usando la construcción singleton como una especie de resina epoxi, creando enlaces entre las fases. Eso está muy lejos de permitir expresiones arbitrarias en tiempo de ejecución en tipos, pero no es nada.

¿Qué es desagradable? ¿Qué falta?

Pongamos un poco de presión en esta tecnología y veamos qué comienza a tambalearse. Podríamos tener la idea de que los singletons deberían ser manejables un poco más implícitamente

class Nattily (n :: Nat) where
  natty :: Natty n
instance Nattily Z where
  natty = Zy
instance Nattily n => Nattily (S n) where
  natty = Sy natty

permitiéndonos escribir, decir,

instance Nattily n => Applicative (Vec n) where
  pure = vReplicate natty
  (<*>) = vApply

Eso funciona, pero ahora significa que nuestro Nattipo original ha generado tres copias: una clase, una familia singleton y una clase singleton. Tenemos un proceso bastante torpe para intercambiar Natty nvalores explícitos y Nattily ndiccionarios. Además, Nattyno lo es Nat: tenemos algún tipo de dependencia de los valores de tiempo de ejecución, pero no del tipo en el que primero pensamos. ¡Ningún lenguaje tipeado totalmente dependiente hace que los tipos dependientes sean tan complicados!

Mientras tanto, aunque Natpuede promoverse, Vecno puede. No puede indexar por un tipo indexado. Completo en los idiomas mecanografiados de forma dependiente no impone tal restricción, y en mi carrera como presumido mecanografiado de forma dependiente, he aprendido a incluir ejemplos de indexación de dos capas en mis charlas, solo para enseñar a las personas que han hecho una indexación de una capa difícil pero posible no esperar que me doble como un castillo de naipes. ¿Cuál es el problema? Igualdad. Los GADT funcionan traduciendo las restricciones que logras implícitamente cuando le das a un constructor un tipo de retorno específico en demandas ecológicas explícitas. Me gusta esto.

data Vec (n :: Nat) (x :: *)
  = n ~ Z => VNil
  | forall m. n ~ S m => VCons x (Vec m x)

En cada una de nuestras dos ecuaciones, ambos lados tienen tipo Nat.

Ahora intente la misma traducción para algo indexado sobre vectores.

data InVec :: x -> Vec n x -> * where
  Here :: InVec z (VCons z zs)
  After :: InVec z ys -> InVec z (VCons y ys)

se convierte

data InVec (a :: x) (as :: Vec n x)
  = forall m z (zs :: Vec x m). (n ~ S m, as ~ VCons z zs) => Here
  | forall m y z (ys :: Vec x m). (n ~ S m, as ~ VCons y ys) => After (InVec z ys)

y ahora formamos restricciones equitativas entre as :: Vec n xy VCons z zs :: Vec (S m) xdonde los dos lados tienen tipos sintácticamente distintos (pero demostrablemente iguales). ¡El núcleo GHC no está equipado actualmente para tal concepto!

¿Qué más falta? Bueno, la mayoría de Haskell falta en el nivel de tipo. El lenguaje de los términos que puede promover tiene solo variables y constructores no GADT, realmente. Una vez que los tenga, la type familymaquinaria le permite escribir programas de nivel de tipo: algunos de ellos podrían ser funciones que consideraría escribir a nivel de término (p. Ej., Equipar Natcon la suma, por lo que puede dar un buen tipo para agregar Vec) , pero eso es solo una coincidencia!

Otra cosa que falta, en la práctica, es una biblioteca que utiliza nuestras nuevas habilidades para indexar tipos por valores. ¿Qué hacer Functor y Monadconvertirse en este valiente mundo nuevo? Estoy pensando en eso, pero aún queda mucho por hacer.

Ejecución de programas de nivel de tipo

Haskell, como la mayoría de los lenguajes de programación de tipo dependiente, tiene dos semánticas operativas. Existe la forma en que el sistema de tiempo de ejecución ejecuta programas (solo expresiones cerradas, después de la eliminación de tipos, altamente optimizado) y luego está la forma en que el typechecker ejecuta programas (sus familias de tipos, su "Prólogo de clase de tipo", con expresiones abiertas). Para Haskell, normalmente no se mezclan los dos, porque los programas que se ejecutan están en diferentes idiomas. Los lenguajes de tipo dependiente tienen modelos de ejecución estáticos y de tiempo de ejecución separados para el mismo lenguaje de programas, pero no se preocupe, el modelo de tiempo de ejecución todavía le permite borrar el tipo y, de hecho, borrar la prueba: eso es lo que extrae Coqel mecanismo te da; eso es al menos lo que hace el compilador de Edwin Brady (aunque Edwin borra valores innecesariamente duplicados, así como tipos y pruebas). La distinción de fase puede que ya no sea una distinción de categoría sintáctica , pero está viva y bien.

Los lenguajes mecanografiados de forma dependiente, al ser total, le permiten al typechecker ejecutar programas sin temor a nada peor que una larga espera. A medida que Haskell se vuelve más tipeado de forma dependiente, nos enfrentamos a la pregunta de cuál debería ser su modelo de ejecución estático. Un enfoque podría ser restringir la ejecución estática a funciones totales, lo que nos permitiría la misma libertad de ejecución, pero podría obligarnos a hacer distinciones (al menos para el código de nivel de tipo) entre datos y codatos, para que podamos saber si hacer cumplir la terminación o la productividad. Pero ese no es el único enfoque. Somos libres de elegir un modelo de ejecución mucho más débil que sea reacio a ejecutar programas, a costa de hacer que salgan menos ecuaciones solo por cálculo. Y en efecto, eso es lo que realmente hace GHC. Las reglas de escritura para GHC core no mencionan la ejecución programas, pero solo para verificar la evidencia de ecuaciones. Al traducir al núcleo, el solucionador de restricciones de GHC intenta ejecutar sus programas de nivel de tipo, generando un pequeño rastro plateado de evidencia de que una expresión dada es igual a su forma normal. Este método de generación de evidencia es un poco impredecible e inevitablemente incompleto: por ejemplo, lucha contra la recurrencia de aspecto aterrador, y eso probablemente sea sabio. Una cosa de la que no debemos preocuparnos es la ejecución de los IO cálculos en el typechecker: ¡recuerde que el typechecker no tiene que dar launchMissilesel mismo significado que el sistema de tiempo de ejecución!

Cultura Hindley-Milner

¡El sistema de tipo Hindley-Milner logra la coincidencia verdaderamente asombrosa de cuatro distinciones distintas, con el desafortunado efecto secundario cultural de que muchas personas no pueden ver la distinción entre las distinciones y asumir que la coincidencia es inevitable! De que estoy hablando

  • términos vs tipos
  • cosas escritas explícitamente vs cosas escritas implícitamente
  • presencia en tiempo de ejecución frente a borrado antes del tiempo de ejecución
  • abstracción no dependiente vs cuantificación dependiente

Estamos acostumbrados a escribir términos y dejar tipos para inferir ... y luego borrar. Estamos acostumbrados a cuantificar las variables de tipo con la abstracción de tipo correspondiente y la aplicación que ocurre de forma silenciosa y estática.

No tiene que desviarse demasiado de la vainilla Hindley-Milner antes de que estas distinciones se desalineen, y eso no es malo . Para empezar, podemos tener tipos más interesantes si estamos dispuestos a escribirlos en algunos lugares. Mientras tanto, no tenemos que escribir diccionarios de clase de tipo cuando usamos funciones sobrecargadas, pero esos diccionarios están ciertamente presentes (o en línea) en tiempo de ejecución. En lenguajes de tipo dependiente, esperamos borrar más que solo los tipos en tiempo de ejecución, pero (como con las clases de tipos) que algunos valores inferidos implícitamente no se borrarán. Por ejemplo, vReplicateel argumento numérico a menudo es inferible del tipo del vector deseado, pero aún necesitamos saberlo en tiempo de ejecución.

¿Qué opciones de diseño de lenguaje debemos revisar porque estas coincidencias ya no son válidas? Por ejemplo, ¿es correcto que Haskell no proporcione una forma de instanciar un forall x. tcuantificador explícitamente? Si el typechecker no puede adivinar xunificando t, no tenemos otra manera de decir lo que xdebe ser.

En términos más generales, no podemos tratar la "inferencia de tipos" como un concepto monolítico del que tenemos todo o nada. Para empezar, necesitamos separar el aspecto de "generalización" (la regla de "dejar" de Milner), que depende en gran medida de restringir qué tipos existen para garantizar que una máquina estúpida pueda adivinar uno, desde el aspecto de "especialización" ("var" de Milner "regla) que es tan eficaz como su solucionador de restricciones. Podemos esperar que los tipos de nivel superior sean más difíciles de inferir, pero que la información de tipos internos seguirá siendo bastante fácil de propagar.

Próximos pasos para Haskell

Estamos viendo que el tipo y los niveles de tipo se vuelven muy similares (y ya comparten una representación interna en GHC). También podríamos fusionarlos. Sería divertido tomarlo * :: *si podemos: perdimos la solidez lógica hace mucho tiempo, cuando permitimos el fondo, pero la solidez del tipo suele ser un requisito más débil. Hay que comprobarlo. Si debemos tener distintos niveles de tipo, tipo, etc., al menos podemos asegurarnos de que todo en el nivel de tipo y superior siempre se puede promover. Sería genial reutilizar el polimorfismo que ya tenemos para los tipos, en lugar de reinventar el polimorfismo a nivel amable.

Deberíamos simplificar y generalizar el sistema actual de restricciones al permitir ecuaciones heterogéneasa ~ b donde los tipos de ay bno son sintácticamente idénticos (pero pueden probarse iguales). Es una técnica antigua (en mi tesis, del siglo pasado) que hace que la dependencia sea mucho más fácil de manejar. Podríamos expresar restricciones sobre las expresiones en GADT y, por lo tanto, relajar las restricciones sobre lo que se puede promover.

Debemos eliminar la necesidad de la construcción Singleton mediante la introducción de un tipo de función dependiente pi x :: s -> t. Una función con dicho tipo podría aplicarse explícitamente a cualquier expresión de tipo sque viva en la intersección de los lenguajes de tipo y término (por lo tanto, variables, constructores, con más por venir más adelante). La lambda y la aplicación correspondientes no se borrarían en tiempo de ejecución, por lo que podríamos escribir

vReplicate :: pi n :: Nat -> x -> Vec n x
vReplicate Z     x = VNil
vReplicate (S n) x = VCons x (vReplicate n x)

sin reemplazar Natpor Natty. El dominio de pipuede ser de cualquier tipo promocionable, por lo que si se pueden promover los GADT, podemos escribir secuencias cuantificadoras dependientes (o "telescopios" como los llamó De Briuijn)

pi n :: Nat -> pi xs :: Vec n x -> ...

a cualquier longitud que necesitemos.

El objetivo de estos pasos es eliminar la complejidad trabajando directamente con herramientas más generales, en lugar de conformarse con herramientas débiles y codificaciones torpes. La aceptación parcial actual hace que los beneficios de los tipos dependientes de Haskell sean más caros de lo que deberían ser.

¿Demasiado duro?

Los tipos dependientes ponen nerviosas a muchas personas. Me ponen nervioso, pero me gusta estar nervioso, o al menos me resulta difícil no estar nervioso de todos modos. Pero no ayuda que haya tanta niebla de ignorancia en torno al tema. Algo de eso se debe al hecho de que todos todavía tenemos mucho que aprender. Pero se sabe que los defensores de enfoques menos radicales avivan el miedo a los tipos dependientes sin asegurarse siempre de que los hechos estén totalmente de acuerdo con ellos. No nombraré nombres. Estos "controles de tipo indecidibles", "Turing incompleto", "sin distinción de fase", "sin borrado de tipo", "pruebas en todas partes", etc., los mitos persisten, a pesar de que son basura.

Ciertamente, no es el caso de que los programas mecanografiados de forma dependiente siempre se demuestren correctos. Uno puede mejorar la higiene básica de sus programas, imponiendo invariantes adicionales en tipos sin tener que llegar a una especificación completa. Pequeños pasos en esta dirección a menudo resultan en garantías mucho más fuertes con pocas o ninguna obligación de prueba adicional. No es cierto que los programas de tipo dependiente estén inevitablemente llenos de pruebas, de hecho, generalmente considero la presencia de cualquier prueba en mi código como la señal para cuestionar mis definiciones .

Porque, como con cualquier aumento en la articulación, nos volvemos libres de decir cosas malas y nuevas. Por ejemplo, hay muchas formas malas de definir árboles de búsqueda binarios, pero eso no significa que no haya una buena manera . Es importante no presumir que las malas experiencias no pueden ser mejoradas, incluso si esto perjudica al ego para admitirlo. ¡El diseño de definiciones dependientes es una nueva habilidad que requiere aprendizaje, y ser un programador de Haskell no te convierte automáticamente en un experto! E incluso si algunos programas son sucios, ¿por qué negarías a otros la libertad de ser justos?

¿Por qué todavía molestarse con Haskell?

Realmente disfruto los tipos dependientes, pero la mayoría de mis proyectos de piratería aún están en Haskell. ¿Por qué? Haskell tiene clases de tipo. Haskell tiene bibliotecas útiles. Haskell tiene un tratamiento viable (aunque lejos de ser ideal) de programación con efectos. Haskell tiene un compilador de fuerza industrial. Los idiomas de tipo dependiente se encuentran en una etapa mucho más temprana en el crecimiento de la comunidad y la infraestructura, pero llegaremos allí, con un cambio generacional real en lo que es posible, por ejemplo, mediante metaprogramación y genéricos de tipo de datos. Pero solo tiene que mirar a su alrededor lo que la gente está haciendo como resultado de los pasos de Haskell hacia los tipos dependientes para ver que también se pueden obtener muchos beneficios al impulsar la generación actual de idiomas.

trabajador porcino
fuente
66
Realmente no me importan las cosas de DataKinds todavía. Sobre todo porque quiero hacer algo como esto: fmap read getLine >>= \n -> vReplicate n 0. Como notan, Nattyestá muy lejos de esto. Además, vReplicate debe ser traducible a una matriz de memoria real, algo así como newtype SVector n x = SVector (Data.Vector.Vector x), donde ntiene kind Nat(o similar). ¿Quizás otro punto de demostración para un "show-off de tipo dependiente"?
John L
77
¿Podría decir lo que tiene en mente para un tratamiento ideal de programación con efectos?
Steven Shaw
66
Gracias por la gran escritura. Me encantaría ver algunos ejemplos de código tipeado de forma dependiente donde algunos datos se originan fuera del programa (por ejemplo, leer de un archivo), para tener una idea de cómo se vería la promoción de valores a tipos en un entorno de este tipo. Tengo la sensación de que todos los ejemplos involucran vectores (implementados como listas) con tamaños conocidos estáticamente.
tibbe
44
@pigworker Usted toma "ninguna distinción de fase" como un mito (los otros que estoy de acuerdo son mitos). Pero no lo ha desmantelado en los documentos y charlas que he visto, y mientras tanto otra persona a la que respeto me dice "la teoría de tipos dependientes es diferente de un compilador típico porque no podemos separar significativamente las fases de verificación de tipo, compilación y ejecución. " (ver la última publicación de Andrej del 8 de noviembre de 2012) En mi experiencia "fingiendo", a veces al menos desdibujamos la distinción de fase, aunque no es necesario borrarla. ¿Podría ampliar, si no aquí, en otro lugar, sobre este tema?
sclv
44
@sclv Mi trabajo no se ha centrado especialmente en el mito de la "distinción sin fase", pero otros sí. Recomiendo el rechazo "Distinciones de fase en la compilación del epigrama", de James McKinna y Edwin Brady, como un buen lugar para comenzar. Pero vea también trabajos mucho más antiguos sobre extracción de programas en Coq. La evaluación de términos abiertos realizada por typechecker está completamente separada de la ejecución mediante extracción a ML, y está claro que la extracción elimina los tipos y las pruebas.
trabajador porcino
20

John es otro concepto erróneo común sobre los tipos dependientes: que no funcionan cuando los datos solo están disponibles en tiempo de ejecución. Así es como puedes hacer el ejemplo de getLine:

data Some :: (k -> *) -> * where
  Like :: p x -> Some p

fromInt :: Int -> Some Natty
fromInt 0 = Like Zy
fromInt n = case fromInt (n - 1) of
  Like n -> Like (Sy n)

withZeroes :: (forall n. Vec n Int -> IO a) -> IO a
withZeroes k = do
  Like n <- fmap (fromInt . read) getLine
  k (vReplicate n 0)

*Main> withZeroes print
5
VCons 0 (VCons 0 (VCons 0 (VCons 0 (VCons 0 VNil))))

Editar: Hm, se suponía que era un comentario a la respuesta del trabajador porcino. Claramente fallo en SO.

ulfnorell
fuente
Tu primera oración parece un poco extraña; Yo diría que el punto de tipos dependientes es que hacen el trabajo cuando los datos sólo está disponible en tiempo de ejecución. Sin embargo, esta técnica de estilo CPS no es la misma. Supongamos que tienes una función Vec Zy -> IO String. No se puede usar con withZeroes, porque el tipo Zyno se puede unificar con forall n. Tal vez pueda evitar eso para uno o dos casos especiales, pero rápidamente se sale de control.
John L
La clave al tomar un valor simplemente escrito (como el String de getLine) y convertirlo en algo con un tipo más fuerte (como un Natty n arriba) es que tiene que convencer al verificador de tipo de que está haciendo las verificaciones dinámicas necesarias. En su ejemplo, está leyendo un número arbitrario, por lo que forall ntiene sentido. Se pueden implementar restricciones más precisas de la misma manera. ¿Tiene un mejor ejemplo que Vec Zy(el programa aún necesitaría manejar al usuario ingresando 5 en lugar de 0)?
ulfnorell
1
Lo que quise decir con la primera oración es que ocasionalmente me encuentro con personas que creen que no puedes usar tipos dependientes si obtienes tus datos al interactuar con el mundo exterior. Mi punto es que lo único que tiene que hacer es escribir un analizador tipeado de forma dependiente, que generalmente es sencillo.
ulfnorell
1
ulfnorell: Lo siento, no estaba claro. Suponga que tiene una función con la que funcionará Vec Zy -> IO Stringy otra para Vec n -> IO String, y desea usar la primera solo si el tipo coincide. Sí, es posible, pero los mecanismos para habilitarlo son torpes. Y esta es una lógica muy simple; Si tienes una lógica más compleja, es peor. Además, es posible que deba volver a escribir una gran cantidad de código en CPS. Y todavía no tiene una expresión de nivel de tipo que dependa de un término en el nivel de valor
John L
Ah, ya veo lo que estás diciendo. Para esto es Natty, como en vReplicate, donde hacemos diferentes cosas dependiendo de n. De hecho, esto puede volverse un poco torpe. Una alternativa al estilo de CPS es trabajar con los existenciales empacado: zeroes :: IO (Some (Flip Vec Int)).
ulfnorell
19

El trabajador porcino da una excelente discusión de por qué deberíamos dirigirnos hacia tipos dependientes: (a) son increíbles; (b) en realidad simplificarían mucho lo que Haskell ya hace.

En cuanto al "¿por qué no?" pregunta, creo que hay un par de puntos. El primer punto es que, si bien la noción básica detrás de los tipos dependientes es fácil (permitir que los tipos dependan de los valores), las ramificaciones de esa noción básica son sutiles y profundas. Por ejemplo, la distinción entre valores y tipos sigue viva y bien; pero discutir la diferencia entre ellos llega a ser lejosmás matizado que en su Hindley - Milner o System F. Hasta cierto punto, esto se debe al hecho de que los tipos dependientes son fundamentalmente difíciles (por ejemplo, la lógica de primer orden es indecidible). Pero creo que el problema más grande es que nos falta un buen vocabulario para capturar y explicar lo que está sucediendo. A medida que más y más personas aprendan sobre los tipos dependientes, desarrollaremos un mejor vocabulario y las cosas serán más fáciles de entender, incluso si los problemas subyacentes siguen siendo difíciles.

El segundo punto tiene que ver con el hecho de que Haskell está creciendohacia tipos dependientes. Debido a que estamos progresando progresivamente hacia ese objetivo, pero sin llegar realmente allí, estamos atrapados con un lenguaje que tiene parches incrementales además de parches incrementales. Lo mismo ha sucedido en otros idiomas a medida que las nuevas ideas se hicieron populares. Java no solía tener polimorfismo (paramétrico); y cuando finalmente lo agregaron, obviamente fue una mejora incremental con algunas fugas de abstracción y poder paralizado. Resulta que mezclar subtipos y polimorfismos es inherentemente difícil; pero esa no es la razón por la cual los Java Generics funcionan de la manera en que lo hacen. Funcionan como lo hacen debido a la restricción de ser una mejora incremental para las versiones anteriores de Java. Lo mismo, para más atrás en el día cuando se inventó la POO y la gente comenzó a escribir "objetivo" C (no debe confundirse con Objective-C), etc. Recuerde, C ++ comenzó con el pretexto de ser un superconjunto estricto de C. Agregar nuevos paradigmas siempre requiere definir el lenguaje nuevamente, o terminar con un desorden complicado. Mi punto en todo esto es que, agregar verdaderos tipos dependientes a Haskell requerirá una cierta cantidad de destripamiento y reestructuración del lenguaje, si vamos a hacerlo bien. Pero es realmente difícil comprometerse a ese tipo de revisión, mientras que el progreso incremental que hemos estado haciendo parece más barato a corto plazo. Realmente, no hay tanta gente que piratee GHC, pero hay una buena cantidad de código heredado para mantener con vida. Esta es parte de la razón por la cual hay tantos lenguajes derivados como DDC, Cayenne, Idris, etc. C ++ comenzó bajo el pretexto de ser un superconjunto estricto de C. Agregar nuevos paradigmas siempre requiere definir el lenguaje nuevamente, o terminar con un desorden complicado. Mi punto en todo esto es que, agregar verdaderos tipos dependientes a Haskell requerirá una cierta cantidad de destripamiento y reestructuración del lenguaje, si vamos a hacerlo bien. Pero es realmente difícil comprometerse a ese tipo de revisión, mientras que el progreso incremental que hemos estado haciendo parece más barato a corto plazo. Realmente, no hay tanta gente que piratee GHC, pero hay una buena cantidad de código heredado para mantener con vida. Esta es parte de la razón por la cual hay tantos lenguajes derivados como DDC, Cayenne, Idris, etc. C ++ comenzó bajo el pretexto de ser un superconjunto estricto de C. Agregar nuevos paradigmas siempre requiere definir el lenguaje nuevamente, o terminar con un desorden complicado. Mi punto en todo esto es que, agregar verdaderos tipos dependientes a Haskell requerirá una cierta cantidad de destripamiento y reestructuración del lenguaje, si vamos a hacerlo bien. Pero es realmente difícil comprometerse a ese tipo de revisión, mientras que el progreso incremental que hemos estado haciendo parece más barato a corto plazo. Realmente, no hay tanta gente que piratee GHC, pero hay una buena cantidad de código heredado para mantener con vida. Esta es parte de la razón por la cual hay tantos lenguajes derivados como DDC, Cayenne, Idris, etc. o de lo contrario terminar con un lío complicado. Mi punto en todo esto es que, agregar verdaderos tipos dependientes a Haskell requerirá una cierta cantidad de destripamiento y reestructuración del lenguaje, si vamos a hacerlo bien. Pero es realmente difícil comprometerse a ese tipo de revisión, mientras que el progreso incremental que hemos estado haciendo parece más barato a corto plazo. Realmente, no hay tanta gente que piratee GHC, pero hay una buena cantidad de código heredado para mantener con vida. Esta es parte de la razón por la cual hay tantos lenguajes derivados como DDC, Cayenne, Idris, etc. o de lo contrario terminar con un lío complicado. Mi punto en todo esto es que, agregar verdaderos tipos dependientes a Haskell requerirá una cierta cantidad de destripamiento y reestructuración del lenguaje, si vamos a hacerlo bien. Pero es realmente difícil comprometerse a ese tipo de revisión, mientras que el progreso incremental que hemos estado haciendo parece más barato a corto plazo. Realmente, no hay tanta gente que piratee GHC, pero hay una buena cantidad de código heredado para mantener con vida. Esta es parte de la razón por la cual hay tantos lenguajes derivados como DDC, Cayenne, Idris, etc. Es realmente difícil comprometerse con ese tipo de revisión, mientras que el progreso incremental que hemos estado haciendo parece más barato a corto plazo. Realmente, no hay tanta gente que piratee GHC, pero hay una buena cantidad de código heredado para mantener con vida. Esta es parte de la razón por la cual hay tantos lenguajes derivados como DDC, Cayenne, Idris, etc. Es realmente difícil comprometerse con ese tipo de revisión, mientras que el progreso incremental que hemos estado haciendo parece más barato a corto plazo. Realmente, no hay tanta gente que piratee GHC, pero hay una buena cantidad de código heredado para mantener con vida. Esta es parte de la razón por la cual hay tantos lenguajes derivados como DDC, Cayenne, Idris, etc.

wren romano
fuente