第 6 章 モナド と命令型言語の意味
IO は効率のために Haskell の処理系で特別扱いされる組込みのモナドであるが、他の言語の副作用を模倣するためにユーザがモナドを定義することも可能である。モナドを用いる利点は、“計算” の意味が変わっても、モナド の標準的な関数 unitM, bindM のみを用いている部分は、変更する必要がないところである。
以下では、簡単な命令型プログラミング言語（つまり副作用を持つ言語）を定義し 、モナド を利用してその意味を与えることにする。Haskell で意味を与えるということは、結局はラムダ計算で意味を与えることになる。具体的には命令型プログラミング言語から Haskell へのコンパイラを作成する。
簡単な言語からはじめて様々な特徴をもつ言語を定義していく。名前がないと不便なので、これらの対象言語を Util (Util: Tiny Imperative Language)1と呼び 、必要により、UtilErr, UtilST, UtilCont, . . .などのようにバージョンを表す接尾語をつけることにする。いろいろな特徴を導入していくにつれ 、その “計算” を表すモナド の定義が変わることになる。
やが必要である。字
実際のコンパイラにはフロントエンド、つまり句解析や構文解析の原理は Haskell でも C 言語などの命令型言語で記述するときと変わりはない。再帰下降構文解析法（あるいは LR 構文解析法）などの方法を利用する。(ただし 、再帰下降法で構文解析部を記述するときに、後述のようにモナド を利用することができる。)

しかし 、ここではこれらフロントエンド の作り方は既知のものとして、構文木ができた状態から話をはじめることにする。

6.1

構文規則

Util の構文木のデータ構造として、次のような Haskell データ型を使用する。

type Decl = (String, Expr)data Expr = Const Target| Var String| If Expr Expr Expr
| While Expr Expr
| Begin [Expr]| Let [Decl] Expr
| Val Decl Expr| Lambda String Expr
| Delay Expr
| App Expr Exprderiving Show1-- 定数（ Target は後述）-- 変数-- if 文-- while 文-- ブロック-- let 式（ 関数定義）-- val 式（ 変数定義）-- ラムダ式-- delay 式（ 後述）-- 関数適用

PHP, GNU などの略語の由来も参照すること。

VI - 1つまり、式 (Expr) とは、定数 (Const) または、変数 (Var) または、 if 式 (If) 、let 式 (Let) 、ラムダ
式 (Lambda) 、関数適用 (App) などからなる。
（あとから必要に応じて構文要素を追加することにする。）
具体的な構文としては次のような BNF で定義されていると仮定する。
（演算子の優先順位なども適切に宣言されているとする。）

ExprExprs
Decl
Decls

→||||→→→Const | Var | ( Expr )if Expr then Expr else Expr | while Expr do Expr | begin Exprs end
let Decls in Expr | val Decl in Expr
\ Var -> Expr | Expr Expr
Expr + Expr | Expr * Expr | · · · （ 他の中置演算子）· · ·Expr | Expr ; Exprs
Var = Expr
Decl | Decl ; Decls

ここに示されていないが 、定数 Const と変数 Var の字句の定義は Haskell と同じとする。ただし 、_（アンダーバー）から始まる変数名はコンパイラ内部で使用するために予約済みとする。
そして、次のような関数も既に定義されているものと仮定する。

myParse :: String -> Expr-- 字句解析・構文解析の関数• “val x=2*2 in val y=x*x in y*y” というソースプログラムは Expr 型のデータとして次のように構文解析される。
Val ("x", (App (App times (Const (TLit (Int 2)))) (Const (TLit (Int 2)))))(Val ("y", (App (App times (Var "x")) (Var "x")))(App (App times (Var "y")) (Var "y")))ただし 、times は *に対応する Expr の式である。

• “\ f -> \ x -> f x” という式は、Lambda "f" (Lambda "x" (App (Var "f") (Var "x")))というデータに構文解析される。

• &&, ||は、それぞれ 、
b1 && b27→

b1 || b2 7→という糖衣構文であるように構文解析されるようにしておく。
問 6.1.1 なぜ、&&や ||はプリミティブ関数として定義すると良くないのか ?

Target 型はコンパイラのターゲット言語である Haskell（のサブセット ）を表現する型である。

VI - 2

type TDecl = (String, Target)
data Target = TLit Literal-- 定数| TVar String-- 変数| TIf Target Target Target -- if 文
| Let [TDecl] Target-- let 式（ 変数・関数定義）| TLambda1 String Target-- ラムダ式| TApp1 Target Target-- 関数適用| TUnitM Target| TBindM Target Target
deriving (Show,Eq)
data Literal = Str String | Int Integer | Frac Rational | Char Charderiving (Show,Eq)
Util のコンパイラとは次のような型を持つ関数である。

comp :: Expr -> Target

6.2-- コンパイラ

抽象構文と具象構文

ところで、上の Util の構文規則はExprTermFactor（ ambiguous ）である。通常は曖昧さを避けるために、→→→Expr + Term | Term
Term * Factor | Factor
Const |( Expr )のように曖昧さを避けるために構文規則を工夫する。この後者のように実際に構文解析に用いるための構文を（ concrete syntax ）という。
それに対して、いったん構文解析が終了してしまえば 、曖昧さを避けるための補助的な仕掛けは必要なくなり、本質的な構造のみを扱えばよい。そのため、前者のような構文規則で十分である。このように構成要素の本質的な関係を記述した構文のことを（ abstract syntax ）という。
この章で “構文” と呼んでいるのは、この抽象構文のことである。データ型 Expr の定義は、抽象構文を代数的データ型として直訳したものである。

VI - 3

6.3 コンパイラの定義comp の定義は次のようになる。個々の構文要素に対する定義は比較的平易である。
comp :: Expr -> Target
comp (Const c)= TUnitM ccomp (Var x)= TUnitM (TVar x)
comp (Val (x, m) n)= comp m ‘TBindM‘ TLambda1 x(comp n)comp (Let decls n)= TLet (map (\ (x, m) -> let TUnitM c = comp min (PVar x, c)) decls)(comp n)comp (App f x)
= comp f ‘TBindM‘ TLambda1 "_f"(comp x ‘TBindM‘ TLambda1 "_x")TApp1 (TVar "_f") (TVar "_x")comp (Lambda x m)
= TUnitM (TLambda1 x (comp m))comp (Delay m)= TUnitM (comp m)comp (If e1 e2 e3)= comp e1 ‘TBindM‘ TLambda1 "_b"
(TIf (TVar "_b") (comp e2) (comp e3))
comp (While e1 e2)= TLet [(PVar "_while", body)] (TVar "_while")
where body = comp e1 ‘TBindM‘ TLambda1 "_b"
(TIf (TVar "_b") (comp e2 ‘TBindM‘ TLambda1 (TVar "_")
(TVar "_while"))(TUnitM (TVar "()")))
comp (Begin [e])= comp ecomp (Begin (e:es))= comp e ‘TBindM‘ TLambda1 (TVar "_")
(comp (Begin es))

右辺で使われている _f, _x, _b, _while などの識別子は、Util ソースプログラム中に使われている識別子と衝突しないように選んでいる。
comp 関数を理解するために、変換前と変換後をそれぞれ Util と Haskell の文法で記述したのが次の表である。
（ 詳細はソースプログラムを参照すること。）ただし bindM や unitM など 、末尾に M が付
く関数名は、対象のモナドに応じて適切な名前に置き換えられるものとする。
この表のなかで ソース中で Italic フォントで示されている m, n などは任意の Util の式で、ターゲット中で m’, n’ のように ’（プライム）が付いている式は、その comp による変換後の Haskell の式を表す。なお、delay については内部的に使用されるので、実際には Util のソースプログラムに現れることはない。

VI - 4ソース（ Util ）ターゲット（ Haskell ）c （ただし c は定数）x （ただし x は変数）
val x = m in n
let f = \ x -> mg = \ y -> nin nfx

unitM cunitM xm’ ‘bindM‘ \ x -> n’
let f = \ x -> m’x = \ y -> n’
in n’
f’ ‘bindM‘ \ _f ->x’ ‘bindM‘ \ _x ->_f _x
unitM (\ x -> m’)unitM m’c’ ‘bindM‘ \ _b -> if _b then t’ else e’let _while = c’ ‘bindM‘ \ _b ->if _b then t’ ‘bindM‘ \ _ ->_whileelse ()in _while\ x -> mdelay m
if c then t else ewhile c do t

begins;t;uends’ ‘bindM‘ \ _ ->t’ ‘bindM‘ \ _ ->u’

また、Util プログラム中の+, -, * などの二項演算子は、他の関数が unitM (\ x -> . . . ) という形に変換されること、戻り値はアクションを持たないことから、同名の Haskell 内のオペレータを用いて、それぞれunitM (\ x -> unitM (\ y -> unitM (x+y)))
unitM (\ x -> unitM (\ y -> unitM (x-y)))unitM (\ x -> unitM (\ y -> unitM (x*y)))という Haskell の式に置換するようにしておく。すると、comp 関数による他の部分の変換と整合する。
ソース（ Util ）ターゲット（ Haskell ）⊗ （ただし ⊗ は二項演算子） unitM (\ x -> unitM (\ y -> unitM (x ⊗ y)))2

®この comp を用いて、例えば次の Util プログラムを変換 すると©

let fact = \ n -> if n==0 then 1 else n*fact(n-1)
in fact 9­
次のような Haskell のプログラムが得られる。

ª2

ただし 、この fact 関数は副作用を含んでいないので、この変換自体にはあまり意味はない。

VI - 5let fact= \ n ->((unitM (\ x -> unitM (\ y -> unitM (x == y))) ‘bindM‘\ _f -> unitM n ‘bindM‘ \ _x -> _f _x)‘bindM‘ \ _f -> unitM 0 ‘bindM‘ \ _x -> _f _x)‘bindM‘\ _b ->
if _b then unitM 1 else
(unitM (\ x -> unitM (\ y -> unitM (x * y))) ‘bindM‘\ _f -> unitM n ‘bindM‘ \ _x -> _f _x)‘bindM‘\ _f ->(unitM fact ‘bindM‘\ _f ->((unitM (\ x -> unitM (\ y -> unitM (x - y))) ‘bindM‘\ _f -> unitM n ‘bindM‘ \ _x -> _f _x)‘bindM‘ \ _f -> unitM 1 ‘bindM‘ \ _x -> _f _x)‘bindM‘ \ _x -> _f _x)‘bindM‘ \ _x -> _f _x
in unitM fact ‘bindM‘ \ _f -> unitM 9 ‘bindM‘ \ _x -> _f _x
これは多くの冗長な部分を含んでいるので、前述の monad law などを利用して単純化すると、次のような式が得られる。
let fact= \ n ->if n == 0 then unitM 1 else
fact (n - 1) ‘bindM‘ \ _x ->unitM (n * _x)
in fact 96.4

最初のバージョン – Util1

最初のバージョン Util1 では、 モナドはトリビアルな計算（何もしない計算）としておく。つまり、Util1 は副作用を持たない言語である。
type I a = aunitI :: a -> I a
unitI a = abindI :: I a -> (a -> I b) -> I bm ‘bindI‘ k = k m
このとき、¨¥letfact=\n->
ifn==0
then1else
n*fact(n-1)
infact9§¦という Util プログラムをコンパイルして実行すると、同じプログラムを Haskell として実行したときと同じ 362880 という値になる。

VI - 6

6.5

UtilST – 状態の導入

Util に更新（ 代入）可能な状態の概念を導入する。C 言語や Java 言語のように、変数に対して代入を導入することも可能であるが 、非本質的な部分が多くなってしまうので、ここで紹介する例では、2 つだけ更新可能な “参照” xP と yP を導入することにする。2 という数は別に本質的なものではなく、いくつにすることも可能である。
例えば 、¨¥

begin set xP 1; set xP (get yP+3); get xP end§¦という UtilST プログラムを評価すると、 という結果が得られる。
状態を導入するために、やはり “計算の型” を定義する必要がある。まず 次の ST を定義する。
type ST s a = s -> (a, s)

unitST :: a -> ST s a
unitST a =bindST :: ST s a -> (a -> ST s b) -> ST s bm ‘bindST‘ k =unitST a は状態（ s ）の変更を行なわず、a をそのまま返す計算である。m ‘bindST‘ k は、m で変更された状態（ s1 ）をそのまま、k に受渡す計算である。
プリミティブは次のように定義する。
type Pos s a = s -> (a, a -> s)
xP :: Pos (x, y) x
xP = \ (x, y) -> (x,x1 -> (x1, y))yP :: Pos (x, y) y
yP = \ (x, y) -> (y,y1 -> (x, y1))getST :: Pos s a -> ST s agetST p = \ s -> (fst (p s), s)
setST :: Pos s a -> a -> ST s ()setST p v = \ s -> ((), snd (p s) v)
setST は状態を書き換え、また getST は状態の値の一部を複製している。
UtilST の setM, getM, . . . という関数は、そのまま Haskell の setM, getM, . . . にコンパイルされるようにしておく3 。
ソース（ Util ）ターゲット（ Haskell ）setM p m

ap’ ‘bindM‘ \ _p ->m’ ‘bindM‘ \ _x ->setM _p _xp’ ‘bindM‘ \ _p ->getM _p

getXM p’UtilST プログラム（ 右は対応する C プログラム）:このプリント中では、getM のように “M” という接尾辞を使っているときは、一般のモナドに適用可能な関数や型であり、getST のように “M” 以外の（例えば “ST” ）という接尾辞を使っているときは、特定のモナド ST に関する関数や型であるものと約束する。つまり、M という接尾辞がついている識別子は実際に使うときに適宜名前を付け替える。
3

VI - 7'$

let fact = \ n ->int fact(int y) {begin
setM xP 1; setM yP n;
int x = 1;
while getM yP > 0 do begin
while (y > 0) {setM xP (getM xP * getM yP);x = x * y;setM yP (getM yP - 1)
y = y - 1;end;}
getM xP
return x;end}
in fact 9&%
をコンパイルすると次のような Haskell の関数（ 一部、見易くするために変数名の変更などをしている）になり、
let fact n = setST xP 1 ‘bindST‘ \ _ ->setST yP n ‘bindST‘ \ _ ->(let _while = getST yP ‘bindST‘ \ y ->if y > 0 thengetST xP
‘bindST‘ \ x ->getST yP‘bindST‘ \ y ->setST xP (x*y)‘bindST‘ \ _ ->getST yP‘bindST‘ \ y ->setST yP (y-1)‘bindST‘ \ _ ->_whileelse unitST ()in _while)‘bindST‘ \ _ ->getST xP
in fact 9fact 9 を実行する（ fst (fact 9 (0, 0)) ）とその結果は 362880 になる。
階乗の場合、普通に関数的な定義を書いた方が簡潔だが、パラメータの数が多い場合などは、このような命令的な書き方の方が簡潔になる場合もありうる。
この ST の定義では、エラー処理を考慮していない。エラー処理を行なうためには、この ST と（ 後述する）Maybe の定義を合成する必要がある。参考までに、次のようなモナドになる。
type EST s a = s -> Maybe (a, s)
unitEST :: a -> EST s aunitEST a = \ s -> unitE (a, s)bindEST :: EST s a -> (a -> EST s b) -> EST s bm ‘bindEST‘ k = \ s0 -> case m s0 ofJust (a, s1) -> k a s1
Nothing-> Nothing

6.6

UtilIO – 入出力の導入

入出力は、入出力ストリームを状態の一種と考えれば 、6.5 節の UtilST と同じ方法で取り扱うことができる。
計算のモナド の定義は 6.5 節と基本的に同じだが 、状態に入力と出力のストリームを表す String

VI - 8型の部分を追加しておく。
type MyState = ((Integer, Integer), String, String)type MyIO a = ST MyState a-- つまり、 MyState -> (a, MyState)
入出力のプリミティブの定義は次のようになる。
getIO :: Pos s a -> ST (s, i, o) agetIO p = \ (s, i, o) -> (fst (p s), (s, i, o))setIO :: Pos s a -> a -> ST (s, i, o) ()setIO p v = \ (s, i, o) -> ((), (snd (p s) v, i, o))readIO :: () -> MyIO Char
readIO () =writeIO :: Show s => s -> MyIO ()writeIO v =eofIO :: () -> MyIO BooleofIO () = (s, i, o) -> (null i, (s, i, o))readIO は入力ストリームから 1 文字を取出し 、writeIO v は出力ストリーム o に v を String に変換したものを追加している4 。
©
®すると、次の UtilIO プログラム
let sq = \ x -> if x>0 then x*x else 0-x*x
in writeM (sq 2)­ªを実行したときの出力は、"4"になる。

6.7

UtilErr – エラー処理の導入

次に Util にエラー処理を導入する。UtilErr は、生真面目に (?) エラー処理を行ない、部分式にエラーがあれば式全体もエラーになるようにする。この場合、UtilErr は （ Haskell のような）遅延評価ではなくて、関数の引数を必ず先に評価する（ eager evaluation ）をシミュレートすることに注意する必要がある。
エラーと正常な振舞いを区別するために、次のようにデータ型 Maybe を使用する。
-- Prelude に定義済み
data Maybe a =|deriving (Show,Eq)
正常な振舞いは Just という構成子で表す。エラーの場合は Nothing という構成子を用いる。この型に対して次のような補助関数を定義しておく。

++の計算量は左オペランド の長さに比例するので、この定義のように文字列の後ろに新しい文字列を追加（ ++ ）していくと、出力文字列が長くなるにしたがって効率が悪くなる。これを避けて効率の良い定義を与えることも可能であるが 、ここでは簡単のために ++を使った定義を採用する。
4VI - 9

unitE :: a -> Maybe aunitE a = Just abindE :: Maybe a -> (a -> Maybe b) -> Maybe b(Just a) ‘bindE‘ k =Nothing‘bindE‘ k =m ‘bindE‘ k は、まず m を計算し 、その計算が正常終了すれば 、その値を k という関数に渡す。しかし 、いったん m でエラーが起こると、k は評価されず、ことを表している。
さらに、補助関数を定義しておく。failE はときに用いる UtilErr の計算の型に特有の関数である。
failE :: String -> Maybe afailE _ = Nothing“プ リミティブ関数” もエラー処理を利用するように書き換えることができる。例えば 、割り算（ / ）は次のような Haskell の式に置換されるようにする。
\ x -> unitM (\ y -> if y==0 then failM "Division by 0"
else unitM (x/y))
これで 0 で割ろうとした場合にはエラーが報告される。
例えば “(\ x -> 0) (1/0)” のような式は、Haskell ではが 、UtilErr では次のような Haskell プログラムに翻訳され 、(if 0 == 0 then failE "Division by 0"
else unitE (1/0))‘bindE‘ \ _x ->unitE 0
実行すると6.8という結果になる。

例外処理の導入

例外のモナド E を利用して、Java の try〜catch のように例外を捕捉する構文を導入することも可能である。
BNF には以下の構文を追加する。

Expr→...

|

try Expr catch Expr“try m catch h” は m を評価し 、エラーがなかった場合は、その戻り値を try 式の戻り値とする。
しかし m の評価中にエラーが生じた場合は、h を評価する。“try m catch h” は “tryM (delaym) (delay h)” という式として構文解析されるようにしておく。
また、failM という Util の関数は 、そのまま Haskell の failM にコンパイルされるようにしておく。この関数は、Java の throw 文に対応する。
ソース（ Util ）ターゲット（ Haskell ）try m catch n
failM mtryM (delay m’) (delay n’)m’ ‘bindM‘ \ _x ->failM _x
VI - 10

tryE は関数である。
tryE :: Maybe a -> Maybe a -> Maybe atryE (Just v) h =tryE Nothing h=

例えば¨§ try 1/0 catch 99999という UtilErr プログラムをコンパイルすれば 、出力される Haskell プログラムは、¥¦

tryE (if 0 == 0 then failE "Division by 0" else unitE (1/0))(unitE 99999)
であり、その結果は Just 99999.0 である。

6.9

UtilNonDet – 非決定性の導入

ここからは対象言語 Util に非決定性を導入する。非決定性（ nondeterminism ）とはを言う。ある選択肢を選んだ結果、計算が失敗する場合がある、その場合は前の選択肢に戻って計算をやり直す（バックトラック）。非決定性は探索型のパズル・ゲームや構文解析プログラムなどで利用できる。
非決定性の “計算” のモナド は通常のリストを使用する。
unitL :: a -> [a]unitL a = [a]appendL :: [a] -> [a] -> [a](x:xs) ‘appendL‘ ys = x : (xs ‘appendL‘ ys)[]‘appendL‘ ys = ysbindL :: [a] -> (a -> [b]) -> [b](a:es) ‘bindL‘ k = k a ‘appendL‘ (es ‘bindL‘ k)[]‘bindL‘ k = []こモナドは複数の選択肢を単にリストとして表現している。
実は unitL と bindL は、リストの内包表記を説明する時に使った unit ::[a] -> (a -> [b]) -> [b] とまったく同一の関数である。
計算の失敗は空リストで表される。
failL :: String -> [a]a -> [a] と bind ::failL _ =UtilNonDet は、構文は UtilErr と同じである。つまり、以下の構文を持つ。

Expr → . . . | try Expr catch Exprtry m catch h は、m を評価し 、h は “バックトラック” が起こったときに評価される。
tryL は appendL そのものである。
VI - 11tryL :: [a] -> [a] -> [a]tryL = appendL

UtilNonDet プログラム¨§ test0 = (try 1 catch 2) * (try 3 catch 4)¥¦

をコンパイルすると、次の Haskell プログラムが得られる。
test0 = tryL (unitL 1) (unitL 2) ‘bindL‘ \ x ->tryL (unitL 3) (unitL 4) ‘bindL‘ \ y ->unitL (x*y)
この、test0 は [ x*y | x <- [1,2], y <- [3,4]] というリスト内包表記に対応する。test0 は、[3,4,6,8] となる。
また、次の UtilNonDet プログラム¥¨§ test1 = (try 1 catch 2) / (try 0 catch 4)¦をコンパイルすると、次の Haskell プログラムが得られる。
test1 = tryL (unitL 1) (unitL 2) ‘bindL‘ \ x ->tryL (unitL 0) (unitL 4) ‘bindL‘ \ y ->if y == 0 then failL "Division by 0" else unitL (x/y)

test1 は 、[0.25,0.5] となる。失敗している計算については結果に現れていないことに注意する。
同じプログラムを UtilErr でコンパイルすると、UtilErr ではバックトラッキングが起こらないので、この計算は全体が失敗に終わる。
なお、次の headL を用いてリストの頭部を取ることにより、成功した最初の計算だけを返すことも可能である。
headL :: [a] -> aheadL (x:_) = x
headL test1 の値は 0.25 となる。この場合、Haskell がを採用しているため、他の選択肢の計算は行なわれない。そのため選択肢が無限個あるような場合でも最初の選択肢の計算結果を出力することができる。
問 6.9.1 非決定性と状態の両方の特徴を持つ計算の型として、

type STL s a =type LST s a =s -> ([a], s)s -> [(a, s)]の 2 つのバリエーションが考えられる。このそれぞれに対して、インタプリタの定義を完成させ、2つの違いを説明せよ。

VI - 12

この章の参考文献[1] Philip Wadler 「 The essence of functional programming 」
19th Annual Symposium on Principles of Programming Languages (invited talk), 1992 年 1 月
おもにモナド を用いてインタプリタを構築する方法を解説している。
[2] Philip Wadler 「 Monads for functional programming 」
Program Design Calculi, Proceedings of the Marktoberdorf Summer School, 1992 年 7–8 月
モナド を用いてパーサを構築する技法の解説がある。
[3] Ralf Hinze 「 Prological Features in a Functional Setting Axioms and Implementations 」
Third Fuji International Symposium on Functional and Logic Programming, 1998 年
Prolog のカット等のオペレータの意味を整理している。

VI - 13