haskell - Intérprete duplicador con HOAS

ghc dsl

Question

En la sección 2.3 de these notas realmente geniales sobre intérpretes finales sin etiquetas para DSL, Oleg Kiselyov muestra cómo resolver el problema de analizar una expresión DSL serializada una vez e interpretarla varias veces.

Brevemente, muestra que el "polimorfismo falso de primera clase" con los tipos

newtype Wrapped = Wrapped (∀ repr. ExpSYM repr ⇒ repr)
fromTree :: String → Either ErrMsg Wrapped

no es satisfactorio porque no es extensible: tenemos que tener un Wrapper / fromTree diferente para cada conjunto de restricciones en la repr . Por eso me inclino a usar su solución de un intérprete duplicador . Esta pregunta es sobre cómo usar ese intérprete con HOAS.

Específicamente, considere el siguiente idioma para los enlaces de idioma de destino:

class Lam repr where
  lam :: (repr a -> repr b) -> repr (a -> b)
  app :: repr (a -> b) -> repr a -> repr b

Tengo problemas para dar una instancia de sonido de la clase Lam para mi intérprete duplicador. Esto es lo que tengo:

data Dup repr1 repr2 a = Dup {unDupA :: repr1 a, unDupB :: repr2 a}

instance (Lam repr1, Lam repr2) => Lam (Dup repr1 repr2) where
  lam f = Dup (lam $ unDupA . f . flip Dup undefined) (lam $ unDupB . f . Dup undefined)
  app (Dup fa fb) (Dup a b) = Dup (app fa a) (app fb b)

¿Hay alguna manera de dar una instancia recursiva de Lambda para algo como mi tipo Dup que no implique undefined ?

También he intentado usar la versión más poderosa de lam de este documento , que permite intérpretes monádicos con HOAS, aunque no vi cómo me ayudaría con mi caso para Dup . ¡Una solución que use cualquiera de las versiones de lam con HOAS sería genial!

_{*: Oleg mostró cómo definir una instancia de sonido utilizando los índices de Bruijn, pero estoy realmente interesado en una solución para HOAS.}

    class Lam repr where
      lam :: repr (a,g) b -> repr g (a -> b)
      app :: repr g (a->b) -> repr g a -> repr g b

    data Dup repr1 repr2 g a = Dup{d1:: repr1 g a, d2:: repr2 g a}

    instance (Lam repr1, Lam repr2) => Lam (Dup repr1 repr2) where
      lam (Dup e1 e2) = Dup (lam e1) (lam e2)
      app (Dup f1 f2) (Dup x1 x2) = Dup (app f1 x1) (app f2 x2)

Answer 1

Después de trabajar con Template Haskell, tuve una idea que se aplica aquí. Otra opción sería hacerlo como lo hace TH:

class Fail.MonadFail m => Quasi m where
    -- All the things here, like inspecting types, generating names, etc.
    ...

-- Many instances, including
instance Quasi IO where ... -- So you can debug your TH
instance TH.Quasi GHCiQ where ... -- see https://github.com/ghc/ghc/blob/master/libraries/ghci/GHCi/TH.hs#L167
instance TH.Quasi TcM where ... -- see https://github.com/ghc/ghc/blob/master/compiler/typecheck/TcSplice.hs#L835

data Q a = { unQ :: forall m. Quasi m => m a }
instance Quasi Q where ...

Puedes encontrar la definición de la mónada Q here .

Un usuario final trabaja dentro de la mónada Q , y puede ser interpretado por cualquier intérprete del compilador interno, o la mónada IO para la depuración, etc. Cualquier duplicación la maneja el forall . Podrías, igualmente, hacer algo como

data L a = { unL :: forall repr. Lam repr => repr a }
instance Lam L where ...

myEndUserThing :: L ((a -> b) -> a -> b)
myEndUserThing = lam $ /f -> lam $ /x -> app f x

L a es fácilmente convertible a cualquier otra repr que desee, y si necesita más funcionalidad, simplemente agréguela a la clase Lam o cree una clase derivada con la funcionalidad adicional.

Answer 2

Esto es imposible.

Para mostrar un ejemplo, primero haré una instancia muy simple de Lam :

newtype Id a = Id a

instance Lam Id where
    lam (Id f) = Id (/x -> let Id r = f x in r)
    app (Id f) (Id x) = Id (f x)

Ahora haré una función que opera en Dup s:

f :: Dup Id Id Int -> Dup Id Id Int
f (Dup (Id x) (Id y)) = Dup (Id x*y) (Id y)

Yo, desde una instancia de Lam , podría hacer la lam f :: Dup Id Id (Int -> Int) . Esto podría parecer

Dup (Id (/x -> x*y)) (Id (/y -> y))

que no se pudo hacer, porque y no está disponible desde x -lambda. (El uso de undefined s reemplaza la y con undefined aquí, generando errores en el tiempo de ejecución siempre que no funcione bien). Esto no es una ocurrencia rara: ocurre cada vez que usa una de las variables en el resultado de la otra.

No estoy seguro de lo que está preguntando con la Monad más generalizada, pero esto también sucede con otras Monad : por ejemplo, con Maybe , no podría convertir lo siguiente en Maybe (Int -> Int) porque depende del valor dado:

f :: Maybe Int -> Maybe Int
f m = m >>= /x -> if x > 5 then Just x else Nothing

(Podría usarlo desde fromJust it y esperar que nadie lo haga, pero es lo mismo que la solución undefined ).

Sin embargo, el s undefined arroja un error si la función necesita mirar las otras variables. Si está absolutamente seguro de que nunca se ejecutará en algo como esto (por ejemplo, si restringe el desenvolvimiento / creación a un módulo de ocultación ampliamente probado), entonces la forma undefined funcionaría.

Solo una recomendación más: use un mensaje de error más detallado en lugar de undefined , en caso de que algo salga mal.