プログラミング言語論 論理型プログラミング 言語

プログラミング言語論 論理型プログラミング

言語

目次

1.

2.

3.

１

.

１ . １ 論理型言語

１ . ２ 論理プログラミング

１ . ３ 述語

１

.

 公理（論理式）の集合を定義し、

推論規則の適用により計算を行う



 Prolog が代表



復習

１

.

 Prolog の応用











※ パターン照合、後戻り検索、

不完

全な情報を扱う応用に向いて ⁵

復習

１

.

 論理プログラミングとは

(1) 情報の表現のための事実と規 則の使用

(2) 質問の応答への論理推論の使 用



し、質問を与える。処理系が論 6

復習

?- mortal(Y).

Y=socrates

１

.

 Prolog の例

human(socrates).

mortal(X) :- human(X).

事実と規則

回答 質問

復習

１

.

 論理プログラミングでは、

関数ではなく、関係 (relation) を扱う



関数プログラミングよりも柔軟 である

１

.

 述語 (predicate)







（関数のように数値等の値を返

１

.





述語名（項，項，・・・，

項）

１

.



「 taro は hanako の父親で ある」

システムは、様々な質問に答え

father(taro, hanako).

事実を述べておく

１

.

質問とその回答 （ 1 ）

質問（述語）が、真か偽かを 答える

?- father(taro, hanako).

true.

１

.

質問とその回答 （２）

?- father(taro, X).

X = hanako .

?- father(Y, hanako).

Y = taro .

X

Y

１

.

 Prolog の述語について



、で Prolog の述語を表現する ( 例 ) atom/1



２

. Prolog

２ . １ 基本構文

２ . ２ プログラム ２ . ３ 質問

２ . ４ 否定

２ . ５ 演算

２

.

Prolog

 Prolog の基本構文

<fact> ::= <term> .

<rule> ::= <term> :- <terms> .

<query> ::= <terms> .

<term> ::= <number> | <atom> |

<variable> | <atom>(<terms>) 事実

規則

質問

２

.

Prolog

 項 (term)



２

.

Prolog



数 (number)

アトム (atom)

小文字で始まる、それ自身を表 す

変数 (variable)

大文字で始まる

[ 例 ]

２

.

Prolog



アトムと括弧でくくられた部分 項の並び

述語は複合項により表記される

link(bcpl, c)

２

.

Prolog



若干の演算子は、前置記法だ けではなく、中置記法で書か れることもある

[ 例 ]

=(X,Y) ⇒ X=Y

２

.

Prolog

 Prolog のプログラム





述語名 引数の数

２

.

Prolog

 規則 (rule) と事実 (fact)



body₁ から body_N までがすべ て成り立てば head が成立す る、ということを表す

head :- body

, body

,

,

body

.

２

.

Prolog



ホーン節で書くと

body

∧

body

→ head

head ∨ body₁ ∨ body₂ ∨ ・・∨ body_N

２

.

Prolog



path(L,M) :- link(L,X), path(X,M).

ヘッド ボディ

２

.

Prolog



ヘッド部のみで、ボディ部 のない 特別な規則

とみなす事ができる

link(fortran, algol60).

２

.

Prolog

 プログラム例

% links of programming languages

link(fortran, algol60).

link(algol60, cpl).

link(cpl, bcpl).

２

.

Prolog

（続き）

link(algol60, simula67).

link(simula67, cplusplus).

link(simula67, smalltalk80).

path(L,L).

path(L,M) :- link(L,X), path(X,M).

２

.

Prolog

プログラミング言語の関係を表 している

２

.

Prolog



path(L,L).

は、

すべての

L

path(L,L)

２

.

Prolog

次の規則の意味は、

path(L,M) :- link(L,X), path(X,M).

すべての

L, M

もし、ある

X

link(L,X)

path(X,M)

２

.

Prolog



「矢印」を "link" で表し、

「矢印をたどってたどり着く 道があること」を "path" で 表している

２

.

Prolog

 コンサルト (consult) は、事実 と規則からなるプログラムファイ ルを読込み、その内容を 「規則 データベース」 に追加する

２

.

Prolog



?- consult( 'links.swi' ).

% links.swi compiled 0.00 sec, 1,652 bytes true.

?-

２

.

Prolog

 演習 ８ . １





 father

 mother

 parent （ father と mothe

２

.

Prolog

jiro masae

ichiro reiko

taro keiko

yoshio hanako

２

.

Prolog

 質問 （ query ）





質問を入力する

２

.

Prolog



（質問となる述語列）を、ゴー ル節 と呼ぶ

（処理系は、ゴール到達 を 目指して推論を進め

２

.

Prolog

 次の質問

の意味は、

<term>

, <term>

,

,<term>

.

<term>

<term>

かつ

<term>

２

.

Prolog



?- father(taro,hanako),

father(hanako,ichiro).

false.

応答は、単に

true(yes)

２

.

Prolog



?-

father(jiro,L),father(L,

M).

father(jiro,L)

father(L,M)

L,

２

.

Prolog

 解 (solution)



質問文（ゴール節）を真とす るよう

な、変数の値への束縛 である



充足可能 (satisfiable) で

ある ⁴¹

２

.

Prolog



?-

father(jiro,L),father(L, M).

L = yoshio,

２

.

Prolog

セミコロンを入力 次の解を表示する

改行 (Enter) を入力

解の表示を終了し、次の質問 を受け付けるプロンプトを表 示する

( 注 ) 細かな動作は、システムに ₄₃

２

.

Prolog

セミコロンを入力した例

?- father(jiro,L),father(L,M ). L = yoshio,

M = ichiro L = yoshio,

;

２

. ４ Prolog

 失敗による否定 (negation as fa ilure)



⇒ Prolog は false (no) と応 証明することが出来なけれえる ば、

偽に違いない

２

. ４ Prolog

【例】 前述のプログラムは、 ta ro の親

　　については何も言っていな い

?-

father(saburo,taro).

false.

２

. ４ Prolog

 否定演算子 not



注： not は、複雑な文の場合は使用方法

?- parent(L,N), parent(M,N), not(L=M).

L = jiro,

N = yoshio, M = masae ; L = taro,

N = hanako,

２

. ４ Prolog



２

. ４ Prolog

前ページの例と比較

?- not(L=M), parent(L,N), parent(M,N).

false.

質問が始まった時点で、

L

M

の値は不明である。不明な値は等 しくなりえるので、

not(L=M)

２

. ５ Prolog

 四則演算



数の除算、 mod は剰余

 比較演算 （数値の比較）



２

. ５ Prolog

 演算結果を変数にセットするには is を使用する

?- X is 1 + 2 + 3.

X = 6.

is

２

. ５ Prolog

注： is は、通常の代入とは異 なる

?- X is 3, X is 4.

false.

最初の is では、パターンマッチン グ（単一化という＝後述）により、

変数 X は３となる。次の is では、

２

. ５ Prolog

 演算の例（ 1 ）

square(X, Y) :- Y is X * X.

?- square(5, Y).

2

実行結果

２

. ５ Prolog

 演算の例（ 2 ）

%

fact(0, 1).

fact(N, F) :- N > 0, N1 is N - 1,

階乗を求めるプログラム

２

. ５ Prolog



%

fact(0, 1).

fact(N, F) :- N > 0,

fact(N - 1, F1),

F is N * F1.

２

. ５ Prolog

 演習８ . ２



★ フィボナッチ数の定義

fib(0) = 0, fib(1) = 1 fib(n) = fib(n-1) + fib(n

３

. Prolog

３ . １ 単一化

３ . ２ バックトラック

３ . ３ カット

３

.

Prolog

 具体化





 具体値 (instance)

３

.

Prolog



?- f(X,b) = f(a,Y).

X = a, Y = b.

f(a,b)

f(X,b)

f(a,Y)

３

.

Prolog

 単一化 （ unification ）



、 同じ値で具体化する）

３

.

Prolog



により定義されているとする

次の応答を計算するため、単一 化が使用される

identity(Z,Z).

?- identity( f(X,b),

f(a,Y) ).

３

.

Prolog

次の二つを単一化

identity(Z,Z)

identity(f(X,b),f(a,Y)) これにより、以下も単一化され る

３

.

Prolog

 Prolog プログラムの動作の流れ

1.

語をヘッド部にもつ節を探す

2.

真になるかを調べる

3.

３

.

Prolog

4.

5.

３

.

Prolog

 バックトラックの例



?- parent(keiko, hanako).

どのような順序で、

true.

３

.

Prolog

① ヘッド部に述語 parent を持 つ節を探す

⇒ parent(X,Y) :- father(X,

見つける

② {X=keiko, Y=hanako} で単一 化

⇒ father(keiko, hanako)

３

.

Prolog

③ ヘッド部に father を持つ節 を探す

⇒ father(jiro, yoshio). が

⇒ バックトラック

④ 別の father をヘッド部とす る述語を探す

⇒ 同様に単一化できず、失敗

３

.

Prolog

⑤ バックトラック して、別の節 でヘッド部に述語 parent を 持つものを探す

⇒ parent(X,Y) :- mother (X,Y). を

見つける

⑥ {X=keiko, Y=hanako} で単一

化

⇒ mather(keiko, hanako)

３

.

Prolog

⑦ ヘッド部に mother を持つ節を 探す

⇒ mother(masae, yoshio). が

⇒ バックトラック

３

.

Prolog

⑧ 別の mother をヘッド部とす る述語を探す

⇒ mother(keiko, hanako).

を見つ ける

⇒ mother(keiko, hanako) が

⇒ parent(keiko, hanako) が

真 ⁷⁰

３

.

Prolog

 強制バックトラック



かった）後も、ユーザが セミコ ロンを入力すると、バックト

ラックを行い次の解を探す

３

.

Prolog



?- father(jiro,L),father(L,M ). L = yoshio,

M = ichiro

；

３

.

Prolog

 バックトラックを続けると、探索 空間全体を調べる



カット により、バックトラックを

３

.

Prolog

 組込み述語 ！を評価（実行）す ると、以降の節を探索しない

（そこを後戻りできない）





３

.

Prolog



head :- goal_A, ..., goal_M, !, goal_N, ..., goal_Z.

再試行は行われない 再試行する

一方通行

３

.

Prolog



head

:- goal

, !, goal

. head

:- goal

, goal

.

head

:- goal

, goal

.

カットは

goal

３

.

Prolog

 カット利用の例 ＝ 条件判断

condSubr(X) :- X =:= 1, !, print('One').

condSubr(X) :- print('not One').

カット

(!)

1

'not One'

x

【参考】 Ｐｒｏｌｏｇ 参考Ｕ ＲＬ

 ＳＷＩ -Prolog's home

http://www.swi-prolog.org/

 お気楽 Prolog プログラミング 入門http://www.geocities.jp/m_hi roi /prolog/

 Prolog 入門

http://bach.istc.kobe-u.ac.j ⁷⁸

お疲れさまでした