MINERVA superseeded IF/Prolog.
Please see
http://www.ifcomputer.co.jp/MINERVA
for details.
We discontinued to sell IF/Prolog Dec 31. 2003.
Dedicated technical support for IF/Prolog ended Dec 31 2008.
This site is maintained as a community service only.
制約処理パッケージにより、資源割り当ての課題が、より容易に処理できるようになりました。
IF/PrologV5.0制約処理パッケージ(オプション)は、IF/Prologに最新の「制約に基づ
いた問題解決」パラダイムを導入しました。これにより、従来「複雑す
ぎて扱えない」とされてきた拡張的な領域の問題も、IF/Prologを使用
して解決することができるようになりました。
例えば、航空・鉄道での運航計画、生産計画、乗務員などの人員配置
計画を始めとするほぼすべての資源割り当ての課題が、効果的な宣言的
方法で処理できるようになりました。
制約処理パッケージでは、異なる制約クラスを、異なるPrologの
モジュールに分割しています。モジュール化はIF/Prologの非常に
重要な特長であり、産業分野でのアプリケーションでも使用され実証
されてきました。既存のアプリケーションのコードとの互換性もあり
ます。
現在、様々な分野で、制約処理パッケージを使用したアプリケーシ
ョンの開発が進んでいます。また、すでに以下に挙げるような本格
的なアプリケーション開発中に制約処理技術の改良も行なわれ、
この技術自体もすでに実証されています。
- 鉄道信号および交通制御:
リアルタイムデータに基づいて、鉄道時刻表を再スケジューリング
するために開発された、プロトタイプシステム。
- 設計制御ソフトウェア:
シンボリックモデルチェック方式を利用して、幅広い分野の複雑な
技術システムを検証する。システムの記述、特性の仕様を入力する
と、自動的にシステムの特性をチェックする。
- 回路検証環境
新規に開発された回路が論理的に正確なものかどうかを検証する
システム。
デジタル回路の出力と入力を論理関数として計算し、それをシンボリ
ックに回路仕様の対応する関数と比較している。ASICの検証に使用
されている。
制約処理パッケージは、Prologが提供する計算領域に加えて、さら
に5つの計算領域を備えています。
・長精度整数と有理数: 任意の長さを持つ整数と有理数の正確な計算。
・コルーチン: 変数の具体化に伴って活性化されるデータ駆動型計算。
・数値的制約: 累積、論理和、最小化、最大化などの高レベル述語を
含む有理数の線形方程式、不等式を解くシステム。
・有限領域: 変数に結びつけられた値の領域を能動的に狭める。この
技術により、有効な値の可能な組合せのみを考慮し、探索空間を非常
に小さくすることができる。
・論理制約: ブール式として形式化される関係を使用し、効率の良い
決定木の操作を行なう。
IF/Prologの開発環境は、制約ベースのアプリケーションを簡単に
デバッグやトレースできるように拡張されました。 デバッガと
トレーサは、制約の一時停止や活性化を分かりやすく示すために、
従来の4ポートから10ポートのセマンティックモデルになりました。
この環境は文字ベースおよびMotifの両方のバージョンで使用する
ことができます。これにより、ランタイムの操作を容易に制御でき
るようになりました。さらに、オンラインでのハイパーテキスト
マニュアルも用意されており、この開発環境を使用することにより
プログラマの生産性を飛躍的に改善することができます。
制約処理パッケージは、IF/Prologの他のデータベースインタフェ
ース、プログラミング言語インタフェース、文字セット、グラフィ
カルウィンドウシステムとの互換性を持っています。このパッケー
ジは、IF/Prologがサポートしているすべてのハードウェアプラット
フォーム上で使うことができるオプションとして提供されています。
制約処理パッケージの第1の利点として、プログラマの生産性の向上
が挙げられます。制約処理パッケージにより、プログラムをより
宣言的に書くことができるようになりました。これにより、複雑な
問題をより単純に解決することが可能です。さらに、上に挙げたよ
うな使いやすい開発環境ができたことで、より効率的にプログラミ
ングができるようになりました。
第2に、プログラム実行に必要な時間が短縮されました。
制約処理のために必要であるとして追加された内部データエリアは
すべて、ユーザアプリケーションから透明な形で、自動的にリサイ
ズされ、ガーベッジコレクションが行なわれているために、プログ
ラム実行に必要な時間が短縮されました。制約処理パッケージは、
システムカーネルの中心的な部分となり、最新の制約技術の実装形
となっています。
制約処理パッケージにより、問題解決の速度がいかに向上したかを
示すのが次の表です。Sun SPARCstation IPX上のIF/Prolog V4.1と
IF/Prolog V5.0とで書かれたサンプルプログラムの実行速度を比較
しています。 IF/Prolog V5.0を使った場合については、制約処理
パッケージを使った場合と使わない場合の解決を比較しています。
制約処理パッケージを利用した場合の処理速度がいかに速いかがわ
かります。
|
(1) |
(2) |
(3) |
| Eight-Queens |
30.13 |
18.01 |
4.19 |
| Farmer |
4.50 |
3.42 |
0.98 |
| SEND MORE MONEY |
65.50 |
53.47 |
0.85 |
(1) IF/Prolog V4.1での測定
(2) IF/Prolog V5.0での測定
(3) IF/PrologV5.0 および制約処理パッケージでの測定
CPU時間の単位は秒。100回測定の結果
制約処理パッケージは、ANSI標準互換Cにより書かれています。こ
の中にある述語は、ISO Prolog標準に定義されたものと同じスタイ
ルであり、この標準と同じように厳しく定義されています。
この新しい制約処理パッケージは学術研究用のシステムCHIPを土台
にしています。CHIPはECRC(European Computer Research Centre)が
開発したシステムです。 シーメンス(IF/Prolog5.0の開発元)は、
CHIPで試験的に開発された制約処理技術に、新しい技術を加え、
SNI Prolog 3.1を開発しました。 この度、これらの技術がより
改良されモジュール化されIF/Prolog5.0に統合され、製品化され
ました。
制約処理パッケージではコルーチン、数値的制約、有限領域、論理
制約の4つの制約クラスを提供しています。このすべてのクラスに
対して、Prologモジュールは様々な内蔵述語を提供しています。
ここで、制約クラスに内蔵されたすべての述語を説明することはでき
ませんが、下の例ではその一部を紹介しています。
IF/Prologの中で数字として解釈実行される範囲が拡張され、長精度
整数や有理数も扱うようになりました。長精度整数では小数点以上
約三十万桁までの数字の処理が可能です。(ほとんど任意の整数を
扱うことができます。
有理数は、2つの長精度整数の約分されない部分として表現され、
これにより高精度な計算式を処理することができます。
コルーチンは、データ制御下のゴールの数値を与え始める基礎的な
メカニズムであり、これを用いて、より宣言的にPrologプログラム
を書くことができます。内蔵述語を使用して、数個の変数に値が
与えられるまでゴールの数値を与えることを遅延させることも
可能です。
しかし、一般的な制約メカニズムとしては、コルーチンのみでは十分
ではありません。なぜならば、従来型のPrologと同様に、コルーチンは
一貫性条件を受身的にテストしているからです。より効率的な方法は、
予め変数の領域を限定し、一貫性条件を能動的に処理することです。
いずれにせよ、コルーチンはより複雑な制約を定義するのに役立ちます。
以下の例では、コールーチンを使用することにより、いかにうまく
宣言型プログラミングができるかを示しています。この例の場合、
Prologは左から右へと手続きを踏んでサブゴールを証明しますので、
宣言的観点からは正しくありません。
[user] ?- A \= a, A = b.
no
[user] ?- A = b, A \= a.
A = b
yes
論理的な観点から見ると、サブゴールの順序はどちらが先でもかま
いません。このような場合、制約処理パッケージのコルーチンクラスの
内蔵述語であるfreeze/2を使用して、"A"の変数に値が与えられるまで、
最初のゴールである "A \ = a" の証明を遅らせることができます。
[user] ?- freeze(A, A \= a), A = b.
A = b
yes
数値的制約を使用して、解答が無限にあり「値が連続している」
最適化問題を解決することができます。数値的制約は、等式、
不等式の組合せを増分アルゴリズムによって解きます。
(別ページのプログラミング例を御覧下さい。)
有限領域という制約クラスは、不連続の問題を解決するのに有効で
す。「不連続」とは、ここで、有限領域の制約によって表現された
条件を満足する数値が有限であるという意味です。この場合、従来の
Prologでは「値を生成してみてテストする」というプログラミン
グのパラダイムが使われていましたが、可能な値のみを生成する
というパラダイムになりました。
有限領域の変数は、例えば、間隔、列挙、数列などで制限された整数
です。変数は、限られた領域で値をとることができます。有限領域用
の制約のクラスの中では、変数間を、数学的な制約、記号的制約で
特定することができます。さらに、累積制約も提供されます。
(別ページのプログラミング例を御覧下さい。)
論理制約は、量的な測定を必要としないスケジューリングや決定
支援の分野でのアプリケーションに非常に適した手法です。
バイナリ領域で真の値を演算し、条件値を効果的に決定するために
用いられます。
実行中に、真の値が、多くの「論理」内蔵述語に伝えられます。
論理単一化アルゴリズムが、決定を容易に組合せることができる
ように真の領域を越えて動作します。
(別ページのプログラミング例を御覧下さい。)
| 
