TAPL4章の型無し算術式の実装

型無し算術式の実装 - プログラミング勉強日記に影響されて実装。

data Term = TmTrue
          | TmFalse
          | TmIf Term Term Term
          | TmZero             
          | TmSucc Term
          | TmPred Term        
          | TmIsZero Term
  deriving(Eq, Show)
  
isnumericval :: Term -> Bool
isnumericval TmZero = True
isnumericval (TmSucc t) = isnumericval t
isnumericval _ = False

isval :: Term -> Bool
isval TmTrue = True
isval TmFalse = True
isval t | isnumericval t = True
isval _ = False

eval1 :: Term ->  Maybe Term
eval1 (TmIf TmTrue x _) = pure x
eval1 (TmIf TmFalse _ y) = pure y
eval1 (TmIf b x y) = TmIf <$> eval1 b <*> pure x <*> pure y
eval1 (TmSucc x) = TmSucc <$> eval1 x
eval1 (TmPred TmZero) = pure TmZero
eval1 (TmPred (TmSucc x)) | isnumericval x = pure x
eval1 (TmPred x) = TmPred <$> eval1 x
eval1 (TmIsZero TmZero) = pure TmTrue
eval1 (TmIsZero (TmSucc x)) | isnumericval x = pure TmFalse
eval1 (TmIsZero x) = TmIsZero <$> eval1 x
eval1 x = Nothing

eval :: Term -> Term
eval t = maybe t eval $ eval1 t

アプリカティブファンクターとmaybeが便利だと思いました(小並感)

Eitherを使うことでどこでeval1が失敗したか分かるようにしてる。本当は失敗したところの1つ前の段階を出力して欲しかったけど眠いのでこれでいいや。

2016/04/13 色々と勘違いをしていたのでソースを修正しました。

ghci > eval $ TmIf (TmIsZero TmZero) TmFalse TmZero
TmFalse
ghci > eval $ TmIf (TmIsZero (TmSucc TmZero)) (TmSucc $ TmSucc $ TmSucc TmZero) TmZero
TmZero
ghci > eval $ TmIf (TmIf TmZero TmFalse TmTrue) TmZero TmZero
TmIf (TmIf TmZero TmFalse TmTrue) TmZero TmZero

eval1の最後の節で評価が終わったことを表すNothingを返すことで、evalで結果(=これ以上評価ができないもの)を返しています。これはOCamlの元ネタにおいて例外を投げたステップで結果を返すことに相当します。

ghciでの最後の例は1ステップ目で、内側のTmIfの第一引数であるTmZeroを評価しようとしてNothingを返すので、このステップの値である全体がそのまま返ってきています。OCamlのコードを読んだした感じでもそういう実装っぽい(OCamlの環境がないので予想)。

TmIf、TmSucc、TmPred、TmIsZeroは1ステップの中で引数(TmIfは第一引数)をもう一度評価するので、そこが評価ができないと全体を返すっぽいぽいぽい!!

今回はここまで。 最後にみなさんご一緒に。

Haskellと夕立はいいぞ。