如何在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 表达式。

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

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 #-}

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