やってみよう
Last-modified: 2011-01-15 (土) 21:42:12 (4872d)
Top / やってみよう
準備 †
- ここではCHRプログラミングを行うための処理系のインストールについて解説します。 本サイトではPCのOSとしてWindows Vistaを想定し、Prologの処理系として有名なSWI-Prologを用います。
1. 処理系のダウンロード †
- SWI-Prologをインストールするための実行ファイルをダウンロードします。
- SWI-Prologのホームページを開く。
- 左側のメニューからダウンロードを選択。
- Available versionsのstable releaseを選択。
- SWI-Prolog/XPCE (バージョン番号) for Windows NT/2000/XP/Vistaをダウンロードしてください。
- 64bit版のWindowsやUNIXを使用している場合は、それに対応したものをダウンロードしてください。
2. 処理系のインストール †
- SWI-Prologをインストールします。ダウンロードした.exeファイルを実行しましょう。
- 利用規約に同意。
- インストール形式(特にこだわりが無ければ"Typical")を選択します。
- インストールディレクトリを指定します。
- Prologソースファイルとして使用する拡張子を設定します。
- 初期設定では.plとなっていますが、マニュアルで推奨されている.swiを指定しましょう。.plはPerlで使用されているなど色々と不都合があるようです。
- ここで指定した拡張子のファイルを実行すると、自動的にSWI-Prologが起動されるようになります。
- Installを押してインストールを実行します。Completedと表示されたらfinishedを押して終了です。
3. 処理系の起動確認 †
- SWI-Prologを起動してみましょう。
- Windowsのスタートメニュー⇒すべてのプログラム⇒SWI-Prolog⇒Prologを選択してください。 下図のようなウィンドウが開けば、正常に起動できている（はず）です。
- SWI-Prologを終了させるためには、haltを打ちます。
?- halt.
CHR プログラミング †
- それでは実際にCHRプログラムを書いてみましょう。ここでは例としてユークリッドの互除法によって最大公約数を求める例題（GCD）を扱います。
CHR ライブラリの呼び出し †
- 前述の通り、CHRはホスト言語上にライブラリとして提供されていますので、ソースファイル中でライブラリ呼び出しを行います。
:- use_module(library(chr)).
制約の宣言 †
- CHR プログラム中に出現する制約は、全て宣言が必要です。今回はgcdという1引数の制約を用います。
:- chr_constrain gcd/1.
ルールの宣言 †
- CHRには3種類のルールがあります。
- Simplification rule
Head <=> Guard | Body.
- Guard部が成り立つとき、Head部をBody部へと書き換える
- Propagation rule
Head ==> Guard | Body.
- Guard部が成り立つとき、同等なHead部に対してBody部を高々1回追加する。
- Simpatation rule
Head \ Head' <=> Guard | Body.
- Guard部が成り立つとき、\よりも後ろのHead'部をBody部へと書き換える。
- 今回は基本的なルールであるSimplification ruleを2本記述します。
- 1本目のルールは次のようになります。
gcd(X), gcd(Y) <=> 0<X, X=<Y | Z is Y mod X, gcd(X), gcd(Z).
- このルールでは、0<XかつX=<Yを満たすような二つの整数XとYがある場合に、Yの整数を持つ制約gcd(Y)をY mod Xの整数であるZを持つ制約gcd(Z)へと書き換えています。
- 2本目のルールは次のようになります。
gcd(0) <=> true.
- 1本目のルールによってgcd(0)が生成された場合は、それを消去しています。trueは通常の制約ではなく、そのルールが成り立つことを示す特別な制約です。
実行 †
- 以上のCHRプログラムを記述したソースファイルがこちらです。
- このファイルをダウンロードしたら、SWI-Prologを起動しましょう。
- メニューからconsultを選択し、gcd.swiファイルを開きましょう。
- 下図のようにコンパイルが行われます。エラー出力が無ければコンパイル成功です。
- それでは適当なクエリを与えて、プログラムを実行してみましょう。
?- gcd(8), gcd(2).
- 8と2の最大公約数は2です。これを打ち込んでエンターキーを押すと以下のようになります。
- gcd(2)が得られていることが分かります。
- プログラムの実行を終了するときは、セミコロン(;)を打ちます。
- 以上が基本的なプログラムの実行方法になります。
- 本家CHR サイトの例題ページには様々なCHRソースコードが置かれています。ダウンロードして色々と遊んでみましょう。
オプション †
- CHRにはソースコード中に記述する便利なオプション・関数が用意されていますので、いくつか紹介します。
トレースモード †
- 計算処理を1ステップずつ表示させながら実行します。CHRプログラムの挙動だけではなく、CHR処理系（ここではSWI-Prologですが）が内部でどのような処理を行っているのかを把握する手助けをしてくれます。
:- chr_trace.
実行時間計測 †
- CHRではなくPrologの関数としてcputime関数が用意されています。
hoge <=> cputime(X).
- 上のルールのように、何らかのルールのボディ部に1引数のcputime制約（関数）を記述すると、ルールが適用された時点での時間を変数Xに代入します。
最適化モード †
- CHRでは論理変数や型体系などを利用した最適化モードが用意されています。
:- chr_option(optimize, full).
- このオプションを指定することで、以下のような最適化が利用可能となります。
共通論理変数を利用したマッチング最適化 †
- マッチングとはヘッド部の構造に当てはまる制約を探索する処理です。以下のルールを例に解説します。
a(X), b(Y) <=> X == Y | true.
- このルールは下図の(1)から(3)の順でルール適用を試みます。
- このルールの場合、下図のように1引数のa, bという制約が数多く存在した場合には、マッチングが非効率的に行われる可能性が高くなります。
- この問題を解決するため、CHRでは共通論理変数を利用したマッチング最適化が用意されています。
- この最適化を利用するためには、下記のようにルールを変更するだけでOKです。
a(X), b(X) <=> true.
- こうすることで、マッチング時の処理の順序が下図の(1)から(3)のようになり、
- マッチングの失敗を極力減らすことが出来ます。
添付ファイル:
matching5.jpg 203件
[詳細]
matching4.jpg 209件
[詳細]
matching3.jpg 185件
[詳細]
matching2.jpg 180件
[詳細]
matching.jpg 122件
[詳細]
gcd2.jpg 209件
[詳細]
gcd.jpg 205件
[詳細]
test.jpg 193件
[詳細]
consult.jpg 238件
[詳細]
gcd.swi 248件
[詳細]
