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

Question

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

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"))

这是（应该）定义复杂树结构的一种真正巧妙的方法。特别是，这应该是定义语法树的语法上最不嘈杂，用户友好的方法。

通常，我很难理解 a中 TreeM a的确切含义。我看 a的方式可以是 Variable， Function， PlaceHolder等任何类型。

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


在 forall b. Append (TreeM b) (TreeM a)中， TreeM a和 TreeM b自变量的顺序似乎相反。无论如何，总和类型中存在量词的使用看起来很奇怪。如果我正确理解这一点，它将为 Append定义一系列构造函数。
在 TreeM， Functor和 Applicative所需的所有功能中，唯一实际使用的是monad Monad。 （这表明一个免费的monad可能是完成此工作的正确工具。）实际上，我从来没有想到do表示法使用了 >>运算符并且可以使用此事实。
为了使功能合计，必须在 >>中使用 undefined。


如前所述，上面的示例有缺陷：构造的某些部分不适用于AST：


subTreeOf的定义对于HTML树很有意义，它用于 Empty这样的空标记。但是对于AST，这没有任何意义。保持 <br />和 Applicative实现正常工作。
同样， Functor和 Functor的实现可能对HTML树有意义，但对AST没有意义。即使对于HTML，我也不太了解 Applicative和适用性 fmap的目的。两者都通过按下节点并添加 <*>类型来扩展树。我不太明白HTML树上代表了哪种自然转换。


我很惊讶适用的 Empty定义中的 subTreeOf x (subTreeOf y)实际上是正确的语法，还是存在隐式的 <*>？

AST转换

对AST应用转换是很自然的。 >>用作应用转换的小玩具。这里只有部分实现的函数 PlaceHolder应该用注释替换占位符“ the_rest”。必要
sub无法编译，但是 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的定义，现在我陷入了困境。

实际上，这不是AST的 sub p@(PlaceHolder n)到底应该是什么？

免费的monad？

在讨论AST的单子时，经常会弹出“免费单子”一词。但是免费的monad依靠 sub fmap进行免费的构造，此处显示的 Functor不足以用于AST。一旦识别出正确的 fmap，则免费的monad应该执行其余的操作-也许可以。

fmap

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

用例

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

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

有条件的部分可以使用 <*>， forM_等。

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

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

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

背景

关于可能的发展方向，可能需要说几句话：想法是使用足够好的嵌入式DSL，它可以自动定义一个AST，而AST抽象地表示一个复杂的FSM，需要用C，C ++，Python， Java，Go，Rust，Javascript等等...类似于上面的 unless函数然后将可以证明正确的AST映射到目标语言。

更新


请注意， forM_并非默认为 render，而是默认为 >>！

Answer 1

我不确定整个方法是否是一个好主意（尽管我实际上已经做过很多次类似的事情了）。

请注意，诸如Blaze.MarkupM，HaTeX.LaTeXM等的单子并不是真正的单子。它们实际上只是想要访问Monadic组合器的类对象（主要是滥用do表示法，但它也允许在顶部使用堆栈monad转换器，这在一定程度上是有道理的）。也就是说，它们不过是专门的Writer单子。如果您打算这样做，那么最好的方法是将类型设计为Monoid Tree，然后查看Writer Tree monad的结构，如果需要，将其重构为< cc>数据结构。 （HaTeX不会这样做，但是将TreeM和LaTeX的类型保留为单独的类型，而只有一个通用的类接口，这可以说是一种更简洁的方法，尽管它可能不是最佳的性能。）

结果将非常类似于LaTeXM /您现在拥有的结构。我可以讨论您的个人问题，但实际上，只需查看类型对作者单子的同构性就可以回答所有问题。



实际上，使用Blaze.MarkupM完全不需要Monad实例，例如：

Prelude> 2 * do 1 + 1
4

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

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

真正的唯一问题是：这些行不能包含 <>运算符，因为它的优先级低于 $。避免这种情况的一种不错的方法是观察 <>，因此您可以将示例编写为

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

这是否比定义一个不那么单例的实例甚至更滥用语法是有争议的。 IMO，如果您定义了此类monad实例，则应立即将其设置为monad转换器，就像 ($) = id一样，因为它还提供了允许在AST构建中包括 HaTeX操作的选项（例如，硬包含）外部源文件）。



话虽如此：对于您的应用程序来说，拥有一个 IO实例不仅有意义，它实际上是一种有用的方法，它可以绑定变量。这是一项不适用于 Monad的功能，但肯定适用于AST等C ++ / Python / JavaScript语言，并且它非常有用，因为它可以确保在使用之前在Haskell语法内定义变量。而不是您的示例，您将编写

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