chapter3

春休みに入って時間に余裕ができたので図書館で

Types and Programming Languages (The MIT Press)

を借りてきて読んでます。

第3章まで読み終わったので、第3章の言語を実装してみた。
この言語は、if構文,bool値,自然数,succ,pred,iszeroのみを持つ。
なんか、パターンマッチングできる言語のほうが実装しやすいよーと書いていたのでhaskellで。

{- Simple Arith Expressions (Untyped) -}

data Term = MTrue
          | MFalse
          | MIf Term Term Term
          | MZero
          | MSucc Term
          | MPred Term
          | MIszero Term
          deriving (Show,Eq)

isnumerical :: Term -> Bool
isnumerical MZero = True
isnumerical (MSucc x) = isnumerical x
isnumerical _ = False

isval :: Term -> Bool
isval MTrue = True
isval MFalse = True
isval x = isnumerical x

eval1 :: Term -> Term
eval1 (MIf MTrue x y) = x
eval1 (MIf MFalse x y) = y
eval1 (MIf t1 t2 t3) = MIf x t2 t3
  where x = eval1 t1
eval1 (MSucc t) = MSucc x
  where x = eval1 t
eval1 (MPred MZero) = MZero
eval1 (MPred (MSucc t)) = if isnumerical t
                          then t
                          else error "badnat"

eval1 (MPred t) = MPred x
  where x = eval1 t   
eval1 (MIszero MZero) = MTrue
eval1 (MIszero (MSucc t)) = if isnumerical t
                            then MFalse
                            else error "badnat"
eval1 (MIszero t) = MIszero x
  where x = eval1 t
eval1 _ = error "No Rule can apply"                     

eval :: Term -> Term
eval t = if isval t
         then t
         else eval $ eval1 t

> eval (MIf (MIszero (MPred (MSucc MZero))) MTrue MFalse)
> MTrue

みたいな感じでとりあえずうごく。
eval1にvalueを与えたときにvalueを返すようにして、evalをfixで書くとかもできそうな感じがする。