第10章 型とクラスの定義 #7

10.8 練習問題

6. 関数 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"

7. 乗算を扱えるように仮想マシンを拡張せよ。

仮想マシンの命令を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)