如何在 Haskell 中的嵌入式 DSL 中捕获高阶函数？

Question

我想在 Haskell 中编写一个嵌入式 DSL，从中我可以生成另一种语言的代码（即 Python，但这与问题无关）。有很多不同的方法可以做到这一点，比如使用我所知道的基于 Free monad 的解释器或无标记解释器。但据我所知，似乎没有一种方法能够捕获函数定义，这是有道理的，但也相当有限。

我的问题是：如何将实际的 Haskell 函数嵌入到 DSL 中？这个想法是将 Haskell 函数定义捕获转换为类似

Lam var body

构造函数，如下所示：

data Var = Var ...  -- use DeBruijn numbering?

data Expr repr = Lam Var repr

理想情况下，我希望能够写出类似的内容：

foo :: Expr repr
foo = \ n -> n + n * 12

然后能够以各种方式解释这个

Expr

，包括生成外来代码。

我尝试了https://hackage.haskell.org/package/data-reify，它提供了一些捕获函数的技术，但没有取得很大进展。我正在寻找的东西是否可能实现？

Answer 1

我自己对 Haskell 还很陌生，但是，我最近自己正在开发 DSL，所以这就是我的方法：

假设您有一个简单的 AST，其中包含一个小型 lambda 演算：

data Exp :: Type -> Type where
  Var ::
    String ->       -- Name
    Exp a
  Apply ::
    Exp (a -> b) -> -- Function
    Exp a ->        -- Parameter
    Exp b
  Lambda ::
    String ->       -- Bound variable name
    Exp b ->        -- "Right hand side" of lambda
    Exp (a -> b)
  ...

deriving instance Show (Exp t)

请注意，上面的结构实际上并不是类型安全的： 不能确保绑定变量与其各自的用途具有相同的类型：

unsafe :: Exp (Int -> String)
unsafe = Lambda "x" (Var "x" :: Exp String)

将毫无问题地编译。 （请注意，内部变量的类型与 lambda 表达式的参数不同。）事实上，上面的 AST 甚至不能保证引用的变量受到外部表达式的绑定。

由于无论如何我们更喜欢使用 Haskell 函数类型，因此只需不将 lambda 演算导出到其他包就足够了。

现在让我们将一元函数“转换”为 AST 的表达式。我们希望用

Var

占位符替换给定变量的所有出现，然后通过 lambda 绑定该变量：

convert :: String -> (Exp a -> Exp b) -> Exp (a -> b)
convert varName f = Lambda varName . f $ Var varName

ghci> convert "x" $ \x -> x
Lambda "x" (Var "x")

目前，每当我们想要绑定变量时，我们都没有办法确定不同的变量名称。然而，我们需要它来可靠地避免变量名称冲突。

实现此目的的一个简单方法是跟踪编译器中全局绑定的变量数量，并根据该计数生成新的变量名称。不过，由于作用域的原因，这可能不是必需的，具体取决于稍后如何使用/编译 lambda 表达式。

使用类型类，我们可以将其推广为 n 元函数的

convert

函数：

class Convertible t d where
  convert :: Int -> t -> Exp d

instance Convertible (Exp t) t where
  convert :: Int -> Exp t -> Exp t
  convert _ = id

instance (Convertible b c) => Convertible (Exp a -> b) (a -> c) where
  convert :: Int -> (Exp a -> b) -> Exp (a -> c)
  convert varCount f = Lambda var . convert (varCount + 1) . f $ Var var
    where
      var = "v" ++ show varCount

这已经很好了，但会导致一些不明确的类型，因为我们将

c

声明为自由类型变量，因此理论上可能存在多个用于转换函数类型的实例（本质上，

c

不是由

Exp a -> b

，这里）。

作为此问题的解决方案，您可以使用封闭类型族来确定

c

：

type family Dropped a :: Type where
  Dropped (Exp a -> b) = a -> Dropped b
  Dropped (Exp t) = t

所以，例如：

Dropped (Exp Int) ~ Int,
Dropped (Exp Int -> Exp String) ~ Int -> String
and
Dropped (Exp a1 -> ... -> Exp an) ~ a1 -> ... -> an

现在我们可以从上面重写我们的类了：

class Convertible t where
  convert :: Int -> t -> Exp (Dropped t)

instance Convertible (Exp t) where
  convert :: Int -> Exp t -> Exp t
  convert _ = id

instance (Convertible b) => Convertible (Exp a -> b) where
  convert :: Int -> (Exp a -> b) -> Exp (a -> Dropped b)
  convert varCount f = Lambda var . convert (varCount + 1) . f $ Var var
    where
      var = "v" ++ show varCount

现在我们可以方便地转换 AST 的函数了：

ghci> :{
ghci| fstE :: Exp a -> Exp b -> Exp a
ghci| fstE x _ = x
ghci| :}
ghci> convert 0 fstE
Lambda "v0" (Lambda "v1" (Var "v0"))

注1

上面的实现并不涵盖所有带有我们的AST表达式的函数，而是以下形式的函数

Exp t1 -> ... -> Exp tn

但是可以添加更多类型的功能。

注2

根据 DSL 的实现/设计，最好直接从函数转换为生成语言的 AST，跳过中间的 lambda 演算。这甚至可以帮助对 Haskell 的函数进行咖喱化，而这些函数始终是咖喱化的。

注3

您必须启用许多扩展才能运行上面的代码。这些应该足够了：

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE InstanceSigs #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TypeFamilies #-}

我希望这实际上可以帮助您解决您所描述的问题。