12

Typed Tagless Final Interpreters是免费 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 类型系统，并使用多态来实例化各种解释器。

(.+)如果没有导致左值和右值概念的操作，一切都会好起来的：赋值运算符(.=)在其左侧有一个左值，在其右侧有一个左值或右值。基本思想取自Impredicative Polymorphisms, a Use Case中的两条评论：

{-# 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例如，为了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)
    ...

不过，这一切都很奇怪：

  • (.=)并且(.+)在他们需要monad的地方和不需要的地方是不对称的m。

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

  • 实例ToyLang化为 aWriter String看起来很整洁，但并没有真正完成这项工作。a .= a .+ num 1不能如此漂亮地打印，因为a .+ num 1在.=.

我觉得这在某种程度上都是错误的。有一个更好的方法吗？

这个ToyLang例子的源代码在github 上。

参考：

4

0 回答 0