今日は 3, 4 章を読んだ。
3 章は、今後の説明に使われるであろう、シンプルな言語 arith の導入。boolean と integer しかない。
4 章は arith の evaluator のインプリメンテーション。例は OCaml だったので、Haskell で書いてみた。
data Term = TmTrue
| TmFalse
| TmIf Term Term Term
| TmZero
| TmSucc Term
| TmPred Term
| TmIsZero Term
deriving Show
isNumVal :: Term -> Bool
isNumVal TmZero = True
isNumVal (TmSucc t) = isNumVal t
isNumVal (TmPred t) = isNumVal t
isNumVal _ = False
isVal :: Term -> Bool
isVal TmTrue = True
isVal TmFalse = True
isVal t = isNumVal t
eval1 :: Term -> Maybe Term
eval1 (TmIf TmTrue t _) = Just t
eval1 (TmIf TmFalse _ t) = Just t
eval1 (TmIf t1 t2 t3) = eval1 t1 >>= \t -> Just $ TmIf t t2 t3
eval1 (TmSucc t) = eval1 t >>= \s -> Just $ TmSucc s
eval1 (TmPred TmZero) = Just TmZero
eval1 (TmPred (TmSucc nv)) | isNumVal nv = Just nv
eval1 (TmPred t) = eval1 t >>= \s -> Just $ TmPred s
eval1 (TmIsZero TmZero) = Just TmTrue
eval1 (TmIsZero (TmSucc nv)) | isNumVal nv = Just TmFalse
eval1 (TmIsZero t) = eval1 t >>= \s -> Just $ TmIsZero s
eval1 _ = Nothing
eval :: Term -> Term
eval t = case eval1 t of
Just s -> eval s
Nothing -> t
ghci で動かしてみるとこんな感じ。
*Main> eval $ TmIsZero $ TmPred $ TmSucc $ TmZero
TmTrue
*Main> eval $ TmIsZero $ TmPred $ TmSucc $ TmSucc $ TmZero
TmFalse
0 件のコメント:
コメントを投稿