属性文法は重要か

Why Attribute Grammars Matter というページを見つけた．日付が01-07-05 なんだけど，これは 2001年7月5日か，2005年1月7日かわからない．

まだ読み始めたばかりだけれど，中央付近にあるグラフがなんかあやしい．リスト構造の逆をたどるともっと柔軟にデータが扱えますよー，てことなのだろうか．

Parsec(Haskell)わからないこといろいろ 

show b::BinOp = bLeft b ++ bRight b ++ bOp b

って書いたらおこられた

  • 異なるクラスで同名のフィールドが定義できない
data Foo=Foo { a:: Int}
data Bar=Bar { a:: Int}

を定義すると「a が2重定義」といわれる．

data Foo = Foo {a::Int} |  Bar {a::Int}

ならOK
しかし

data Foo = Foo {a::Int} |  Bar {a::String}

は，だめ．
まあ，aはフィールドじゃなくて関数だから仕方ないのはわかるけど，Java人間としてはフィールド的に扱いたい．いっそのこと foo.a とか書かせてほしいぐらい．

Parsec入門

ちょっとParsecをいじってみた．整数定数の足し算と引き算の式，変数宣言が書ける（宣言できるけど使えない）．計算をせずにASTだけを出力する．

import Text.ParserCombinators.Parsec

 --main
r :: String -> String
r input = case parse source "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found value" ++ show val

 --util
mny :: Parser a -> Parser [a] 
mny p = many (do { spc; p } )
spc :: Parser ()
spc = skipMany space

 --grammar
source :: Parser [Decl]
source = do { bodies <- mny ( vardecl <|> statement)
            ; return bodies 
            }

vardecl :: Parser Decl
vardecl = do { string "var" ; spc
             ; name <- symbol; spc ; string ";"
             ; return $ VarDecl {vdName = name }
             } 
statement :: Parser Decl
statement = do { e <- expr; spc
               ; string ";"
               ; return $ Statement {ex = e}
               }
expr :: Parser Expr
expr = do { left <- intConst 
          ; rights <- mny (do { op   <- operators 
                              ; elem <- intConst 
                              ; return (op,elem) } )
          ; return (makeBinOp left rights)
          }
operators :: Parser String
operators = string "+" <|> string "-" 

intConst :: Parser Expr
intConst = do { v <- digits 
              ; return $ IntConst { iValue= v} 
              }

symbol  :: Parser String
symbol  = many1 letter
digits  :: Parser Int
digits  = do { d <- many1 (oneOf "0123456789")
             ; return (read d::Int)  -- ???
             }

 --semantics
makeBinOp :: Expr -> [(String,Expr)] -> Expr
makeBinOp left [] = left
makeBinOp left ((op,elem):rest) = 
   makeBinOp BinOp { bOp=op, bLeft = left, bRight= elem} rest

data Decl = VarDecl { vdName:: String } |
            Statement { ex :: Expr } 
            deriving Show

data Expr = BinOp { bOp::String, bLeft:: Expr,  bRight::Expr } |
            IntConst { iValue::Int }  |
            VarRef { vrName:: String }
            deriving Show

出力例

Main> r "1+2-3;4-5-6;"
Loading package parsec-2.0 ... linking ... done.
"Found value[Statement {ex = BinOp {bOp = \"-\", bLeft = BinOp {bOp = \"+\", bLe
ft = IntConst {iValue = 1}, bRight = IntConst {iValue = 2}}, bRight = IntConst {
iValue = 3}}},Statement {ex = BinOp {bOp = \"-\", bLeft = BinOp {bOp = \"-\", bL
eft = IntConst {iValue = 4}, bRight = IntConst {iValue = 5}}, bRight = IntConst
{iValue = 6}}}]"

大事なのはLookup力

Sublinear-space evaluation algorithms for attribute grammars という論文を見つける．1987年もの．attribute grammar というのは死に絶えた技術なんだろうか，それはさておき

ROOT -> exp
  exp.env = φ
exp -> exp + exp
  exp1.val = exp2.val + exp3.val
  exp2 .env = exp1 .env
  exp3.env = exp1 .env
exp -> exp - exp
  exp1 .val = exp2 .val - exp3 .val
  exp2 .env = exp1 .env
  exp3 .env = exp1 .env
exp -> let id = exp in exp ni
  exp1 .val = exp3 .val
  exp2 .env = exp1 .env
  exp3 .env = exp1 .env U ( (id, exp2 .val) )
exp -> id
  exp.val= LookUp(id, exp.env)
exp -> integer
  exp.val = ValueOf(integer)

これは典型的なattribute grammarの例としてこの論文に載っている．この中にある LookUp という関数はid と 環境（スコープ）をもとに値を探してくるものだが，その実装はAttribute Grammarでは規定されていない，というか書きにくい？このへんにAttribute Grammarの限界があるのかもしれない．

突然Parsecを思い出す

パーサジェネレータって，

  • パーサジェネレータの持つ言語（文法定義)
  • JavaとかCとかの一般的な言語

という2重の言語が必要だなー，と思っていたら，これがあったことを思い出す．Parsec はパーサジェネレータじゃないから確かに単一の言語（Haskell)で書ける．

じゃあParsecで思い通りのコンパイラが書けるのか...というとまた違うきがする．ちょっと実際にParsecを使いながら考えていこう

XQuery

上の論文は，XQuery についても言及している．たぶんXML文書を変更したときに，XQueryに対する検索結果をインクリメンタルに変える，という仕組みも提供しているらしい．

XQueryの文法をしらなかったのでこのへんを読んでみた．

for $i in
 document("Tutorial/data/projects.xml")//project[count(
members/member)>=2]
return
 {$i/name/text()}
  {$i//member/name}

うーん，見かけの問題だけど，/ で区切っているのは見づらいというかまぎらわしい．// はコメントに見えるわ，members/member は割り算しているように見えるわ....

[論文] XMLの制約検証をインクリメンタルに行う．

Consistently updating XML documents using incremental constraint check queries

ある XML 文書とそのXML Schema を与えて，XML文書の変更があったとき，XML Schemaを満たしているかどうかを，差分を検出して高速に行うものらしい．

すべての言語をXML と XML Schemaに落とせば，これを使ってインクリメンタルなコンパイラが作れるかもしれない．といってもXML Schemaが型の検証にどこまで使えるかはわからず．