12

所以，我在玩HaskellDataKinds并TypeFamilies开始研究生成的 Core GHC。

这是一个小测试用例来激发我的问题：

{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE KindSignatures #-}

module TestCase where

data Ty = TyBool | TyInt

type family InterpTy (t :: Ty) :: *
type instance InterpTy TyBool = Bool
type instance InterpTy TyInt  = Int

data Expr (a :: Ty) where
  I :: Int  -> Expr TyInt
  B :: Bool -> Expr TyBool

eval :: Expr a -> InterpTy a
eval (I i) = i
eval (B b) = b

让我们看一下为eval函数生成的Core

TestCase.eval =
  \ (@ (a_aKM :: TestCase.Ty)) (ds_dL3 :: TestCase.Expr a_aKM) ->
    case ds_dL3 of _ [Occ=Dead] {
      TestCase.I dt_dLh i_as6 ->
        i_as6
        `cast` (Sub (Sym TestCase.TFCo:R:InterpTyTyInt[0])
                ; (TestCase.InterpTy (Sym dt_dLh))_R
                :: GHC.Types.Int ~# TestCase.InterpTy a_aKM);
      TestCase.B dt_dLc b_as7 ->
        b_as7
        `cast` (Sub (Sym TestCase.TFCo:R:InterpTyTyBool[0])
                ; (TestCase.InterpTy (Sym dt_dLc))_R
                :: GHC.Types.Bool ~# TestCase.InterpTy a_aKM)
    }

显然，我们需要携带有关a特定分支中可能存在的信息。如果我不对 Datakind 进行索引并且不使用 TypeFamilies，则演员表更容易理解。

它会是这样的：

Main.eval =
  \ (@ a_a1hg) (ds_d1sQ :: Main.Simpl a_a1hg) ->
    case ds_d1sQ of _ [Occ=Dead] {
      Main.I' dt_d1to i_aFa ->
        i_aFa
        `cast` (Sub (Sym dt_d1to) :: GHC.Integer.Type.Integer ~# a_a1hg);
      Main.B' dt_d1tk b_aFb ->
        b_aFb `cast` (Sub (Sym dt_d1tk) :: GHC.Types.Bool ~# a_a1hg)
    }

这个我可以很好理解，TypeFamilies例子中让我困扰的是这部分：

(Sub (Sym TestCase.TFCo:R:InterpTyTyInt[0])
      ; (TestCase.InterpTy (Sym dt_dLh))_R
      :: GHC.Types.Int ~# TestCase.InterpTy a_aKM);

第二行是真正让我感到困惑的地方。分号在那里做什么？这里似乎有点不合适，或者我错过了什么？有没有地方可以读到这个（如果你能推荐的话，我很乐意拿论文）

亲切的问候，

来秋

4

1 回答 1

10

分号是强制传递性的语法。

最新的（截至 2014 年 9 月）关于 System FC 的论文是来自 ICFP 2014的“Haskell 中的安全零成本强制” 。

特别是，在那篇论文的图 3 中，我们看到了强制转换的语法。“γ₁;γ₂”是强制传递性。如果 γ₁ 是见证“τ₁ ~ τ₂”的强制，而 γ₂ 是见证 τ₂ ~ τ₃ 的强制，那么“γ₁;γ₂”是见证 τ₁ ~ τ₃ 的强制。

在示例中，当您编写eval (I i) = i编译器时，右侧看到的是 type 的值Int，而它需要（从函数的返回类型）是InterpTy a. 所以现在它需要构造一个证明Int ~ InterpTy a.

非正式地，（从右到左阅读并忽略角色-有关其详细信息，请参见链接的论文）：

  1. 通过进行 GADT 模式匹配，我们了解到“ a ~ Int”（即dt_dLh）
  2. 所以我们申请Sym它，得到“ Int ~ a”。
  3. 然后应用InterpTy族得到“ InterpTy Int ~ InterpTy a”（这是/congruence/的一个实例）
  4. 然后我们将它与“ Sym InterpTyTyInt”（这是声明“ InterpTy TyInt ~ Int”的公理的翻转版本）组合起来以获得我们所追求的强制：“ Int ~ InterpTy a”
于 2014-09-19T21:02:10.853 回答