Haskell 中的类型化抽象语法和 DSL 设计
Typed abstract syntax and DSL design in Haskell
我正在Haskell中设计一个DSL，我想要一个赋值操作。像这样（下面的代码只是为了在有限的上下文中解释我的问题，我没有类型检查 Stmt 类型）：
data Stmt = forall a . Assign String (Exp a) -- Assignment operation
| forall a. Decl String a -- Variable declaration
data Exp t where
EBool :: Bool -> Exp Bool
EInt :: Int -> Exp Int
EAdd :: Exp Int -> Exp Int -> Exp Int
ENot :: Exp Bool -> Exp Bool
在前面的代码中，我能够使用 GADT 对表达式强制执行类型约束。我的问题是如何强制赋值的左侧是：1) 已定义，即变量必须在使用前声明，以及 2) 右侧必须具有与左侧变量相同的类型？
我知道在完全依赖类型的语言中，我可以定义由某种类型上下文索引的语句，即已定义变量及其类型的列表。我相信这会解决我的问题。但是，我想知道在 Haskell.
中是否有某种方法可以实现这一点
非常感谢任何指向示例代码或文章的指针。
你应该知道你的目标很远大。我认为您不会将变量完全视为字符串。我会做一些使用起来稍微烦人但更实用的事情。为你的 DSL 定义一个 monad，我称之为 M:
newtype M a = ...
data Exp a where
... as before ...
data Var a -- a typed variable
assign :: Var a -> Exp a -> M ()
declare :: String -> a -> M (Var a)
我不确定为什么你有 Exp a 用于赋值而只有 a 用于声明，但我在这里复制了它。 declare 中的 String 只是为了装饰，如果您需要它来生成代码或错误报告或其他东西——变量的标识实际上不应与该名称相关联。所以通常用作
myFunc = do
foobar <- declare "foobar" 42
这是烦人的冗余位。 Haskell 并没有真正解决这个问题的好方法（尽管根据您使用 DSL 所做的事情，您可能根本不需要该字符串）。
至于实现，可能是这样的
data Stmt = forall a. Assign (Var a) (Exp a)
| forall a. Declare (Var a) a
data Var a = Var String Integer -- string is auxiliary from before, integer
-- stores real identity.
对于M，我们需要唯一的名称供应和要输出的语句列表。
newtype M a = M { runM :: WriterT [Stmt] (StateT Integer Identity a) }
deriving (Functor, Applicative, Monad)
然后操作通常相当微不足道。
assign v a = M $ tell [Assign v a]
declare name a = M $ do
ident <- lift get
lift . put $! ident + 1
let var = Var name ident
tell [Declare var a]
return var
我使用非常相似的设计为另一种语言的代码生成制作了一个相当大的 DSL，并且它的扩展性很好。我发现留下 "near the ground" 是个好主意，只是在不使用太多花哨的类型级神奇功能的情况下进行实体建模，并接受轻微的语言烦恼。这样 Haskell 的主要优势——它的抽象能力——仍然可以用于 DSL 中的代码。
一个缺点是所有内容都需要在 do 块中定义，随着代码量的增加，这可能会阻碍良好的组织。我会偷 declare 来展示解决这个问题的方法：
declare :: String -> M a -> M a
像
一样使用
foo = declare "foo" $ do
-- actual function body
然后你的 M 可以有一个从名称到变量的缓存作为其状态的一个组成部分，并且你第一次 使用 一个具有特定名称的声明你渲染它并将其放入变量中（这需要比 [Stmt] 更复杂的幺半群作为 Writer 的目标）。稍后您只需查找变量即可。不幸的是，它确实对名称的唯一性有相当松散的依赖；命名空间的显式模型可以帮助解决这个问题，但永远不会完全消除它。
在查看了@Cactus 的所有代码和@luqui 的 Haskell 建议后，我设法在 Idris 中找到了接近我想要的解决方案。完整代码可在以下要点获得：
(https://gist.github.com/rodrigogribeiro/33356c62e36bff54831d)
我需要在之前的解决方案中修复一些小问题：
- 我（还）不知道 Idris 是否支持整数文字重载，什么对构建我的 DSL 非常有用。
- 我尝试在 DSL 语法中为程序变量定义一个前缀运算符，但它并没有像我喜欢的那样工作。我有一个解决方案（在前面的要点中）使用关键字 --- use --- 进行变量访问。
我会和 Idris #freenode 频道的人一起检查这两个小点，看看这两点是否可行。
鉴于我的工作重点是在类型级别编码的范围和类型安全的相关问题，我在谷歌搜索时偶然发现了这个老问题，并认为我会试一试。
我认为 post 提供了与原始规范非常接近的答案。一旦你有了正确的设置，整个事情就会出人意料地短。
首先，我将从一个示例程序开始，让您了解最终结果是什么样的：
program :: Program
program = Program
$ Declare (Var :: Name "foo") (Of :: Type Int)
:> Assign (The (Var :: Name "foo")) (EInt 1)
:> Declare (Var :: Name "bar") (Of :: Type Bool)
:> increment (The (Var :: Name "foo"))
:> Assign (The (Var :: Name "bar")) (ENot $ EBool True)
:> Done
范围界定
为了确保我们只能为之前声明过的变量赋值，我们需要一个作用域的概念。
GHC.TypeLits 为我们提供了类型级别的字符串（称为 Symbol），因此如果我们愿意，我们可以很好地使用字符串作为变量名。并且因为我们要确保类型安全，所以每个变量声明都带有一个类型注释，我们会将其与变量名称一起存储。因此，我们的范围类型是：[(Symbol, *)].
我们可以使用类型族来测试给定的 Symbol 是否在范围内以及 return 其关联类型是否在这种情况下：
type family HasSymbol (g :: [(Symbol,*)]) (s :: Symbol) :: Maybe * where
HasSymbol '[] s = 'Nothing
HasSymbol ('(s, a) ': g) s = 'Just a
HasSymbol ('(t, a) ': g) s = HasSymbol g s
根据这个定义，我们可以定义一个变量的概念：范围g中类型a的变量是一个符号s使得HasSymbol g sreturns 'Just a。这就是 ScopedSymbol 数据类型通过使用存在量化来存储 s.
所表示的内容
data ScopedSymbol (g :: [(Symbol,*)]) (a :: *) = forall s.
(HasSymbol g s ~ 'Just a) => The (Name s)
data Name (s :: Symbol) = Var
在这里，我故意在各处滥用符号：The 是类型 ScopedSymbol 的构造函数，而 Name 是具有更好名称的 Proxy 类型和构造函数。这允许我们写出这样的细节：
example :: ScopedSymbol ('("foo", Int) ': '("bar", Bool) ': '[]) Bool
example = The (Var :: Name "bar")
报表
现在我们有了作用域和该作用域中类型良好的变量的概念，我们可以开始考虑 Statements 应该具有的效果。鉴于可以在 Statement 中声明新变量，我们需要找到一种在范围内传播此信息的方法。事后看来，关键是要有两个索引：一个输入 和一个输出范围 。
到Declare一个新的变量连同它的类型将扩展当前范围与变量名和相应类型的对。
另一方面，Assignments 不修改范围。他们只是将 ScopedSymbol 关联到相应类型的表达式。
data Statement (g :: [(Symbol, *)]) (h :: [(Symbol,*)]) where
Declare :: Name s -> Type a -> Statement g ('(s, a) ': g)
Assign :: ScopedSymbol g a -> Exp g a -> Statement g g
data Type (a :: *) = Of
我们再次引入了代理类型以提供更好的用户级语法。
example' :: Statement '[] ('("foo", Int) ': '[])
example' = Declare (Var :: Name "foo") (Of :: Type Int)
example'' :: Statement ('("foo", Int) ': '[]) ('("foo", Int) ': '[])
example'' = Assign (The (Var :: Name "foo")) (EInt 1)
Statements 可以通过定义以下类型对齐序列的 GADT 以范围保留的方式链接：
infixr 5 :>
data Statements (g :: [(Symbol, *)]) (h :: [(Symbol,*)]) where
Done :: Statements g g
(:>) :: Statement g h -> Statements h i -> Statements g i
表达式
表达式与您的原始定义几乎没有变化，只是它们现在被限定了范围，并且新的构造函数 EVar 让我们可以取消引用先前声明的变量（使用 ScopedSymbol），从而为我们提供一个表达式合适的类型。
data Exp (g :: [(Symbol,*)]) (t :: *) where
EVar :: ScopedSymbol g a -> Exp g a
EBool :: Bool -> Exp g Bool
EInt :: Int -> Exp g Int
EAdd :: Exp g Int -> Exp g Int -> Exp g Int
ENot :: Exp g Bool -> Exp g Bool
程序
A Program 是一个非常简单的从空范围开始的语句序列。我们再次使用存在量化来隐藏我们最终得到的范围。
data Program = forall h. Program (Statements '[] h)
显然可以在 Haskell 中编写子程序并在您的程序中使用它们。在示例中，我有非常简单的 increment 可以这样定义：
increment :: ScopedSymbol g Int -> Statement g g
increment v = Assign v (EAdd (EVar v) (EInt 1))
我已经上传了整个代码片段以及正确的 LANGUAGE pragma 和此处列出的示例 in a self-contained gist。但是我没有在那里发表任何评论。
我正在Haskell中设计一个DSL，我想要一个赋值操作。像这样（下面的代码只是为了在有限的上下文中解释我的问题，我没有类型检查 Stmt 类型）：
data Stmt = forall a . Assign String (Exp a) -- Assignment operation
| forall a. Decl String a -- Variable declaration
data Exp t where
EBool :: Bool -> Exp Bool
EInt :: Int -> Exp Int
EAdd :: Exp Int -> Exp Int -> Exp Int
ENot :: Exp Bool -> Exp Bool
在前面的代码中，我能够使用 GADT 对表达式强制执行类型约束。我的问题是如何强制赋值的左侧是：1) 已定义，即变量必须在使用前声明，以及 2) 右侧必须具有与左侧变量相同的类型？
我知道在完全依赖类型的语言中，我可以定义由某种类型上下文索引的语句，即已定义变量及其类型的列表。我相信这会解决我的问题。但是，我想知道在 Haskell.
中是否有某种方法可以实现这一点非常感谢任何指向示例代码或文章的指针。
你应该知道你的目标很远大。我认为您不会将变量完全视为字符串。我会做一些使用起来稍微烦人但更实用的事情。为你的 DSL 定义一个 monad，我称之为 M:
newtype M a = ...
data Exp a where
... as before ...
data Var a -- a typed variable
assign :: Var a -> Exp a -> M ()
declare :: String -> a -> M (Var a)
我不确定为什么你有 Exp a 用于赋值而只有 a 用于声明，但我在这里复制了它。 declare 中的 String 只是为了装饰，如果您需要它来生成代码或错误报告或其他东西——变量的标识实际上不应与该名称相关联。所以通常用作
myFunc = do
foobar <- declare "foobar" 42
这是烦人的冗余位。 Haskell 并没有真正解决这个问题的好方法（尽管根据您使用 DSL 所做的事情，您可能根本不需要该字符串）。
至于实现，可能是这样的
data Stmt = forall a. Assign (Var a) (Exp a)
| forall a. Declare (Var a) a
data Var a = Var String Integer -- string is auxiliary from before, integer
-- stores real identity.
对于M，我们需要唯一的名称供应和要输出的语句列表。
newtype M a = M { runM :: WriterT [Stmt] (StateT Integer Identity a) }
deriving (Functor, Applicative, Monad)
然后操作通常相当微不足道。
assign v a = M $ tell [Assign v a]
declare name a = M $ do
ident <- lift get
lift . put $! ident + 1
let var = Var name ident
tell [Declare var a]
return var
我使用非常相似的设计为另一种语言的代码生成制作了一个相当大的 DSL，并且它的扩展性很好。我发现留下 "near the ground" 是个好主意，只是在不使用太多花哨的类型级神奇功能的情况下进行实体建模，并接受轻微的语言烦恼。这样 Haskell 的主要优势——它的抽象能力——仍然可以用于 DSL 中的代码。
一个缺点是所有内容都需要在 do 块中定义，随着代码量的增加，这可能会阻碍良好的组织。我会偷 declare 来展示解决这个问题的方法：
declare :: String -> M a -> M a
像
一样使用foo = declare "foo" $ do
-- actual function body
然后你的 M 可以有一个从名称到变量的缓存作为其状态的一个组成部分，并且你第一次 使用 一个具有特定名称的声明你渲染它并将其放入变量中（这需要比 [Stmt] 更复杂的幺半群作为 Writer 的目标）。稍后您只需查找变量即可。不幸的是，它确实对名称的唯一性有相当松散的依赖；命名空间的显式模型可以帮助解决这个问题，但永远不会完全消除它。
在查看了@Cactus 的所有代码和@luqui 的 Haskell 建议后，我设法在 Idris 中找到了接近我想要的解决方案。完整代码可在以下要点获得：
(https://gist.github.com/rodrigogribeiro/33356c62e36bff54831d)
我需要在之前的解决方案中修复一些小问题：
- 我（还）不知道 Idris 是否支持整数文字重载，什么对构建我的 DSL 非常有用。
- 我尝试在 DSL 语法中为程序变量定义一个前缀运算符，但它并没有像我喜欢的那样工作。我有一个解决方案（在前面的要点中）使用关键字 --- use --- 进行变量访问。
我会和 Idris #freenode 频道的人一起检查这两个小点，看看这两点是否可行。
鉴于我的工作重点是在类型级别编码的范围和类型安全的相关问题，我在谷歌搜索时偶然发现了这个老问题，并认为我会试一试。
我认为 post 提供了与原始规范非常接近的答案。一旦你有了正确的设置，整个事情就会出人意料地短。
首先，我将从一个示例程序开始，让您了解最终结果是什么样的：
program :: Program
program = Program
$ Declare (Var :: Name "foo") (Of :: Type Int)
:> Assign (The (Var :: Name "foo")) (EInt 1)
:> Declare (Var :: Name "bar") (Of :: Type Bool)
:> increment (The (Var :: Name "foo"))
:> Assign (The (Var :: Name "bar")) (ENot $ EBool True)
:> Done
范围界定
为了确保我们只能为之前声明过的变量赋值，我们需要一个作用域的概念。
GHC.TypeLits 为我们提供了类型级别的字符串（称为 Symbol），因此如果我们愿意，我们可以很好地使用字符串作为变量名。并且因为我们要确保类型安全，所以每个变量声明都带有一个类型注释，我们会将其与变量名称一起存储。因此，我们的范围类型是：[(Symbol, *)].
我们可以使用类型族来测试给定的 Symbol 是否在范围内以及 return 其关联类型是否在这种情况下：
type family HasSymbol (g :: [(Symbol,*)]) (s :: Symbol) :: Maybe * where
HasSymbol '[] s = 'Nothing
HasSymbol ('(s, a) ': g) s = 'Just a
HasSymbol ('(t, a) ': g) s = HasSymbol g s
根据这个定义，我们可以定义一个变量的概念：范围g中类型a的变量是一个符号s使得HasSymbol g sreturns 'Just a。这就是 ScopedSymbol 数据类型通过使用存在量化来存储 s.
data ScopedSymbol (g :: [(Symbol,*)]) (a :: *) = forall s.
(HasSymbol g s ~ 'Just a) => The (Name s)
data Name (s :: Symbol) = Var
在这里，我故意在各处滥用符号：The 是类型 ScopedSymbol 的构造函数，而 Name 是具有更好名称的 Proxy 类型和构造函数。这允许我们写出这样的细节：
example :: ScopedSymbol ('("foo", Int) ': '("bar", Bool) ': '[]) Bool
example = The (Var :: Name "bar")
报表
现在我们有了作用域和该作用域中类型良好的变量的概念，我们可以开始考虑 Statements 应该具有的效果。鉴于可以在 Statement 中声明新变量，我们需要找到一种在范围内传播此信息的方法。事后看来，关键是要有两个索引：一个输入 和一个输出范围 。
到Declare一个新的变量连同它的类型将扩展当前范围与变量名和相应类型的对。
Assignments 不修改范围。他们只是将 ScopedSymbol 关联到相应类型的表达式。
data Statement (g :: [(Symbol, *)]) (h :: [(Symbol,*)]) where
Declare :: Name s -> Type a -> Statement g ('(s, a) ': g)
Assign :: ScopedSymbol g a -> Exp g a -> Statement g g
data Type (a :: *) = Of
我们再次引入了代理类型以提供更好的用户级语法。
example' :: Statement '[] ('("foo", Int) ': '[])
example' = Declare (Var :: Name "foo") (Of :: Type Int)
example'' :: Statement ('("foo", Int) ': '[]) ('("foo", Int) ': '[])
example'' = Assign (The (Var :: Name "foo")) (EInt 1)
Statements 可以通过定义以下类型对齐序列的 GADT 以范围保留的方式链接：
infixr 5 :>
data Statements (g :: [(Symbol, *)]) (h :: [(Symbol,*)]) where
Done :: Statements g g
(:>) :: Statement g h -> Statements h i -> Statements g i
表达式
表达式与您的原始定义几乎没有变化，只是它们现在被限定了范围，并且新的构造函数 EVar 让我们可以取消引用先前声明的变量（使用 ScopedSymbol），从而为我们提供一个表达式合适的类型。
data Exp (g :: [(Symbol,*)]) (t :: *) where
EVar :: ScopedSymbol g a -> Exp g a
EBool :: Bool -> Exp g Bool
EInt :: Int -> Exp g Int
EAdd :: Exp g Int -> Exp g Int -> Exp g Int
ENot :: Exp g Bool -> Exp g Bool
程序
A Program 是一个非常简单的从空范围开始的语句序列。我们再次使用存在量化来隐藏我们最终得到的范围。
data Program = forall h. Program (Statements '[] h)
显然可以在 Haskell 中编写子程序并在您的程序中使用它们。在示例中，我有非常简单的 increment 可以这样定义：
increment :: ScopedSymbol g Int -> Statement g g
increment v = Assign v (EAdd (EVar v) (EInt 1))
我已经上传了整个代码片段以及正确的 LANGUAGE pragma 和此处列出的示例 in a self-contained gist。但是我没有在那里发表任何评论。