SystemT 编译器和处理 Haskell 中的无限类型
SystemT Compiler and dealing with Infinite Types in Haskell
我正在关注此博客 post：http://semantic-domain.blogspot.com/2012/12/total-functional-programming-in-partial.html
它显示了 System T (a simple total functional language) 的小型 OCaml 编译器程序。
整个管道采用 OCaml 语法（通过 Camlp4 元编程）将它们转换为 OCaml AST，然后转换为 SystemT Lambda 微积分（参见：module Term），最后是 SystemT 组合器微积分（参见：
module Goedel)。最后一步也是用OCaml元编程包裹Ast.expr类型
我试图在不使用模板 Haskell 的情况下将其翻译成 Haskell。
对于 SystemT Combinator 形式，我将其写为
{-# LANGUAGE GADTs #-}
data TNat = Zero | Succ TNat
data THom a b where
Id :: THom a a
Unit :: THom a ()
ZeroH :: THom () TNat
SuccH :: THom TNat TNat
Compose :: THom a b -> THom b c -> THom a c
Pair :: THom a b -> THom a c -> THom a (b, c)
Fst :: THom (a, b) a
Snd :: THom (a, b) b
Curry :: THom (a, b) c -> THom a (b -> c)
Eval :: THom ((a -> b), a) b -- (A = B) * A -> B
Iter :: THom a b -> THom (a, b) b -> THom (a, TNat) b
注意Compose是正向合成，不同于(.)。
在将 SystemT Lambda 微积分转换为 SystemT 组合子微积分的过程中，Elaborate.synth 函数尝试将 SystemT Lambda 微积分变量转换为一系列组合投影表达式（与 De Brujin 指数相关）。这是因为组合子演算没有 variables/variable 名称。这是通过使用 Quote.find 函数的 Elaborate.lookup 完成的。
问题在于我将组合演算编码为 GADT THom a b。翻译 Quote.find 函数：
let rec find x = function
| [] -> raise Not_found
| (x', t) :: ctx' when x = x' -> <:expr< Goedel.snd >>
| (x', t) :: ctx' -> <:expr< Goedel.compose Goedel.fst $find x ctx'$ >>
进入Haskell:
find :: TVar -> Context -> _
find tvar [] = error "Not Found"
find tvar ((tvar', ttype):ctx)
| tvar == tvar' = Snd
| otherwise = Compose Fst (find tvar ctx)
导致无限类型错误。
• Occurs check: cannot construct the infinite type: a ~ (a, c)
Expected type: THom (a, c) c
Actual type: THom ((a, c), c) c
问题源于这样一个事实，即使用 THom a b GADT 中的 Compose 和 Fst 以及 Snd 会导致类型签名的无限变化。
这篇文章没有这个问题，因为它似乎使用 Ast.expr OCaml 东西来包装底层表达式。
我不确定如何解决 Haskell。我应该使用像
这样的存在量化类型吗？
data TExpr = forall a b. TExpr (THom a b)
或某种类型级别 Fix 来适应无限类型问题。但是我不确定这会如何改变 find 或 lookup 函数。
这个答案必须有点高级，因为有三个完全不同的 系列 可能的设计可以解决这个问题。您正在做的事情似乎更接近方法三，但这些方法是按复杂性递增的顺序排列的。
原文中的做法post
翻译原文post需要模板Haskell和偏爱； find 会 return 一个 Q.Exp 代表一些 Hom a b，就像原来的 post 一样避免了这个问题。就像在原始 post 中一样，在对所有模板 Haskell 函数的输出进行类型检查时，将捕获原始代码中的类型错误。因此，仍然会在before 运行时捕获类型错误，但您仍然需要编写tests 来查找您的宏输出错误类型表达式的情况。可以以显着增加复杂性为代价提供更强的保证。
依赖typing/GADTs 输入和输出
如果您想与 post 不同，一种替代方法是在整个过程中使用“依赖类型”并使 输入 依赖类型。我宽松地使用这个术语来包括实际依赖类型的语言、实际依赖 Haskell（当它落地时），以及今天在 Haskell 中伪造依赖类型的方法（通过 GADT、单例等等） .
但是，您无法编写自己的类型检查器并选择要使用的类型系统；通常，您最终会嵌入一个简单类型的 lambda 演算，并且可以通过多态 Haskell 函数模拟多态性，这些函数可以在给定类型下生成项。这在依赖类型的语言中更容易，但在 Haskell.
中完全可能
但老实说，在这条路上使用高阶抽象语法和Haskell函数更容易，比如：
data Exp a where
Abs :: (Exp a -> Exp b) -> Exp (a -> b)
App :: Exp (a -> b) -> Exp a -> Exp b
Var :: String -> Exp a —- only use for free variables
exampleId :: Exp (a -> a)
exampleId = Abs (\x -> x)
如果您可以使用这种方法（这里省略了详细信息），您可以从复杂性有限的 GADT 中获得高保证。然而，这种方法对于许多场景来说太不灵活了，例如因为输入上下文只对 Haskell 编译器可见，而不是在你的类型或术语中。
从无类型到有类型的术语
第三个选项是 go dependently-typed and 仍然可以使您的程序将弱类型输入转换为强类型输出。在这种情况下，您的类型检查器总体上将某种类型 Expr 的术语转换为 GADT TExp gamma t、Hom a b 等术语。由于您静态地不知道 gamma 和 t（或 a 和 b）是什么，因此您确实需要某种存在性。
但是普通的存在主义太弱了：要构建更大的类型良好的表达式，您需要检查生成的类型是否允许它。例如，要从两个较小的 TExpr 构建一个包含 Compose 表达式的 TExpr，您需要（在运行时）检查它们的类型是否匹配。对于简单的存在主义，你不能。因此，您还需要在值级别表示类型。
更重要的是，存在主义处理起来很烦人（像往常一样），因为您永远无法在 return 类型中公开隐藏的类型变量，或将它们投射出去（与依赖 records/sigma-types 不同).
老实说，我并不完全确定这最终能否奏效。这是 Haskell 中可能的部分草图，最多为 find.
的一种情况
data Type t where
VNat :: Type Nat
VString :: Type String
VArrow :: Type a -> Type b -> Type (a -> b)
VPair :: Type a -> Type b -> Type (a, b)
VUnit :: Type ()
data SomeType = forall t. SomeType (Type t)
data SomeHom = forall a b. SomeHom (Type a) (Type b) (THom a b)
type Context = [(TVar, SomeType)]
getType :: Context -> SomeType
getType [] = SomeType VUnit
getType ((_, SomeType ttyp) :: gamma) =
case getType gamma of
SomeType ctxT -> SomeType (VPair ttyp
find :: TVar -> Context -> SomeHom
find tvar ((tvar’, ttyp) :: gamma)
| tvar == tvar’ =
case (ttyp, getType gamma) of
(SomeType t, SomeType ctxT) ->
SomeHom (VPair t ctxT) t Fst
我正在关注此博客 post：http://semantic-domain.blogspot.com/2012/12/total-functional-programming-in-partial.html
它显示了 System T (a simple total functional language) 的小型 OCaml 编译器程序。
整个管道采用 OCaml 语法（通过 Camlp4 元编程）将它们转换为 OCaml AST，然后转换为 SystemT Lambda 微积分（参见：module Term），最后是 SystemT 组合器微积分（参见：
module Goedel)。最后一步也是用OCaml元编程包裹Ast.expr类型
我试图在不使用模板 Haskell 的情况下将其翻译成 Haskell。
对于 SystemT Combinator 形式，我将其写为
{-# LANGUAGE GADTs #-}
data TNat = Zero | Succ TNat
data THom a b where
Id :: THom a a
Unit :: THom a ()
ZeroH :: THom () TNat
SuccH :: THom TNat TNat
Compose :: THom a b -> THom b c -> THom a c
Pair :: THom a b -> THom a c -> THom a (b, c)
Fst :: THom (a, b) a
Snd :: THom (a, b) b
Curry :: THom (a, b) c -> THom a (b -> c)
Eval :: THom ((a -> b), a) b -- (A = B) * A -> B
Iter :: THom a b -> THom (a, b) b -> THom (a, TNat) b
注意Compose是正向合成，不同于(.)。
在将 SystemT Lambda 微积分转换为 SystemT 组合子微积分的过程中，Elaborate.synth 函数尝试将 SystemT Lambda 微积分变量转换为一系列组合投影表达式（与 De Brujin 指数相关）。这是因为组合子演算没有 variables/variable 名称。这是通过使用 Quote.find 函数的 Elaborate.lookup 完成的。
问题在于我将组合演算编码为 GADT THom a b。翻译 Quote.find 函数：
let rec find x = function
| [] -> raise Not_found
| (x', t) :: ctx' when x = x' -> <:expr< Goedel.snd >>
| (x', t) :: ctx' -> <:expr< Goedel.compose Goedel.fst $find x ctx'$ >>
进入Haskell:
find :: TVar -> Context -> _
find tvar [] = error "Not Found"
find tvar ((tvar', ttype):ctx)
| tvar == tvar' = Snd
| otherwise = Compose Fst (find tvar ctx)
导致无限类型错误。
• Occurs check: cannot construct the infinite type: a ~ (a, c)
Expected type: THom (a, c) c
Actual type: THom ((a, c), c) c
问题源于这样一个事实，即使用 THom a b GADT 中的 Compose 和 Fst 以及 Snd 会导致类型签名的无限变化。
这篇文章没有这个问题，因为它似乎使用 Ast.expr OCaml 东西来包装底层表达式。
我不确定如何解决 Haskell。我应该使用像
这样的存在量化类型吗？data TExpr = forall a b. TExpr (THom a b)
或某种类型级别 Fix 来适应无限类型问题。但是我不确定这会如何改变 find 或 lookup 函数。
这个答案必须有点高级，因为有三个完全不同的 系列 可能的设计可以解决这个问题。您正在做的事情似乎更接近方法三，但这些方法是按复杂性递增的顺序排列的。
原文中的做法post
翻译原文post需要模板Haskell和偏爱； find 会 return 一个 Q.Exp 代表一些 Hom a b，就像原来的 post 一样避免了这个问题。就像在原始 post 中一样，在对所有模板 Haskell 函数的输出进行类型检查时，将捕获原始代码中的类型错误。因此，仍然会在before 运行时捕获类型错误，但您仍然需要编写tests 来查找您的宏输出错误类型表达式的情况。可以以显着增加复杂性为代价提供更强的保证。
依赖typing/GADTs 输入和输出
如果您想与 post 不同，一种替代方法是在整个过程中使用“依赖类型”并使 输入 依赖类型。我宽松地使用这个术语来包括实际依赖类型的语言、实际依赖 Haskell（当它落地时），以及今天在 Haskell 中伪造依赖类型的方法（通过 GADT、单例等等） . 但是，您无法编写自己的类型检查器并选择要使用的类型系统；通常，您最终会嵌入一个简单类型的 lambda 演算，并且可以通过多态 Haskell 函数模拟多态性，这些函数可以在给定类型下生成项。这在依赖类型的语言中更容易，但在 Haskell.
中完全可能但老实说，在这条路上使用高阶抽象语法和Haskell函数更容易，比如：
data Exp a where
Abs :: (Exp a -> Exp b) -> Exp (a -> b)
App :: Exp (a -> b) -> Exp a -> Exp b
Var :: String -> Exp a —- only use for free variables
exampleId :: Exp (a -> a)
exampleId = Abs (\x -> x)
如果您可以使用这种方法（这里省略了详细信息），您可以从复杂性有限的 GADT 中获得高保证。然而，这种方法对于许多场景来说太不灵活了，例如因为输入上下文只对 Haskell 编译器可见，而不是在你的类型或术语中。
从无类型到有类型的术语
第三个选项是 go dependently-typed and 仍然可以使您的程序将弱类型输入转换为强类型输出。在这种情况下，您的类型检查器总体上将某种类型 Expr 的术语转换为 GADT TExp gamma t、Hom a b 等术语。由于您静态地不知道 gamma 和 t（或 a 和 b）是什么，因此您确实需要某种存在性。
但是普通的存在主义太弱了：要构建更大的类型良好的表达式，您需要检查生成的类型是否允许它。例如，要从两个较小的 TExpr 构建一个包含 Compose 表达式的 TExpr，您需要（在运行时）检查它们的类型是否匹配。对于简单的存在主义，你不能。因此，您还需要在值级别表示类型。
更重要的是，存在主义处理起来很烦人（像往常一样），因为您永远无法在 return 类型中公开隐藏的类型变量，或将它们投射出去（与依赖 records/sigma-types 不同).
老实说，我并不完全确定这最终能否奏效。这是 Haskell 中可能的部分草图，最多为 find.
data Type t where
VNat :: Type Nat
VString :: Type String
VArrow :: Type a -> Type b -> Type (a -> b)
VPair :: Type a -> Type b -> Type (a, b)
VUnit :: Type ()
data SomeType = forall t. SomeType (Type t)
data SomeHom = forall a b. SomeHom (Type a) (Type b) (THom a b)
type Context = [(TVar, SomeType)]
getType :: Context -> SomeType
getType [] = SomeType VUnit
getType ((_, SomeType ttyp) :: gamma) =
case getType gamma of
SomeType ctxT -> SomeType (VPair ttyp
find :: TVar -> Context -> SomeHom
find tvar ((tvar’, ttyp) :: gamma)
| tvar == tvar’ =
case (ttyp, getType gamma) of
(SomeType t, SomeType ctxT) ->
SomeHom (VPair t ctxT) t Fst