Используйте нотацию do монады Haskell для определения синтаксического дерева

Я пытаюсь построить абстрактное синтаксическое дерево, которое позволяет определение с использованием нотации монады 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 и т. д.

Отмечу несколько вещей, которые кажутся мне странными:

1. В forall b. Append (TreeM b) (TreeM a) порядок аргументов TreeM a и TreeM b для Append кажется обратным. В любом случае использование квантора существования в суммовом типе выглядит странно. Если я правильно понимаю, он определяет семейство конструкторов для TreeM.
2. Из всех функций, требуемых Functor, Applicative и Monad, реально используется только монада >>. (Это указывает на то, что свободная монада может быть подходящим инструментом для этой работы.) На самом деле мне никогда не приходило в голову, что нотация do использует оператор >> и что этот факт можно использовать.
3. undefined необходимо использовать в subTreeOf, чтобы сделать функцию общей.

Как уже отмечалось, приведенный выше пример ошибочен: части конструкции не подходят для AST:

4. Определение Empty имеет смысл для деревьев HTML, оно используется для пустых тегов, таких как <br />. Но для АСТ это не имеет смысла. Он был оставлен как есть, чтобы реализации Applicative и Functor работали.
5. Точно так же реализации Functor и Applicative могут иметь смысл для деревьев HTML, но не для AST. Даже для HTML я не совсем понимаю назначение fmap и аппликативного <*>. Оба расширяют дерево, опуская узел и добавляя тип Empty. Я не совсем понимаю, какое естественное преобразование HTML-деревьев это представляет.

Я удивлен, что subTreeOf x (subTreeOf y) в определении аппликативного <*> на самом деле является правильным синтаксисом, или есть неявное >>?

Трансформации АСТ

Естественно применять преобразования к 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 именно то, чем должно быть fmap для AST?

Свободная монада?

Термин «свободная монада» регулярно всплывает, когда обсуждаются монады для AST. Но свободная монада опирается на Functor fmap для свободной конструкции, а показанное здесь fmap не подходит для AST. Как только правильное fmap определено, свободная монада должна сделать все остальное - возможно.

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-else, forM_ и т. д., начинаются с нижнего регистра, тогда как строки AST начинаются с верхнего регистра.

Задний план

Несколько слов о том, к чему это, возможно, ведет: Идея состоит в том, чтобы использовать достаточно хороший встроенный DSL, который позволяет автоматически определять AST, который довольно абстрактно представляет, скажем, запутанный FSM, который необходимо реализовать на C, C++, Python, Java, Go, Rust, Javascript, что угодно... Функция render, подобная приведенной выше, затем сопоставляет достоверно правильный AST с целевым языком.

Обновления

• Обратите внимание, что >> по умолчанию не *>, а m >> k = m >>= (\_ -> k)!