SmallOPS を発展させた Toy Open Production System を SourceForge.jp にて公開しています。
また、本コンテンツを書くに辺り、以下の参考書を参考にしています。
プロダクションシステムは、 事実を蓄積するためのワーキングメモリ、 プロダクションルールを蓄積するためのルールベース、 競合解消を行いながら事実とプロダクションルールから推論を行うルールインタプリタからなり、 以下のようなクラス構成となる。
これは非常に簡潔な表現であり、 そのとおりProductionSystemクラスの定義を確認すると以下のような記述を見ることができる。
class ProductionSystem { private: /** * ルールベースです。 */ RuleBase rulebase_; /** * ワーキングメモリです。 */ WorkingMemory workingMemory_; /** * ルールインタプリタです。 */ RuleInterpreterPtr interpreter_; };
事実とプロダクションルールの格納順序は、 ルールインタプリタが推論を行う際の動きに大きな影響を与える。 そこでWorkingMemoryクラスとRuleBaseクラスは、 事実とプロダクションルールのそれぞれを挿入された順序で管理する。 従って、 WorkingMemoryクラスとFactクラス間、RuleBaseクラスとProductionRuleクラス間の関連は <<ordered>>である。
WorkingMemoryクラスは、事実の蓄積を目的としたクラスである。 以下にWorkingMemoryクラスのクラス図を示す。 ワーキングメモリは蓄積した事実に一意となる時刻タグと呼ばれる数値を割り振る。 一意な数値を割り振るために、WorkingMemoryクラスはcount属性を持っている。 新しい事実がワーキングメモリに追加されると、 このcount値が増加していき追加された事実に対して一意な値が割り振られることが保障される。 WMElementクラスは、追加された事実に時刻タグを付加するためのクラスである。
以上のクラス図から、 WorkingMemoryクラスはWMElementインスタンス群を順序付けて所有することがわかる。 しかし、これに対応するC++のコードは少々単純ではない。 これに対応するC++のコードを以下に示す。
class WorkingMemory : public Printable { private: typedef std::multimap<std::string, WMElementPtr> WMElementMap; typedef std::vector<WMElementPtr> WMElementVector; private: /** * 名前で検索可能なワーキングメモリ要素列です。 */ WMElementMap namedElements_; /** * 挿入順序にソーティングされたワーキングメモリ要素列です。 */ WMElementVector orderedElements_; };
WorkingMemoryクラスは、 一つのWMElementインスタンスをmultimapとvectorという二つのデータ構造で管理している。 multimapとはキーと値の組み合わせでデータを管理するマップと呼ばれるデータ構造の一種で、 キーから値を高速に検索することができる。 WorkingMemoryクラスはキーとして事実の名前を用いているため、名前から事実の検索を高速に行うことができる。 ただし、挿入順序には関係無い順番で値が格納される。 vectorとは動的配列の一種で、 ランダムアクセスも挿入順序に従ったシーケンシャルアクセスも可能なデータ構造である。
これらの二つのデータ構造は、別の目的で使用される。 multimapは名前で高速に事実を検索できることから、 ワーキングメモリに重複する事実が追加されないように、 追加時にmultimapにより管理されたデータを使って同名の事実を絞り込み、 同一のデータがあった場合には挿入を行わない処理を実現できる。 以下に、それに対応するC++のコードを示す。
bool WorkingMemory::add(const FactPtr& fact) { // 要素が重複してたら失敗する if(searchFact(fact)) { return false; } // 要素が重複してなかったら成功する else { WMElementPtr element(new WMElement(count_++, fact)); namedElements_.insert(WMElementPair(fact->getName(), element)); orderedElements_.push_back(element); return true; } } bool WorkingMemory::searchFact(const FactPtr& target) const { // 同じ名前を持つ範囲だけを検索対象とする pair<const_mapIterator, const_mapIterator> range =namedElements_.equal_range(target->getName()); for(const_mapIterator i=range.first;i!=range.second;++i) { if(i->first!=target->getName()) break; // 等値と判断されたら見つかったとする const FactPtr& fact=i->second->getFact(); if(target->equals(*fact)) { return true; } } return false; }
vectorは挿入順序に従ったシーケンシャルアクセスができるため、 推論のときに事実を参照するときに使用する。 これは、事実の順序は推論の結果に大きな影響が与えてしまうためである。
RuleBaseクラスは、プロダクションルールの蓄積を目的としたクラスである。 以下にRuleBaseクラスのクラス図を示す。
以上のクラス図から、 RuleBaseクラスはProductionRuleインスタンス群を順序付けて所有することがわかる。 しかし、これに対応するC++のコードもWorkingMemoryクラスの場合と同様に単純ではない。 これに対応するC++のコードを以下に示す。
class RuleBase : public Printable { private: typedef std::set<std::string> StringSet; typedef std::vector<ProductionRulePtr> ProductionRuleVector; /** * プロダクションルールの名前列です。 */ StringSet names_; /** * プロダクションルール列です。 */ ProductionRuleVector rules_; };
RuleBaseクラスも、 一つのProductionRuleインスタンスをsetとvectorという二つのデータ構造で管理している。 setとは格納された値を高速に検索することができる。 RuleBaseクラスはこのデータ構造にプロダクションルールの名前を格納しており、 名前から同名のプロダクションルールが既に登録されているかどうかを高速に判断できる。 以下に、それに対応するC++のコードを示す。
bool RuleBase::add(const ProductionRulePtr& rule) { pair result=names_.insert(rule->getName()); // 同じ名前のルールが既にあったら失敗する if(result.second) { rules_.push_back(rule); return true; } else { return false; } }
vectorを使用した理由はWorkingMemoryクラスのときと同様である。
RuleInterpreterクラスは、 ワーキングメモリに蓄積された事実とルールベースに蓄積されたプロダクションルールから 推論を行うことを目的としたインタプリタである。 その際、競合集合を求めるためにConflictSetインスタンスを生成し、 戦略に基づいて競合解消を行いながら推論を行う。 以下に、RuleInterpreterクラスのクラス図を示す。
RuleInterpreterクラスは、競合解消を行うための戦略を決定するgetStrategyメソッドを持っており、 推論を行う際に呼び出され、その戦略に基づいて例化が行われる。 それに対応するC++のコードを示す。
bool RuleInterpreter::instantiate(ConflictSet& conflictSet, InstancePtr& result) { ConflictResolutionStrategyPtr strategy=getStrategy(); return strategy->resolve(conflictSet, result); }
本章では、 ProductionSystemクラス・ WorkingMemoryクラス・RuleBaseクラス・RuleInterpreterクラスという システムの全体を構成するクラスについて説明を行った。 次章では、事実やプロダクションルールで用いられるOAV形式のデータに関するクラス構成について説明する。