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

Question

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

Бесплатная монада?

Термин "свободная монада" регулярно появляется, когда обсуждаются монады для AST. Но свободная монада опирается на Functorfmap для свободного строительства и 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, что угодно... A render функция, подобная приведенной выше, затем отображает достоверно правильный AST на целевой язык.

Обновления

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

Answer 1

Я не уверен, что весь этот подход - хорошая идея (хотя на самом деле я несколько раз делал что-то подобное сам).

Обратите внимание, что монады как Blaze.MarkupM, HaTeX.LaTeXM и т. д. на самом деле не так уж много монады Они на самом деле просто моноиды, которые хотят получить доступ к монадным комбинаторам do нотации, но он также позволяет размещать монадные трансформаторы сверху, что может иметь некоторый смысл). То есть они только специализированные Writer монады!
На данный момент вы действительно делаете то же самое; если это то, что вы намереваетесь, то, возможно, лучший способ сделать это - просто разработать свой тип как Monoid Tree, а затем посмотрите на структуру Writer Tree монаду и, при желании, рефакторинг ее в TreeM структура данных. (HaTeX не делает этого, но сохраняет LaTeX а также LaTeXM отдельные типы только с общим интерфейсом классов, что, возможно, является более чистым подходом, хотя может быть не оптимальным для производительности.)

Результат будет довольно похож Blaze.MarkupM / структура у вас сейчас. Я мог бы обсудить ваши индивидуальные вопросы, но на самом деле, на все они можно ответить, просто посмотрев, как тип изоморфен монаде писателя.

---

На самом деле вам не нужно Monad экземпляр вообще использовать do, в качестве таких:

Prelude> 2 * do 1 + 1
4

Так что если вы просто хотите злоупотреблять do Чтобы избежать скобок в древовидной структуре, но на самом деле нет разумного способа сохранения привязываемых переменных в вашей структуре, не пишите ни одного экземпляра монады. Этот экземпляр нужен только для 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."

Вопрос о том, является ли это еще большим злоупотреблением синтаксисом, чем определение экземпляра "не слишком много монады", спорен. ИМО, если вы определите такой экземпляр монады, вы должны сразу превратить его в монадный преобразователь, например HaTeX делает, потому что это также дает возможность включить IO действия в вашей сборке AST (например, для жесткого включения внешних исходных файлов).

---

Все это говорит: для вашего приложения, возможно, имеет смысл иметь Monad Например, это не просто "засахаренный моноид", а фактически полезные переменные. Эта функция не применима к blaze, но, конечно, для языка C++/Python/JavaScript, такого как AST, и это может быть весьма полезным, поскольку обеспечивает определение переменных перед использованием, прямо в синтаксисе 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

Answer 2

Путь, который я выбрал с этим Append кодировка AST кажется тупиком, поэтому я углубился в свободные монады. Вот результат:

Свободная монада хорошо подходит для такого рода проблем. Бесплатные монады позволяют отделить "логику" программы от ее эффектов. АСТ попадают в эту модель. В этом примере "логика" - это AST, а эффект - просто красивая печать.

В более общем смысле "эффект" может означать анализ, тестирование (например, пробные прогоны), запуск пробных отпечатков, приятную печать, сжатие,... и, конечно же, фактическое выполнение.

О свободных монадах написано много, вот несколько полезных ресурсов для начала:

• "Почему свободные монады имеют значение" Габриэля Гонсалеса
• "Что такое шаблон" Free Monad + Interpreter "?" (Вопрос SE)
• "Навигация и модификация AST, построенных на Free monad в Haskell" (вопрос SE)

Теперь, используя Control.Monad.Free решение будет выглядеть так:

{-# LANGUAGE DeriveFunctor #-}
module Main where

import           Control.Monad.Free
import           Data.Monoid        ((<>))
import           Data.String.Utils  (rstrip)

type NumberOfBits = Word
type VariableName = String

data Type = UInt NumberOfBits
        | Int NumberOfBits
        | Void
        deriving Eq

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 AST n = Variable Type VariableName n                -- variable declaration
            | Function Type VariableName (Free AST ()) n -- function declaration
            | Comment String n                           -- a comment
            | PlaceHolder String n                       -- a placeholder with @name holds holds more code
            | End                                        
            deriving (Eq, Show, Functor)

end :: Free AST ()
end = liftF End -- is exactly Pure ()

variable :: Type -> VariableName -> Free AST ()
variable y n = liftF (Variable y n ())

function :: Type -> VariableName -> Free AST () -> Free AST ()
function t n p = liftF (Function t n p ())

placeHolder :: String -> Free AST ()
placeHolder n = liftF (PlaceHolder n ())

comment :: String -> Free AST ()
comment c = liftF (Comment c ())

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

render :: Free AST r -> String
render (Free (Variable y n next))   = "Variable " <> show y <> " " <> show n <> "\n" <> render next
render (Free (Function t n f next)) = "Function \"" <> n <> "\" returning " <> show t <> ":\n"
                                    <> indent (render f) <> "\n" <> render next
render (Free (Comment c next))      = "//  " <> c <> "\n" <> render next
render (Free (PlaceHolder s next))  = "PlaceHolder \"" <> s <> "\"\n" <> render next
render (Free End)                   = "end"
render (Pure r)                     = "return\n"

code :: Free AST ()
code = do
    placeHolder "includefiles"
    variable uint8 "i"
    variable int8 "j"
    function Void "f" $ do
        comment "This is a function!"
        variable (Int 8) "local_i"

sub :: AST (Free AST b) -> Free AST b
sub (Variable t n next) = do
    variable t n
    next
sub (Function t n f next) = do
    function t n f
    next
sub (Comment c next) = do
    comment c
    next
sub (PlaceHolder s next) = do
    comment "placeholder"
    next

main :: IO ()
main = do
    putStrLn $ render code
    putStrLn "-- Apply subst\n"
    putStrLn $ render (iterM sub code)

Не все это должно быть так четко прописано. Часть шаблона может быть удалена с помощью Control.Monad.Free.TH,

Control.Monad.Free В некотором смысле это каноническая реализация, но цепочечная структура данных означает квадратичную сложность некоторых операций. Об этом говорил сам автор Эд Кметт в Control.Monad.Free.Churchгде используется другая кодировка. См. Бесплатный тест монады для тестов и указателей на другие бесплатные реализации монады.

Выходя за пределы свободных монад, бездонные монады формализуют интерпретатора и его связь с "логикой". См., Например, "Бесплатно для DSL, бесплатно для переводчиков" Дэвида Лейнга.