第 5 章 モナド と命令型言語の意味
IO は効率のために Haskell の処理系で特別扱いされる組込みのモナドであるが、他の言語の副作用を模倣するためにユーザーがモナド を定義することも可能である。モナド を用いる利点は、“計算” の意味が変わっても、モナド の標準的な関数
return と (>>=) のみを用いている部分は、変更する必要がないところである。
以下では、簡単な命令型プログラミング言語（つまり副作用を持つ言語）を定
義し 、モナド を利用してその意味を Haskell で与えることにする。Haskell で意味を与えるということは 、結局はラムダ計算で意味を与えることになる。
（ 等式による推論が可能になる。）具体的には命令型プログラミング言語から Haskell へのコンパイラーを作成する。

5.1 Util コンパイラー
この節では、コンパイラーの実装を紹介していく。実装の詳細は把握しなくても、ソースプログラムとターゲットプログラムを比べれば 、副作用を持つプログ
ラミング言語がどのように変換されるか感覚的に掴めるはずである。
簡単な言語からはじめて様々な特徴をもつ言語を定義していく。名前がないと不便なので、これらの命令型言語を Util (Util: Tiny Imperative Language)1と呼び 、必要により、UtilErr, UtilST, UtilCont, . . . などのようにバージョンを表す接尾語をつけることにする。いろいろな特徴を導入していくにつれ、その “計算” を表すモ
ナド の定義が変わることになる。
（ 空欄 5.1.1 ）実際のコン パ イラーにはフロント エンド、つまりや（ 空欄 5.1.2 ）が必要である。字句解析や構文解析の原理は Haskell でも C 言語などの命令型言語で記述するときと変わりはない。再帰下降構文解析法（あるいは LR 構文解析法）などの方法を利用する。(ただし 、再帰下降法で構文解析部を記述するときに、後述のようにモナド を利用することができる。)

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

1
いわゆる再帰的頭字語 (recursive acronym) である。PHP, GNU などの略語の由来も参照すること。

V-1

5.1.1

構文規則

Util の構文木のデータ構造として、次のような Haskell データ型を使用する。
ファイル RecType.hs

1
2
3
4
5
6
7
8
9
10
11
12

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 Show-- 定数（ Target は後述）-- 変数-- if 文-- while 文-- ブロック-- let 式（ 関数定義）-- val 式（ 変数定義）-- ラムダ式-- delay 式（ 後述）-- 関数適用

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

Expr

Exprs
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 と同じとする。ただし 、_（アンダーバー）から始まる変数名はコンパイラー内部で使用するために予約済みとする。while〜do 式や begin〜end 式があるところがHaskell と異なり、命令型言語らしいところである。

5.1.2

字句解析・構文解析関数

次のような関数が既に定義されているものと仮定する。

myParse :: String -> Expr-- 字句解析・構文解析の関数• “val x=2*2 in val y=x*x in y*y” というソースプログラムは Expr型のデータとして次のように構文解析される。
V-2

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 && b2 7→ if b1 then b2 else False
b1 || b2 7→ if b1 then True else b2という糖衣構文であるように構文解析されるようにしておく。
問 5.1.1 なぜ、&&や ||はプリミティブ関数として定義すると良くないのか ?

5.1.3 ターゲット 言語
コンパイラーのターゲット言語である Haskell のサブセットの構文木を表現す
る型 Target 型を定義しておく。
ファイル Target.hs

1
2
3
4
5
6
7
8
9
10
11
12

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

comp :: Expr -> Target-- コンパイラー

5.1.4 抽象構文と具象構文
ところで、上の Util の構文規則は曖昧さを避けるために、（ 空欄 5.1.3 ）（ ambiguous ）である。通常は

V-3

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

5.1.5 コンパイラーの定義
comp の定義は次のようになる。個々の構文要素に対する定義は比較的直截である。
ファイル RecCompiler.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

comp :: Expr -> Target
comp (Const c)= TUnit ccomp (Var x)= TUnit (TVar x)
comp (Val (x, m) n)= comp m ‘TBind‘ TLambda1 x(comp n)comp (Let decls n)= TLet (map (\ (x, m) ->let TUnit c = comp min (PVar x, c)) decls)(comp n)comp (App f x)
= comp f ‘TBind‘ TLambda1 "_f"(comp x ‘TBind‘ TLambda1 "_x"(TApp1 (TVar "_f") (TVar "_x")))comp (Lambda x m)
= TUnit (TLambda1 x (comp m))comp (Delay m)= TUnit (comp m)comp (If e1 e2 e3)= comp e1 ‘TBind‘ TLambda1 "_b"
(TIf (TVar "_b") (comp e2) (comp e3))
comp (While e1 e2)= TLet [(PVar "_while", body)](TVar "_while")
where body = comp e1 ‘TBind‘ TLambda1 "_b"
(TIf (TVar "_b")(comp e2 ‘TBind‘ TLambda1 (TVar "_while"))(TUnit (TVar "()")))
comp (Begin [e])= comp ecomp (Begin (e:es))= comp e ‘TBind‘ TLambda1 (TVar "_")
(comp (Begin es))
右辺で使われている _f, _x, _b, _while などの識別子は、Util ソースプログラム中に使われている識別子と衝突しないように選んでいる。

V-4

comp 関数を理解するために、変換前と変換後を代数的データ型ではなく、それ
ぞれ Util と Haskell の文法で記述したのが次の表である。
（ 詳細はソースプログラ
ムを参照すること。）
この表のなかで ソース中で Italic フォントで示されている m, n などは任意の
Util の式で、ターゲット中で ṁ, ṅ のように ˙（ド ット ）が付いている式は 、そのcomp による変換後の Haskell の式を表す。なお、delay については内部的に使用されるので、実際には Util のソースプログラムに現れることはない。
ソース（ Util ）ターゲット（ Haskell ）c （ただし c は定数）x （ただし x は変数）
val x = m in n
let f = \ x -> m
g = \ y -> nin nfa

return creturn xṁ >>= \ x -> ṅlet f = \ x -> ṁ
x = \ y -> ṅin ṅḟ >>= \ _g ->ȧ >>= \ _x ->_g _xreturn (\ x -> ṁ)return ṁ
ċ >>= \ _b -> if _b then ṫ else ė
let _while = ċ >>= \ _b ->if _b then ṫ >>= \ _ ->_whileelse ()
in _while\ x -> mdelay mif c then t else e
while c do t

begin
s;
t;
u
end

ṡ >>= \ _ ->ṫ >>= \ _ ->u̇

要点は、変数や定数の出現など “副作用” が発生しないところには return が付
くこと、関数適用は (>>=) を使った式に翻訳されることなどである。
また、Util プログラム中の+, -, * などの二項演算子は、他の関数が return (\x -> . . . ) という形に変換されること、戻り値はアクションを持たないことから、同名の Haskell 内のオペレーターを用いて、それぞれreturn (\ x -> return (\ y -> return (x+y)))return (\ x -> return (\ y -> return (x-y)))return (\ x -> return (\ y -> return (x*y)))という Haskell の式に置換するようにしておく。すると、comp 関数による他の部分の変換と整合する。
ソース（ Util ）ターゲット（ Haskell ）⊗ （ただし ⊗ は二項演算子） return (\ x -> return (\ y -> return (x ⊗ y)))V-5

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

fact = \ n −> if n==0 then 1 else n∗fact(n−1)
次のような Haskell のプログラムが得られる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

1
2
3

fact = \ n -> if n == 0 then return 1 else
fact (n - 1) >>= \ _x ->return (n * _x)

5.2

最初のバージョン – Util1

最初のバージョン Util1 では、モナドはトリビアルな計算（何もしない計算）としておく。つまり、Util1 は副作用を持たない言語である。
ファイル Id.hs

1
2
3
4
5

newtype I a = I ainstance Monad I wherereturn a = I a(I m) >>= k = k m（ 空欄 5.2.1 ）ここで 、は 、Haskell の新しい型の宣言の形式の一つである。data 宣言と似ているが、フィールドが一つの構成子を一つしか持つことがで
2

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

V-6

きない。data 宣言の構成子と異なり、newtype 宣言で導入される構成子は型変換の意味しか持たず、実行時の計算を伴わない。また、型の別名を宣言する type 宣
言との違いは 、型の変換が構成子によって明示的になる点である。
（ 型クラスのインスタンスには、type 宣言で導入された型の別名は指定できない。例えば リストに通常の辞書式順序と異なる順序（ Ord のインスタンス宣言）を与えたいときは newtype を使って別名を用意し 、別名に対してインスタンス宣言する必要がある）
上記の newtype 宣言では型構成子と構成子に同じ I という名前を使っているが 、文脈でど ちらか判断することができるので問題ない。
このとき、fact = \ n −> if n==0 then 1 else n∗fact(n−1)という UtilI プログラムをコンパイルして実行する（ unI (fact 9) ）と、同じプ
ログラムを Haskell として実行したときと全く同じ 362880 という値になる。
ただし 、unI は次のように定義された型変換関数である。
ファイル Id.hs

12

unI :: I a -> aunI (I a) = a

5.3

UtilST – 状態の導入

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

begin set xP 1; set xP (get xP+3); get xP endという UtilST プログラムを評価すると、 （ 空欄 5.3.1 ）という結果が得られる。
状態を導入するために、やはり “計算の型” を定義する必要がある。まず 次のST を定義する。
ファイル ST.hs

1
2
3
4
5
6
7
8
9

newtype ST s a = ST (s -> (a,s))unST :: ST s a -> s -> (a,s)
unST (ST s) = s
instance Monad (ST s) wherereturn a = ST ()(ST m) >>= k = ST (\ s0 -> let { (a,s1) = m s0 }in unST (k a) s1)
V-7

10
11

-- ST, unST がなければ 、次のようになる-- m >>= k = \ s0 -> let { (a,s1) = m s0 } in k a s1
return a は状態（ s ）の変更を行なわず、a をそのまま返す計算である。このモナ
ド の m >>= k は、m で変更された状態（ s1 ）をそのまま、k に受渡す計算である。
参照は次のように定義する。
ファイル MyState.hs

1
2
3
4
5
6
7

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))
xP（ yP ）はペアの第 1（ 第 2 ）成分にアクセスするための参照である。参照に対する読み出し・書き込みのメソッドは、後で別のモナドでも使用するので、型クラス MyState のメソッド として定義しておくことにする。
ファイル MyState.hs

1
2
3

class MyState m where
get :: Pos s a -> m s a
set :: Pos s a -> a -> m s ()ST をこの MyState クラスのインスタンスとして宣言する。
ファイル ST.hs

1
2
3
4
5

instance MyState ST where
get p= ST (\ s -> (fst (p s), s))set p v = ST (\ s -> ((), snd (p s) v))-- 例えば get xP ≡ ST (\ (x,y) -> (x,(x,y)))set は状態を書き換え、また get は状態の値の一部を複製している。
UtilST の set, get, . . . という関数は、Haskell の set, get, . . . にコンパイルされるようにしておく
ソース（ Util ）ターゲット（ Haskell ）set p mṗ >>= \ _p ->ṁ >>= \ _x ->set _p _x
ṗ >>= \ _p ->get _pget p

UtilST プログラム（ 右は対応する C プログラム）:

V-8

1
2
3
4
5
6
7
8

fact = \ n −> begin
set xP 1; set yP n;
while get yP > 0 do begin
set xP (get xP ∗ get yP);
set yP (get yP − 1)end;
get xP
end

1
2
3
4
5
6
7
8

int fact(int y) {int x = 1;
while (y > 0) {x = x * y;y = y - 1;}
return x;}

をコンパイルすると次のような Haskell の関数（ 一部、見易くするために変数名の変更などをしている）になる。

1
2
3
4
5
6
7
8
9
10
11
12
13

fact n = set xP 1 >>= \ _ ->set yP n >>= \ _ ->(let _while = get yP >>= \ y ->if y > 0 thenget xP
get yP
set xP (x*y)
get yP
set yP (y-1)_whileelse return ()in _while)>>= \ _ ->get xP>>= \ x ->>>= \ y ->>>= \ _ ->>>= \ y ->>>= \ _ ->fact 9 を実行する（ fst (unST (fact 9) (0,0)) ）とその結果は 362880 になる。
階乗の場合、普通に関数的な定義のほうが簡潔だが 、パラメーターの数が多い
場合などは、このような命令的な書き方が簡潔になる場合もありうる。
この ST の定義では 、エラー処理を考慮していない。エラー処理を行なうためには、この ST と（ 後述する）Maybe の定義を合成する必要がある。参考までに、次のようなモナドになる。
ファイル EST.hs
1
2
3
4
5
6
7
8
9
10

newtype EST s a = EST (s -> Maybe (a,s))
unEST :: EST s a -> s -> Maybe (a,s)
unEST (EST m) = m
instance Monad (EST s) wherereturn a = EST (\ s -> return (a,s))(EST m) >>= k = EST (\ s0 -> case m s0 ofJust (a,s1) -> unEST (k a) s1
Nothing-> Nothing)V-9

問 5.3.1 次の C の関数とほぼ同等な Haskell の関数をモナド を用いて作成せよ。
1.
int foo(int n) {int i = 1, j = 1;
while (i < n) {i = i + j;
j = i - j;}return i;
}

2.

5.4

int bar(int n) {int i = 0;
while (n > 1) {i = i + 1;
n = n / 2;}
return i;}

UtilIO – 入出力の導入

入出力は、入出力ストリームを状態の一種と考えれば 、5.3 節の UtilST と同じ方法で取り扱うことができる。
計算のモナドの定義は 5.3 節と基本的に同じだが、状態に入力と出力のストリームを表す String 型の部分を追加しておく。
ファイル MyStream.hs

1

type WithIO s = (s,String,String)
ファイル MyIO.hs

1
2
3
4

newtype MyIO s a = MyIO (WithIO s -> (a, WithIO s))
unMyIO :: MyIO s a -> WithIO s -> (a, WithIO s)
unMyIO (MyIO m) = m
参照のプリミティブの定義は次のようになる。
ファイル MyIO.hs

1
2
3

instance MyState MyIO
get p
= MyIO (\ (s,i,o) -> (fst (p s),(s,i,o)))set p v = MyIO (\ (s,i,o) -> ((),(snd (p s) v,i,o)))
入出力に関するプリミティブも後で別のモナドで使用するので、型クラス MyStreamのメソッド として定義しておく。
ファイル MyStream.hs

V - 101
2
34class MyStream m where
readChar:: m Chareof:: m Bool
writeStr:: String -> m ()ファイル MyIO.hs

1
2
3
4

instance MyStream (MyIO s) where
readChar= MyIO (\ (s,c:cs,o) -> (c,(s,cs,o)))eof= MyIO (\ (s,i,o) -> (null i,(s,i,o)))writeStr v = MyIO (\ (s,i,o) -> ((),(s,i,o++v)))
readChar は入力ストリームから 1 文字を取出し 、writeStr str は出力ストリーム o に str を 追加している3 。write という関数を次のように定義しておく。
ファイル MyStream.hs

1
2

write :: (Show v, MyStream m) => v -> m ()write v = writeStr (show v)
すると、次の UtilIO プログラム（ただし 、// は整数の除算を表す演算子とする。）

1
2
3
4
5
6
7

foo = \ n −> begin
set xP n;
while get xP > 0 do begin
write (get xP % 10);
set xP (get xP // 10)
end
end
をコンパイルした結果は、

1
2
3
4
5
6
7
8
9
10
11

foo n =

set xP n >>= \ _ ->let _while= get xP >>= \ _x ->if _x > 0 thenget xP>>= \ _x ->write (_x ‘mod‘ 10) >>= \ _ ->get xP>>= \ _x ->set xP (_x ‘div‘ 10) >>= \ _ ->_whileelse return ()in _whileとなり、これを

let (_,(_,_,o)) = unMyIO (foo 12345) ((0,0),"","") in oのように実行したときの出力は、"54321" になる。
問 5.4.1 次の C の関数とほぼ同等な Haskell の関数をモナド を用いて作成せよ。
3++の計算量は左オペランド の長さに比例するので、この定義のように文字列の後ろに新しい文字列を追加（ ++ ）していくと、出力文字列が長くなるにしたがって効率が悪くなる。これを避けて効率の良い定義を与えることも可能であるが 、ここでは簡単のために ++を使った定義を採用する。

V - 11

1.

2.

5.5

int baz(int n) {int i, j;for (i = 0; i < n; i++) {for (j = 0; j <= i; j++) {printf("*");}
printf("\n");}return i;}
int qux(int n) {int i, j;for (i = 0; i < n; i++) {printf("*");
if (i % 3 == 0) {printf("!");}
printf("\n");}return i;}

UtilErr – エラー処理の導入

次に Util にエラー処理を導入する。UtilErr は 、生真面目に (?) エラー処理を行ない、部分式にエラーがあれば式全体もエラーになるようにする。この場合、UtilErr は（ Haskell のような）遅延評価ではなくて、関数の引数を必ず先に評価す（ 空欄 5.5.1 ）（ eager evaluation ）を模倣することに注意する必要がある。
る
エラーと正常な振舞いを区別するために、次のような標準ライブラリに用意されているデータ型 Maybe を使用する。

-- Prelude に定義済み
data Maybe a =deriving (Show,Eq)|

正常な振舞いは Just という構成子で表す。エラーの場合は Nothing という構成子を用いる。この型に対して次のようなインスタンス宣言がされている。

1
2
3
4
5

-- Prelude に宣言済み
instance Monad Maybe wherereturn a = Just a(Just a) >>= k =Nothing >>= k =このモナド の m >>= k は、まず m を計算し 、その計算が正常終了すれば 、その値を k という関数に渡す。しかし 、いったん m でエラーが起こると、k は評価され（ 空欄 5.5.2 ）していくことを表している。
ず、V - 12

さらに 、MonadPlus というクラスに属するいくつかの メソッド を用意する。
（ 空欄 5.5.3 ）mzero は状況をつくり出すときに用いる。

1
2
3
4
5
6
7
8
9

-- モジュール Control.Monad に定義済み
class Monad m => MonadPlus m wheremzero :: m a
mplus :: m a -> m a -> m a-- モジュール Control.Monad に宣言済み
instance MonadPlus Maybe wheremzero = Nothing...
-- mplus の定義は後掲“プリミティブ関数” もエラー処理を利用するように書き換えることができる。例
えば 、割り算（ / ）は次のような Haskell の式に置換されるようにする。
\ x -> return (\ y -> if y==0 then mzero
else return (x/y))
これで 0 で割ろうとした場合にはエラーが報告される。
例えば(\ x −> 0) (1/0)（ 空欄 5.5.4 ）のような式は、Haskell では 1/0 の部分式はに全体の結果が 0 となるが 、UtilErr では次のような Haskell プログラムに翻訳され 、

123(if 0 == 0 then mzero
else return (1/0)) >>= \ _x ->return 0
実行すると（エラーが起こったことを表す）

5.6（ 空欄 5.5.5 ）という結果になる。

例外処理の導入

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

Expr

→

...

|

try Expr catch Expr“try m catch h” は m を評価し 、エラーがなかった場合は、その戻り値を try
式の戻り値とする。しかし m の評価中にエラーが生じた場合は、h を評価する。
Util の “try m catch h” は “m’ ‘mplus‘ h’” という式として構文解析されるようにしておく。
また、fail という Util の関数は、Haskell の mzero を返す関数にコンパイルされるようにしておく。この関数は、Java の throw 文に対応する。

V - 13

ソース（ Util ）ターゲット（ Haskell ）try m catch n
fail ()ṁ ‘mplus‘ ṅ
mzero

Maybe に対する mplus は第 1 引数を評価し、第 2 引数を評価する関数である。
12
3
4（ 空欄 5.6.1 ）instance MonadPlus Maybe where...
-- mzero は紹介済
Just a ‘mplus‘ _ = Just a
Nothing ‘mplus‘ m = m
例えば

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

12(if 0 == 0 then mzero else return (1/0))‘mplus‘ (return 99999)
であり、その結果は Just 99999.0 である。

5.7

UtilNonDet – 非決定性の導入

ここからは対象言語 Util に非決定性を導入する。非決定性（ nondeterminism ）と（ 空欄 5.7.1 ）が存在することを言う。あはプログラムの動作にる選択肢を選んだ結果、計算が失敗する場合がある、その場合は前の選択肢に戻って計算をやり直す（バックトラック）。非決定性は探索型のパズル・ゲームや構文解析プログラムなどで利用できる。バックトラックをプリミティブな機能として（ 空欄 5.7.2 ）提供する言語としては、論理型言語のが有名である。
非決定性の “計算” のモナド は通常のリストを使用する。

1
2
3
4
5
6
7
8
9
10

-- Prelude で宣言済み
instance Monad [] wherereturn a = [a][]>>= k = [](x:xs) >>= k = k x ++ (xs >>= k)-- モジュール Control.Monad で宣言済み
instance MonadPlus [] wheremzero = []mplus = (++)
このモナドは複数の選択肢を単にリストとして表現している。
実はリストに対する return と (>>=) は、リストの内包表記を説明する時に使った unit :: a -> [a] と bind :: [a] -> (a -> [b]) -> [b] と全く同一の関数である。

V - 14

計算の失敗は空リストで表される。
UtilNonDet は、構文は UtilErr と同じである。つまり、以下の構文を持つ。

Expr → . . . | try Expr catch Expr
UtilNonDet の try m catch h は、m を評価し 、h は “バックトラック” が起こったときに評価される。
UtilNonDet プログラム

test0 = (try 1 catch 2) ∗ (try 3 catch 4)
をコンパイルすると、次の Haskell プログラムが得られる。

123

test0 = (return 1 ‘mplus‘ return 2) >>= \ x ->(return 3 ‘mplus‘ return 4) >>= \ y ->return (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 プログラムが得られる。

123

test1 = (return 1 ‘mplus‘ return 2) >>= \ x ->(return 0 ‘mplus‘ return 4) >>= \ y ->if y == 0 then mzero else return (x/y)
test1 は、[0.25,0.5] となる。失敗している計算については結果に現れていないことに注意する。同じプログラムを UtilErr でコンパイルすると、UtilErr ではバッ
クトラッキングが起こらないので、この計算は全体が失敗 (Nothing) に終わる。
なお、次の head を用いてリストの頭部を取ることにより、成功した最初の計算だけを返すことも可能である。

1
2
3-- Prelude に定義済み
head :: [a] -> ahead (x:_) = x（ 空欄 5.7.3 ）head test1 の値は 0.25 となる。この場合、Haskell がを採用しているため、他の選択肢の計算は行なわれない。そのため選択肢が無限個あるような場合でも最初の選択肢の計算結果を出力することができる。

問 5.7.1 非決定性と状態の両方の特徴を持つ計算の型として、

1
2

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

V - 15

5.8 さらに詳し く知りたい人のために . . .
Parsec [1] はモナド を利用した有名なパーサーライブラリーである。[3] にも、モナドを用いてパーサーを構築する技法の解説がある。[2] はモナドを用いてインタプリターを構築する方法を解説している。[4] は、Prolog のカット等のオペレー
ターの意味を整理している。

この章の参考文献[1] Daan Leijen and Erik Meijer 「 Parsec: Direct Style Monadic Parser Combinators
for the Real World 」
Technical Report UU-CS-2001-35, Dept. of Comp. Sci, Universiteit Utrecht, 2001
年, http://www.cs.uu.nl/people/daan/parsec.html[2] Philip Wadler 「 The essence of functional programming 」
19th Annual Symposium on Principles of Programming Languages (invited talk),
1992 年 1 月[3] Philip Wadler 「 Monads for functional programming 」
Program Design Calculi, Proceedings of the Marktoberdorf Summer School, 1992
年 7–8 月[4] Ralf Hinze 「 Prological Features in a Functional Setting Axioms and Implementations 」
Third Fuji International Symposium on Functional and Logic Programming, 1998
年

V - 16