カテゴリー別アーカイブ: ECLiPse

[Prolog] DCGで双方向性のある述語を作成

最近stackoverflowでPrologの質問に良く回答しているのですが、面白そうな問題があり、自分でもプログラムを作ってみました。

質問

内容は、[1,2,3,4,1,4,7,5,7,8,9] のようなリストが与えられた際に「続いている数字は[最初の数字,最後の数字]の形で表し、そうでないものは単体の数字で表したようなリストを生成する という問題です。
[1,2,3,4,1,4,7,5,7,8,9]は[[1,4],1,4,7,5,[7,9]] に変換されます。

作っているうちにどんどんアイデアがわいてきて、はじめは長いプログラムだったのがDCG使ってエレガントな方法で実装する方法を思いつき、最後には入出力逆転してもOKなような非常に汎用的な形で作成できました。

ECLiPSeで作成(多分他の環境でも問題なく動きます):

chunk_list([])-->[],!.
chunk_list([Chunk|Rest])-->chunk(Chunk),!,chunk_list(Rest).

% sequence
chunk([First,Last])-->sequence([ First , Last ] ),{ First < Last }.

% isolated number
chunk(Val)-->sequence([Val,Val]).

sequence([First,Last]) -->
{ ( number ( First ) , number( Last ) ) -> First < Last ; true } ,
[ First ] ,
{ succ ( First , Second ) } , sequence( [ Second , Last ] ) .

sequence([Val,Val])-->[Val].

実行結果:

[eclipse 4]: phrase(chunk_list([2,[2,6],[3,5],3,7,[1,3]]),Ret).

Ret = [2, 2, 3, 4, 5, 6, 3, 4, 5, 3, 7, 1, 2, 3]
Yes (0.00s cpu)

[eclipse 5]: phrase(chunk_list(Ret),[3,4,5,2,1,6,7,88,9,4,5,6,7,2,1,2,3]).

Ret = [[3, 5], 2, 1, [6, 7], 88, 9, [4, 7], 2, [1, 3]]
Yes (0.00s cpu)

[eclipse 6]: phrase(chunk_list([[2,4],A,[2,8],3]),[2,B,4,6,2,C,4,5,6,7,D,E]).

A = 6
B = 3
C = 3
D = 8
E = 3
Yes (0.00s cpu)

最後のマッチング例は「やってみたら、できた」という実験で、自分の予想を上回る汎用性が実現できていてびっくりしました。

入出力がどちらもリストの述語を作成するときは、工夫すると双方向性が実現できることがあると思います。

Prologの真髄に触れたような気がしました。

[Prolog]最近の勉強

最近あんまりPrologのブログ書いてませんが、ずっと研究してます(具体的にブログに書けるような結果が出てない)現在はECLiPse(IDEのほうじゃなくて制約プログラミングのほう)の勉強してます。

書くネタないので今までのPrologの勉強の流れを説明すると以下のような感じで進んできました(スパンは数年単位)

広井さんのページでPrologの基礎を把握しいくつかのパズルのソルバーを作る(20年近く前に大学の授業で受けていたがあまり深いところまで理解していなかった)

SWI-Prologのマニュアル読み込むうちCLPFDを発見し衝撃を受け、勉強開始

ProjectEulerでPrologで問題を解くうち、正答者スレでECLiPseを用いてSWIの自分のプログラムよりはるかに速いスピード(数十倍)で結果を出している人を発見して衝撃を受ける。プログラムの内容自体はCLPFDを使用した自分のとそんなに変わらなかった。

ECLiPseの勉強を始める。だんだんSWI-PrologのCLPFDがSicstusやECLiPseの制約ソルバーに比べると「オモチャ」レベルだったということがわかってくる。また、SWI-PrologのCLPFD開発者のmarkus triskaさんは開発の継続をsicstusで行うみたいな記述を最新のSWIのマニュアルで見つけた。

また、ECLiPse は node.jsを使用してjavascriptで呼び出せるらしく、ECLiPseの勉強はWeb系の仕事でのちのち面白い威力を発揮するかもしれないと期待を抱く。

ECLiPseには、自分がSWIのCLPFDでどうしてもできなかった自作制約の作成がPropiaとCHRの2種類の方法で可能なことを知り、そちらの勉強を開始。SWIのCLPFDの自作制約の作成方法はマニュアルが意味不明だった(まだ完成してないとも書いてある)

Propiaのほうは大体の概要を把握。任意の述語をそのまま制約にできて、Propagationの厳密さをinferという述語の引数でコントロールするという仕組みらしい

CHRの勉強に移る。ルール自体は少ないが結構難しくてどのように作ればよいかなかなか理解できない。CHRはHaskellやJavaなどでも使用できるようだ。

CHRが並列計算に向いていると知り、ハードウェアで実行したりGPUを使用したりして解くといった論文をネットで見つけて読み始め、少しECLiPseの勉強から浮気する。

「CHRをGPUを用いて計算する」方法を記載した論文を見つけるが実際にやった時の速度比較が載ったものを見つけることができなかったので、そういう論文が出ないかを定期的にウォッチすることに決め、とりあえず論文リサーチはやめる。CHRをハードウェアでやった論文では数万倍とかのスピードで解いてるの見つけたが良く読むとCHRの機構だけではなくプログラムのほうもハードウェア化していてちょっとちがうだろという感じだった(論文で使用している最大公約数求めるみたいな単純なロジックしかハードウェア化できなくて現実的ではないし、そもそもそれってCHR自体の速さではない)

またECLiPseのCHRの勉強に戻る

△いまここです。

まあ日本語の情報がないです。
ずーーっと英語読んでます。ECLiPse、日本で使ってる人100人もいないんじゃなかろうか。日本のECLiPse界では望まずして第一人者になりそうです。もしそういう人たちいれば仲間に入れてほしい。誰か一緒に勉強しませんか?情報交換して一緒に研究の成果を教えあいましょう

CHRはルール自体は3種類しかなくて単純なんだけど以下が良くわかってなくてまだ自作の制約を作るまで至ってない

・labelingの振る舞い
・制約の述語の変数に「値を設定した時?」と「新しい制約がセットされたとき?」に再度bodyがfireされるらしいがそこらへんの振る舞い

多分CHRの制約の形が「自分がCLPFDを勉強してきた上で持っている制約のイメージ」とかなりずれているのが理解が滞ってる理由だと思います。

自分の数年の目標であるTantrixというパズルのソルバーをECLiPseの自作制約でいつか作れれば良いなあ。手続き型だと現在のスキルで多分作れるが制約プログラミングで作るという目標がありわざとそういう手法では作ってない

…………………………うーん。

この記事書いてるうちになんで自分がCHRを必死に勉強してるのか分かんなくなってきた…
Propiaで間に合ってるような気がしてきたので、そっちでやるかな…。CHRは「つかうとすごいスピードが出るケースが見つかる(並列処理とかで)」とか「CHRで書かれためちゃくちゃエレガントなコードを見つける」みたいな状況になってから改めて勉強しようかな。
CHRの良さをご存じの方いらっしゃればぜひ koyahata*koyahatataku.com(*を@に変更) にメール下さい。そうでなくてもProlog関連で勉強中の人はぜひ連絡取り合って一緒に勉強しましょう

ブログまとめるのも自分の行動を見直す良い機会になりますね

よし方向転換