Diferencia entre Haskell e Idris: Reflexión de Runtime/Compiletime en los universos de tipo

dependent-type type-level-computation

Question

Así que en Idris es perfectamente válido escribir lo siguiente.

item : (b : Bool) -> if b then Nat else List Nat
item True = 42
item False = [1,2,3] // cf. https://www.youtube.com/watch?v=AWeT_G04a0A

Sin la firma de tipo, esto parece un lenguaje tipificado dinámicamente. Pero, de hecho, Idris es de tipo dependiente. El tipo concreto del item b solo se puede determinar durante el tiempo de ejecución.

Esto es, por supuesto, un programador de Haskell que habla: el tipo de item b en el sentido de Idris se da durante el tiempo de compilación, es if b then Nat ...

Ahora mi pregunta: ¿Tengo razón al concluir que en Haskell, el límite entre el tiempo de ejecución y el tiempo de compilación se ejecuta exactamente entre el mundo de los valores (Falso, "foo", 3) y el mundo de los tipos (Bool, String, Integer) mientras que En Idris, ¿el límite entre el tiempo de ejecución y el tiempo de compilación pasa por los universos?

Además, ¿tengo razón al suponer que incluso con los tipos dependientes en Haskell (usando DataKinds y TypeFamilies, consulte este artículo ) el ejemplo anterior es imposible en Haskell, porque Haskell, a diferencia de Idris, no permite que los valores se filtren al nivel de tipo?

Answer 1

Ahora mi pregunta: ¿Tengo razón al concluir que en Haskell, el límite entre el tiempo de ejecución y el tiempo de compilación se ejecuta exactamente entre el mundo de los valores (Falso, "foo", 3) y el mundo de los tipos (Bool, String, Integer) mientras que En Idris, ¿el límite entre el tiempo de ejecución y el tiempo de compilación pasa por los universos?

Idris compila a Epic (ACTUALIZACIÓN: no, ya no compila a Epis como dice Spearman en el comentario a continuación):

No hay verificación semántica, excepto para ver si los nombres están dentro del alcance --- se supone que el lenguaje de nivel superior habrá realizado una verificación de tipo, y en cualquier caso, Epic no debe hacer suposiciones sobre el sistema de tipo de nivel superior o cualquier transformación que haya aplicado. Se requieren anotaciones de tipo, pero solo dan sugerencias al compilador (podría cambiar esto).

Así que los tipos no importan denotativamente, es decir, el significado de un término no depende de su tipo. Además, algunas cosas de nivel de valor se pueden borrar, por ejemplo, en Vect n A (donde Vect es el tipo de listas con longitud estáticamente conocida) n (la longitud) se pueden borrar, because

Hay métodos descritos por Brady, McBride y McKinna en BMM04 para eliminar los índices de las estructuras de datos, aprovechando el hecho de que las funciones que operan en ellos ya tienen una copia del índice apropiado o el índice se puede reconstruir rápidamente si es necesario.

La cosa aquí es que pi en Idris actúa para los tipos casi de la misma manera que para todos en Haskell: ambos son paramétricos (aunque, estas parametricidades son diferentes) en este caso. Un compilador puede usar tipos para optimizar el código, pero en ambos idiomas el flujo de control no depende de los tipos, es decir, no se puede decir if A == Int then ... else ... (sin embargo, si A está en forma canónica , entonces usted sabe estáticamente si es Int o no y, por can tanto, can escribir A == Int , pero eso todavía no afecta el flujo de control, porque todas las decisiones se toman antes del tiempo de ejecución). El tipo concreto de item b simplemente no importa en el tiempo de ejecución.

Sin embargo, como dice el , no necesariamente es de tipo paramétrico. Además de no ser necesariamente no paramétrico en valores. Tipo de nivel - nivel de valor y paramétrico - no paramétrico son dicotomías completamente ortogonales. Vea this respuesta para más detalles.

Por lo tanto, Haskell e Idris son diferentes en la forma en que tratan las cosas de nivel de valor en el tiempo de ejecución / compilación del contenido (porque en Idris puede marcar un argumento con . Para que sea borrable), pero tratan los tipos de la misma manera.

Answer 2

Sí, tiene razón al observar que la distinción entre tipos y valores en Idris no se alinea con la distinción solo en tiempo de compilación y en tiempo de ejecución y en tiempo de compilación. Eso es bueno. Es útil tener valores que existen solo en tiempo de compilación, al igual que en las lógicas de programa, las "variables fantasma" se usan solo en las especificaciones. También es útil tener representaciones de tipo en tiempo de ejecución, lo que permite la programación genérica de tipos de datos.

En Haskell, DataKinds (y PolyKinds ) nos permiten escribir

type family Cond (b :: Bool)(t :: k)(e :: k) :: k where
Cond ''True t e = t
Cond ''False t e = e

y en un futuro no muy lejano, podremos escribir

item :: pi (b :: Bool) -> Cond b Int [Int]
item True = 42
item False = [1,2,3]

pero hasta que se implemente esa tecnología, tenemos que conformarnos con las falsificaciones únicas de los tipos de funciones dependientes, como esto:

data Booly :: Bool -> * where
Truey :: Booly ''True
Falsey :: Booly ''False
item :: forall b. Booly b -> Cond b Int [Int]
item Truey = 42
item Falsey = [1,2,3]

Puedes llegar bastante lejos con tales falsificaciones, pero todo sería mucho más fácil si tuviéramos la cosa real.

De manera crucial, el plan para Haskell es mantener y separar forall y pi , soportando el polimorfismo paramétrico y ad hoc, respectivamente. Las lambdas y las aplicaciones que acompañan a forall todavía pueden borrarse en la generación de código de tiempo de ejecución, como ahora, pero se conservan las de pi . También tendría sentido tener abstracciones de tipo runtime pi x :: * -> ... y lanzar el nido de complejidad de ratas que es Data.Typeable en el cubo de basura.