带有RValue LValue问题的无标签最终DSL

Question

类型化的无标签最终解释器是免费的monad方法的一种有趣替代方法。

但是，即使使用无ToyLang标签的最终样式中的一个非常简单的示例，仍然会弹出模糊的类型变量。

ToyLang 是一个EDSL，应读取以下内容：

toy :: ToyLang m => m (Maybe Int)
toy = do
    a <- int "a"       -- declare a variable and return a reference
    a .= num 1         -- set a to 1
    a .= a .+ num 1    -- add 1 to a
    ret a              -- returns a

当然，总的目标是在此EDSL中尽可能多地使用Haskell类型系统，并使用多态来实例化各种解释器。

如果不是用于(.+)导致左值和右值概念的运算，那么一切都会很好：赋值运算符(.=)的左侧是左值，而右侧是左值或右值。基本思想来自于“ 强制多态性”中的两个注释，一个用例：

{-# LANGUAGE GADTs #-}

data L -- dummies for Expr (see the comments for a better way)
data R

-- An Expr is either a lvalue or a rvalue
data Expr lr where
    Var :: String -> Maybe Int -> Expr L
    Num :: Maybe Int -> Expr R

-- tagless final style
class Monad m => ToyLang m where
    int :: String -> m (Expr L)             -- declare a variable with name
    (.=) :: Expr L -> Expr lr -> m (Expr L) -- assignment
    (.+) :: Expr lr -> Expr lr' -> Expr R   -- addition operation - TROUBLE!
    ret :: Expr lr -> m (Maybe Int)         -- return anything
    end :: m ()                             -- can also just end

漂亮的“解释器”将像这样开始：

import Control.Monad.Writer.Lazy

-- A ToyLang instance that just dumps the program into a String
instance ToyLang (Writer String) where
    int n = do
        tell $ "var " <> n <> "\n"
        return (Var n Nothing)
    (.=) (Var n _) e = do
        tell $ n <> " = " <> toString e <> "\n"
        return $ Var n (toVal e)
    ...

小帮手toString必须从GADT的加法中找出值：

toString :: Expr lr -> String
toString (Var n mi) = n
toString (Num i)    = show i

聪明的构造函数num很简单

num :: Int -> Expr R
num = Num . Just

这(.+)很麻烦，原因有两个：

1. (.+)不在monad中，m因为否则我们将无法编写a .= a + num 1，但Writer String例如，需要monad才能tell。

2. 类型检查器将阻止由创建的歧义类型(.+) :: Expr lr -> Expr lr' -> Expr R。显然，如果没有进一步的注释，它将无法确定该实例的含义。但是a .= a .+ num 1，如果有可能，对这样的子句进行注释将使DSL非常笨拙。

使类型起作用的一种方法是(.+)在某种程度上进入monad，并且(.=)：

 class Monad m => ToyLang m where
    ...
    (.=) :: Expr L -> m (Expr lr) -> m (Expr L)
    (.+) :: Expr lr -> m (Expr lr') -> m (Expr R)
    ...

尽管这一切都很奇怪：

• (.=)并且(.+)是在他们需要的单子不对称m和他们没有。

• 即使在Writer Stringmonad中，我也不得不执行整数算术以创建m (Expr R)返回类型，尽管实际上并不需要结果

• 实例化ToyLang一个Writer String看起来整洁，但并没有真正做的工作。a .= a .+ num 1不能这样漂亮地打印，因为a .+ num 1在之前进行评估（因此打印）.=。

我觉得这完全是错误的。有一个更好的方法吗？

该ToyLang示例的源代码在github上。

参考文献：

• Oleg Kiselyov打字的无标签最终口译员
• Impredicative多态性，用例由augustss
• 为什么免费Monads很重要 Gabriel Gonzalez
• JP Royo Sales 在Haskell中进行无标签最终编码