10.8 練習問題
- 関数
isTautと、前の二つの章で定義したパーサーと対話プログラムのライブラリを用いて、対話的に恒真式か検査する関数を実装せよ。ユーザーがキーボードからわかりやすい文法で命題を入力できるようにすること。
ヒント：8章で定義した数式のパーサーを改良して、命題のパーサーを作れ。
なかなか面倒な問題だった。パーサーがうまく構成できなくてね。優先度をまちがえて、"True"をパースしたら"T"だけが Var 'T' とパースされたり。
module TenEightSix where import Parsing import NineFive import TenEightFive factor :: Parser Prop factor = do symbol "(" e <- expr symbol ")" return e +++ bool +++ variable bool :: Parser Prop bool = do symbol "True" return (Const True) +++ do symbol "False" return (Const False) variable :: Parser Prop variable = token (do c <- letter return (Var c)) term :: Parser Prop term = do symbol "!" f <- factor return (Not f) +++ factor expr :: Parser Prop expr = do t <- term (do symbol "&&" t2 <- term return (And t t2) +++ do symbol "||" t2 <- term return (Or t t2) +++ do symbol "=>" t2 <- term return (Imply t t2) +++ do symbol "==" t2 <- term return (Equiv t t2) +++ return t) run :: IO () run = do putStr "Enter a proposition: " xs <- getLine parseTaut xs parseTaut :: String -> IO () parseTaut xs = case parse expr xs of [(p,"")] -> showTaut p _ -> putStrLn "Syntax Error" showTaut :: Prop -> IO () showTaut p = if isTaut p then putStrLn "Tautology" else putStrLn "Not tautology"
- 乗算を扱えるように仮想マシンを拡張せよ。
仮想マシンの命令を2つ増やさざるを得ないと思われる。EVAM ExprとMUL Int。最初に定義していたEVAL Exprは加算の右辺評価命令なので、左辺はとりあえずADD Intを突っ込んでおいて、右辺評価後に加算する。EVAM Exprは乗算の右辺評価命令なので、左辺はとりあえずMUL Intを突っ込んでおいて、右辺評価後に乗算する。
1c1 < data Expr = Val Int | Add Expr Expr --- > data Expr = Val Int | Add Expr Expr | Mul Expr Expr 4c4 < data Op = EVAL Expr | ADD Int --- > data Op = EVAL Expr | ADD Int | EVAM Expr | MUL Int 8a9 > eval (Mul x y) c = eval x (EVAM y:c) 13a15,16 > exec (EVAM y:c) n = eval y (MUL n:c) > exec (MUL n:c) m = exec c (n * m)
