Fundeps y GADTs:Cuando es la comprobación del tipo de decidable?

Question

Estaba leyendo un artículo de investigación sobre Haskell y cómo HList se implementa y se preguntaba cuando las técnicas descritas son y no son decidable para el tipo de corrector.También, porque se pueden hacer cosas similares con GADTs, me preguntaba si GADT tipo de comprobación es siempre decidable.

Yo prefiero las citas, si los tiene, así que puedo leer/entender las explicaciones.

Gracias!

Answer 1

Creo GADT tipo de comprobación es siempre decidable;es la inferencia que es indecidible, ya que se requiere de orden superior de la unificación.Pero un GADT tipo de corrector es una forma restringida de la prueba de damas que ver en por ejemplo.Coq, donde los constructores construir la prueba de plazo.Por ejemplo, el clásico ejemplo de incrustación de cálculo lambda en GADTs tiene un constructor para cada reducción de la regla, así que , si quieres encontrar la forma normal de un término, hay que decir que los constructores para llegar a ella.La detención problema ha sido trasladado en las manos del usuario :-)

Answer 2

Es probable que ya hayas visto esto, pero hay una colección de artículos sobre este tema de investigación de Microsoft: Comprobación del tipo de papeles.El primero describe la decidable algoritmo utiliza realmente en el Glasgow Haskell compiler.