que name keywords etiqueta haskell type-systems dependent-type

haskell - name - ¿Por qué no teclear de forma dependiente?



meta tags (4)

Dependiente Typed Haskell, ahora?

Haskell es, en pequeña medida, un lenguaje dependiente de tipeo. Hay una noción de datos de nivel de tipo, ahora más sensible DataKinds gracias a DataKinds , y hay algunos medios ( GADTs ) para dar una representación en tiempo de ejecución a los datos de tipo de nivel. 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 escriba de manera dependiente.

Los tipos de datos simples se promueven al nivel de tipo, 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 ello, 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 n es un elemento puramente estático en esa función, lo que garantiza que los vectores de entrada y salida tengan la misma longitud, aunque esa longitud no desempeña 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 n copias de una x determinada (que sería pure para vApply ''s <*> )

vReplicate :: x -> Vec n x

porque es vital saber cuántas copias hacer en tiempo de ejecución. Ingrese 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, habitado por duplicados en tiempo de ejecución de sus valores. Natty n es el tipo de copias en tiempo de ejecución del tipo de nivel 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, hay un valor de nivel de tipo yugo en un valor de tiempo de ejecución: la inspección de la copia en tiempo de ejecución refina el conocimiento estático del valor de nivel de tipo. Aunque los términos y los tipos están separados, podemos trabajar de una manera dependiente a tipeo utilizando la construcción singleton como un tipo de resina epoxi, creando vínculos entre las fases. Eso es un largo camino desde 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 sobre 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 tipo Nat original ha engendrado tres copias: una especie, una familia singleton y una clase singleton. Tenemos un proceso bastante torpe para intercambiar valores Natty n explícitos y diccionarios Nattily n . Además, Natty no es Nat : tenemos algún tipo de dependencia de los valores de tiempo de ejecución, pero no del tipo que pensamos inicialmente. ¡Ningún lenguaje dependiente completamente tipeado hace que los tipos dependientes sean tan complicados!

Mientras tanto, aunque Nat puede promoverse, Vec no puede. No puede indexar por un tipo indexado. Lleno de idiomas subtitulados no impone tal restricción, y en mi carrera como un tipo de mecanografía 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 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. Las GADT funcionan traduciendo implícitamente las restricciones que logras cuando le das a un constructor un tipo de devolución específico en demandas ecuacionales 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 el tipo Nat .

Ahora intenta 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 ecuacionales entre as :: Vec nx y VCons z zs :: Vec (S m) x donde los dos lados tienen tipos sintácticamente distintos (pero provablemente iguales). ¡GHC core no está actualmente equipado para tal concepto!

¿Qué más falta? Bueno, la mayor parte de Haskell falta en el nivel de tipo. El lenguaje de los términos que puede promover tiene solo variables y constructores que no son GADT, realmente. Una vez que los tiene, la maquinaria type family permite escribir programas a nivel de tipo: algunos de ellos podrían ser funciones similares a las que consideraría escribir a nivel de término (por ejemplo, equipar Nat con suma, para que pueda dar un buen tipo a anexar para Vec ), pero eso es solo una coincidencia!

Otra cosa que falta, en la práctica, es una biblioteca que hace uso de nuestras nuevas habilidades para indexar tipos por valores. ¿En qué se convierten Functor y Monad en este mundo nuevo y valiente? Estoy pensando en eso, pero todavía hay mucho por hacer.

Ejecución de programas de nivel de tipo

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

Los lenguajes dependientes, al ser totales, le permiten al programador de tchetes ejecutar programas sin miedo a algo peor que una larga espera. A medida que Haskell se vuelve más dependientemente tipado, 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 forzarnos a hacer distinciones (al menos para el código de tipo de nivel) entre datos y codata, para que podamos decir 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 aparezcan menos ecuaciones solo por computación. Y, en efecto, eso es lo que realmente hace GHC. Las reglas de tipaje para GHC core no mencionan ejecutar programas, pero solo para verificar evidencias de ecuaciones. Al traducir al núcleo, el solucionador de restricciones de GHC intenta ejecutar tus 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: lucha contra la recurrencia de aspecto aterrador, por ejemplo, y eso es probablemente sensato. Una cosa de la que no tenemos que preocuparnos es la ejecución de cálculos IO en el contador de tipos: recuerde que typechecker no tiene que dar a launchMissiles el mismo significado que el sistema en tiempo de ejecución.

Cultura Hindley-Milner

El sistema tipo Hindley-Milner logra la coincidencia verdaderamente increíble de cuatro distinciones distintas, con el desafortunado efecto secundario cultural de que muchas personas no pueden ver la distinción entre las distinciones y suponer que la coincidencia es inevitable. ¿De qué estoy hablando?

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

Estamos acostumbrados a escribir términos y dejar tipos que se deducen ... y luego se borran. Estamos acostumbrados a cuantificar las variables de tipo con la correspondiente abstracción de tipos y la aplicación que ocurre silenciosa y estáticamente.

No tiene que alejarse demasiado de Vanilla 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 clases de tipo cuando utilizamos funciones sobrecargadas, pero esos diccionarios están ciertamente presentes (o integrados) en tiempo de ejecución. En los idiomas de tipo dependiente, esperamos borrar más que solo los tipos en tiempo de ejecución, pero (al igual que con las clases de tipo) que algunos valores inferidos implícitamente no se borrarán. Por ejemplo, el argumento numérico de vReplicate menudo es deducible del tipo del vector deseado, pero aún necesitamos saberlo en tiempo de ejecución.

¿Qué opciones de diseño del lenguaje deberíamos revisar porque estas coincidencias ya no se mantienen? Por ejemplo, es correcto que Haskell no proporcione ninguna forma de instanciar un forall x. t forall x. t cuantificador explícitamente? Si typechecker no puede adivinar x unificando t , no tenemos otra manera de decir qué x debe ser.

En términos más generales, no podemos tratar la "inferencia de tipo" como un concepto monolítico del que tenemos todo o nada. Para empezar, tenemos que separar el aspecto de "generalización" (regla de "dejar" de Milner), que depende en gran medida de restringir qué tipos existen para asegurar que una máquina estúpida pueda adivinar uno, desde el aspecto de "especialización" (var de Milner "regla" que es tan efectiva 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 tipo interno seguirá siendo bastante fácil de propagar.

Los próximos pasos para Haskell

Estamos viendo que los niveles tipo y tipo crecen muy similares (y ya comparten una representación interna en GHC). También podríamos fusionarlos. Sería divertido tomar * :: * 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. Debemos verificar Si debemos tener distintos niveles de tipo, tipo, etc., podemos al menos asegurarnos de que todo en el nivel de tipo y superior siempre se puede promover. Sería genial simplemente reutilizar el polimorfismo que ya tenemos para los tipos, en lugar de reinventar el polimorfismo en el nivel amable.

Deberíamos simplificar y generalizar el sistema actual de restricciones al permitir ecuaciones heterogéneas a ~ b donde las clases de b no son sintácticamente idénticas (pero pueden ser probadas 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. Podremos expresar restricciones sobre las expresiones en las GADT, y así relajar las restricciones sobre lo que se puede promover.

Deberíamos eliminar la necesidad de la construcción singleton introduciendo 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 s que viva en la intersección del tipo y los lenguajes de 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án en el 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 Nat por Natty . El dominio de pi puede ser de cualquier tipo promocionable, de modo que si se pueden promover las GADT, podemos escribir secuencias cuantificadoras dependientes (o "telescopios", como de Briuijn los llamó)

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. El buy-in parcial actual hace que los beneficios de los tipos dependientes de Haskell sean más caros de lo que deben 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 neblina de ignorancia sobre el tema. Algo de eso se debe al hecho de que todos todavía tenemos mucho que aprender. Pero se sabe que los defensores de los enfoques menos radicales avivan el miedo a los tipos dependientes sin asegurarse siempre de que los hechos concuerden por completo con ellos. No nombraré nombres. Estas "pruebas de tipo indecidibles", "Turing incompleto", "sin distinción de fase", "sin borrado de tipo", "pruebas en todas partes", etc., los mitos persisten, aunque sean basura.

Ciertamente, no es el caso que los programas dependientes deben siempre ser correctos. Uno puede mejorar la higiene básica de los programas, imponiendo invariantes adicionales en tipos sin 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 adicional de prueba. No es verdad que los programas de tipos dependientes estén inevitablemente llenos de pruebas, de hecho, generalmente tomo la presencia de pruebas en mi código como la señal para cuestionar mis definiciones .

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

¿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 no ideal) de la programación con efectos. Haskell tiene un compilador de fuerza industrial. Los idiomas dependientes 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, a través de metaprogramación y genéricos de tipo de datos. Pero solo tiene que observar lo que la gente está haciendo como resultado de los pasos de Haskell hacia los tipos dependientes para ver que hay muchos beneficios que se pueden obtener empujando la presente generación de idiomas hacia adelante también.

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 va a la deriva en esa dirección general, pero todavía no está allí.

Básicamente, hay dos cosas que me gustaría saber. El primero es, simplemente, ¿qué significa "ser un lenguaje dependiente de tipeo"? (Afortunadamente sin ser demasiado técnico al respecto).

La segunda pregunta es ... ¿cuál es el inconveniente? Quiero decir, la gente sabe que nos dirigimos hacia allí, por lo que debe haber alguna ventaja. Y, sin embargo, todavía no hemos llegado, por lo que debe haber algunas personas que dejen de hacerlo todo el camino. Me da la impresión de que el problema es un aumento pronunciado de la complejidad. Pero, sin entender realmente qué es la tipificación dependiente, no estoy seguro.

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

John es otro error común sobre los tipos dependientes: que no funcionan cuando los datos solo están disponibles en tiempo de ejecución. A continuación, le indicamos cómo puede 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 cerdo. Claramente fallo en SO.

Pigworker ofrece una excelente discusión sobre por qué debemos dirigirnos hacia tipos dependientes: (a) son increíbles; (b) en realidad simplificarían mucho de lo que Haskell ya hace.

En cuanto al "¿por qué no?" pregunta, hay un par de puntos, creo. El primer punto es que si bien la noción básica detrás de los tipos dependientes es fácil (permite 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 todavía está viva y bien; pero discutir la diferencia entre ellos se vuelve mucho más matizado que en su Hindley - Milner o Sistema 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 carecemos de un buen vocabulario para capturar y explicar qué está pasando. A medida que más y más personas aprendan acerca de los tipos dependientes, desarrollaremos un mejor vocabulario y, por lo tanto, las cosas serán más fáciles de comprender, incluso si los problemas subyacentes aún son difíciles.

El segundo punto tiene que ver con el hecho de que Haskell está creciendo hacia tipos dependientes. Debido a que estamos logrando un progreso gradual hacia ese objetivo, pero sin llegar a hacerlo, nos encontramos con un lenguaje que tiene parches incrementales además de parches incrementales. El mismo tipo de cosas 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 filtraciones de abstracción y poder paralizado. Resulta que mezclar subtipaje y polimorfismo es intrínsecamente difícil; pero esa no es la razón por la cual los genéricos de Java funcionan de la manera en que lo hacen. Funcionan de la manera que lo hacen debido a la restricción de ser una mejora incremental de las versiones anteriores de Java. Ídem, más atrás en el día en que se inventó OOP y las personas comenzaron a escribir C "objetiva" (que no debe confundirse con el Objetivo C), etc. Recuerde, C ++ comenzó bajo el pretexto de ser un superconjunto estricto de C. Agregando nuevo los paradigmas siempre requieren la definición del lenguaje de nuevo, o bien terminar con un lío complicado. Mi punto en todo esto es que, agregar verdaderos tipos dependientes a Haskell va a requerir una cierta cantidad de eviscerar y reestructurar el lenguaje --- si lo vamos a hacer bien. Pero es realmente difícil comprometerse con ese tipo de revisión, mientras que el progreso incremental que hemos estado haciendo parece más barato en el corto plazo. Realmente, no hay tantas personas que piratean GHC, pero hay una gran 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.

La tipificación dependiente es solo la unificación de los niveles de valor y 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 es posible, estrictamente hablando, en Haskell) , aunque DataKinds acerca mucho).

Editar: Aparentemente, de aquí en adelante, me equivoqué (vea el comentario de @ pigworker). Conservaré el resto de esto como un registro de los mitos que me han alimentado. :PAG

El problema de pasar a mecanografía dependiente completa, por lo que he escuchado, es que rompería la restricción de fase entre el tipo y los niveles de valor que permiten que Haskell se compile con códigos de máquina eficientes con tipos borrados. Con nuestro nivel actual de tecnología, un idioma de tipo dependiente debe pasar por un intérprete en algún momento (ya sea inmediatamente o después de compilarse en un bytecode de tipo dependiente o similar).

Esto no es necesariamente una restricción fundamental, pero personalmente no estoy al tanto de ninguna investigación actual que parezca prometedora en este aspecto, pero que aún no lo haya hecho en GHC. Si alguien más sabe más, me gustaría que me corrijan.