Prologとか論理プログラミングについて色々

ここ最近、論理プログラミングとか、Prologについて調べてたので現状のまとめ。

発端

VDMとかAlloyとか、形式手法関連を色々調べていた途中でPrologの存在を知る。
論理型言語ということで、いまいちイメージが掴めないところがあった。
最近、本腰入れて調べてみることにした。

Prolog入門系の情報

いくつかサイト見たり、本買ったりした。

"Prolog 入門" でググると、チュートリアルサイトがいくつか出たのでそれは見た。

Lisp, Prologネタ: ホットコーナー
 Lisp, Prologネタその２: ホットコーナー
 Java版Prologリンク集、Prolog、オントロジーなどのチュートリアル集: ホットコーナー
 http://iiyu.asablo.jp/blog/2011/02/03/5660275

中村正三郎氏。色々ネタがあったので参考に。

宣言型プログラミングの可能性と限界 | Think IT（シンクイット）

若槻俊宏氏。プログラミングパラダイムの話。
命令型と宣言型のそれぞれを語って、等価変換型につなげている。
等価変換型は…実現可能なのだろうか。

上記記事に、宣言型という点でPrologとSQLを比較する話もあった。
一階述語論理に基づく、という点で親戚ではある。
Prologにおいて、事実の記述の集合がデータベースとして扱われる、ということだったので、
現在一般的に使われているRDBとの関係あたりをもうちょっと突っ込んで調べたい気になった。

買った本。

『Prologプログラミング入門』

Prologプログラミング入門

作者: 安部憲広
出版社/メーカー: 共立出版
発売日: 1985/03/20
メディア: 単行本
クリック: 18回
この商品を含むブログ (3件) を見る

1985年初版発行。
中村氏のところで紹介されていたので。
Prologの挙動の細かいところが載ってる、みたい。

『知識と推論』

知識と推論 (Information Science & Engineering)

作者: 新田克己
出版社/メーカー: サイエンス社
発売日: 2002/06/01
メディア: 単行本
購入: 3人クリック: 37回
この商品を含むブログ (13件) を見る

2002年初版発行。
Amazonで「一緒に買いませんか」されたので。

こちらは、「知識と推論」がメインテーマで、Prologはその過程で触れられているのみ。
後で述べるが、Prologの範囲外の論理に関する話題も扱っている。
Prologありきでなく、論理プログラミングという視点。良本と思われる。

処理系

適当に調べて目についたものだけ。

SWI-Prolog
http://www.swi-prolog.org/index.txt

有名らしい。サイトの情報量が多い。日本語なし。
MacOSX版バイナリも配っていたのでこれをインストールした。

トップページに

Multi-threaded Web server library with comprehensive libraries to generate HTML, HTTP authorization, session management, exchanging JSON (used by many AJAX widgets), etc.

と紹介されてる。そういうのもあるのか。

このサイトのWebサーバもPrologで書かれてるようで、マニュアルのURLが、

http://www.swi-prolog.org/pldoc/doc_for?object=section(2,'1',swi('/doc/packages/nlp.html'))

とかになってる…。パラメータの記法がProlog風。
へぇ。

AZ-Prolog
http://www.az-prolog.com/

こちらは日本。商用でアップデートされているものがあったとは。
自分でインストールはしてない。

SQLとの比較

一旦、調べものは上記までの段階で止まってた。
Prologの言語仕様とか書き方はなんとなく分かったのだが、
どう使うか、他のものとどう違うか、が自分の中で整理できてなかったので。

一つ、気になったのは、集合ベースのシステムと、述語ベースのシステムの差異である。
集合と述語は、性質を記述するものとして表裏の関係にあるはず。

SQLの、

CREATE TABLE person ( name VARCHAR(32) );
INSERT INTO person VALUES ('サザエ');
INSERT INTO person VALUES ('カツオ');
INSERT INTO person VALUES ('ワカメ');

という記法と、
Prologの、

person('サザエ').
person('カツオ').
person('ワカメ').

という記法の差が、どうシステムに表れてくるのか。

Prologの記法では、RDBのように枠の記述と中身の記述を分けておらず、person という枠(=性質)の宣言と、「サザエという個体がpersonに含まれる」という中身についての記述が一文で行われる。
この辺り、Prolog方式は柔軟とも言えるし、細かい管理を要する用途には向かない、とも言えるのではないか。

あと、

person(X) :- male(X); female(X).

のようなPrologのルールは、SQLだとビューになるようだが。
これも…Prologの方が記述の自由度はある、と言えるのかな？

演繹データベースとか、解集合プログラミングとか

↑のようなことを考えつつモニョモニョしていたのだが、
Web上をだらだら見ていたら、↓の書籍が公開されているのを見つけた。

『Logic, Programming and Prolog』
http://www.ida.liu.se/~ulfni/lpp/

Logic, Programming and Prolog

作者: Ulf Nilsson,Jan Maluszynski
出版社/メーカー: Wiley
発売日: 1995/08/30
メディア: ペーパーバック
クリック: 1回
この商品を含むブログを見る

初版が1990年発行。第二版は1995年。
例によってざっと見た限りだが、Prologというよりは論理プログラミングの本。

これの第２章が、Logic and Database となっていて、Relational Database と Deductive Database についてまず述べられている。
6.2 Deductive Database の章から引用。

The part of a logic program which consists of rules and nonground facts is called the intentional database (IDB). Since logic programs facilitate definition of new atomic formulas which are ultimately deduced from explicit facts, logic programs are often referred to as deductive databases.

通常のRDBは外延的に事実を定義するが、論理プログラムでは内包的に事実を定義することもでき、それはIDBと呼べると。deductive は「推論的、演繹的」という訳なので、推論DB、演繹DBということになる。

本書の、この後のところはまだちゃんと読んでない。

で、「演繹データベース」でググったところ色々出てきた。

QUIXOTE
http://www.jipdec.or.jp/archives/icot/ARCHIVE/Museum/SOFTWARE/QUIXOTE/

「キホーテ」と読む。演繹オブジェクト指向データベース、らしい。
↓で、誕生の経緯、命名の由来について説明されている。（ページの文字コードがISO…）
http://www.jipdec.or.jp/archives/icot/ARCHIVE/Museum/SOFTWARE/QUIXOTE/intro/name.html

開発したICOT = 新世代コンピュータ開発機構で、例の第五世代コンピュータプロジェクトの一部、ということになるらしい。
第五世代コンピュータ - Wikipedia

あと、和歌山大の坂間千秋氏。
http://www.wakayama-u.ac.jp/~sakama/j-index.html

元ICOTの方とのこと。

論理プログラミングについて解説がある。
http://www.wakayama-u.ac.jp/~sakama/intro_lp.html

また、「論理プログラミングから解集合プログラミングへ」という論文が公開されている。
http://ci.nii.ac.jp/naid/110006840397

引用

ホーン論理プログラムはチューリング機械と同等の計算能力を持ち、データベースの分野では関係データベースに演繹機能を持たせた演繹データベース(deductive database)の記述言語としても有用である。しかしながら一方では、ホーン論理プログラムを知識表現言語として考えた場合、プログラム中のルールは確定情報しか記述することが出来ず、実世界における不確定・不完全な知識を表現するには限界があること、また単調な演繹推論は限定的であり、人間が日常的に行う非演繹的な常識推論(commonsense reasoning)が必要な局面では役に立たないことなどが問題点として指摘されるようになった。

この問題への対応として、否定と選言が導入されて〜、とのこと。詳細は原文を参照。

前述の『知識と推論』でも第６章「仮説に関する推論」でこのあたりの話に触れられていた。

別の論文でだが、解集合プログラミングの実際の処理系が紹介されていた。