8 7 章のドリル

8
7 章のドリル
前章で紹介した四則演算の文法を発展させて，Prolog と言う言語を定義してみよう．
Prolog（Programming with predicate Logic）は，1971 年にフランスで発明された論理型言語である．述語論
理に基づいた定理証明に似た振舞いをすることが知られているが，通常のプログラミング言語としても利用する
ことができる．まず，プログラムの形式から見ていくことにしよう．
8.1
Prolog の外観
Prolog では，プログラムを，事実（fact）と規則（rule）からなる節（clause）の集合として記述する．例えば，
事実とは，次のようなものである．
プログラム 70: 事実の例
male(namihei). male(katsuo). male(tara). male(masuo).
female(fune). female(wakame). female(sazae).
father(masuo, tara). father(namihei, sazae). father(namihei, katsuo).
father(namihei, wakame).
mother(sazae, tara). mother(fune, sazae). mother(fune, katsuo).
mother(fune, wakame).
male，female，father，mother をそれぞれ，
「男性である」，
「女性である」，
「父親である」，
「母親である」とい
う述語であるとすると，引数は，主語を表すと見ることができる．例えば，male(katsuo) は，
「カツオは男性で
ある」という事実を表している．ここで，小文字から始まる名前をオブジェクトと呼ぶ．Prolog では，事実を
プログラム 71: 事実の Prolog 表記
述語 ( 引数, 引数, ..., 引数 ) .
のように記述する．
次に，事実と事実を組み合わせて，規則を記述することができる．例えば，次のようなものが規則である．
93
8. 7 章のドリル
94
プログラム 72: 規則の例
parents(X, Y) :- father(X, Y).
parents(X, Y) :- mother(X, Y).
son(X, Y) :- parents(Y, X), male(X).
daughter(X, Y) :- parents(Y, X), female(X).
grandfather(X, Y) :- parents(Z, Y), father(X, Z).
grandmother(X, Y) :- parents(Z, Y), mother(X, Z).
規則 son(X, Y) :- parents(Y, X), male(X). は，
「Y はX の親であり，かつ，X が男性であるならば．X は Y の
息子である」を表している．ここで，大文字から始まる名前は，変数を表している．規則は，次の形式で記述し，
「本体部ならば頭部である」という関係を表す．
プログラム 73: 事実の Prolog 表記
頭部 :- 本体部
本体部は，goal1 , goal2 , ..., goaln のように，複数のゴールを「，
」で区切った形式で記述する．
「，
」は「かつ」
を意味する．事実や規則を単純に並べると，
「または」の関係になる．
それでは，前述の事実と規則を，プログラムとして実行してみよう．まず，事実と規則をファイル isono.pl
に記述する．実行には，これから実現していく Prolog 処理系の Simple-Prolog（以降，SProlog と呼ぶ）を使う．
SProlog は，次のように起動する．
プログラム 74: SProlog の起動
> spl ←- ?-
?-のプロンプトが表示されたら，この後に，操作コマンドか質問を入力する．まず，open を使って，プログラム
を読み込んでみよう．
プログラム 75: プログラムの読込み
?- open isono. ←- 続いて，質問を入力してみる．質問は，事実の問い合わせなので，事実と同じ形式で記述する．
プログラム 76: 質問 (1)
?- grandfather(namihei, tara).
Yes.
?- son(katsuo, fune).
Yes.
8.2. その他の機能
95
入力した質問が正しければ，
「Yes」が，そうでなければ，
「No」が印字される．最後に「.」を入力すると，プロン
プトが返ってくるので，他の質問を継続して入力することができる．
では，Prolog は，どのようにYes とNo を判断しているのであろうか．Prolog の基本的な振舞いとして，
「かつ」
で結ばれた質問が，すべてプログラム中の事実とマッチしたときYes を返す．また，質問が規則の頭部にマッチす
ると，その質問を，規則の本体部に記述されたゴールに置き換える．この規則の置換えは，繰り返し適用されの
で，元の質問を最も基本的な事実に還元する．例えば，
「grandfather(namihei,tara)」は，次のように，変形さ
れながら，事実とマッチするか調べられる．
grandfather(namihei, tara).
↓ grandfather(X, Y) :- parents(Z, Y), father(X, Z). の適用
parents(Z, tara), father(namihei, Z)
↓ parents(X, Y) :- mother(X, Y). の適用
mother(X, tara), father(namihei, X)
↓ mother(sazae, tara). と father(namihei, sazae). の適用
Yes
ここで，変数は，相手が何であろうとマッチすることに注意したい．また，一旦，変数がマッチすると，その
変数が現れるすべての場所が，マッチした対象で置き換わる．この変数の性質を利用すると，質問を満たすオブ
ジェクトを問い合わせることができる．例えば，
「フネ」のすべての「娘」を問い合わせてみよう．
プログラム 77: 質問 (2)
?- daughter(X, fune). ←- X = sazae
Yes; ←- X = wakame
Yes; ←- No.
?-
問い合わせたい部分を変数にすることによって，質問を満たす候補が表示される．1 つ候補が表示されるたびに，
Yes が印字されるが，
「;」を入力すると，次候補が表示される．Prolog は，; が入力されるたびに，マッチする別
の可能性を探索する．このような後戻りをしながら探索する方法を，バックトラック（backtrack）と呼ぶ．これ
以上候補を印字する必要がなければ，
「.」を入力することによって，バックトラックを中止させることができる．
8.2
その他の機能
Prolog は，SML と同様にリストを扱うことができる．要素を並べてリストを生成するには，次のようにする．
プログラム 78: リスト (1)
[ 要素, 要素, 要素, ..., 要素 ]
既にあるリストの先頭の要素を付加するためには，
「|」を使う．
8. 7 章のドリル
96
プログラム 79: リスト (2)
[ 要素 | 後続 ]
後続部分は，リストであってもよいし，要素であってもよい．リストを使ったプログラム例を示しておこう．
プログラム 80: リストを使ったプログラム
first([X | Ys], X).
rest([X | Ys], Ys).
append([], Xs, Xs).
append([X | Ls], Ys, [X | Zs]) :- append(Ls, Ys, Zs).
reverse([], []).
reverse([X | Xs], Ys) :reverse(Xs, Zs), append(Zs, [X], Ys).
member(X, [X | Ls]).
member(X, [Y | Ls]) :- member(X, Ls).
select(X, [X | Xs], Xs).
select(X, [Y | Ys], [Y | Zs]) :- select(X, Ys, Zs).
selects([], Ys).
selects([X | Xs], Ys) :- select(X, Ys, Ys1), selects(Xs, Ys1).
これらの述語が何を意味しているのか考えてみるとよい．
Prolog は，算術計算を行うこともできる．その際には，計算結果を変数にマッチさせる．記述の仕方は次のよ
うになる．
プログラム 81: 算術計算)
変数 is 計算
算術計算の例として，2 乗を求めるプログラムを示しておこう．
プログラム 82: リストを使ったプログラム
square(X,Y) :- Y is X*X.
8.3. SPROLOG の字句解析
8.3
97
SProlog の字句解析
SProlog には，四則演算より多くの予約語が存在し，文字列の表現も現われる．SIMPLE のトークンをデータ
型で定義すると次のようになる．
プログラム 83: データ型によるトークンの定義
datatype token = CID of string | VID of string | NUM of string |
TO | IS | QUIT | OPEN |
EOF | ONE of string;
このトークンを生成する字句解析部は，四則演算の場合と次の処理が異なる．
• 識別子を，先頭が小文字で始まるもの（オブジェクト）と，大文字で始まるもの（変数）で区別する．それ
ぞれ，CID とVID で表す．
• NUM の引数は文字列である．
• 識別子からの予約語の判別する．
• 2 文字からなる演算子（:-）を解析して，TO として返す．
字句解析を行った結果は，次の print token で印字させることができる．
プログラム 84: 字句解析部
fun print_token (CID i) = (print "CID("; print i; print ")")
|
print_token (VID i) = (print "VID("; print i; print ")")
|
print_token (NUM i) = (print "NUM("; print i; print ")")
|
|
print_token (TO) = print ":-"
print_token (QUIT) = print "quit"
|
|
|
print_token (OPEN) = print "open"
print_token (IS) = print "is"
print_token (EOF) = print "eof"
|
print_token (ONE c) = (print "ONE("; print c; print ")")
問題 1 ：字句解析部の実装を次に示す．省略してある部分にコードを付加し，“structure Lexer = struct … end”
で括ってプログラムを完成させなさい．さらに，四則演算同様，gettoken を繰り返し呼び出す “run” 関数を
実装し，振舞を確かめなさい．
8. 7 章のドリル
98
プログラム 85: 字句解析部
fun read ISTREAM = case TextIO.input1 ISTREAM of
SOME x => String.str x
| NONE
=> ""
and integer ISTREAM i =
(* 文字列として数字を構成 *)
and identifier ISTREAM id =
let val c = TextIO.lookahead ISTREAM in
case c of NONE => ""
| SOME v => if (Char.isLower v) orelse (Char.isUpper v)
orelse (Char.isDigit v) orelse v = #"_" then
identifier ISTREAM (id^(read ISTREAM))
else id
end
and native_token ISTREAM =
let val c = TextIO.lookahead ISTREAM in
case c of NONE => EOF
| SOME v =>
if (* CID に対する識別子および予約語 *)
else if (* VID に対する識別子 *)
else if (Char.isDigit v) then NUM (integer ISTREAM "")
else if (* :- を認識して TO を返す *)
else ONE (read ISTREAM)
end
and gettoken ISTREAM =
let val token = native_token ISTREAM in
case token of ONE " " => gettoken ISTREAM
| ONE "\t"=> gettoken ISTREAM
| ONE "\n"=> gettoken ISTREAM
| _ => token
end