忍者ブログ

好きい夢 昭和な気まぐれ飛行機

SchemeとPrologの幸せな結婚

この投稿は2013年12月25日Lisp advent calenderの記事です。
25日は仕事が超多忙で忘れてしまいそうなため前倒しで投稿させていただきます。


今は昔、第五世代コンピューター計画というものありけり。

そう、それは昭和57年頃のことでした。I/Oというマイコン雑誌にPrologが紹介されていました。何?これは?? Basicやアセンブラとは全然違うみたいだけど。ところが当時はまだ一般の人が試せるようなProlog処理系はありません。中島秀之先生の「Prolog」という本の巻末にはLISP1.5で書かれたProlog処理系があるではなりませんか。

そう、それが私とLispとのファーストコンタクトでした。



あれから幾年月が経過したことでありましょう。Gauche上にNorvig先生の本にあったPrologを拡張してのっけて・・・。動きました。SchemeとPrologの融合です。しかし、いくら高速なGaucheであったとしてもその上にのっかった形のPrologは本格的なSWI-Prologに比べたら比べものにならないほどに遅かったのでした。

それなら、自分で作ってしまえ!

日本Prolog協会の会長さんに教わりながらあのWarrenさん(WAMの開発者)の文献を読み、GaucheでWAMシミュレーターを作り、そして自作のScheme処理系であるNormalにVMレベルでSchemeと対等に動作するPrologコンパイラの作成にとりかかったのは2013年の夏頃でした。

で、性能は・・・
norm> (&time (&queens))
(4 2 7 3 6 8 5 1)
(5 2 4 7 3 8 6 1)
・・・・・・・
(5 7 2 6 3 1 4 8)
0.063 second
GC 0.0 second
#t
norm>

8クイーン全解出力で0.063秒。SWIには敵いませんが悪くはない。ムフフフ


Human is error.

映画、「2001年宇宙の旅」で人工知能であるHALはつぶやきます。Human is error.
おっちょこちょいな人間で悪かったなぁ。でも、お前を作ったのは人間様だからな。>HAL殿

(assert (&human _x)(&error _x))

(assert (&error taro))

(assert (&error sym_num))

norm> (&human sym_num)
#t
norm>

おお、Prologってすげぇと思ったのは30年前。

この質問に答える間にunificationとバックトラックをしています。
debug> (&human sym_num)
|(&human sym_num)
| (&error sym_num)
#t
debug> 

このバックトラックというやつ。Schemeの例題にも出てきますよね。そう、call/ccを使ったamb。
 



助け合いの精神
 
Schemeは関数型でありPrologは論理型です。論理型はT/Fのいずれかしか返さない関数とも考えられます。後藤先生の古い記号処理の本を読みますと当時から融合しようという試みはあったようです。Prologの述語isは X is sin(0.5). のように使えますがこの関数の部分をSchemeで書けてしまったらば。

Normalだとこんな風にも書けます。
(assert (&fact _x _y)
        (is _y (fact _x)))

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

これだけだとあまり幸せ感がないかなぁ。バックトラックにより非決定性の計算を得意とするPrologですが、計算はあまり得意ではありません。決定性の計算は末尾再帰最適化ができるSchemeの方が得意なのでした。頑固一徹なProlog男と器用に計算をこなすScheme女。互いに補いながらうまくやれるように思うのですよね。



似たものカップル

Scheme: ねえねえ、私ってすごい得意技があるの。

Prolog: え?なに?

Scheme: 見て見て。
norm> (* 3 (call/cc (lambda (k)  (+ 1 (k 2)))))
6

Prolog: ・・・ 見せられないけど僕も同じハートは持ってるよ。

 
Schemeは継続、call/ccという摩訶不思議な関数を持ちます。Prologはあからさまに継続を扱うことはないのですが、内部ではしっかり継続をコントロールしています。unificationに失敗すると他の選択肢を求めてバックトラックしますが、ここでしっかりと継続がでてきます。call/ccの実装で頭を悩ませた経験がとても役に立ちました。

実際のコンパイルコードをご覧ください。
(assert (&human _x)(&error _x))

norm> (compile '&human)
((fn 1 ((argsp 1) (try #f) (unifyv 0 0 _x) (deref _x) (gvar &error) (callp 1) (pop) (proceed))) (def &human) (halt))

整形機能がなく、見にくくて恐縮です。
 
SchemeのクロージャをPrologの述語にも流用しています。argsp命令はクロージャを生成しますが、レキシカルな環境を必要としないPrologには不要な局所変数保存場所の一部を成功継続のためのスタック、環境、プログラムカウンタの保存場所にしています。Schemeの継続に似ています。proceedは述語が成功した場合で成功継続を起動します。

失敗したときの継続はProlog専用のtrailスタックに積んであります。try命令がそれを行っており失敗継続をtスタックに積んでいます。述語が失敗した場合には今までunifyした変数情報を捨ててバックトラックしますが、失敗継続には戻るためのlocalスタックの位置などが記憶されています。

ああ、ごめんなさい。説明が下手。なんとなく雰囲気は伝わりましたでしょうか。




継続は力なり。

実際の結婚というのは、もうこれは努力、努力です。別々な人生を歩んできた二人ですから、時にぶつかり大喧嘩することもあるでしょう。結婚生活はともかく継続しなければなりません。嗚呼。

SchemeとPrologは継続という同じような機能を内蔵しています。明示的に継続を取り出せるSchemeと、内部に秘めた継続機能を駆使して黙々とバックトラックを繰り返すProlog。たぶん、うまくやれるはず。

今のところProlog側からSchemeを呼び出す形式しか用意していないのですが、いずれ(prolog->scheme _var) という手続きを用意してSchemeから呼び出してunifyした変数を取り込むということも検討中です。

おや、今日はクリスマス。シティーホテルの最上階のバーで夜景を見ながら楽しく過ごした二人。来年の6月頃にはめでたくゴールインでしょうか。

参考
Normalの仕様はここにあります。
http://practical-scheme.net/wiliki/wiliki.cgi?sasagawa%3ANormal2
http://practical-scheme.net/wiliki/wiliki.cgi?sasagawa%3ANormal3

Normalの実装はBabbageという簡易開発環境にバンドルされて公開されています。
http://homepage1.nifty.com/~skz/Scheme/normal.html

PR

コメント

プロフィール

HN:
No Name Ninja
性別:
非公開

P R