第 5 章 非決定的な計算

5.1 Prolog 超簡単入門
Prolog は、と呼ばれるプログラミング言語の仲間のうち、もっとも代表的なものである。論理型言語では、「〜ならば〜」という論理式の集まりをプログラムとみなし 、論理式の証明をプログラムの実行とみなす。
Prolog などの論理型言語に特徴的な概念としては、（ 単一化）、（ 後戻り）、などが挙げられる。

5.2 Prolog でのプログラミング
Prolog では「〜ならば〜」という論理式の集まりをプログラムとみなすが、この「〜」の部分を構成するのが 、次のような形式である。
述語 (項 1 , . . . , 項 n )1と呼ぶ。
このかたちを「項」は数・文字列などの定数や変数、あるいはリストなどのデータ構造などである。
「 述語」は直観的には項 1 , . . . , 項 n の間の関係を表す。例えば 、father(adam,cain) という素論理式は「 Adam は Cain の父である」という関係を表す。
Prolog のプログラムは、（ Horn clause ）と呼ばれる形式の集まりである。ホーン節とは、素論理式 0 :-素論理式 1 , . . . , 素論理式 n .という形である。
（ 最後に必ずピリオド（ . ）が必要である。）:-は左向きの矢印（ ← ）と考えれば良い。つまり、これは素論理式 1 , . . . , 素論理式 n がすべて成り立つならば 、素論理式 0 も成り立つという規則を表している。
ホーン節の:-の左側には素論理式は一つのみであり、これを（ head ）と呼ぶ、:-の右側の素論理式の並びは例えば 、（ body ）と呼ぶ。

grandchild(X, Z) :- child(X, Y), child(Y, Z).
は、X と Y, Y と Z の間に child という関係がある（ X が Y の子であり、Y が Z の子である）ならば 、X と Z の間に grandchild という関係がある（ X は Z の孫である）という規則を述べている。ここでX, Y, Z は変数である。Prolog の変数は X, Xs, Y のように、アルファベットの（あるいはアンダースコア “_” ）からはじまる識別子（ 名前）を使用する。一方、小文字からはじまる識別子は、述1

アトム（ Atom ）、複合項などと呼ぶこともある。

V-1

語や構成子などの定数に利用される2 。変数はどのような項に具体化しても良いので、変数を使用した規則は、実際には無数の規則を表していることになる。
ホーン節のうちボディがないものを（ fact ）と言う。このときは、:-も省略する。
（ 文末のピリオドは必要である。） 例えば 、child(hidetada, ieyasu).
は hidetada（ 秀忠）が ieyasu（ 家康）の子である、という事実を表明している。ここで hidetada,ieyasu は小文字からはじまるので定数である。
Prolog のプログラムは、このようなホーン節（ 事実を含む）を集めたものである。例えば徳川家の家系図を表すプログラムの一部は次のようになる。

grandchild(X, Z) :- child(X, Y), child(Y, Z).
child(hideyasu, ieyasu).
child(hidetada, ieyasu).
child(yoshinao, ieyasu).
child(yorinobu, ieyasu).
child(yorifusa, ieyasu).
child(iemitsu, hidetada).
child(tadanaga, hidetada).
child(masayuki, hidetada).
child(ietsuna, iemitsu).
child(tsunayoshi, iemitsu).
このようなプログラムをファイルに作成し 、処理系にロード 3 する。例えば Windows 上で動作する
SWI-Prolog という処理系ではメニューの「 File 」—「 Consult . . . 」 でプログラムファイルをロード することができる。
プログラムは、このようなホーン節の集まりに対して質問を発することにより起動される。Prologの処理系は「 ?- 」というプロンプトを出力するので、このあとに質問を入力する。
（質問も最後に必ずピリオドが必要である。）?- grandchild(hidetada, ieyasu).
No?- grandchild(iemitsu, ieyasu).
Yes
1 番目の質問は、Hidetada（秀忠）は Ieyasu（家康）の孫か ? という質問である。これはプログラム中の規則から導出できないので、処理系は No と答えている。2 番目の質問は、Iemitsu（家光）は家康の孫か ? という質問である。これは 、 child(hidetada, ieyasu). と child(iemitsu, hidetada).という二つの事実とgrandchild(X, Z) :- child(X, Y), child(Y, Z).というホーン節から導出できるので Yes と答えている。
さらに Prolog では質問の中に変数を含めることができる。すると Prolog の処理系は、を出力する。例えば 、
23

Haskell と全く逆なので注意する。
Prolog では伝統的に consult という。

V-2

?- grandchild(X, ieyasu).という質問に対しては、

X = iemitsuという解を出力する。ここで、リターンキーを押すとこれで終ってしまうが、「 ; 」を入力すると、さらに別解を表示させることができる。

X = iemitsu ;X = tadanaga ;X = masayuki ;No
質問には一般に複数の素論理式を並べることができる。

?-素論理式 1 , . . . , 素論理式 n .

このような形をと呼ぶ。直観的には、並べた素論理式がすべて成り立つか ?（ 成り立たせるような変数への代入が存在するか ? ） という質問を表している。

5.3

単一化と後戻り

この節では、Prolog のプログラムの実行方法を解説する。解説を簡単にするために、まず、最初にいくつかの言葉を定義しておく。
2 つ以上の（通常変数を含む）素論理式があり、変数に適切な代入をして、これらの素論理式をまったく同一のものにすることができる時、これらの素論理式は（ unifiable ）であるとい（ unifier ）という。例えば 、次の 2 つの素論理式う。また、その時の代入をp(a, Y, Z) と p(X, b, Z)
は X = a, Y = b を単一化代入として単一化可能である。単一化可能な時は 、通常必要なのは最汎（ 最も一般的な）単一化代入（ most general unifier,）である。例えば 、上の例では、X = a, Y= b, Z = c という代入も単一化代入であるが 、前者の方がより一般的である。実際、この例の場合
は X = a, Y = b が最汎単一化代入になる。
プログラム中のホーン節

P :- Q1 ,Q2 , . . . ,Qn ,の頭部 P が素論理式（ G ）と単一化可能なとき、このホーン節は G に
Prolog のプログラムの実行方法は、次のようにまとめられる。

1. ゴ ール節中のという。

素論理式に対し 、適用できるホーン節を選ぶ。適用できるホーホーン節から試みる4 。

ン節が複数ある時は、プログラム中に4Prolog を定理証明系として見た時には、ここで、「最も左」、「先に書かれている」という選択をするために、証明系としての力が弱くなってしまう。つまり、このような制限をしなければ証明できるはずの論理式が証明できなくなってしまう。しかし 、プログラミング言語として見た時は、効率を確保するために必要な制限である。

V-3

2. 選んだ適用可能なホーン節に対して、その最汎単一化代入をゴ ール節の残りの素論理式に適用し 、さらにゴ ール節中の最左素論理式を、上で選んだホーン節のボディに最汎単一化代入を適用したものと置き換える。
（ホーン節のボデ ィがないときは、最左素論理式を消す。）
3. もし適用できるホーン節がなければ 、後戻り（）して、ひとつの前のゴ ール節中の素論理式がある状態からやり直す。そして、その素論理式に適用できるホーン節のうち次の候補を選ぶ。
4. ゴ ール節に素論理式がなくなれば 、プログラムの実行を終了し 、その時得られた変数への代入を表示する。素論理式がまだあれば 、1 に戻る。
具体的に、?- grandchild(X, ieyasu).というゴール節での動作を説明することにする。まずこのゴール節の最左（ 1 つしかないが ）素論理式は grandchild(X, ieyasu) である。これに適用できるホーン節は、今のプログラムでは、grandchild(X, Z) :- child(X, Y), child(Y, Z).
しかなく、最汎単一化代入は Z = ieyasu である。するとゴ ール節は··· 1に変換される。
次に、この最左の child(X, Y) に適用できる最初のホーン節は、child(hideyasu, ieyasu).
であり、最汎単一化代入は X = hideyasu, Y = ieyasu である。すると、ゴ ール節は、に変換される。しかし 、このゴ ール節に適用できるホーン節はない。
そこで、上の 1 のところまでバックトラックし 、次の候補である

child(hidetada, ieyasu).の適用を試みる。しばらくのあいだ同様にバックトラックが続き、最終的に 1 のゴ ール節に対し 、child(iemitsu, hidetada).というホーン節を選ぶ。そのとき最汎単一化代入は X = iemitsu, Y = hidetada となる。すると、
ゴ ール節は、に書き換えられる。これはすぐに適用できるホーン節が見つかり、ゴール節が空になって、結果として代入:

X = iemitsu

V-4

が出力される。ここで ; が入力されると、またバックトラックが起こる。
ホーン節の適用は命令型言語・関数型言語の関数呼出しのようなものだと考えることもできるが 、単一化により呼び出される側（ホーン節の頭部）から呼び出す側（ゴール節）に情報が流れることがある、というところが論理型言語に特徴的なところである。例えば 、?- child(X, ieyasu).という呼出しに対しては、X = hideyasu（あるいは hidetada, yoshinao . . . ）という情報が、呼び出された側から、呼び出した側に伝えられる。
Prolog の変数は命令型言語の変数と異なり、いったん単一化により値が代入されれば 、以降は値を変更されることはない。ただし 、（純）関数型言語の変数とも異なり、最初はいったん不定（ unknown ）（ logical variable ）と呼な値を取ることができる。このような振舞いをする変数は一般にばれる。

5.4

Prolog でのリスト 処理

Prolog でのリストの記法は要素を , で区切り、角括弧（ [と ] ）で囲んで、[1, 2, 3] のように書く。
また、先頭の要素が X で、先頭を除く残りの要素からなるリストが Xs であるようなリストは [X|Xs]という書き方に相当する。[1, 2, 3] は実はと表記される。これは Haskell のの略記法である。
Prolog でのリストを連接（ append ）するプログラムは次のように記述できる。
append([], Y, Y).
append([H|X], Y, [H|Z]) :- append(X, Y, Z).
これは 、1 番目の引数と 2 番目の引数を連接した結果が 3 番目の引数になる、という関係を表している。
例えば , [1, 2] と [3, 4] の連接は次のように求められる。

?- append([1, 2], [3, 4], X).
X = [1, 2, 3, 4] ;No
問 5.4.1 実際に、上のような結果が出ることを、上に示した Prolog の実行方法で 1 ステップずつ確認せよ。

V-5

上の問を解いてみるとわかるが、変数 X は後ろの要素が不定（ 変数）のまま、前の要素から順に定まっていく。後ろの要素がもっと後で定まるようなプログラムを書くことも可能である。例えば 、

myconcat([], []).
myconcat([Xs|Xss], Ys) :- append(Xs, Zs, Ys), myconcat(Xss, Zs).
これは、リストのリストを平坦なリストに変換するプログラムである。

?- myconcat([[1, 2], [3, 4], [5, 6]], Xs).
Xs = [1, 2, 3, 4, 5, 6] ;Noappend の第 2 引数の Zs はあとの myconcat の呼出しで値が定まる。append の第 3 引数の Ys はしばらくの間、最後が論理変数で終る形で扱われることになる。
このように cdr 部分が論理変数になっているリストを（ open list ）という。開リストはProlog でリストを扱う時に良く使われるイデ ィオムである。
さらに Prolog のおもしろいところは append の逆向きの計算もできるということである。
?- append(X, Y, [1, 2, 3]).
X = []
Y = [1, 2, 3] ;X = [1]Y = [2, 3] ;X = [1, 2]
Y = [3] ;X = [1, 2, 3]
Y = [] ;No
この例では連接して [1, 2, 3] になる 2 つのリストの、すべての可能性を求めていることになる。
ユーザが「 ; 」を入力するたびに別解を表示する。
問 5.4.2 実際に、上のような結果が出ることを、上に示した Prolog の実行方法で 1 ステップずつ確認せよ。

V-6

5.5

UtilNonDet – 非決定性の導入

ここからは Prolog の非決定性を模倣するために 、対象言語 Util に非決定性を導入する。非決定性（ nondeterminism ）とはを言う。ある選択肢を選んだ結果、計算が失敗する場合がある、その場合は前の選択肢に戻って計算をやり直す。非決定性は探索型のゲームや構文解析プログラムなどで利用できる。
Util に、新しく Amb と Fail の構文を追加する。

data Expr = Const Value | Let Decl Expr | Var String| Lambda String Expr | App Expr Expr | If Expr Expr Expr
| Letrec Decl Expr ||;Amb m1 m2 は、m1 または m2 のいずれかを評価する計算を表す。Fail は計算の失敗を表す。これに対する具象構文としては、Expr → . . . | amb Expr or Expr | fail Exprを想定する。
非決定性の “計算” の型 M は次のように定義する。
data List a = Cons a (List a) | Failure String;type M a = List a;nil :: List a;nil = Failure "";append :: List a -> List a -> List a;(Cons x xs) ‘append‘ ys = Cons x (xs ‘append‘ ys);
(Failure s) ‘append‘ (Failure "") = Failure s;(Failure s) ‘append‘ ys= ys;
unitM :: a -> M a;unitM a = Cons a nil;bindM :: M a -> (a -> M b) -> M b;m ‘bindM‘ k = case m of {Cons x xs -> k x ‘append‘ (xs ‘bindM‘ k);
Failure m -> Failure m};
つまり、List a は基本的には a のリスト型だが 、空リストに String 型のメッセージが付加されている。unitM と bindM は、リストの内包表記を説明する時に使った unit :: a -> [a] と bind ::[a] -> (a -> [b]) -> [b] に類似の関数である。この M は複数の選択肢を単にリストとして表現している。
計算の失敗は空リストに対応する Failure で表される。
failM :: String -> M a;

failM message =;すると、Amb と Fail に対する interp は次のように定義される。

interp (Amb m1 m2) e =interp (Fail e1) e= interp e1 e ‘bindM‘ \ v ->failM (showValue v);
V-7;

Amb m1 m2 は m1, m2 の 2 つの式の評価の結果を append で単に連接しているだけである。
割算のように失敗する可能性のある計算は、上記の failM を用いて定義しておく。
Fun (\ v ->case v of {Num c -> unitM (Fun (\ w ->case w of {Num 0 -> failM "Division by 0";
Num d -> unitM (Num (c/d));_-> failM "Number expected"}));_-> failM "Number expected"})
ここで、run という関数をrun :: String -> String;
run prog = showL (interp (myParse prog) initEnv);

showL (Cons a (Cons b cs)) = showValue a ++ " or " ++ showL (Cons b cs);
showL (Cons a _)= showValue a;showL (Failure str)= "Failure: " ++ str;と定義しておくと、run "(amb 1 or 2) * (amb 3 or 4)"の値は、"3.0 or 4.0 or 6.0 or 8.0"となり、run "(amb 1 or 2) / (amb 0 or 4)"の値は "0.25 or 0.5"となる。失敗している計算については結果に現れていないことに注意する。
なお、run の定義を
run1 :: String -> String;run1 prog = showValue ((interp (myParse prog) initEnv));

hdL :: List a -> a;hdL (Cons a _) = a;のようにして、リストの頭部を取ることにより、成功した最初の計算だけを返すようにすることも可能である。すると、run1 "(amb 1 or 2) / (amb 0 or 4)"の値は "0.25"となる。この場合、メタ言語として使用している Haskell がを採用しているため、他の選択肢の計算は行なわれない。そのため選択肢が無限個あるような場合でも最初の選択肢の計算結果を出力することができる。
さらに Prolog にはカットといって後戻りの振舞いを変更する機構があるが 、このような機構を導入するためには、後で紹介する接続（ continuation ）のような仕組みが必要である。
問 5.5.1 非決定性と状態の両方の特徴を持つ計算の型として、
type M a = MyState -> ([a], MyState);type M a = MyState -> [(a, MyState)];の 2 つのバリエーションが考えられる。このそれぞれに対して、インタプリタの定義を完成させ、2つの違いを説明せよ。

この章の参考文献[1] Ralf Hinze 「 Prological Features in a Functional Setting Axioms and Implementations 」
Third Fuji International Symposium on Functional and Logic Programming, 1998 年Prolog のカット等のオペレータの意味を整理している。
V-8