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í 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. (?)
fuente
Respuestas:
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
DataKinds
acerca 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.
fuente
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
se hace posible, y con él, definiciones como
lo cual es bueno. Tenga en cuenta que la longitud
n
es 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 devApply
. Por el contrario, es mucho más complicado (es decir, imposible) implementar la función que hacen
copias de un determinadox
(que seríapure
paravApply
's<*>
)porque es vital saber cuántas copias hacer en tiempo de ejecución. Ingresa singletons.
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 n
es el tipo de copias en tiempo de ejecución del nivel de tipon :: Nat
. Ahora podemos escribirEntonces, 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
permitiéndonos escribir, decir,
Eso funciona, pero ahora significa que nuestro
Nat
tipo original ha generado tres copias: una clase, una familia singleton y una clase singleton. Tenemos un proceso bastante torpe para intercambiarNatty n
valores explícitos yNattily n
diccionarios. Además,Natty
no lo esNat
: 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
Nat
puede promoverse,Vec
no 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.En cada una de nuestras dos ecuaciones, ambos lados tienen tipo
Nat
.Ahora intente la misma traducción para algo indexado sobre vectores.
se convierte
y ahora formamos restricciones equitativas entre
as :: Vec n x
yVCons z zs :: Vec (S m) x
donde 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 family
maquinaria 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., EquiparNat
con la suma, por lo que puede dar un buen tipo para agregarVec
) , 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
yMonad
convertirse 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 darlaunchMissiles
el 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
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,
vReplicate
el 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. t
cuantificador explícitamente? Si el typechecker no puede adivinarx
unificandot
, no tenemos otra manera de decir lo quex
debe 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éneas
a ~ b
donde los tipos dea
yb
no 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 tipos
que 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 escribirsin reemplazar
Nat
porNatty
. El dominio depi
puede 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)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.
fuente
fmap read getLine >>= \n -> vReplicate n 0
. Como notan,Natty
está muy lejos de esto. Además, vReplicate debe ser traducible a una matriz de memoria real, algo así comonewtype SVector n x = SVector (Data.Vector.Vector x)
, donden
tiene kindNat
(o similar). ¿Quizás otro punto de demostración para un "show-off de tipo dependiente"?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:
Editar: Hm, se suponía que era un comentario a la respuesta del trabajador porcino. Claramente fallo en SO.
fuente
Vec Zy -> IO String
. No se puede usar conwithZeroes
, porque el tipoZy
no se puede unificar con forall n. Tal vez pueda evitar eso para uno o dos casos especiales, pero rápidamente se sale de control.forall n
tiene sentido. Se pueden implementar restricciones más precisas de la misma manera. ¿Tiene un mejor ejemplo queVec Zy
(el programa aún necesitaría manejar al usuario ingresando 5 en lugar de 0)?Vec Zy -> IO String
y otra paraVec 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 valorzeroes :: IO (Some (Flip Vec Int))
.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.
fuente