宣言的プログラミング(2) -Clips- #BRMS

Clips(C Language Integrated Production System)

前回はひとまず雰囲気をということで、かなり駆け足になってしまったので、直近必要になりそうなClipsの言語仕様/動作¹に限って改めて見ていこうと思います。なお、今回端折ってしまう、言語の背景についてはWikipedia、言語仕様等については、公式サイトの Documentationにあるリファレンスマニュアル(Basic Programming GuideやAdvanced Programming Guide)やユーザーズガイドを参照ください。

Clipsのデータ型

Clipsで使う(primitiveな)データ型としては、以下があります²。
float, integer, string, symbol, fact-address
このうちfloat, integer, stringはよいかと思います³。symbolは、英数字記号のシーケンスで他の言語で言えば定数的な扱いになります(Lispだったらまさにsymbol)。以下はいろいろなsymbolの例です。
red Hello B76-HI bad_value 127A 456-93-039
fact-addressについては下のファクトの項で一緒に説明します。

multifield value

またClipsではLispでいうListのようなものが定義できます。形式的には()で囲まれた複数のprimitiveなデータ型の値です。たとえば、
(a) (1 blue red) () (x 3.0 "red" 567)
となります⁴。

関数

前回は特に言及していませんでしたが、Clipsにも関数があります。他の言語と同様、組込み関数とユーザ定義関数があります。使い方は
(<関数名> <引数1> <引数2> <引数3> ...)
という感じ。たとえば、

CLIPS> (+ 3 4 5)
12
CLIPS> (* 5 6.0 2)
60.0
CLIPS> (+ 3 (* 8 9) 4)
79
CLIPS> (* 8 (+ 3 (* 2 3 4) 9) (* 3 4))
3456
CLIPS>

もう、ほぼLispですよね。またユーザ定義関数はdeffunctionを用いて定義しますが、今回の一連の記事ではあまり使わない(はず)ので詳しくはリファレンスマニュアルを参照ください。

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

Clipsの動作の基礎となっているプロダクションシステムはもともとAI研究において提唱されたもので、人間の思考をモデル化しています。知識表現においてよく使われるうちの一つの方法となります。前回にも書きましたが、図に表すと

といった感じ。前向き推論のClipsの場合、処理の１サイクルは、

長期記憶に保持しているルールの条件部とワーキングメモリ内のファクトを照合させて、マッチしたルールとファクトの組(ほとんどの場合複数存在)を候補として列挙し(照合)、
その候補の中から一つ実行する組を選び出し(競合解消)、
実行する(実行)

になります。3.の実行時にファクトを追加/変更/削除したりすることで、次の処理サイクルでマッチするルールとファクトの組が増減し、最終的にマッチする組が無くなって処理が終了します。

ワーキングメモリとファクト

ワーキングメモリ...これが人間の短期(作業)記憶をモデル化しており、記憶の中のひとつひとつの情報はファクト(fact)の形で表現されます。ファクトはワーキングメモリ(Clipsではfact-listとも言っています)に対して、追加(assert)されたり、削除(retract)されたり、変更(modify)されたりします。ワーキングメモリの中のファクトは一意に特定するために、fact-index, fact-addressなどと呼ばれる整数のインデックスが付番されます。このインデックスを表示するときは、頭にf-をつけてf-10などと表示されます。ただルールなどでファクトを操作する場合、明示的にfact-indexを指定するというよりも、後に説明するファクトを指定する変数を定義してその変数に対して操作することになるので直接fact-indexの値を意識することはあまりないかと思います。

Ordered facts

Clipsではファクトを表現する際に、2種類のフォーマットがあります。Ordered facts と Non-ordered facts です。Ordered factsは前回使った形で

(card spade 9)
(father-of jack bill)

といった形。それぞれのファクトの一番最初のシンボル⁵ (上の例では、cardとかfather-of)は、ファクトの全体の意味を表したり、あとに続くフィールド値間の関係を表したりするように使います。Ordered factsでは、ファクト内での値の順(位置)に意味があり、のちに説明するパターンマッチの際に、同じ位置どうしがマッチ対象となります。したがってファクト内での位置に意味が付随してきます。

Non-ordered facts

さて一方、Non-ordered factsでは、ファクトのフィールドに名前をつけることができるのでOrdered factsのように順番には依存しなくなります。たとえば

(card (suit spade) (rank 9))
; (card (rank 9) (suit spade))　のように順番変えてもOK

といった感じ。このデータ構造を定義するにはdeftemplateを使います。たとえば

(deftemplate card
    (slot suit
        (type SYMBOL)
        (allowed-symbols spade heart diamond club))
    (slot rank
        (type INTEGER)
        (range 1 13))
)

見てもらえば何となくわかると思うのですが、この例で card というのが、deftemplateで定義するファクトの名称、さらにスロット(slot)というのが並んでいますが、これがフィールドにあたり、suit, rank はそれぞれのフィールドに名付けられた名前になります。typeは、そのスロットのデータ型を示し、SYMBOL, STRING, LEXEME(SYMBOLまたはSTRING), INTEGER, FLOAT, NUMBER(INTEGERまたはFLOAT)などが入ります。またallowed-symbolsは、そのスロットに許されているSYMBOLの選択肢、rangeは、数の場合の許容範囲を示しています。

deffacts

初期状態などを指定するときに、factをひとつひとつassertで定義するのが大変...という場合にはdeffactsが使えます。

(deffacts cards
    (card (suit spade) (rank 2))
    (card (suit spade) (rank 3))
    (card (suit spade) (rank 4))
    (card (suit heart) (rank 2))
    (card (suit heart) (rank 3))
    (card (suit heart) (rank 4))
)

といった塩梅です。
ただし、deffactsを使った場合、下で説明する(reset)コマンドを使わないと、factが挿入されないので注意ください。なので、初期状態のfactを一覧列挙するといったときに使うのが最も適切かもしれません。

ルール定義と変数

ルールの定義にはdefruleを使います。前回も書きましたが簡単に復習します。

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

具体的には、たとえば

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

といった感じ。また否定(~)、And(&)、Or(|)も使えて

(defrule not-heart-spade
         (card (suit ~heart & ~spade))
    =>
         (printout t "ハートでもスペードでもなし" crlf)
)

という書き方も可能です。
またルールの条件部分に、?を先頭につけたSYMBOLで表す変数(variable もっと言うとここでは single-field-variable)を使うこともできて、

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

といった書き方ができます。パターンマッチによって変数の値が一旦定まるとそのルールの中で同じ変数は同じ値をとります。たとえば上記ルールの最初の条件部分のパターン(card (suit ?suit) (rank ?rank))がファクト(card (suit spade) (rank 9))にマッチしたとすると、?suit ← spade, ?rank ← 9となります。
すると、条件部分の2番目のパターン(card (suit ~?suit) (rank ?rank))は、(card (suit ~spade) (rank 9))と解釈され、この条件に合うファクトが探されます。
ワーキングメモリに(card (suit spade) (rank 9))、(card (suit heart) (rank 9))というファクトがあって、上記ルールの条件部分、1番目のパターンにファクト(card (suit spade) (rank 9))、2番目のパターンにファクト(card (suit heart) (rank 9))がマッチすると、変数?rankには、9が割り当てられるため、ルール実行の際にも実行部分で出現する?rank変数には 9が割り当てられます。したがって 9のワンペアです。という表示になります。
　また、ファクト自身を参照する変数を定めることができます。記述としてはファクトの前に、<変数> <- を指定します(以下の例参照)。これは条件部分でマッチしたファクトを実行部分でretract(削除)したり、modify(変更)したりするときなどに使います。たとえば⁶

(defrule retract-spade "スペード無くなり事件"
         ?spade <- (card (suit spade))
    =>
         (retract ?spade)
)

は、スペードのカードをすべて削除するルールです。また

(defrule retract-spade "ハートをダイヤへ、いかさまルール"
         ?heart <- (card (suit heart))
    =>
         (modify ?heart (suit diamond))
)

は、ハートのカードをすべてダイヤに変えてしまうルールです。

競合解消と優先度

　上で認知実行のサイクル(Clipsの処理サイクル)の話をしましたが、その中で競合解消(conflict resolution)については特に触れていませんでした。前向き推論のルールベースの場合、ルールとマッチするファクトとの組は、複数存在する可能性があり(というか大抵の場合複数存在)、どれを実行すべきかを判断する必要があります。そのフェーズが競合解消となります。
　競合解消には競合解消「戦略」という一般的な判断基準があって、どの戦略を選ぶかによって動きが変わってきます。探索問題でも深さ優先探索と幅優先探索というのがあるのと同じように、Clipsでも「戦略」を指定することで動きを制御することができます。ただ実際問題としては「戦略」を変更して動きを制御するというよりも、ルールに優先度を設定して個々のルールレベルで動きを制御する方が普通なので、ここでは「戦略」には立ち入らないことにします⁷。Clipsのデフォルトの戦略は、depth(いわゆる深さ優先)で、新しくできたfactにマッチするルールの組を優先的に実行する戦略です。考え方としてはなるべく新しい情報に基づいて判断するということでそれほど違和感はないかと思います。
　上にもあげましたが、戦略は競合解消の一般的な方向性であり、それより重視されるのがルールにつけられる優先度です。競合解消の際に、高い優先度がつけられたルールから実行することになります。
　たとえばどんな時に優先度を使うかというと、ある禁止されたファクトの組が存在したときに、優先度を高くした形で禁止ルールを記述しておき、禁止される組み合わせのファクトが生成されたと同時に禁止ルールが動くといった形でしょうか。
　また、トランプの例で恐縮ですが、ババ抜きで、手札に同じ数のカードがあったら直ちに捨てるといったルールを優先度を高くして作っておくとしましょう。通常のサイクルでは手札を取って、渡すというのが順繰りに回っていきますが、常に優先度の高い「同じ数ペア」ルールが手札の内容を監視しており、マッチしたら直ちに手札を捨て、通常のサイクルに戻る...。こういったときなどに使えるでしょう。
　ルールの優先度の指定の仕方ですが、ルールの名称の次の行に
(declare (salience <整数(-10000～10000)>))
を加えます。指定しないデフォルト状態では優先度 0 となります。たとえば

(defrule matched "2枚揃った！"
    (declare (salience 100))
    ?c1 <- (card (suit ?suit) (rank ?rank) (player ?player&~discarded))
    ?c2 <- (card (suit ~?suit) (rank ?rank) (player ?player))
=>
    (modify ?c1 (player discarded))
    (modify ?c2 (player discarded))
)

のように書きます。

追加のコマンド少々

(clear)
環境を立ち上げた最初の状態に戻します。すなわちファクトもルールも定義されていない状態です。
(reset)
ルールはそのままに、ワーキングメモリをクリアします。その上でdeffactsに定義されているファクトを読み込みます。
(run <正の整数>)　(正の整数はオプション)
正の整数回だけ認知実行サイクルを実行します。途中でマッチするファクトとルールの組がなくなったら停止します。引数を指定しないときはマッチするファクトとルールの組がなくなるまで実行します。
(load <ファイル名>)
defrule, deftemplate, deffactsなどが記述されたファイル名で指定された外部ファイルを読み込みます。

今回のまとめ

必要なところだけ説明すれば...と、気軽に書き始めてしまったのですが、ちょっとでもちゃんと書こうとすると思ったよりも手間がかかり...;;。前回の最後に今回はポーカーの役判定を説明するとか言っておきながら必要な言語仕様を簡単に説明しただけで終わってしまいました。次回こそはポーカーの役判定の説明をと思っております。

連載記事

Clipsについてすっかり失念していたのですが、実は基本、日本語使えません...;;。 ↩
この他にクラスなども定義できたりするのですが、今回はオブジェクト指向の機能についての説明は省きます。 ↩
floatは内部的には Cのdouble, integerは Cのlongです。また文字列はダブルクォートで囲みます(シングルクォートは文字列にならない)。 ↩
Clipsでは、プレースホルダー(placeholder - 入れもの、場所)のことをフィールド(field)と呼んでおり、ひとつのプレースホルダーに入っている値をsingle-field valueと呼び、通常のprimitiveなデータ型の値を指しています。さらに0個以上のsingle-field valueの並びをmultifield valueと呼び、表現上は上記のように()で囲まれた複数のsingle-field valueの並びとなります。 ↩
Ordered、Non-orderedに関わらずファクトの最初のシンボルには、以下の予約語は使うことができません。
test,and,or,not,declare,logical,object,exists,forall ↩
ちなみにですが、defruleやdeftemplateなどは、その名前の横にダブルクォートで囲んだコメントを書くことができます。 ↩
初期の頃は競合解消「戦略」という考えは確かにあったのですが、一般的な動きを制御する「戦略」に依存した作りは、作者の意図しない動きを招きやすく、現在では明示的に優先度を指定するという形が普通です。 ↩