宣言的プログラミング(1) -論理型言語・ルールベース-

宣言的プログラミング

どうも宣言的なプログラミングが(多少?)注目を集めているようでうれしい限り(笑)。

とは言え、本当のところ「宣言的」あるいは「宣言型」といった定義がはっきりした言葉があるのか？とも思います。まあケースケースによって厳密な定義はできるかもしれないけれど、総体的には結局のところ感覚的なもののような気がしないでもないですね¹。

ただ手続き型(命令型)プログラミングの対極として考えれば、何となくの感覚は割と共有はできるかもと思いつつ、7～8年ほど前に自分のブログで以下のようなたとえ

たとえて言えば、手続き型のプログラミングは、処理の手順を一から教えなければならない新入社員のようなものである一方、ルールベースによる宣言的プログラミングは、「これこれをやっておいて(問題の性質や制約 ! )」と伝えておけば、それなりにいいようにやってくれる、常識的な処理手順はわかっている入社1～２年目の社員といったところでしょうか。
(if-then文とif-thenルール －宣言的プログラミングのすすめ (1)－)

を書きました...やっぱり感覚的(笑)。

で、結局のところある程度個別に見ていかないと具体的にはよくわからないと思うので、ここでは個人的には一番とっつきやすいと思われる前向き推論のプロダクションシステムの言語を使って「宣言的」というのを具体的にみていこうかと思います²。

プロダクションシステムとBRMS

ところで前向き推論のプロダクションシステムの言語って何？という方は多いかと思うので、もうちょっとは身近(でもないかもですが)な言い方をすると、BRMS³の基盤となっている言語と言えばよいでしょうか。

実はBRMSのルーツは昔のAI研究(エキスパートシステム⁴)にあって、その中身はAIで言われるところのプロダクションシステム(ルールベース)そのものなんですね。そしてその記述言語が、ルールベースの論理型の言語⁵となります。

まず、一般的な観点からプロダクションシステムの動きについてみてみます⁶。

プロダクションシステムの動き

ここにAならばB、BならばCというルールがあったとしましょう。論理式の形で書くと

A→B, B→C

です。ここで

A

という事実が成り立ったならば、上記のルールを適用して

B, C

という事実が成り立ちます。この推論過程⁷をモデル化したのがプロダクションシステムになります。

さてプロダクションシステムのシステム的な構成要素は

• ワーキングメモリ
  人間の短期記憶をモデル化したもので、事実(factと呼ぶ)が読み書きされる記憶の場。
• 知識ベース
  人間の長期記憶をモデル化したもので、ルールが保持される記憶の場。
• 推論エンジン
  事実(fact)に対して実際にルールを適用させて推論を進めていく機構。

の３つ。で、上記のルールの例を使って、プロダクションシステムの動きのイメージをみていくとすると、たとえばホワイトボードをワーキングメモリに例えて

1. 目の前のホワイトボード(ワーキングメモリ)を推論エンジンがじっと見ていて、知識ベースにあるAならばB、BならばCというルールが適用できないか今か今かと待ち構えている。
2. Aという事実(fact)がホワイトボードに書き込まれた！
3. 推論エンジンは待ってましたとばかりにAならばBというルールを適用してBという事実をホワイトボードに書き込む。
4. 今度はBという事実が書き込まれたということに気づいた推論エンジンはBならばCというルールを適用してCという事実をホワイトボードに書き込む。
5. 新たな適用できるルール、事実がなくなったのでひとまず実行終了。

といった感じ。

CLIPS

さてさて、今回ルールベース⁸の言語として選んだのがCLIPS(Wikipediaはこっち)という言語。近年ではDroolsがルールベースを説明するのに割と使われるのですが、

• Droolsは、もう最近道具立てが大きくなりすぎて準備が面倒になってきた(ただDockerイメージもあるみたいだけど)こと。
• CLIPSは、NASA発で由緒正しく(?)パブリックドメインでもあったので、一時期(って言っても30年ほど前(笑))は実質デファクトスタンダード状態になっていたこと。
• CLIPSは、その後に作られたルールベースの言語に多大な影響を与えている(たぶんDroolsにも)こと。

などのことからCLIPS⁹を選んでみました。

では、実際にCLIPSを使って書いていってみましょう。まずインストールして、CLIPSIDEを立ち上げると以下のようなウィンドウが表示されます。

factの挿入

この状態で(assert (card spade 9))と入力して改行してみましょう。
このassertは、引数にあたるfactをワーキングメモリ(ホワイトボード)に書き込みます。
さらにここで(facts)と打ち込んで改行してみましょう。すると現在ワーキングメモリに書かれているfactの一覧が表示されます。ここまでやった画面が以下

ルールの定義

次にルールを定義してみましょう。ルールの定義は論理式¹⁰

LHS→RHS

と似たような形で

(defrule <rule名> 
         ;LHS factにマッチするようなパターンを列挙します。
    =>
         ;RHS ここにassertなどのアクションを書きます。
)

というように書きます。具体的な例をあげると

(defrule spade-9
         (card spade 9)
    =>
         (printout t "spade 9 です" crlf)
)

一目で何となくやってることはわかると思うのですが、一応書き下してみると、

spade-9という名称のルールは、
もし(card spade 9)というfactがワーキングメモリにあった
ならば、spade 9 です　という文字列と改行を出力する(printout)
(ちなみに次に書いてあるtは標準出力を表す呪文だと思ってください)
と定義される

ということになります。
では、このspade-9というルールをCLIPSIDEにコピペでも何でもして改行を入れてみましょう。するとルールが知識ベースに読み込まれます。

実行

　ここでさらに(run)と打ち込んで改行してみましょう。これは推論エンジンの実行を開始するという意味になります。すると、spade 9 ですという文字列が出力されることがわかるでしょう。
　これはルールspade-9の条件部分がfactの(card spade 9)とマッチし、ルールspade-9が「発火」(ルールが動くことを発火とよく言います)し、標準出力に spade 9 です という文字列と改行が出力されたことになります¹¹。

さて、ルールのRHSにはassertを書くこともできます。たとえば

(defrule spade-5
         (card spade 9)
    =>
         (assert (card spade 5))
)

というルールを読み込ませて、(run)で実行してみましょう。その後(facts)でfactを表示させてみると以下のように2つのfactがワーキングメモリに存在することがわかります。

変数

で、ルールのLHSのパターンには変数を設定することもできます。変数は?で始まります。たとえば?suitとか?rankとかいった感じ。LHSのパターンに変数が含まれる場合、該当する箇所のfactの値がその変数にバインド(束縛)されます。実際、ルールのLHS(条件部分)のパターンとfactとは、パターンマッチの機構を使ってマッチされます。たとえば以下

(card ?suit ?rank) ; LHSのパターン
(card spade   9  ) ; fact

のような場合、位置の一致している¹²?suitとspadeの間でマッチして、変数?suitにspadeがバインドされます。また?rankと9の間でマッチして、変数?rankに9がバインドされます。

上記のパターンマッチの例を利用してこんなルールを作ることができます。

(defrule printout-cards
         (card ?suit ?rank)
    =>
         (printout t ?suit ?rank crlf)
)

このルールを読み込ませて(run)で実行させてみましょう。するとこんな感じ

printout-cardsルールの(card ?suit ?rank)のパターン部分が、fact(card spade 9)とfact(card spade 5)それぞれにマッチしてルールが2回動いています。その結果(card spade 9)にマッチしたときには、?suitにはspadeがバインドされ、?rankには 9 がバインドされ spade9 が表示されます。同様に(card spade 5)にマッチしたときには spade5 が表示されます。

パターンマッチ

実はこのLHSのパターンマッチの機構って非常に強力なものなんですね。ルールのLHSは複数のパターンを書くことができ、それらはAND条件で結ばれます。たとえばこんなルール

(defrule one-pair
         (card ?suit ?rank)
         (card ~?suit ?rank)
    =>
         (printout t ?rank "のワンペアです。" crlf)
)

を書くこともできます(ちなみに~は否定を表します)。数は同じで種類の違う2枚があるとワンペア。(card heart 9)というfactをassertして上記のルールを読み込み(run)してみましょう。すると

となります。
結果をみてみましょう。
このうちheart9が出力されているのは、ルールprintout-cardsが、(card heart 9)に適用された結果。9のワンペアです。が2回出ているのは、実はルールのLHSの２つのパターンに対し

         (card ?suit ?rank)   → (card spade 9)
         (card ~?suit ?rank)　→ (card heart 9)

         (card ?suit ?rank)   → (card heart 9)
         (card ~?suit ?rank)　→ (card spade 9)

2通りのマッチングの仕方が出てくるからです。これを回避するにはcardにid番号をつけたり、種類(suit)の部分に順番をつけたりして、常に上から昇順になるように限定したりすればよいです。

以上、まずはプロダクションシステム(ルールベース)のプログラミングの雰囲気はつかめたでしょうか。かなり駆け足で余分なところは端折っての説明で、わかりにくい部分も多々あったかもしれませんが、この続きの次の記事では、ポーカーの役判定を例にとってもう少し「宣言的」ということのはっきりするようなプログラミング例を見ていきたいと思います。

連載記事

1. 宣言的プログラミング(1) -論理型言語・ルールベース-
2. 宣言的プログラミング(2) -Clips-
3. 宣言的プログラミング(3) -ババ抜きシミュレータw-

1. 宣言型プログラミング(Wikipedia)。 ↩

2. 宣言型の言語というと最近は関数型の話が比較的話題にのぼったりもしていますし、私も実は言語としては論理型より関数型言語が好みなのですが...。古くはLispから、結局処理系自体は触らずじまいのMiranda(Haskellのルーツ)とか、最近だとScalaとかね。ちなみにCourseraにこんな(Functional Programming in Scala Specialization)のあるのね。 ↩

3. 正確に言うと、主流となっているBRMSの基盤。
   主流のBRMSとは、たとえば、日本で使われてるものだったらこの辺
   ・IBM Operational Decision Manager
   ・IBM Decision Manager open edition (Red Hat Decision Manager, Drools)
   ・Progress Corticon
   ・Sparkling Logic SMARTS ↩

4. エキスパートシステムって、ディープラーニングの検定試験などでは終わった感が醸し出されている(笑)ような気がするのですが、今は、その知識表現方法(ルールベースなど)の利点(ルールを抜き差ししたり変更したりしやすい)を活かされて、(BRMSという形で)実用面においてよく活用されています。 ↩

5. あまり論理型の言語の中に入れることは少ないけど、述語論理ベースで前向き推論のしくみなので一応論理型と言ってもよいかと。 ↩

6. ずいぶん昔にこんなのも書いていたのでご参考まで ↩

7. ちなみに、この推論過程がA→B、B→Cと矢印方向に前向きに進んでいくのでプロダクションシステムを前向き推論と言ってます、またfactをつくりながらそのfactを元に推論を進めていくのでデータ駆動などという言い方もします。一方Prologは逆に結論の方から前提のfactを確かめていくといった動きになるので、後向き推論と呼ばれます。またそのためゴール指向であるなどと言われることもあります。 ↩

8. ルールベースって言葉、最近なんとなく非常に拡大解釈されてしまっていて、単純なif-then文をルールとしている向きが多いような気がします。でもでも、本来ルールとは宣言的なものであって、手続き的なif-then文とは違うものなんだが...混同されてしまうとなあ...なんか違うなあ...ということでその昔書いた(嘆き節(笑)の)記事がこれ。 ↩

9. ちなみに昔こんなのも書いています-CLIPS超入門- ↩

10. ここでA→Bと書かずにあえてLHS→RHSと書いたのは、プロダクションシステムの言語ではよく矢印の左(if部分)をLHS(Left Hand Side)と言い、矢印の右(then部分)をRHS(Right Hand Side)と言うのでその慣例に従いました。 ↩

11. ちなみにこの状態のまま(run)をもう一回入力して改行しても何も起こりません。推論エンジンが実行し始めると、原則として条件が合致するようなfactとルールの組が存在する限り実行を続けますが、一旦実行したfactとルールの組は二度と実行されません(そうでないと無限ループに入ってしまうので...)。 ↩

12. 今回は簡単のために単純にfactの位置に対してそれぞれ意味を与えて(factのリストの2番目に来るのがトランプのマーク(suit)、3番目に来るのがトランプの数字)、位置の一致をもってフィールドの意味の同一性を担保してます。ただ、さすがにこれ、プログラムのつくりとしてどうなの？という話は当然出てくると思います。でもご安心ください。今回は説明しませんが、factについてレコードやクラスの定義のようにフィールドに名前をつけたデータ構造を定義することも当然でき(deftemplateなどで定義する)、同じフィールド名のフィールド値の間でのパターンマッチもできる機構は備わっています。 ↩