13

オンラインで読んだ参考文献に基づいて Free モナドを使用して AST を構築しようとしています。

これらの種類の AST を実際に使用することについていくつか質問があります。それを次の例にまとめました。

私の言語で次のコマンドが許可されているとします。

{-# LANGUAGE DeriveFunctor #-}

data Command next
  = DisplayChar Char next
  | DisplayString String next
  | Repeat Int (Free Command ()) next
  | Done
  deriving (Eq, Show, Functor)

Free モナドのボイラープレートを手動で定義します。

displayChar :: Char -> Free Command ()
displayChar ch = liftF (DisplayChar ch ())

displayString :: String -> Free Command ()
displayString str = liftF (DisplayString str ())

repeat :: Int -> Free Command () -> Free Command ()
repeat times block = liftF (Repeat times block ())

done :: Free Command r
done = liftF Done

これにより、次のようなプログラムを指定できます。

prog :: Free Command r
prog =
  do displayChar 'A'
     displayString "abc"

     repeat 5 $
       displayChar 'Z'

     displayChar '\n'
     done

ここで、プログラムを実行したいと思います。これは非常に単純に思えます。

execute :: Free Command r -> IO ()
execute (Free (DisplayChar ch next)) = putChar ch >> execute next
execute (Free (DisplayString str next)) = putStr str >> execute next
execute (Free (Repeat n block next)) = forM_ [1 .. n] (\_ -> execute block) >> execute next
execute (Free Done) = return ()
execute (Pure r) = return ()

と

λ> execute prog
AabcZZZZZ

わかった。それはそれでいいのですが、今度は自分の AST について学び、それに変換を実行したいと思います。コンパイラでの最適化のように考えてください。

簡単なものを次に示します。Repeatブロックにコマンドしか含まれていない場合DisplayChar、全体を適切なDisplayString. repeat 2 (displayChar 'A' >> displayChar 'B')つまり、 で変身したいdisplayString "ABAB"。

これが私の試みです：

optimize c@(Free (Repeat n block next)) =
  if all isJust charsToDisplay then
    let chars = catMaybes charsToDisplay
    in
      displayString (concat $ replicate n chars) >> optimize next
  else
    c >> optimize next
  where
    charsToDisplay = project getDisplayChar block
optimize (Free (DisplayChar ch next)) = displayChar ch >> optimize next
optimize (Free (DisplayString str next)) = displayString str >> optimize next
optimize (Free Done) = done
optimize c@(Pure r) = c

getDisplayChar (Free (DisplayChar ch _)) = Just ch
getDisplayChar _ = Nothing

project :: (Free Command a -> Maybe u) -> Free Command a -> [Maybe u]
project f = maybes
  where
    maybes (Pure a) = []
    maybes c@(Free cmd) =
      let build next = f c : maybes next
      in
        case cmd of
          DisplayChar _ next -> build next
          DisplayString _ next -> build next
          Repeat _ _ next -> build next
          Done -> []

GHCI で AST を観察すると、これが正しく機能していることがわかります。

λ> optimize $ repeat 3 (displayChar 'A' >> displayChar 'B')
Free (DisplayString "ABABAB" (Pure ()))


λ> execute . optimize $ prog
AabcZZZZZ
λ> execute prog
AabcZZZZZ

しかし、私は幸せではありません。私の意見では、このコードは反復的です。AST を調査するたびに AST をトラバースする方法を定義するかproject、ビューを提供する my のような関数を定義する必要があります。ツリーを変更したいときは、これと同じことをしなければなりません。

だから、私の質問：このアプローチは私の唯一の選択肢ですか？大量のネストを処理せずに AST でパターン マッチを行うことはできますか? 一貫した一般的な方法でツリーをトラバースできますか (ジッパー、トラバーサブルなど)。ここで一般的に取られるアプローチは何ですか？

ファイル全体は次のとおりです。

{-# LANGUAGE DeriveFunctor #-}

module Main where

import Prelude hiding (repeat)

import Control.Monad.Free

import Control.Monad (forM_)
import Data.Maybe (catMaybes, isJust)

main :: IO ()
main = execute prog

prog :: Free Command r
prog =
  do displayChar 'A'
     displayString "abc"

     repeat 5 $
       displayChar 'Z'

     displayChar '\n'
     done

optimize c@(Free (Repeat n block next)) =
  if all isJust charsToDisplay then
    let chars = catMaybes charsToDisplay
    in
      displayString (concat $ replicate n chars) >> optimize next
  else
    c >> optimize next
  where
    charsToDisplay = project getDisplayChar block
optimize (Free (DisplayChar ch next)) = displayChar ch >> optimize next
optimize (Free (DisplayString str next)) = displayString str >> optimize next
optimize (Free Done) = done
optimize c@(Pure r) = c

getDisplayChar (Free (DisplayChar ch _)) = Just ch
getDisplayChar _ = Nothing

project :: (Free Command a -> Maybe u) -> Free Command a -> [Maybe u]
project f = maybes
  where
    maybes (Pure a) = []
    maybes c@(Free cmd) =
      let build next = f c : maybes next
      in
        case cmd of
          DisplayChar _ next -> build next
          DisplayString _ next -> build next
          Repeat _ _ next -> build next
          Done -> []

execute :: Free Command r -> IO ()
execute (Free (DisplayChar ch next)) = putChar ch >> execute next
execute (Free (DisplayString str next)) = putStr str >> execute next
execute (Free (Repeat n block next)) = forM_ [1 .. n] (\_ -> execute block) >> execute next
execute (Free Done) = return ()
execute (Pure r) = return ()

data Command next
  = DisplayChar Char next
  | DisplayString String next
  | Repeat Int (Free Command ()) next
  | Done
  deriving (Eq, Show, Functor)

displayChar :: Char -> Free Command ()
displayChar ch = liftF (DisplayChar ch ())

displayString :: String -> Free Command ()
displayString str = liftF (DisplayString str ())

repeat :: Int -> Free Command () -> Free Command ()
repeat times block = liftF (Repeat times block ())

done :: Free Command r
done = liftF Done
4

4 に答える 4

1

あなたは確かにこれをもっと簡単に行うことができます. 最初のパスでは完全な最適化を実行しないため、まだいくつかの作業が必要ですが、2 回のパスの後、サンプル プログラムが完全に最適化されます。その演習はあなたに任せますが、それ以外の場合は、実行したい最適化のパターン マッチングを使用して非常に簡単に行うことができます。それはまだ少し繰り返しですが、あなたが持っていた複雑さの多くを取り除きます:

optimize (Free (Repeat n block next)) = optimize (replicateM n block >> next)
optimize (Free (DisplayChar ch1 (Free (DisplayChar ch2 next)))) = optimize (displayString [ch1, ch2] >> next)
optimize (Free (DisplayChar ch (Free (DisplayString str next)))) = optimize (displayString (ch:str) >> next)
optimize (Free (DisplayString s1 (Free (DisplayString s2 next)))) = optimize (displayString (s1 ++ s2) >> next)
optimize (Free (DisplayString s (Free (DisplayChar ch next)))) = optimize (displayString (s ++ [ch]) >> next)
optimize (Free (DisplayChar   ch next)) = displayChar ch >> optimize next
optimize (Free (DisplayString str next)) = displayString str >> optimize next
optimize (Free Done) = done
optimize c@(Pure r) = c

私がしたのはrepeat n (displayChar c)、displayChar c1 >> displayChar c2、displayChar c >> displayString s、displayString s >> displayChar c、およびのパターンマッチだけでしたdisplayString s1 >> displayString s2。実行できる最適化は他にもありますが、これは非常に簡単で、他のものをスキャンすることに依存せず、再帰的に最適化する AST を繰り返しステップ オーバーするだけです。

于 2014-06-11T22:11:17.693 に答える