非破壊Hash

ひさしぶりにParsecをいじってみた．

前回，(http://d.hatena.ne.jp/hoge1e3/20080129)

var a; a=3; var b; b=a+3;

というプログラムがあったときに，a や b にアドレスを割り付けたい，と言ったので，この部分の実装をやろうとした，が失敗．

 var a;  

という変数宣言を読ませる部分．ここで，
「a は アドレス 0 に割り当てる」
という処理をしたい．
その後，var b; がきたら
「b は アドレス 1 に割り当てる」
という処理をしたい．

Parsec には getState / setState があるから，状態にアドレスの連番とハッシュテーブル( 変数名 - アドレス ) をもたせたいと思って，次のように状態を定義し，

data ParserState = PStat Int (HashTable String Int) 
 -- HashTable は 標準のData.HashTable

変数宣言を解析する部分を次のようにした．

vardecl :: Parser Decl
vardecl = do { tok "var" 
             ; name <- symbol; tok ";"
             ; st <- getState  
             ; h <- (getSyms st) 
             ; update h name (getNum st)
             ; setState (PStat ((getNum st)+1) h )
             ; return $ VarDecl name (getNum st)
             } 

が，

Couldn't match expected type `GenParser Char ParserState t'
	   against inferred type `HashTable String Int'

これはdo文はdo文でもパーサのdo文だから，ここで IO を挟んだりはできない，ということらしい.

getState, setStateと馴染むためには，おそらくData.HashTableのようなIOベースのハッシュテーブルじゃなくて，非破壊的なハッシュテーブル，つまり

update :: Hash k v -> k -> v -> Hash k v

のように，
「もとのHash の内容にそっくりだけど，キーk に 値v を設定している点だけがちがう新しい Hash」
を返す，というメソッドがあればいいのに．

多分メモリを食うし速度も遅いからないのだろうか．

プログラミング言語のDOM

久しぶりに JDTのソース を読み進めてみる，けど違うパッケージを読んでみる

org.eclipse.jdt.core.dom

DOM というとXMLとかHTML のものという印象が強いけど，やっぱりJava にもあるのか

   ... 
   ... 
   ... 

こんな感じで，クラスの中に field とか method とかを，順不同に並べられる点では XMLと似たデータ構造をプログラミング言語はもっていることになる．

XMLにまつわる言語...XQuery とか XSLT ていまいち書き方がなじまないけど，コンパイラを作るときには使えそうな機能はあるので，おいしそうな構文糖をまぶしてあげるといいかな

属性文法の面倒な点

Attribute Grammars を読んでみる．これの22ページあたりに出てくる文法をとりあげてみる．

• Symbol-table を毎回書かなければいけない
• add-item て？ 副作用があっていいの？

 ::= program  is 
   Symbol-table() <-
       add-item( (Name(), program),
                  empty-table)

  ::=  begin  end
   Symbol-table() <-
       table-union( Symbol-table(),
                Symbol-table())

 ::=  := 
   Symbol-table() <- Symbol-table()
   Type() <-
      lookup-type( Name(),
                   Symbol-table())

 ::= write 
   Symbol-table() <- Symbol-table()
   Type() <- integer

ここからが大変そう

上の例のかわりに

Parse> r "var a; a=3; var b; b=a+3;"
Found value[ [ ],["1001","3","=","POP"],[ ],
["1002","1001","Read","3","+","=","POP"] ]
Parse> 

みたいに出したい．つまり，var a や var b のための領域(上では1001 と 1002 )を確保して，そのアドレスを生成するような処理をしたいんだけど，これを純粋関数型でどうすればよいのか．

コード生成部できた

Parsec で作る簡単なコンパイラ．

• 結局，字句解析のかわりに tok str というあやしいコンビネータ（str を読んで，その後ろのスペースをとばす） を定義
• コード生成部は toCodable クラスを使う．これで，命令のリストが作られる．
  • toCodable :: a -> CodeState -> [String]
  • CodeState は，現在打ち出しているコードが右辺値か左辺値かを示す．

module Parse where
import Text.ParserCombinators.Parsec

 --main
r :: String -> IO ()
r input = case parse source "lisp" input of
    Left err -> putStrLn $ "No match: " 
                 ++ show err
    Right val -> putStrLn $ "Found value" 
                 ++ (show $ map (toCode RVal) val)

 --util
mny :: Parser a -> Parser [a] 
mny p = many (do { spc; p } )
toks1 :: Parser Char -> Parser String 
toks1 p = do {res<-many1 p ; spc; return res } 

spc :: Parser ()
spc = skipMany space

tok :: String -> Parser String
tok str = do { s <- string str; spc ; return s }

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

vardecl :: Parser Decl
vardecl = do { tok "var" 
             ; name <- symbol; tok ";"
             ; return $ VarDecl name
             } 
statement :: Parser Decl
statement = do { e <- expr
               ; tok ";"
               ; return $ StmtDecl $ ExprStmt e
               }

expr :: Parser Expr
expr = do {
         left <- add ;
         option left (do {
             tok "=" ; a<-add ;
             return (BinOp left "=" a) 
         })
       }
add = do { left <- element
          ; rights <- mny (do { op   <- operators 
                              ; e    <- element 
                              ; return (op,e) } )
          ; return (makeBinOp left rights)
          }
operators :: Parser String
operators = tok "+" <|> tok "-" 

element :: Parser Expr
element = intConst <|> varRef

varRef :: Parser Expr
varRef = do {
   n <- symbol ;
   return $ VarRef n
}
intConst :: Parser Expr
intConst = do { v <- digits 
              ; return $ IntConst v 
              }
symbol  :: Parser String
symbol  = toks1 letter
digits  :: Parser Int
digits  = do { d <- toks1 (oneOf "0123456789")
             ; return (read d::Int)  -- ???
             }
 --semantics
makeBinOp :: Expr -> [(String,Expr)] -> Expr
makeBinOp left [ ] = left
makeBinOp left ((op,elem):rest) = 
   makeBinOp (BinOp left op elem) rest

data Decl = VarDecl String  |
            StmtDecl Statement  -- !
data Statement = ExprStmt Expr
data Expr = BinOp Expr String Expr |
            IntConst Int  |
            VarRef String 
data CodeState = LVal | RVal
class ToCodable a where
     toCode:: CodeState -> a -> [String]
instance ToCodable Statement where
  toCode c (ExprStmt e) = (toCode c e)  ++ ["POP"]   
instance ToCodable Expr where
  toCode c (BinOp l "=" r) =
     (toCode LVal l) ++ (toCode RVal r) ++ ["="]  
  toCode c (BinOp l o r)   = 
     (toCode RVal l) ++ (toCode RVal r) ++ [o]
  toCode c (IntConst i)    = [show i] 
  toCode RVal (VarRef name)  = [name , "Read"];
  toCode LVal (VarRef name)  = [name , "Addr"];
instance ToCodable Decl where
  toCode c (StmtDecl st)  = toCode c st
  toCode c (VarDecl name) = [ ]

実行例

Parse> r "var a; a=3; var b; b=a+3;"
Found value[ [ ],["a","Addr","3","=","POP"],[ ],
["b","Addr","a","Read","3","+","=","POP"] ]
Parse> 

toString と show と

HaskellでtoString - 西尾泰和のはてなダイアリー にて，この前の 「Haskell で toStringを定義する方法 」を書いてくれた．

確かにtoString は実装できるのだけど，すでに show という手段があるのだから，

• 通常はデフォルトのshow を使って
• ある一部のクラスについてはshow をカスタマイズしたい

という書き方ができるとなおよい（JavaはtoStringをオーバーライドすればできる），これがどうもうまくいかない

data Bar = Bar Int 
data Foo = Foo Bar deriving Show
show Foo b = "" ++ show b ++""
main = show (Foo (Bar 5)) 

こんなエラーがでる．

Ambiguous occurrence `show'
It could refer to either `show', defined at C:/eclipse/workspace/haskell/src/Test.hs:5:3
		          or `show', imported from Prelude

ようは show の定義が2つあるからどっちを採用すればわからん，ということらしい．
よりspecific なほうを採用する，というOO な考えはやっぱり関数型言語にはないのだろうか．

Parsec続き

代入式らしいものは書けるようになった．あと型クラスを使って toCode （コードを生成する関数）を実装してみる．うーんやっぱり 型なのに「instance」と書くのはまだ抵抗がある．

あと Foo {bar:: Int} という記法は扱いがすごい面倒なことがわかった．特に関数を書くときに

hoge Foo {bar:: b} = fuga b 

みたいに書かないといけないから．やっぱりこう書かせてよー(まだ言っている）

hoge f::Foo = fuga (f.bar) 

module Parse where
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 $ map toCode val)

 --util
mny :: Parser a -> Parser [a] 
mny p = many (do { spc; p } )
toks1 :: Parser Char -> Parser String 
toks1 p = do {res<-many1 p ; spc; return res } 

spc :: Parser ()
spc = skipMany space

tok :: String -> Parser String
tok str = do { s <- string str; spc ; return s }

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

vardecl :: Parser Decl
vardecl = do { tok "var" 
             ; name <- symbol; tok ";"
             ; return $ VarDecl {vdName = name }
             } 
statement :: Parser Decl
statement = do { e <- expr
               ; tok ";"
               ; return $ StmtDecl $ ExprStmt e
               }


expr :: Parser Expr
expr = do {
         left <- add ;
         option left (do {
             tok "=" ; a<-add ;
             return (BinOp left "=" a) 
         })
       }
add = do { left <- element
          ; rights <- mny (do { op   <- operators 
                              ; e    <- element 
                              ; return (op,e) } )
          ; return (makeBinOp left rights)
          }
operators :: Parser String
operators = tok "+" <|> tok "-" 

element :: Parser Expr
element = intConst <|> varRef

varRef :: Parser Expr
varRef = do {
   n <- symbol ;
   return VarRef {vrName=n}
}

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

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

 --semantics
makeBinOp :: Expr -> [(String,Expr)] -> Expr
makeBinOp left [] = left
makeBinOp left ((op,elem):rest) = 
   makeBinOp (BinOp left op elem) rest

data Decl = VarDecl { vdName:: String } |
            StmtDecl Statement  -- !
			deriving Show
data Statement = ExprStmt Expr
			deriving Show
			
data Expr = BinOp Expr String Expr |
            IntConst Int  |
            VarRef { vrName:: String }
			deriving Show
			
class (Show a)=> Codable a where 
  toCode:: a -> String
  toCode a=show a

instance Codable Statement where
  toCode (ExprStmt e) = "STM "++ (toCode e) ++";"
  
instance Codable Expr where
  toCode (BinOp l o r) = 
     (toCode l) ++ (toCode r) ++ o
  toCode a=show a
instance Codable Decl where
  toCode (StmtDecl st) = toCode st
  toCode a=show a