TaPL はじめました

Types and Programming Languagesを読み始めました。毎日 1 チャプター読めるといいなぁ。

今日は 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