言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella
トップ > なぜ属性文法が重要なのか

なぜ属性文法が重要なのか

http://www.haskell.org/tmrwiki/WhyAttributeGrammarsMatter

問題

属性文法が盛り上がる予感なので、Wikipedia にリンクがあった面白い記事を読む。テーマは、関数型言語は凄いけど、属性文法と組み合わせるともっと凄いという話。例として、ある数列の平均からの差を求める diff という関数が紹介されている。例えば、[1, 2, 3] を与えると、平均は 2 なので [-1.0,0.0,1.0] を返す。素直に Haskell で書くとこんな感じ。

diff0 xs  = map (\x -> x - (avg xs)) xs -- 平均からの差
avg xs   = sum xs / fromIntegral (length xs) -- 平均値

さてこれは気に食わないらしい。なぜかと言うと、sum, length, map で都合三回リストを読む羽目になるから。私は気にしないが、多分ギガとかのデータを処理する際には気になるのだろう。そこで、リストを一度だけ読み込みつつじわじわ求めてみよう。

まずは平均だけじわじわ式に求める。具体的には、[1,2,3] の場合まず最初は 0.0 で、一つ目の 1 を読んだ時は、1 / 1 で、二つ目を読むと (1 + 2) / 2 で、三つ目を読むと (1 + 2 + 3) / 3 のように長さと総和を同時に計算する。著者は foldr が好きみたいだけど、私は末尾再帰の方が好きなのでこんな風に書いてみた。

average :: [Float] -> Float
average xs = average' 0.0 0 xs -- 初期値を設定してサブ関数を呼ぶ

average' :: Float -> Int -> [Float] -> Float
average' sum length []     = sum / fromIntegral length -- リストの最後で平均を返す
average' sum length (x:xs) = average' (x + sum) (1 + length) xs -- じわじわと総和と長さを計算

average を ave の代わりに diff に埋め込めば良いのだが、困った事に平均というのはリストを全部読まないと求まらない。。。という事が続けて記事に書いてあるのだが、この部分は理解できなかった。例題のコードを読んでも少なくとも二度リストを読んでいるようにしか見えない(foldr cons nil xs に (sum / length) を適用する段でリストを作り直しているので map と一緒)。一応転載する。

diff :: [Float] -> [Float]
diff xs = let nil avg = (0.0, 0.0, [])
              cons x fs avg = let (s, l, ds) = fs avg
                              in (s + x, l + 1.0, x - avg : ds)
              (sum, length, ds) = foldr cons nil xs (sum / length)
          in ds

長い前ふりですが、折角効率的に書いたのに最初の定義と比べて随分醜悪になってしまいました。属性文法を使うとこのような定義を美しく書けるというのが著者の主張。ユトレヒト大学属性文法 (UUAG) を利用する。

属性文法

# UUAG インストール方法。ghc 6.8 以降が必要だと思います。
wget http://nix.cs.uu.nl/dist/hut/snapshots/uulib-latest-src.tar.gz
wget http://nix.cs.uu.nl/dist/hut/snapshots/uuagc-latest-src.tar.gz
tar xzvf uulib-latest-src.tar.gz
tar xzvf uuagc-latest-src.tar.gz
cd uulib
ghc --make Setup.hs -o setup -package Cabal
./setup configure
./setup build
./setup install
cd ../uuagc
ghc --make Setup.hs -o setup -package Cabal
./setup configure
./setup build
./setup install

上の例を属性文法で表現してみる。

DATA Root
  | Root  list : List
DATA List
  | Nil
  | Cons  head : Float tail : List

ATTR List [ | | length : Float]
SEM List
  | Nil    lhs.length  = 0.0
  | Cons   lhs.length  = 1.0 + @tail.length

ATTR List [ | | sum : Float]
SEM List
  | Nil    lhs.sum     = 0.0
  | Cons   lhs.sum     = @head + @tail.sum

ATTR List [ avg : Float | | ]
SEM Root
  | Root   list.avg    = @list.sum / @list.length

SEM List
  | Cons   tail.avg    = @lhs.avg

ATTR Root List [ | | res : {[Float]}]
SEM List
  | Nil    lhs.res     = []
  | Cons   lhs.res     = (@head - @lhs.avg) : @tail.res

Diff.ag という名前で以下のテキストを保存後、

$ uuagc -a Diff.ag

で Diff.hs という haskell ファイルに変換される。こ、これは。。。本当に分かりやすいのだろうか？？？例えば最初の Data 宣言は、次のような Haskell の型定義になる。

data Root = Root_Root (List) 
data List = List_Cons (Float) (List) 
          | List_Nil

で、残りの部分で、属性を定義してゆく。詳しくは元記事に書いてあるので、書いてない実行方法だけ書くと次のようになる。

Diff> sem_Root (Root_Root (List_Cons 1 (List_Cons 2 (List_Cons 3 List_Nil))))
[-1.0,0.0,1.0]

構文糖が無いので複雑に感じるが、やってる事は単純だ。ポイントだけ書く。

  • ATTR で属性を宣言する。|| の左に書くと inherited 属性。右に書くと synthesized 属性。
  • SEM で属性の意味を Haskell 擬似構文で定義する。
  • 要素.属性 で値を参照する。ノード自体の参照には lhs を使う。
  • inherited 属性は、親から子に再帰的に定義出来る。
  • synthesized 属性は、子から親に再帰的に定義出来る。
  • 属性文法は、sem_なんとか という関数に変換される。関数の結果は属性の数だけタプルで返る。
  • 直接製関係ない話ですが、Haskell では要素一つのタプルというのは存在しないのでしょうか？属性が一つの場合はタプルになりません。新発見。

属性文法の応用

元々属性文法は、プログラミング言語の解析結果に意味を与える為の発明だそうだが、著者によると関数型言語への影響はそれ以上になる予定らしい。

感想

ほんとかなー。でも一つ言える事は、属性文法はビジュアル表現に適している事。動的なプログラムを静的な属性で表現出来るというのは強み。また、様々なリスト操作に程よい抽象化を与える物と見る事も出来る。ようするに inherited 属性は foldl で、synthesized 属性は foldr で、この二つを組み合わせると何でも書けるというのは分かりやすい。

応用としては、前に文句を書いた http://d.hatena.ne.jp/propella/20071218/p1 イベント処理の記述に特に威力を発揮するのでは無いかと思う。