common-lisp
アルゴリズム
lisp

optimaクローン つくりました

More than 5 years have passed since last update.

論文の締め切りが思っていたより先だったので気が抜けてしまい、こんなのつくっていました。

https://github.com/guicho271828/optima2

なぜ作ったのかというと、主に遅延評価オブジェクトをoptimaで簡単にマッチさせたかったからですね。

自分の作業中、

n要素の集合からm要素の集合への適切な対応付けが欲しかったのですが、(n,mは5~15程度)

気張った枝刈りとかは面倒くさかったので、全探索でやろうとしたんですね。

そう、permutationを作ったんです。n個からm個への。そしたら、簡単に想像が付くとおり、

メモリが爆発して処理系がハングアップします。

でも枝刈りのことを考えるのは面倒、遅延評価にすればとりあえずメモリ爆発は逃れられる。

しかし、optimaでthunkをマッチさせるのはこういうhackをするか、あるいはoptima.ppcreのようにoptima内部オブジェクトを触らないといけなかったわけです。クリーンじゃない。よしつくろう!と、まあそういう感じです。

あとは・・・


  • 以前からoptimaベースのユニフィケーションライブラリを作りたいと思っていたのですが、optimaはエラー処理・リスタートがそんなにたくさん準備されているわけではないので、pullreqを投げてみたりしてみたものの、実装もそんなに綺麗ではなく、受理されませんでした。自分で書けばそういう問題は起こらない、と。


  • ほかにも、ARRAYのマッチングがあります。これもつくってみてpullreq投げたのですが・・・。


コードを殆ど一から書きなおしたので、最適化度合いはoptimaにまったく及びません。従って、実用には

まだ辛いかと思います。ただ、optima付属のtestは(ほぼ)全部通りました。test scriptは無断でマルマル借り物なので、m2ymさんには感謝です。テストスクリプトってユーザからのissuesの反映の積み重ねなので、LLGPLとはいえこれを丸パクしてしまったのはすこしズルをしている感があります。

主な違いについてはリンク先をどうぞ。

追記:thunk は optima2ではこのように書けます:

(defpattern thunk (forced-var)

`(constructor (function () t) #'functionp
,(if (place-pattern-p car)
(error "thunk object cannot be overwritten")
`(:reader #'funcall ,forced-var))))

constructor パターンは type と predicate の両方を指定するようになっていますが、

typeをチェックした後に predicate を呼び出します。

ただし、predicate呼び出し部分はlocally にtype指定、inline指定かつ(optimize (speed 3))指定されるので、sbclなどの速い実装では呼び出しを消してくれる可能性もあります。

今後の課題は、fabrice et.al. の4,5,6章にみられる以下の手法の実装。


  • optimized mixture rule

  • Using exhaustiveness information

  • Optimizing exits

  • Aggressive control flow optimization

  • Better OR pattern compilation