使用 Haskell monad“do”表示法定义语法树

Question

我正在尝试构建一个抽象语法树，允许使用 monaddo表示法进行定义，如下所示：

ast = do
    Variable uint8 "i"
    Function Void "f" $ do
        Variable uint8 "local_y"
        Comment "etc. etc."

我在这里展示的结构是从Text.Blaze.Html中收集的，它用于定义 HTML 树。

问题分散在以下各个部分。主要问题是如何正确地做到这一点。当然，任何有助于理解此结构的输入都将受到高度赞赏。

因此，首先，这是一个虽小、有缺陷但“有效”的示例。它是一个语法树，其中包含特定类型的变量和函数的声明、注释行以及用于替换的占位符声明：

{-# LANGUAGE ExistentialQuantification #-}
module Question
where

import           Control.Applicative
import           Data.Monoid         (Monoid, (<>))
import           Data.String.Utils   (rstrip)

type NumberOfBits = Word
type VariableName = String

data Type = UInt NumberOfBits
          | Int NumberOfBits
          | Void

uint8 = UInt 8
int8 = Int 8

instance Show Type where
    show (UInt w) = "uint" <> show w
    show (Int w)  = "int" <> show w
    show Void     = "void"

data TreeM a = Variable Type VariableName            -- variable declaration
             | Function Type VariableName (TreeM a)  -- function declaration
             | Comment String                        -- a comment
             | PlaceHolder String                    -- a placeholder with                  
             | forall b. Append (TreeM b) (TreeM a)  -- combiner
             | Empty a                               -- needed for what?

type Tree = TreeM ()

subTreeOf :: TreeM a -> a
subTreeOf (Variable _ _)   = undefined
subTreeOf (Function _ _ t) = subTreeOf t
subTreeOf (Comment _)      = undefined
subTreeOf (Empty t)        = t

instance Monoid a => Monoid (TreeM a) where
    mempty = Empty mempty
    mappend = Append
    mconcat = foldr Append mempty

instance Functor TreeM where
    fmap f x = x `Append` (Empty (f (subTreeOf x))) -- fmap :: (a -> b) -> f a -> f b

instance Applicative TreeM where
    pure x = Empty x
    (<*>) x y = (x `Append` y) `Append` (Empty (subTreeOf x (subTreeOf y)))  -- (<*>) :: f (a -> b) -> f a -> f b
    (*>) = Append

instance Monad TreeM where
    return x = Empty x
    (>>) = Append             -- not really needed: (>>) would default to (*>)
    t >>= f = t `Append` (f (subTreeOf t))

indent :: String -> String
indent s = rstrip $ unlines $ map ("    "<>) (lines s)

render :: TreeM a -> String
render (Variable y n)   = "Variable " <> (show y) <> " " <> show n
render (Function r n t) = "Function" <> " " <> n <> " returning " <> (show r) <> ":\n" <> indent (render t)
render (PlaceHolder n)  = "Placeholder \"" <> n <> "\""
render (Append t t')    = (render t) <> "\n" <> (render t')
render (Empty _)        = ""

-- |In input tree t substitute a PlaceHolder of name n' with the Tree t'
sub :: TreeM a -> (String, TreeM a) -> TreeM a
sub t@(PlaceHolder n) (n', t') = if n == n' then t' else t
sub (Function y n t) s         = Function y n (sub t s)
--sub (Append t t') s            = Append (sub t s) (sub t' s)  -- Error!
sub t _                        = t

code :: Tree
code = do
    Variable uint8 "i"
    Variable int8 "j"
    Function Void "f" $ do
        Comment "my function f"
        Variable int8 "i1"
        Variable int8 "i2"
    PlaceHolder "the_rest"

main :: IO ()
main = do
    putStrLn $ render code
    putStrLn "\nNow apply substitution:\n"
    putStrLn $ render (sub code ("the_rest", Comment "There is nothing here"))

这是（应该是）定义复杂树结构的一种非常巧妙的方法。特别是，这应该是语法上噪音最小、用户友好的定义语法树的方法。

一般来说，我很难理解ain的确切含义TreeM a。我认为a可以是任何类型Variable、Function、PlaceHolder等。

我注意到一些让我觉得奇怪的事情：

1. 和 参数forall b. Append (TreeM b) (TreeM a)的顺序似乎颠倒了。无论如何，在求和类型中使用存在量词看起来很奇怪。如果我理解正确的话，它定义了一系列构造函数。TreeM aTreeM bAppendTreeM
2. 在 和 所需的所有功能中Functor，Applicative唯一Monad实际使用的功能是 monad >>。（这表明一个免费的 monad 可能是完成这项工作的正确工具。）实际上我从来没有想到 do 表示法使用了运算符>>并且可以使用这个事实。
3. 必须undefined使用 insubTreeOf才能使函数完整。

正如已经指出的，上面的例子是有缺陷的：部分结构不适合 AST：

4. 的定义Empty对于 HTML 树来说是有意义的，它用于空标签，如<br />. 但对于 AST 来说这是没有意义的。它保持原样是为了保持实施Applicative正常Functor运行。
5. Functor同样，和的实现Applicative对于 HTML 树可能有意义，但对于 AST 则不然。即使对于 HTML，我也不太明白 thefmap和 applicative的目的<*>。两者都通过下推节点并添加Empty类型来扩展树。我不太明白 HTML 树上的哪种自然转换代表什么。

我很惊讶subTreeOf x (subTreeOf y)应用程序的定义<*>实际上是正确的语法，或者是否存在隐式>>？

AST 转换

对 AST 应用转换是很自然的。它PlaceHolder充当应用转换的小玩具。这里的函数sub只有部分实现，应该用注释替换占位符“the_rest”。然而，必要的 sub (Append t t') s = Append (sub t s) (sub t' s)不会编译，预期类型s是(String, TreeM b)，实际类型是(String, TreeM a)。sub :: TreeM a -> (String, TreeM b) -> TreeM a另一方面，将类型更改为 会破坏 的定义sub p@(PlaceHolder n)，现在我陷入困境。

事实上，这不sub正是fmapAST 应该做的吗？

自由单子？

当讨论 AST 的 monad 时，经常会出现“自由 monad”这个术语。但是 free monad 依赖于 来Functor fmap进行自由构造，并且fmap这里显示的内容对于 AST 来说是不够的。一旦fmap确定了正确的内容，自由 monad 就应该完成剩下的工作——也许吧。

fmap

看来正确fmap是成功的关键，而且正确<*>可能会变得更加明显。

用例

可以使用 来编写循环forM_，这是构建 AST 重复部分的好方法：

forM_ ["you", "get", "the", "idea"] $ \varName -> do
    Variable uint8 varName

有条件的部分可以使用when、unless等。

when hasCppDestructor $ do
    Comment "We need the destructor"
    Function NoReturnType "~SomeClass" $ do
        ...

正如第一个答案中指出的那样，语义分析（例如确保正确的声明顺序）也是可能的。

视觉线索：我喜欢的另一件事是，在上面显示的结构中，控制结构（例如 if-then-elseforM_等）以小写字母开头，而 AST 行以大写字母开头。

背景

关于这个方向的几句话可能是这样的：这个想法是使用一个足够好的嵌入式 DSL，它允许自动定义一个 AST，它相当抽象地表示一个需要用 C、C++、Python 实现的复杂的 FSM， Java、Go、Rust、Javascript，等等......然后，render像上面这样的函数会将可证明正确的 AST 映射到目标语言。

更新

• 注意，>>不是默认为*>，而是为m >> k = m >>= (\_ -> k)！

Answer 1

我不确定这整个方法是否是一个好主意（尽管，实际上我自己也曾多次做过类似的事情）。

请注意，像 等这样的单子Blaze.MarkupM并不是HaTeX.LaTeXM真正的单子。它们实际上只是想要访问单子组合器的幺半群do（主要是为了滥用符号，但它也允许在顶部使用堆栈单子变压器，这可能很有意义）。即，它们只不过是专门的Writer单子！
此刻，你确实在做同样的事情；如果这就是您的意图，那么最好的方法可能是将您的类型设计为 a Monoid Tree，然后查看Writer Treemonad 的结构，如果需要，将其重构为TreeM数据结构。（HaTeX 不会这样做，而是仅使用公共类接口来保留LaTeX和LaTeXM分离类型，这可以说是一种更干净的方法，尽管它可能不是性能最佳的。）

结果将非常像Blaze.MarkupM/你现在拥有的结构。我可以讨论您的个人问题，但实际上，只需查看类型与 writer monad 的同构情况即可回答所有这些问题。

Monad实际上你根本不需要实例来使用do，如下所示：

Prelude> 2 * do 1 + 1
4

因此，如果您只是想滥用do以避免树布局中的括号，但实际上没有明智的方法在结构中存储可绑定变量，请考虑不编写任何 monad 实例。仅具有多行的do块需要该实例，但如果这些行都没有绑定任何变量，那么您始终可以将隐式替换为显式，例如>><>

    Function Void "f" $ do
        Variable uint8 "local_y"
     <> Comment "etc. etc."

唯一的问题确实是：这些行不能包含$运算符，因为它的优先级低于<>. 避免这种情况的一个巧妙方法是观察这一点($) = id，因此您可以将示例编写为

ast = do
    Variable uint8 "i"
 <> Function Void "f" `id`do
        Variable uint8 "local_y"
     <> Comment "etc. etc."

这是否比定义一个不太单子的实例更滥用语法是值得商榷的。IMO，如果您定义了这样一个 monad 实例，您应该立即将其设为monad Transformer，就像HaTeX这样做一样，因为这还提供了允许在 AST 构建中包含IO操作的选项（例如，硬包含外部源文件）。

综上所述：对于您的应用程序来说，拥有一个不仅仅是Monad“加糖的幺半群”的实例实际上可能是有意义的，而且实际上以一种有用的方式绑定变量。这个功能不适用于，但肯定适用于像 AST 这样的 C++/Python/JavaScript 语言，并且它可能非常有用，因为它确保变量在使用之前就在 Haskell 语法中定义。而不是你的例子，你会写blaze

ast = do
    i <- variable uint8
    Function Void "f" $ do
        local_y <- variable uint8
        Comment "etc. etc."

这些变量实际上只是根据状态变量选择的编号标识符。

实现大概是这样的：

type VariableName = Int

data TreeS = Variable Type VariableName
           | Function Type VariableName TreeS
           | Comment String
           | PlaceHolder String
           | Append TreeS TreeS
           | Empty
instance Monoid where (<>) = Append

newtype TreeT m a
    = TreeT { runTreeM :: StateT VariableName (WriterT TreeS m) a }
    deriving (Functor, Applicative, Monad)

variable :: Type -> TreeT m VariableName
variable typ = TreeT $ do
   i <- get
   lift . tell $ Variable typ i
   put $ i+1
   return i