haskell - usa - var c#

Importancia de las variables de tipo de ámbito que representan variables de tipo y no tipos

Question

En la documentation GHC para la extensión ScopedTypeVariables, la descripción general establece lo siguiente como un principio de diseño:

Una variable de tipo de ámbito representa una variable de tipo y no un tipo . (Esto es un cambio del diseño anterior de GHC).

Conozco el propósito general de la extensión de variables de tipo de ámbito, pero no conozco las implicaciones de la distinción que se hace aquí entre representar variables de tipo y representar tipos. ¿Cuál es el significado de la diferencia, desde la perspectiva de los usuarios del lenguaje?

El comentario anterior alude a dos diseños que abordaron esta decisión de manera diferente e hicieron concesiones diferentes. ¿Cuál fue el diseño alternativo y cómo se compara con el implementado actualmente?

Answer 1

Estoy agregando esta respuesta (a mi propia pregunta) para ampliar la referencia de duplode en los comentarios. ScopedTypeVariables se está cambiando actualmente para permitir que las variables de tipo de ámbito representen tipos en lugar de solo variables de tipo. La discusión para esto cambia la motivación para los diseños nuevos y antiguos. Sin embargo, esto no aborda el diseño anterior mencionado en la pregunta y en la respuesta de KA Buhr.

En el estado actual, antes del próximo cambio, la definición

prefix :: a -> [[a]] -> [[a]]
prefix (x :: b) yss = map xcons yss
    where xcons ys = x : ys

es válido (con ScopedTypeVariables), en el que b es una variable de tipo recién introducida que representa lo mismo que a . Por otro lado, si el prefix está especializado para

prefix :: Int -> [[Int]] -> [[Int]]
prefix (x :: b) yss = map xcons yss
    where xcons ys = x : ys

entonces se rechaza el programa: b puede representar a Int porque Int no es una variable de tipo. Simon Peyton Jones comentó por qué fue diseñado para que b no pudiera representar a Int :

En ese momento me preocupaba que fuera confuso tener una variable de tipo que fuera solo un alias para Int; que no es una variable de tipo en absoluto. Pero en estos días de GADTs y tipos de igualdad, todos estamos acostumbrados a eso. Hoy haríamos una elección diferente.

En el consenso actual de los mantenedores de GHC, la limitación en contra de b para Int se considera antinatural, especialmente a la luz de la posibilidad de que haya igualdad de tipo (a ~ Int) => ... La presencia de tales restricciones difumina las líneas de lo que realmente significa "estar vinculado a una variable de tipo". En caso de que los ejemplos

f1 :: (a ~ Int) => Maybe a -> Int
f1 (Just (x :: b)) = ...

f2 :: (a ~ Int) => Maybe Int -> Int
f2 (Just (x :: a)) = ...

¿ser permitido? Bajo la nueva propuesta, los cuatro ejemplos anteriores están permitidos.

Desde mi punto de vista, la tensión en última instancia proviene de la coexistencia de dos tipos de sistemas de anotación muy diferentes. Uno de ellos tiene el efecto de evitar que le des nombres diferentes al mismo tipo (por ejemplo, no puede escribir (/x -> x) :: a -> b o (/x -> x) :: Int -> b y espere que b se unifique con a o Int ). La otra habilita y lo alienta a que le dé nombres nuevos a las cosas (firmas de tipo de patrón como foo (x :: b) = ... ), una función que existe para permitirle nombrar tipos que de otro modo no se podrían nombrar. La pregunta restante es si las firmas de tipo de patrón deberían permitirle tipos de alias que ya se pueden nombrar. La respuesta en su núcleo depende de cuál de los dos precedentes encuentre más convincente.

Referencias:

1. Joachim Breitner "nomeata" (abril-agosto de 2018). Boleto de solicitud de funciones "ScopedTypeVariables podría permitir más programas", https://ghc.haskell.org/trac/ghc/ticket/15050
2. nomeata (abril-agosto 2018). Solicitud de extracción "Permitir que ScopedTypeVariables haga referencia a tipos", https://github.com/ghc-proposals/ghc-proposals/pull/128
3. Richard A. Eisenberg, Joachim Breitner y Simon Peyton Jones (junio de 2018). "Escriba variables en patrones", https://www.microsoft.com/en-us/research/uploads/prod/2018/06/tyvars-in-pats-haskell18-preprint.pdf , especialmente las secciones 3.5 y 4.3
4. nomeata (agosto 2018). Propuesta de GHC "Permita que ScopedTypeVariables haga referencia a tipos", https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0029-scoped-type-variables-types.rst

Answer 2

tl; dr: La documentación dice lo que dice porque la implementación anterior de las variables tipificadas con alcance en GHC fue diferente, y la nueva documentación (sobre) enfatiza el contraste entre el comportamiento antiguo y el comportamiento nuevo. De hecho, las variables de tipo de alcance que usa con la extensión ScopedTypeVariables en su lugar son simplemente variables de tipo antiguo (rígido), y son las mismas variables de tipo que ha estado usando en las firmas de tipo Haskell normales sin alcance (incluso si no lo hizo) Me doy cuenta de que eran "rígidos"). Es cierto que las variables de tipo de ámbito no se limitan a "representar tipos", pero las variables de tipo sin ámbito no se limitan a "tipos".

Respuesta más larga:

Primero, dejando de lado el tema de las variables de tipo de ámbito, considere lo siguiente:

pluralize :: [a] -> [a]
pluralize x = x ++ "s"

Si a , como variable de tipo, simplemente "representara un tipo", esto estaría bien. GHC determinaría que a simulación para el tipo Char y la firma resultante [Char] -> [Char] se determinaría como el tipo correcto de pluralize , por lo que no habría ningún problema. De hecho, si estuviéramos inferiendo el tipo de:

pluralize x = x ++ "s"

en un sistema simple tipo Hindley-Milner (HM), esto es probablemente exactamente lo que sucedería. Como paso intermedio al escribir la aplicación (++) , el verificador de tipos asignaría x el tipo [a] para una variable de tipo HM "nueva", y asignaría pluralize el tipo [a] -> [a] antes unificar [a] con el tipo de "s" :: [Char] para unificar a y Char .

En su lugar, esto es rechazado por el verificador de tipo GHC porque a firma en este tipo no es una variable de tipo de estilo HM y, por lo tanto, no significa simplemente un tipo. En cambio, es una variable de tipo Haskell rígida (es decir, especificada por el usuario), y el verificador de tipos no permite que dicha variable se unifique con otra cosa que no sea ella misma mientras define la pluralize .

Del mismo modo, se rechaza lo siguiente:

pairlist :: a -> b -> [a]
pairlist x y = [x,y]

aunque, si a y b solo representaran los tipos, esto estaría bien (ya que funciona para cualquier a y b de tipo * siempre que a b sean del mismo tipo). En su lugar, el comprobador de tipos lo rechaza porque dos variables rígidas de tipo Haskell b no se pueden unificar.

Ahora, puede intentar argumentar que el problema no es que las variables de tipo sean "rígidas" y no se puedan unificar con tipos concretos (como Char ) o entre sí, sino que existe una cuantificación implícita en las firmas de tipo Haskell , por lo que la firma para pluralize es en realidad:

pluralize :: forall a . [a] -> [a]

y así, cuando a está determinado a "representar a Char ", es la contradicción con esto para toda forall a cuantificación que dispara el error. El problema con este argumento es que ambas explicaciones son en realidad más o menos equivalentes. Debido a que las variables de tipo Haskell son rígidas (es decir, porque las firmas de tipos en Haskell están implícitamente universalmente cuantificadas), los tipos no pueden unificarse (es decir, que la unificación contradice la cuantificación). Sin embargo, resulta que la explicación de "variables de tipo rígido" está más cerca de lo que realmente está sucediendo en el verificador de tipo GHC que la explicación de "cuantificación implícita". Es por eso que los mensajes de error generados por las definiciones anteriores se refieren a la incapacidad de hacer coincidir variables de tipo rígido en lugar de a contradicciones con cuantificaciones de variables de tipo universal.

Ahora, volvamos a la cuestión de las variables de tipo de ámbito. En los viejos tiempos, la -fscoped-type-variables de GHC se implementaba de manera muy diferente. En particular, para las firmas de tipo de patrón, se le permitió escribir cosas como las siguientes (tomadas de la documentación de GHC 6.0 ):

f :: [Int] -> Int -> Int
f (xs::[a]) (y::a) = (head xs + y) :: a

y la documentación continuó diciendo:

Las firmas de tipo de patrón en el lado izquierdo de f expresan el hecho de que xs debe ser una lista de cosas de algún tipo a ; y que y debe tener este mismo tipo. La firma de tipo en la expresión (head xs) [sic] especifica que esta expresión debe tener el mismo tipo a . No hay ningún requisito de que el tipo nombrado por " a " sea de hecho una variable de tipo. De hecho, en este caso, el tipo nombrado por " a " es Int . (Esta es una ligera liberalización de las reglas originales bastante complejas, que especifican que una variable de tipo enlazado a un patrón debe cuantificarse universalmente).

Continuó para dar algunos ejemplos adicionales del uso de variables de tipo de ámbito, tales como:

g (x::a) (y::b) = [x,y]       -- a unifies with b

k (x::a) True    = ...        -- a unifies with Int
k (x::Int) False = ...

En 2006, Simon Peyton-Jones realizó un gran compromiso ( ac10f840 ) para agregar impredicatividad al sistema de tipos que también terminó cambiando sustancialmente la implementación de variables de tipo de ámbito léxico. El texto de confirmación contiene una explicación detallada del cambio, incluidos los requisitos para el nuevo diseño.

Una elección de diseño clave fue que las variables de tipo de ámbito léxico ahora se denominan variables de tipo Haskell rígidas (es decir, polimórficas especificadas por el usuario), en lugar de ser más como las variables de estilo HM que simplemente representaban un tipo y estaban sujetas a la unificación.

Eso hizo que los ejemplos anteriores ( f , g , k ) fueran ilegales, porque las variables de tipo de ámbito en las coincidencias de patrones ahora se comportaban más como variables de tipo rígido regulares.

Soooo ... el diseño antiguo era probablemente un truco extraño que hacía que las variables de tipo de ámbito se parecieran más a las variables de tipo HM y, por lo tanto, muy diferentes de las variables de tipo Haskell "normales", y el nuevo sistema las alineaba más con el comportamiento de las variables de tipo sin ámbito.

Sin embargo, para complicar aún más las cosas, el enlace de @ duplode en los comentarios hace referencia a una propuesta para "deshacer" parcialmente esta "restricción" en el contexto de las firmas en las coincidencias de patrones. Creo que sería justo decir que el diseño anterior, que trataba las variables de tipo de ámbito más como un caso especial, era inferior al nuevo diseño que unificaba mejor el tratamiento de las variables de tipo sin ámbito y no desea volver atrás A la antigua implementación. Sin embargo, la nueva implementación, más simple, tuvo el efecto secundario de ser innecesariamente restrictiva para las firmas de patrones, lo que tal vez debería tratarse como un caso especial donde se permiten variables de tipo no rígido.