haskell - 带有 HOAS 的复制器解释器

Question

在 these 的第 2.3 节中关于 DSL 无标记最终解释器的非常酷的注释，Oleg Kiselyov 展示了如何解决解析一次序列化 DSL 表达式并解释多次的问题。

简单地说，他展示了类型的“假一流多态性”

newtype Wrapped = Wrapped (∀ repr. ExpSYM repr ⇒ repr)
fromTree :: String → Either ErrMsg Wrapped

并不令人满意，因为它不可扩展:对于 上的每组 约束，我们必须有一个不同的 Wrapper/fromTree >代表。因此我倾向于使用他的复制解释器解决方案。这个问题是关于如何将解释器与 HOAS 一起使用。

具体而言，请考虑以下语言作为目标语言绑定(bind):

class Lam repr where
  lam :: (repr a -> repr b) -> repr (a -> b)
  app :: repr (a -> b) -> repr a -> repr b

我无法为我的复制器解释器提供 Lam 类的声音实例。这是我所拥有的:

data Dup repr1 repr2 a = Dup {unDupA :: repr1 a, unDupB :: repr2 a}

instance (Lam repr1, Lam repr2) => Lam (Dup repr1 repr2) where
  lam f = Dup (lam $ unDupA . f . flip Dup undefined) (lam $ unDupB . f . Dup undefined)
  app (Dup fa fb) (Dup a b) = Dup (app fa a) (app fb b)

是否有某种方法可以为类似我的 Dup 类型提供 Lambda 的递归实例，且不涉及 undefined ？

我还尝试使用 this paper 中更强大的 lam 版本，它允许使用 HOAS 的 monadic 解释器，尽管我不知道它如何帮助我使用 Dup 实例。使用任一版本的 lam 和 HOAS 的解决方案都会很棒!

<小时/>

_{*:Oleg 展示了如何使用 de Bruijn 索引定义声音实例，但我对 HOAS 的解决方案非常感兴趣。}

<sub>
    class Lam repr where
      lam :: repr (a,g) b -> repr g (a -> b)
      app :: repr g (a->b) -> repr g a -> repr g b

    data Dup repr1 repr2 g a = Dup{d1:: repr1 g a, d2:: repr2 g a}

    instance (Lam repr1, Lam repr2) => Lam (Dup repr1 repr2) where
      lam (Dup e1 e2) = Dup (lam e1) (lam e2)
      app (Dup f1 f2) (Dup x1 x2) = Dup (app f1 x1) (app f2 x2)
</sub>

Answer 1

这是不可能的。

为了展示一个示例，我将首先创建一个非常简单的 Lam 实例:

newtype Id a = Id a

instance Lam Id where
    lam (Id f) = Id (\x -> let Id r = f x in r)
    app (Id f) (Id x) = Id (f x)

现在我将创建一个在 Dup 上运行的函数:

f :: Dup Id Id Int -> Dup Id Id Int
f (Dup (Id x) (Id y)) = Dup (Id x*y) (Id y)

我可以从 Lam 实例执行 lam f::Dup Id Id (Int -> Int)。这可能看起来像

Dup (Id (\x -> x*y)) (Id (\y -> y))

无法实现，因为 y 无法从 x-lambda 中获得。 (在这里使用 undefineds 替换 y 为 undefined，只要它不能正常工作就会抛出运行时错误。)这种情况并不罕见:每当您在另一个结果中使用一个变量时，就会发生这种情况。

我不太清楚你对更强的 Monad 通用化的要求是什么，但这种情况也发生在其他 Monad 上:例如， Maybe，您无法将以下内容转换为 Maybe (Int -> Int)，因为它取决于给定的值:

f :: Maybe Int -> Maybe Int
f m = m >>= \x -> if x > 5 then Just x else Nothing

(您可以对其使用 fromJust 并希望没有人这样做，但这与 undefined 解决方案相同。)

不过，如果函数需要查看其他变量，则 undefined 只会抛出错误。如果您绝对确定它永远不会在类似的东西上运行(例如，您将展开/创建限制为经过广泛测试的隐藏模块)，那么 undefined 方式将起作用。

对此还有一个建议:使用更详细的错误消息而不是未定义，以防万一出现问题。 p>