haskell - programming - ¿Cuál es la forma correcta de verificar la abstracción lambda dependiente usando ''enlazado''?

que es expresiones lambda

Question

Estoy implementando un lenguaje simple de tipo dependiente, similar al descrito por Lennart Augustsson , al mismo tiempo que utilizo el bound para administrar los enlaces.

Al verificar con frecuencia un término lambda dependiente, como λt:* . λx:t . x λt:* . λx:t . x λt:* . λx:t . x , necesito:

1. "Ingrese" el archivador lambda externo, mediante la instanciación de t a algo
2. Typecheck λx:t . x λx:t . x , dando ∀x:t . t ∀x:t . t
3. Extracto pi la t , dando ∀t:* . ∀x:t . t ∀t:* . ∀x:t . t

Si lambda no era dependiente, podría salirme con una instanciación de t con su tipo en el paso 1, ya que el tipo es todo lo que necesito saber sobre la variable mientras verifico el paso 2. Pero en el paso 3 me falta la información para decidir cuál Variables sobre las que abstraerse.

Podría introducir un nuevo nombre de fuente e instanciar t con un Bound.Name.Name contenga tanto el tipo como un nombre único. Pero pensé que con un bound no debería tener que generar nombres nuevos.

¿Hay una solución alternativa que me falta?

Answer 1

Necesitamos algún tipo de contexto para realizar un seguimiento de los argumentos lambda. Sin embargo, no necesariamente tenemos que crear una instancia de ellos, ya que bound nos da los índices de Bruijn, y podemos usar esos índices para indexar en el contexto.

Sin embargo, el hecho de usar los índices es un poco complicado, debido a la maquinaria de nivel de tipo que refleja el tamaño del alcance actual (o, en otras palabras, la profundidad actual en la expresión) a través del anidamiento de Var -s. Requiere el uso de recursión polimórfica o GADTs. También nos impide almacenar el contexto en una mónada estatal (debido a que el tamaño y, por lo tanto, el tipo de contexto cambia a medida que recesamos). Aunque me pregunto si podríamos usar una mónada de estado indexada; sería un experimento divertido Pero yo divago.

La solución más simple es representar el contexto como una función:

type TC  a = Either String a -- our checker monad
type Cxt a = a -> TC (Type a) -- the context

La entrada es esencialmente un índice de Bruijn, y buscamos un tipo aplicando la función al índice. Podemos definir el contexto vacío de la siguiente manera:

emptyCxt :: Cxt a
emptyCxt = const $ Left "variable not in scope"

Y podemos ampliar el contexto:

consCxt :: Type a -> Cxt a -> Cxt (Var () a)
consCxt ty cxt (B ()) = pure (F <$> ty)
consCxt ty cxt (F a)  = (F <$>) <$> cxt a

El tamaño del contexto está codificado en el anidamiento de Var . El aumento en el tamaño es evidente aquí en el tipo de retorno.

Ahora podemos escribir el comprobador de tipos. El punto principal aquí es que usamos fromScope y toScope para toScope debajo de las carpetas, y llevamos un Cxt apropiadamente extendido (cuyo tipo se alinea perfectamente).

data Term a
  = Var a
  | Star -- or alternatively, "Type", or "*"
  | Lam (Type a) (Scope () Term a)
  | Pi  (Type a) (Scope () Term a)
  | App (Type a) (Term a)  
  deriving (Show, Eq, Functor)

-- boilerplate omitted (Monad, Applicative, Eq1, Show1 instances)

-- reduce to normal form
rnf :: Term a -> Term a
rnf = ...

-- Note: IIRC "Simply easy" and Augustsson''s post reduces to whnf
-- when type checking. I use here plain normal form, because it 
-- simplifies the presentation a bit and it also works fine.

-- We rely on Bound''s alpha equality here, and also on the fact
-- that we keep types in normal form, so there''s no need for
-- additional reduction. 
check :: Eq a => Cxt a -> Type a -> Term a -> TC ()
check cxt want t = do
  have <- infer cxt t
  when (want /= have) $ Left "type mismatch"

infer :: Eq a => Cxt a -> Term a -> TC (Type a)
infer cxt = /case
  Var a -> cxt a
  Star  -> pure Star -- "Type : Type" system for simplicity
  Lam ty t -> do
    check cxt Star ty
    let ty'' = rnf ty
    Pi ty'' . toScope <$> infer (consCxt ty'' cxt) (fromScope t)
  Pi ty t -> do
    check cxt Star ty
    check (consCxt (rnf ty) cxt) Star (fromScope t)
    pure Star
  App f x -> 
    infer cxt f >>= /case
      Pi ty t -> do
        check cxt ty x
        pure $ rnf (instantiate1 x t)
      _ -> Left "can''t apply non-function"

Aquí está el código de trabajo que contiene las definiciones anteriores. Espero no haberlo ensuciado demasiado.