Técnicas para rastrear restricciones

322

Este es el escenario: he escrito un código con una firma de tipo y las quejas de GHC no pudieron deducir x ~ y para algunos xy y. Por lo general, puede arrojar un hueso a GHC y simplemente agregar el isomorfismo a las restricciones de la función, pero esta es una mala idea por varias razones:

  1. No enfatiza la comprensión del código.
  2. Puede terminar con 5 restricciones donde una hubiera sido suficiente (por ejemplo, si las 5 están implicadas por una restricción específica más)
  3. Puede terminar con restricciones falsas si ha hecho algo mal o si GHC no ayuda

Acabo de pasar varias horas luchando contra el caso 3. Estoy jugando con syntactic-2.0, y estaba tratando de definir una versión independiente del dominio share, similar a la versión definida en NanoFeldspar.hs.

Tuve esto:

{-# LANGUAGE GADTs, FlexibleContexts, TypeOperators #-}
import Data.Syntactic

-- Based on NanoFeldspar.hs
data Let a where
    Let :: Let (a :-> (a -> b) :-> Full b)

share :: (Let :<: sup,
          Domain a ~ sup,
          Domain b ~ sup,
          SyntacticN (a -> (a -> b) -> b) fi) 
      => a -> (a -> b) -> a
share = sugarSym Let

y GHC could not deduce (Internal a) ~ (Internal b), que ciertamente no es lo que estaba buscando. Entonces, o bien había escrito un código que no tenía la intención (que requería la restricción), o GHC quería esa restricción debido a algunas otras restricciones que había escrito.

Resulta que necesitaba agregar (Syntactic a, Syntactic b, Syntactic (a->b))a la lista de restricciones, ninguna de las cuales implica (Internal a) ~ (Internal b). Básicamente me topé con las restricciones correctas; Todavía no tengo una forma sistemática de encontrarlos.

Mis preguntas son:

  1. ¿Por qué GHC propuso esa restricción? En ninguna parte sintáctica hay una restricción Internal a ~ Internal b, entonces, ¿de dónde sacó GHC eso?
  2. En general, ¿qué técnicas se pueden utilizar para rastrear el origen de una restricción que GHC cree que necesita? Incluso para las limitaciones que puedo descubrir por mí mismo, mi enfoque es esencialmente bruto forzando el camino ofensivo al escribir físicamente las restricciones recursivas. Este enfoque está básicamente bajando por un agujero infinito de restricciones y es el método menos eficiente que pueda imaginar.
haskell constraints ghc crockeea
fuente
21
Ha habido algunas discusiones sobre un depurador de nivel de tipo, pero el consenso general parece estar mostrando que la lógica interna del typechecker no va a ayudar: / En este momento, el solucionador de restricciones de Haskell es un lenguaje lógico opaco horrible :)
Daniel Gratzer
12
@jozefg ¿Tiene un enlace para esa discusión?
crockeea
36
A menudo es útil eliminar completamente la firma de tipo y dejar que ghci le diga cuál cree que debería ser la firma.
Tobias Brandt
12
De alguna manera ay bestán vinculados, mira la firma de tipo fuera de tu contexto a -> (a -> b) -> a, no a -> (a -> b) -> b. Tal vez eso es todo? Con los solucionadores de restricciones, pueden influir en la igualdad transitiva en cualquier lugar , pero los errores generalmente muestran una ubicación "cercana" al lugar donde se indujo la restricción. Sin embargo, eso sería genial @jozefg: ¿quizás anotar restricciones con etiquetas o algo así, para mostrar de dónde vinieron? : s
Athan Clark

Respuestas:

6

En primer lugar, su función tiene el tipo incorrecto; Estoy bastante seguro de que debería ser (sin el contexto) a -> (a -> b) -> b. GHC 7.10 es algo más útil para señalar eso, porque con su código original, se queja de una falta de restricción Internal (a -> b) ~ (Internal a -> Internal a). Después de corregir shareel tipo, GHC 7.10 sigue siendo útil para guiarnos:

  1. Could not deduce (Internal (a -> b) ~ (Internal a -> Internal b))

  2. Después de agregar lo anterior, obtenemos Could not deduce (sup ~ Domain (a -> b))

  3. Después de añadir que, obtenemos Could not deduce (Syntactic a), Could not deduce (Syntactic b)yCould not deduce (Syntactic (a -> b))

  4. Después de agregar estos tres, finalmente escribe; así que terminamos con

    share :: (Let :<: sup,
          Domain a ~ sup,
          Domain b ~ sup,
          Domain (a -> b) ~ sup,
          Internal (a -> b) ~ (Internal a -> Internal b),
          Syntactic a, Syntactic b, Syntactic (a -> b),
          SyntacticN (a -> (a -> b) -> b) fi)
      => a -> (a -> b) -> b
share = sugarSym Let

Entonces diría que GHC no ha sido inútil para guiarnos.

En cuanto a su pregunta sobre el seguimiento de dónde GHC obtiene sus requisitos de restricción, puede probar los indicadores de depuración de GHC , en particular -ddump-tc-trace, y luego leer el registro resultante para ver dónde Internal (a -> b) ~ ty (Internal a -> Internal a) ~ tse agregan al Wantedconjunto, pero eso será una lectura bastante larga .

Cactus
fuente
0

¿Intentaste esto en GHC 8.8+?

share :: (Let :<: sup,
          Domain a ~ sup,
          Domain b ~ sup,
          SyntacticN (a -> (a -> b) -> b) fi,
          _) 
      => a -> (a -> b) -> a
share = sugarSym Let

La clave es usar el tipo de agujero entre las restricciones: _ => your difficult type

Michal Gajda
fuente