haskell - 带有HOAS的复制器口译员

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

简而言之，他展示了“假一流的多态性”与类型

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

不能令人满意，因为它不可扩展:对于Wrapper上的每组约束，我们都必须使用不同的fromTree / repr。因此，我倾向于使用他的复制器解释器的解决方案。这个问题是关于如何在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)

有没有办法为Lambda类型的不涉及Dup的东西提供undefined的递归实例？

我也尝试过使用this paper中功能更强大的lam，它允许使用HOAS的单语解释器，尽管我没有看到它对Dup实例有什么帮助。一个使用HOAS的lam任一版本的解决方案都很棒!

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

最佳答案

这是不可能的。

为了显示一个示例，我将首先创建一个非常简单的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 -lambda无法使用x，因此无法执行。 (在这里，使用undefined s将y替换为undefined，只要运行不正常，就会抛出运行时错误。)
这不是罕见的情况:只要您在另一个结果中使用其中一个变量，就会发生这种情况。

我不确定您使用强壮的Monad -generalized编码的要求是什么，但是其他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方式将起作用。

仅此一项建议:使用更详细的error消息而不是undefined，以防万一出现问题。

关于haskell - 带有HOAS的复制器口译员，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43648182/