Problem 11 格子内の最大の積

問題

最初の問題は簡単だなあ…作業感出てきた…早くもう少し難しくなってほしい

実行結果(解答伏せています):

Problem 10 二百万以下の素数の和

問題

プロジェクトオイラーは一度素数列挙ロジックを作るとあちこちで使いまわせる。

実行結果:

Problem 1 3と5の倍数

問題

CLPFDライブラリ読み込んでるけど使ってなかった…

実行結果
[1] 2 ?- adding(999,R).
***********************(解答伏せます)**********************

[Prolog]制約論理プログラミングへの条件追加と速度の向上に関して

2週間ほど前にProject Eulerの存在を知り、面白いのでチャレンジしている。本日の時点では26問解いた。全部Prologで解いている。

Project Euler

ところどころCLPFDを使える問題があり、使っている。

制約論理プログラミングの動作の特徴?みたいなのを感じられる面白い問題があったので、紹介しようと思う。

Probrem 9 特別なピタゴラス数

この問題は、CLPFDだと探索の処理を一切書かずに以下のようにただ定義だけをずらずら書くだけで解ける。

問題の条件をそのまま書いただけのようなプログラムだけど、本当にこれだけで解けます。

ただ、これだと非常に処理時間がかかかる。僕のしょぼいマシンでは、
以下のように150秒かかった。

ネットで調べるとこのピタゴラス数の法則のようなものがいくつかヒットするのですが、そのひとつが以下の図のようなもので、

triangle

ようするにBとCの関係に関してなのですが、長さBの正方形の辺を1つづつ大きくして一回りづつ囲むように配置してゆくといつか長さCの正方形と等しくなるというもので、しかもこの大きくした分の面積はA × Aと等しいというもの。

大きくした分の面積は、N(=1,2,3..)の数列として以下のように表すことができる。
En = 2 × N × B + N × N
そして、A × A = En

前述のプログラムにこの条件を追加して動作させると、答えを出す速度が段違いに速くなる。

実行結果:

10倍近く速くなった。
多分Aの探索空間が新しい条件の数列で絞り込まれて速くなるのだと思う。

「思う」と書いたのも制約論理プログラミングの特徴といえば特徴で、条件を書くたびに大量の制約伝播用のプログラムが内部で自動的に生成されるため、厳密な動作が非常に追いずらい。ステップ実行などのデバックもしずらい(CLPFDライブラリ内部で自動的に大量のバックトラックが発生している)。

これは悪い面で、動作が見積もれないことが原因となり正確・確実な動作を期待される産業分野でなかなか採用されないかもしれない。ちゃんとした企業ほど異常動作のときなどの原因追及フェーズを徹底的に行っているので、そのときに「思う」とか「これ入れたら速くなるかも」とかは通用しないわけです。動作確認のためのログを埋め込むのも結構大変です(ライブラリに直接埋め込まないと駄目だし制約伝播状態を出力した解析困難なログになることが予想される)

ちなみに制約伝播というのは、prolog の attributed_variableの仕組みを使って変数の探索空間が変更された時点でキックされる述語が予約されていて、ドミノ倒しのように次々と他の変数の探索空間をせばめてゆくという手法です。

CLPFDのソースを読んでゆくとわかるのですが A in 1..500 などという探索空間は木構造で表現されており、探索空間の変更はこの木構造を変えることで行っている。

たとえば A の木構造が最初 左の枝が1、右の枝が500 の状態で、この状態から100~200の可能性がないことが判明した時点で、右の500の枝の部分に100..200のノードが新しく追加される感じ?

Prologの変数は基本的に再代入不可なのですが、attributed_variableは再代入可能かつ履歴情報を保持していてバックトラック時に直前の値に戻る(Prologの通常の自由変数はバックトラック時は未設定状態になるだけで履歴情報は持っていない)ようなのでこれを利用しているのでしょう。

CLPFDは非常に簡単に記述できて問題が解けるため、勉強し始めのころはまるで魔法のツールのようだと感じたが、上記のような、問題自身の性格を表す条件を入れないとすぐに処理時間が膨大になってしまうように感じる。

当たり前のことだが、問題に対する洞察・分析も非常に大切ということだろう。

[Prolog]川渡り問題を解く

ネットで見つけた以下の川渡り問題をPrologで解いてみました。

おなじみのやつですね。

Art of Prologとかm.hiroiさんのホームページでも載っていました。

問題:

ある家族がいて、舟を使って川を向こう岸へ渡ろうとしています。
この家族は父、母、息子1、息子2、娘1、娘2、メイド、犬、じっちゃん、
赤ん坊の10人家族(犬も1人と数えます)です。
舟は1艘(そう)しかなく、1度に2人まで乗ることができます。
また、この舟をこげるのは父と母とメイドとじっちゃんの4人です。

父は、母がいなくなると娘を殺してしまいます。
母は、父がいなくなると息子を殺してしまいます。
じっちゃんは、親がいないと息子や娘、赤ん坊を殺してしまいます。
息子や娘は、親がいないと赤ん坊を殺してしまいます。
犬は、メイドがいないと家族をみんな殺してしまいます。

みんなが無事に川を渡り切るには、どのような手順で渡ればよいでしょうか?

プログラム解説:

盤面生成→チェック → 再帰で次の盤面生成 → チェック → … → クリアするまで繰り返し
失敗すれば バックトラックで次の選択肢を試す
Prologで何も考えずに深さ優先探索で解いています。
枝刈りを行っていず効率の悪いプログラムですが、この程度の問題だと全然問題ないようです。

現在の状態は以下の形式のcompound termで表しています。

state(左岸にいる人のリスト,船に乗っている人のリスト,右岸にいる人のリスト,船の位置(left , right , crossing のいずれか))

assertで生成したstateを登録するようにして、登録済のstateには遷移しないようにしています(意味のない行ったり来たりを防ぐ)

assertする際 順列ではなく組み合わせで登録したいため、リスト内をソートしてから登録しています。

この程度のプログラムだとあまり考えず機械的作業で量産できるようになってきた。

プログラム:

実行結果:
(下から上に答えに近づいていきます)

[Prolog]演算子のカンマとそうでないカンマ、ドット演算子と演算子でないドット(ピリオド)

Prologではプログラムのほとんどの記述は演算子を用いて記述され、言語全体を通して一貫している。

例えば、以下のようなリストの長さを返す述語my_lengthがあるとする。

my_length([],0).
my_length([_|Rest],Cnt):- my_length(Rest,Cnt0),Cnt is Cnt0 + 1.

このとき、下の方のclauseを例とすると、使用されている記号

「:-」 「|」 「,」 「+」 「is」

はどれも組み込みの優先度付き演算子として定義されていて、節全体がPrologの内部表現としては下の図のような木構造で表されている。

operator_tree20161206

ここで、ボディの規則が「,」という演算子で結ばれていることがわかる。
演算子は1項及び2項なので、カンマで3つ以上の規則をつなげた規則a,規則b,規則c のような場合は、演算子の xfy の定義により

‘,’(規則a, ‘,’(規則b,規則c))

というような右方向に入れ子となる木構造として表現される。

Swi-Prologのプロンプトでの実験

6 ?- Test=(a,b,c),Test=..List.
Test = (a, b, c),
List = [',', a, (b, c)].

ここで、abc(prm1,prm2) などの compound term の引数で使われているカンマに関して考えてみると、これは実は演算子ではない。

例えば、少し無理やりですが、以下のプロンプトの実験はマッチング失敗します。

8 ?- abc(','(prm1,prm2)) = abc(prm1,prm2).
false.

しかし右辺のprm1,prm2をさらにカッコでくくるとマッチング成功します。

10 ?- abc(','(prm1,prm2))=abc((prm1,prm2)).
true.

これは(prm1,prm2)とだけ書いた表現が、「カンマ演算子の引数としてprm1、prm2を渡したもの」を表していることを意味している。

そして、[a,b,c,d,e]などのリストで使用されているカンマはそのまま演算子として使用されるのではなく、ドット演算子に変換されます。

プロンプトでの実験

7 ?- [a,b,c]=R,R=..Y.
R = [a, b, c],
Y = ['.', a, [b, c]].

はじめに紹介したmy_lengthの木構造で [_|Rest] の部分が ピリオドに変わっていますが、これもドット演算子で、ドット演算子はPrologのリストを Lisp の car と cdr のように「最初の要素」と「残りのリスト(空リスト含む)」に分けます。

プロンプトでの実験

4 ?- [First|Rest]='.'(First,Rest).
true.

5 ?- [a,b,c,d]='.'(First,Rest).
First = a,
Rest = [b, c, d].

6 ?- [a,b,c,d,e]=','(a,(b,c,d,e)).
false.

上記で分かる通り、Prologでは同じカンマでも「演算子のカンマ」と「演算子でないカンマ(term の引数のカンマ、ドット演算子に変換されるカンマ)」が混在していることになる。

誰かのブログで、Prologの構文をいじれるとしたらterm(prm1,prm2)のカンマをスペースにしたいと書いている人がいて、はじめなぜそうしたいのか意味がわからなかったけど、「演算子ではないカンマは空白にしたい」という意味として考えると、なるほど混乱を避けるためにはその方が良いかもと思うようになった。そうするとリストの要素を分けるカンマも手を付けたほうが良い?

ドット演算子と述語の終わりを意味するピリオドも同じ文字だが全然意味が違い、厳密性を考えるとこれも紛らわしいような気がする。
述語の終わりのピリオドは一体演算子なのかちょっと確認できなかったのですが、多分違うと思います(詳細を知っている方いらっしゃいましたらぜひ教えてください)

[Prolog]存在記号∃を表現する

Prologで述語論理の存在記号∃をどうやって表現するのか?

Prologは一階述語論理をベースに作られているから、論理学の色々な記号を表すのは得意だろう、それなら存在記号∃を表すことも出来るのではないだろうかと思いいろいろ調べていたのですが、文法にはそれっぽいのなく、う~んできないのかな…と悩んでいました。

存在記号というのは

「人間の中には血液型がA型の人間が存在する」

などを表す記号です。

もうひとつ「全称記号∀」というのがあるのですが、これは「すべての」を表す記号で、例えば

「すべての人間は、呼吸をする」

などを表す記号です。

これはPrologで表すのは簡単で、

breathe(A):-human(A). % Aが人間であれば呼吸をするという述語

で表すことが出来ます。
Aというのが自由変数になっていてどのような対象にもマッチングするので、「すべての」が表現できるのです。

このプログラムに、例えば

human(taro). % taroは人間であるという記述

と追記し、プロンプトで

breathe(A).

と入力すると

A = taro.

(呼吸するのはtaro)
という返答が返ってきます。

そして始めの疑問に戻りますが、
上記の存在記号∃バージョンは果たしてどのように記述するのか。

「人間の中には血液型がA型の人間が存在する」

はどうPrologで記述するのか。

yahooの知恵袋や外国のstackoverflowで英語で質問してみたのですが、回答が得られず、あきらめかけていたのですが、以下のページを見てやっとわかりました。

Convert first-order logic expressions to normal form

このページの

4. Somebody has a car.



person(sk10).
car(sk11).
has(sk10, sk11).

に変換されているのを見てやっと分かりました

「なんでもいいから、何か」を登録すれば良いのです

human(someone).
bloodtype_A(someone).

これでOKです。

someoneというのはいったい誰なのか、それは自分もわからない。
とにかくそれは人間です。
そして、bloodtype_A(_)を満たす人間someoneが、間違いなく存在する。
これで∃の条件は満たされます。
ここで引数に自由変数を使ってしまうと、上で述べた「すべての」になってしまうのでアウトです。

さらにいうと、色々な述語をつくるときに、この someone という同じアトムを使いまわすとおかしくなる
(someoneは血液型がAでしかもBでとかになる)
ので、someoneの後ろに添え字を追加し、述語ごとにユニークにする必要があるでしょう。

気付けば単純なことなんだけど、なかなか思い至らなかった。

[Prolog]動的に述語定義する

以下のように記述すると動的に任意の述語を定義できる。カンマで区切って複数述語呼び出すようなものもできる。

javascriptも文字列から関数定義とかできるけど、そんな感じに使えそうだ。

こういう機能は普通は使わないけどしかるべき時に使うとすごいプログラムが書けると思う。

セキュリティホールになりそうな気も、、、

動的に

test(X):-
X1 is X+1,
X2 is X1+1,
write(X2).

という述語を作成したい場合(意味無いけど)

assert(test(X):- (X1 is X+1, X2 is X1+1, write(X2))).

[prolog]attributed_variable に関して

prologは基本的には自由変数には1度しか値を入力できず、処理の途中で書き換えることはできない。

唯一書き換えられるタイミングはバックトラックで、バックトラックが発生するとchoice point以降の処理で設定した自由変数が全て未設定の状態になる。

しかし、attributed variableという、自由変数の属性値のような変数があり、これは変更が可能なようだ。
これは結び付けられた自由変数が設定されるとunify_hookというゴールが駆動されるようになっているようだ。
しかもattributed variableは変更の履歴情報を持っており、バックトラックで以前の値が復活されるような感じらしい。
ちょっとまだ仕組みが良く分からないが、clpfdライブラリのソースをみるとこの仕組みが多用されているのがわかる。

他にfreeze,meltという述語があり、これも自由変数に値を設定するとfreezeにより結び付けられたgoalが自動的に実行されるような仕組みになっている。whenとかいう述語はfreezeの条件付バージョンのようだ。

freeze,meltは30年くらい前の書籍であるart of prologにも記述があるので、かなり歴史のある述語のようだ。
freeze,meltはclpfdのソースでは使っていないようだ(→改めてgrepしてみると使ってる場所ありました 2016/10/04)

clpfdのソースは自分にとってはかなり難解で、Prologの基本レベルの文法を押さえただけではまったく理解することが出来ない。
気長に解析していこうと思う。

[PROLOG] compound term

Art of Prolog を読んでいて、Equation Solver(方程式ソルバー)を作るという記事があり、ふむふむと読んでいた。

その中で、Prologを勉強している人には常識かもしれないのですが、以下の様な記述があり「??」となった

方程式を解く際の移項を行う術語定義で
ikou(A+B=C,A=C-B).

などの記載や、

T=a*b^c

など。

例えば後者のTには一体何が入っているのか?

[a , * , b , ^ , c]
というリストなのか?

実際にSWI-PROLOGで問い合わせて調べてみた。

3 ?- T = a*b^c,atomic(T).
false.

atomicではない。

4 ?- T = a*b^c,atom(T).
false.

atomではない

5 ?- T = a*b^c,var(T).
false.

変数ではない。

8 ?- T = a*b^c,string(T).
false.

stringではない

10 ?- T = a*b^c,compound(T).
T = a*b^c.

というわけで、compound(複合項)らしい。

ちなみに

14 ?- T = a*b^c,T = [First|Rest].
false.

15 ?- T = a*b^c,T = [].
false.

リストへのマッチングが失敗するので、リストではない。

また、

16 ?- T = a*b^c,callable(T).
T = a*b^c.

callableが成功するので、実行可能な述語として認識されている。

それでは 複合項をリストに変換する =.. を使用して調べてみよう。

18 ?- T = a*b^c,T=..List.
T = a*b^c,
List = [*, a, b^c].

Listにした場合、 「*」 「a」 「b^c」 の3つの要素を持つリストとなる。

というわけで a*b^c という記述は 「*という演算子の引数として aとb^c を渡した*(a,b^c)みたいな複合項」 という
意味だということがわかった。

演算子の優先順位は
* 400
^ 200
で ^ のほうが高いため * のほうが外側の演算子ということで b^c はくっついているのであろう。
さらにb^cも枝の部分の複合項として認識されるので、
a*b^c = T という記述は、自動的に *(a, ^(b,c)) みたいな木構造の複合項として認識されているということがわかった。
どちらの演算子が親になるかはおそらく演算子の優先順位で決まるのであろう(実験およびマニュアル確認はしてません)

ちなみに、以下のようにした場合は

21 ?- T=a+b+c+d,T=..List.
T = a+b+c+d,
List = [+, a+b+c, d].

となるので、あくまで一番上位のレベルでは最後の演算子のみ認識され、それ以前の要素は枝として認識されている。
演算子の引数は2つのみということだろう。

これを利用して、以下のように 微分の導関数を求める述語も作れるようだ(実際はsin(x)の微分の定義など他のいろいろな述語定義が追加されます)

d( U^C, X, C*A*U^(C-1) ):-
atomic(C),
C\=X,
d( U, X, A ).

prolog derivative で検索するといくつかサンプルのソースがヒットするので興味のある人は探してみてください。

自分も興味を持ったので微分をする述語を作ってみようと思います。
完成したらこのブログに書きます(挫折するかも…)