Использование привязки с типом аннотированного дерева

Я использую библиотеку Bound для представления лямбда-терминов:

data Exp a = Var a
           | Exp a :@: Exp a
           | Lam (Scope () Exp a)

Чтобы использовать abstract и instantiate с помощью Exp, У меня установлен экземпляр монады:

instance Monad Exp where
    return = Var
    Var a >>= f = f a
    (x :@: y) >>= f = f >>= x :@: f >>= y
    Lam e >>= f = Lam $ e >>>= f

(Где >>>= определяется в Bound.)

Теперь я хотел бы сделать аннотированную версию типа выше. Я думал, что просто сделаю

data Exp a = Var a
           | TypedExp a :@: TypedExp a
           | Lam (Scope () TypedExp a)

data TypedExp a = TypedExp Type (Exp a)

Проблема заключается в том, что тип abstract равен

abstract :: Monad f => (a -> Maybe b) -> f a -> Scope b f a

Это означает, что, если я не хочу просто отказаться от типов при замещении, я должен сделать TypedExp монаду. Я вижу интуицию для операций: return создает переменную с неограниченным типом, а bind выполняет подстановку с унификацией. Но для создания новых переменных и выполнения объединения мне нужно какое-то состояние.

Поработав некоторое время, я придумал довольно естественные определения для

return' :: a -> MyState (TypedExp a)
bind' :: TypedExp a -> (a -> MyState (TypedExp b)) -> MyState (TypedExp b)

но я не могу сделать шаг к фактическому экземпляру монады, который сделает то, что я хочу.

Могу ли я переплетать типы во что-то, что будет работать с Bound, поскольку оно написано? Должен ли я пойти для написания более общей версии abstract, что-то вроде...

data Typed f ty a = Typed ty (f ty a)

class TypeLike ty where
    data Unification ty :: * -> *
    fresh :: Unification ty ty
    unify :: ty -> ty -> Unification ty ty

class Annotatable f where
    typedReturn :: TypeLike ty => a -> Unification ty (Typed exp ty a)
    typedBind :: TypeLike ty => Typed f ty a -> (a -> Unification ty (Typed f ty b)) -> Unification ty (Typed f ty b)

abstract :: (Annotatable f, TypeLike ty) => (a -> Maybe b) -> Typed f ty a -> Unification (Scope b (Typed f ty) a)

... возможно?

Ответы

Ответ 1

( Отказ от ответственности. Я не уверен, что это теоретически "правильный" способ делать вещи, но, похоже, он работает.)

Этот вопрос основан на неправильном предположении, что унификация должна быть частью подстановки. Это не выгодно, когда дело доходит до использования Bound, и не обязательно для обеспечения правильной автоматической унификации.

Не полезно

Bound предоставляет несколько функций, для которых требуется экземпляр monad. Четыре ключевых из них:

abstract :: Monad f => (a -> Maybe b) -> f a -> Scope b f a
instantiate :: Monad f => (b -> f a) -> Scope b f a -> f a
fromScope :: Monad f => Scope b f a -> f (Var b a)
toScope :: Monad f => f (Var b a) -> Scope b f a

Ни один из них не предоставляет дополнительную информацию, которая может быть полезна как информация о типе. Они изменяют способ представления переменных и могут даже изменять представление дерева, но только способами, которые не допускают дальнейших предположений о типах. Это имеет смысл, поскольку Bound не предполагает наличие типов.

Благодаря этому свойству переписывание этих четырех функций для использования таких классов, как TypeLike и Annotatable, приведет только к выполнению унификаций, которые в любом случае тривиальны, так как одно из значений всегда будет иметь новый тип. Поэтому нет необходимости обобщать библиотеку.

Не требуется

Проблема в вопросе возникает из-за неправильного определения конструктора Lam. Мы слишком много комментируем. Рассмотрим выражение \x. a:

Lam $ Scope $ (TypedExp t $ Var $ F (TypedExp t $ Var "a"))

Здесь тип t дублируется. Мы можем удалить это дублирование и решить наши проблемы относительно Lam, изменив способ аннотации типов:

data Typed a = Typed Type a

data Exp a = Var a
           | Typed (Exp a) :@: Typed (Exp a)
           | Lam Type (Typed (Scope () Exp a))

Теперь мы можем записать экземпляр монады, просто всегда предполагая сохранение типа:

instance Monad Exp where
    return = Var
    Var a >>= f = f a
    (Typed tx x :@: Typed ty y) >>= f = Typed tx (f >>= x) :@: Typed ty (f >>= y)
    Lam tp (Typed te e) >>= f = Lam tp $ Typed te (e >>>= f)

Это не всегда верно в целом, но всегда это верно при вызове связанных функций. Если требуется больше безопасности типа, эти вещи можно разделить на вспомогательные функции:

UniContext :: * -> * -- some monad we can do unification in
fresh :: UniContext Type
unify :: Type -> Type -> UniContext Type
-- (a -> b) and a to b
applyType :: Type -> Type -> UniContext Type
-- b and a to a -> b
unapplyType :: Type -> Type -> UniContext Type

variable :: a -> Typed (Exp a)
variable x = (\tx -> Typed tx (return x)) <$> fresh

(|@|) :: Typed (Exp a) -> Typed (Exp a) -> UniContext (Typed (Exp a))
[email protected](Typed tx _) |@| [email protected](Typed ty _) = do
    txy <- applyType tx ty
    return $ Typed txy (x :@: y)

lambda :: a -> Typed (Exp a) -> UniContext (Typed (Exp a))
lambda p (Typed te e) = do
     tp <- fresh
     tf <- unapply te tp
     let f = abstract1 p e
     return $ Lam tp $ Typed tf f

Это обеспечивает достаточные гарантии при создании дерева, поскольку объединение выполняется во всех случаях. Если мы не экспортируем конструктор Typed, мы можем предоставить функцию

bindTyped :: Typed x -> (x -> UniContext (Typed y)) -> UniContext (Typed y)

который будет выполнять унификацию. Заметим, что в этом случае x соответствует не a, как указано выше, а скорее Exp a; для выполнения вычисления можно использовать значение всего выражения, а не только переменные. (Обратите внимание, что это исключает все модификации, модифицирующие тип, которые могут быть нежелательными.)