Hatena::Grouphaskell

mokeheheの日記

2009-08-02

陰に状態を扱うためにSTモナド(に似たもの)を使用する

Parsecで作っている電卓に関数定義を追加しようと考えたところ、関数定義を実現するにはソースのパース時に直接計算を行ってしまわないでいったん構文木を作成して保存しておき、関数が呼び出されたときに構文木を評価して値を求める必要があることに気づいた。

Haskellで構文木を作るのはそんな難しいことではないのでサクッと修正、、、できたのだがパース時と同様に値の評価時にも状態(変数の値など)を持ち回る必要があることに気づいた。「eval node state」という具合に状態を陽に渡すようにしてもいいんだけどメンドクサイし、たとえば変数参照したときに未定義だったらエラーを返すなどの判定と分岐が必要になってしまい大変。

runParserのような仕組みで状態を裏で取り扱ってくれるうまいやりかたがないかな、と調べる。STモナドがそれっぽいんだけど、STモナドに状態を渡して結果を取り出す方法がわからなかった(えー)。

なのでMonads for the Working Haskell ProgrammerのStateTransモナドのあたりを参考に、似たようなものを定義してみる:

newtype ST s a = ST( s -> (s, a) )

instance Monad (ST s)
  where
    -- (>>=) :: ST s a -> (a -> ST s b) -> ST s b
    (ST p) >>= k  =  ST( \s0 -> let (s1, a) = p s0
                                    (ST q) = k a
                                in q s1 )

    -- return :: a -> ST s a
    return a = ST( \s -> (s, a) )

状態を渡して結果を取り出す関数:

-- 結果と状態のペアを取得
applyST :: ST s a -> s -> (s, a)
apply (ST p) s = p s

-- 結果のみを取得
runST :: ST s a -> s -> a
runST (ST p) s = snd $ p s

runParserのgetState, setState, updateStateのように、doの途中で状態を取り出したり変更したりする関数:

getState :: ST st st
getState = ST( \s -> (s, s) )

setState :: st -> ST st ()
setState s' = ST( \s -> (s', ()) )

updateState :: (st -> st) -> ST st ()
updateState f = ST( \s -> (f s, ()) )

これらを使って構文木を評価する関数を作る。まず構文木のノードや環境の定義:

-- ノード
data Node =
		Literal Double
	|	Ident String
	|	Assign String Node
	deriving (Show)

-- 環境
type Environment = [(String, Double)]

doAssign :: String -> Double -> Environment -> Environment
doAssign var val env = (var, val) : filter ((/= var) . fst) env

initialState = [
	("pi",	pi)  -- π
	]

評価を行う関数 eval と状態:

-- eval に必要な状態
type MyST a = ST Environment a

eval :: Node -> MyST Double
eval (Literal v) = return v
eval (Ident name) = do
	env <- getState
	case (lookup name env) of
		Nothing -> fail $ "undefined variable: " ++ name
		Just v  -> return v
eval (Assign name n) = do
	v <- eval n
	updateState $ doAssign name v
	return v
  • どういう仕組みかわからないけど、fail が使える

以上で、例えば変数参照は

> runST (eval (Ident "pi")) initialState
3.141592653589793

代入は

> applyST (eval (Assign "a" (Literal 123))) initialState
([("a",123.0),("pi",3.141592653589793)],123.0)

変数が未定義で途中でエラーが出るときも

> runST (eval (Assign "a" (Ident "b"))) initialState
*** Exception: undefined variable: b

とfailによって例外が出てくれる。

参考
トラックバック - http://haskell.g.hatena.ne.jp/mokehehe/20090802