在运行时类型与 Existentials 杂耍

Question

我正在研究 Haskell 中的存在论和 GADT，我正在尝试为组合器（例如 SKI）定义一个 DSL。我有 GADT 工作，还有一个工作正常的缩减功能（并且与问题无关）

{-# LANGUAGE GADTs, ExistentialQuantification #-}

import Control.Applicative
import Data.Monoid
import Control.Monad

data Comb t where
    S :: Comb ((a -> b -> c) -> (a -> b) -> a -> c)
    K :: Comb (a -> b -> a)
    I :: Comb (a -> a)
    B :: Comb ((b -> c) -> (a -> b) -> a -> c)
    C :: Comb ((b -> a -> c) -> a -> b -> c)
    W :: Comb ((a -> a -> b) -> a -> b)
    (:$) :: Comb (a -> b) -> Comb a -> Comb b

我现在要做的是定义一种在运行时从用户那里读取组合器字符串的方法。显然，我需要一个存在类型来执行此操作，因为需要隐藏 GADT 的类型信息。

data CombBox = forall a. CombBox { unCombBox :: Comb a }

($$) :: CombBox -> CombBox -> Maybe CombBox
x $$ y = undefined -- ???

我希望 ($$) 函数在运行时以某种方式 "look inside" CombBox 存在，如果可以使用 :$ 组合两个组合器并得到一个类型正确的结果，我希望结果是这样的。否则，我要Nothing。所以，例如，

CombBox S $$ CombBox K ==> Just (CombBox (S :$ K))
CombBox W $$ CombBox I ==> Nothing

后者应该会失败，因为 W 需要一个二元函数，其中 I 接受一个参数。但我想将此检查委托给运行时，我不确定在 Haskell（+ GHC 扩展）类型系统中是否可能发生这种情况。

Answer 1

不是正确答案，但可能会有帮助。

Parametricity 不允许控制流依赖于类型，因此您需要一些类型的一阶表示。 Haskell 有 Typeable:

deriving instance Typeable Comb

data CombBox = forall a. Typeable a => CombBox { unCombBox :: Comb a }

使用它我们可以定义

castApply1 :: (Typeable a, Typeable b, Typeable ab) => Comb ab -> Comb a -> Maybe (Comb b)
castApply1 f x = (:$ x) <$> cast f

然而

($$) :: CombBox -> CombBox -> Maybe CombBox
CombBox f $$ CombBox x = CombBox <$> castApply f x

投掷

Could not deduce (Typeable a0) arising from a use of `CombBox' …
    from the context (Typeable a)
    or from (Typeable a1)
    The type variable `a0' is ambiguous

问题是在castApply1的return类型中指定了b，但是如果我们立即将CombBox应用到castApply f x，那么b 未指定，因此仍然不明确。

我们可以通过提供 Proxy b 作为参数来指定 b：

castApply2 :: (Typeable a, Typeable b, Typeable ab) => Proxy b -> Comb ab -> Comb a -> Maybe (Comb b)
castApply2 p = castApply1

允许将结果包装在 CombBox:

castApply3 :: (Typeable a, Typeable b, Typeable ab) => Proxy b -> Comb ab -> Comb a -> Maybe CombBox
castApply3 p f x = CombBox <$> castApply2 p f x

我们终于可以定义一些没有提到烦人的东西了b:

data SomeTypeable = forall a. Typeable a => SomeTypeable (Proxy a)

castApply4 :: (Typeable a, Typeable ab) => SomeTypeable -> Comb ab -> Comb a -> Maybe CombBox
castApply4 (SomeTypeable p) = castApply3 p

现在有

typeRepToSomeTypeable :: TypeRep -> SomeTypeable

我们可以定义

castApply :: (Typeable a, Typeable ab) => TypeRep -> Comb ab -> Comb a -> Maybe CombBox
castApply t = castApply4 (typeRepToSomeTypeable t)

($$) :: CombBox -> CombBox -> Maybe CombBox
CombBox f $$ CombBox x = funResultTy (typeRep f) (typeRep x) >>= \t -> castApply t f x

funResultTy 是 Data.Typeable 中的一个函数，如果第一个参数的域与第二个参数匹配，return 是第一个参数的辅助域。

但是typeRepToSomeTypeable如何定义呢？它似乎没有在某处实施。至少我在 Data.Typeable 和 Singletons.

中都没有找到它

Answer 2

准备好了解 依赖对 和 单身人士 !

我将稍微重写您的系统以简化它。

首先，我将把你的类型范围从 所有 Haskell 缩小到一个由单一原始类型和箭头组成的更简单的范围。

infixr 0 :->
data Type = Unit | Type :-> Type

希望您能够看到如何使用更多原始类型来扩展它。

我还将删除 Comb 中的大部分位，因为它们都可以相互表示。

data Comb a where
    S :: Comb ((a :-> b :-> c) :-> (a :-> b) :-> a :-> c)
    K :: Comb (a :-> b :-> a)
    (:$) :: Comb (a :-> b) -> Comb a -> Comb b

i = S :$ K :$ i
b = (S :$ (K :$ S)) :$ K
c = S :$ (S :$ (K :$ (S :$ (K :$ S) :$ K)) :$ S) :$ (K :$ K)
w = S :$ S :$ (S :$ K)

现在回答你的问题。正如您正确推测的那样，当您阅读用户输入时，您无法静态预测结果术语的类型，因此您需要对其进行存在量化。

data Ex f = forall a. Ex (f a)

问题是：如何恢复类型信息以便能够操纵术语？我们可以将 Comb 与另一个值配对，您可以在运行时对其进行模式匹配，以学习 Comb 的类型。这是一个用于配对的组合器。

data (f :*: g) i = f i :*: g i

（我从 the Hasochism paper 中提取了这两种类型。）:*: 将两种类型配对，确保它们的索引相等。我们将它与 Ex 一起使用来模拟一个 依赖对 或 sigma 类型：一对值的类型第二个组件取决于第一个组件的值。这个想法是 f 将是一个 GADT，它会告诉您有关其索引的一些信息，因此 f 上的模式匹配会为您提供有关 g.

类型的信息

type Sg f g = Ex (f :*: g)
pattern Sg x y = Ex (x :*: y)

现在是聪明的部分：想出一个 GADT，告诉您组合项的类型。

data Typey t where
    Unity :: Typey Unit
    Arry :: Typey a -> Typey b -> Typey (a :-> b)

Typey 被称为单例。对于给定的 t，恰好存在一个 Typey t 类型的值。所以如果你有一个 Typey t 值，你就知道关于 t.

的一切

单例值最终是一种 hack。 Typey 不是 Type；它是 Type 复制的类型级副本的值级替代品。在一个真正的依赖类型系统中，你不需要单例胶水来将值级别的东西附加到类型级别的东西，因为首先不存在区别。

我们的存在量化组合器现在看起来像这样。 AComb 将 Comb 与其类型的运行时表示打包在一起。这种技术使我们能够保证盒装 Comb 的类型正确；我们只是不能静态地说出那个类型是什么。

type AComb = Sg Typey Comb

我们如何编写 ($$)，它试图将 AComb 应用于另一个 AComb？我们需要对它们关联的 Typey 进行模式匹配，以了解是否可以将一个应用到另一个。特别是，我们需要一种方法来了解两种类型是否相等。

命题相等 来了，一个 GADT 证明两个类型级别的东西是相等的。如果您可以向 GHC 解释 a 和 b 实际上是相同的，那么您只能给出 Refl 的值。相反，如果您在 Refl 上进行模式匹配，那么 GHC 会将 a ~ b 添加到输入上下文中。

data a :~: b where
    Refl :: a :~: a
withEq :: a :~: b -> (a ~ b => r) -> r
withEq Refl x = x

这里有一个辅助函数，可以通过 :-> 构造函数提升一对等式。

arrEq :: (a :~: c) -> (b :~: d) -> (a :-> b) :~: (c :-> d)
arrEq Refl Refl = Refl

正如所承诺的，我们可以写一个函数来检查两个 Type 是否相等。我们通过对它们关联的单例 Typey 进行模式匹配来继续，如果我们发现类型不兼容则失败。如果相等测试成功，战利品就是类型相等的证明。

tyEq :: Typey t -> Typey u -> Maybe (t :~: u)
tyEq Unity Unity = Just Refl
tyEq (Arry a b) (Arry c d) = liftA2 arrEq (tyEq a c) (tyEq b d)
tyEq _ _ = Nothing

withTyEq :: Typey t -> Typey u -> (t ~ u => a) -> Maybe a
withTyEq t u x = fmap (\p -> withEq p x) (tyEq t u)

终于可以写$$了。打字规则是这样的：

f : a -> b    y : a
------------------- App
      f y : b

也就是说，如果$$的左边项是函数类型，右边项的类型与函数的域相匹配，我们就可以打出申请。因此，此规则的实施必须测试（使用 withTyEq）相关类型是否匹配，以便 return 结果项。

($$) :: AComb -> AComb -> Maybe AComb
Sg (Arry a b) x $$ Sg t y = withTyEq a t $ Sg b (x :$ y)
_ $$ _ = Nothing

生成 Typey 项对应于类型检查的行为。换句话说，函数 parse :: String -> AComb 必须同时进行解析和类型检查。在真正的编译器中，这两个阶段是分开的。

所以我建议将用户输入解析为 非类型化 语法树，它承认格式不正确的术语，然后单独生成类型信息。

data Expr = S | K | Expr :$ Expr
parse :: String -> Parser Expr
typeCheck :: Expr -> Maybe AComb

一个有趣的练习（在更依赖类型的语言中）是将 typeCheck 修改为 return 更详细地解释类型检查失败的原因，例如伪 Agda：

data Void : Set where
Not : Set -> Set
Not a = a -> Void

data TypeError : Expr -> Set where
    notArr : Not (IsFunction f) -> TypeError (f :$ x)
    mismatch : Not (domain f :~: type x) -> TypeError (f :$ x)
    inFunc : TypeError f -> TypeError (f :$ x)
    inArg : TypeError x -> TypeError (f :$ x)

typeCheck : (e : Expr) -> Either (TypeError e) AComb

你也可以通过保证它不会改变你给它的术语（另一个练习）来使 typeCheck 更精确。

如需进一步阅读，请参阅 The View from the Left，其中包含经过验证的 lambda 演算类型检查器。

在运行时类型与 Existentials 杂耍

Type Juggling with Existentials at Runtime

haskell

dependent-type

gadt

existential-type

combinators