meta_predicate (1)

2009年に入ってからSWI-Prologの更新速度が凄まじい。昨年からJan Wielemakerが5.7.xをVMの設計レベルから修正しており、結果として5.6.xと比較すると格段に高速な処理系へと進化している。しかし5.7.xの真価はVMの置き換えではなく、meta_predicate及びその背後にある新しいモジュールシステムにあると言っても過言ではない。

Defining a meta-predicate
meta_predicateを用いた柔軟なモジュールシステムはQuintus Prolog(SICSに権利譲渡)に源流を求めることが出来る。その設計はPrologと非常に親和性の高い形で与えられており、既に当時からDe factoとして受け入れられたのではないかと思われる。次期ISOへの提案として1990年のWGで議題に乗っており、現行の処理系を見てもコンセンサスが得られている状況だ。とは言え、Prolog産業の層の薄さの所為かどうか、正確な実装は今日に至るもそれほど多く存在しない(フリーではSWIとYAPのみ？)のも事実である。

Prologの知識ベースの問題点として、名前空間の欠落が挙げられる。しかし単純に名前空間を切るだけではあまり意味が無い、単一化候補の探索領域が過少に評価される為である。今日的な言語が供える多態性やdelegate機構を実現するには、適当なシンボルについて複数の空間を結合する必要がある。Quintusの実装はこの問題に良いインターフェースを与えた。例えば汎用的なソートコード(C++で言うtemplate化されたソートアルゴリズム)と、事実ベース(C++で言う個々のクラス)ごとに比較述語(operator<)を別々に定義し、後からこれを結合したいとしよう。モジュールシステムを欠いたPrologでは=../2(univ演算子)とcall/1を組み併せてソートに利用する比較述語を渡してやる必要がある。事実ごとに異なる比較演算子を用意することはコードの肥大化にも繋がる。

モジュールシステムのあるPrologでは、述語や演算子に対して探すべきモジュールを変数として扱うことが出来る。個々のモジュールではインターフェース相当の基本演算子や述語を上書きし、別のタイミングでこれを結合する。本質的に高階な論理の記述が可能となる。例えば次のようなものである。

% mysort.pl
:- module(mysort, [mysort/2]). % エクスポートする述語を指定
:- meta_predicate mysort(:, :). % モジュール変数を(:)で宣言
mysort(Mod:[], Mod:[]).
mysort(Mod:[H|T], Mod:L) :-
                      partition(H, Mod:T, Mod:Less, Mod:Big),
                      mysort(Mod:Less, Mod:L1),
                      mysort(Mod:Big, Mod:L2),
                      append(L1, [H|L2], L).
partition(_, Mod:[], Mod:[], Mod:[]).
partition(X, Mod:[Y|L], Mod:[Y|L1], Mod:L2) :-
                      Mod:(Y < X), % 古いPrologでこのコードは通らない
                      partition(X, Mod:L, Mod:L1, Mod:L2).
partition(X, Mod:[Y|L], Mod:L1, Mod:[Y|L2]) :-
                      \+ Mod:(Y < X), % 記述は柔軟に可能
                      partition(X, Mod:L, Mod:L1, Mod:L2).

% mylist.pl
:- module(mylist, [length/2, (<)/2]).
:- redefine_system_predicate(length(_, _)). % システム述語を上書き
:- redefine_system_predicate(_ < _). % 上に同じ
length([], 0).
length([_|T], N) :- !,
                      length(T, N0),
                      N is N0 + 1.
[_name1, Age1] < [_name2, Age2] :- !, % 自然な記述が可能
                      user:(Age1 < Age2). % 必要に応じ呼び元の意味が使える

% test_case
:- use_module(mysort).
:- use_module(mylist).
:- mysort(mylist:[ [taro, 19], [hanako, 11], [jiro, 14] ], mylist:Sorted).
Sorted = [[hanako, 11], [jiro, 14], [taro, 19]]
true.

% invalid_case
:- mysort(mylist:[ [taro, 19], [hanako, 11], [jiro, 14] ], Sorted).
 T Call: (7) mysort:mysort(mylist:[[taro, 14], [hanako, 11], [jiro, 10]], _G1778)
 T Fail: (7) mysort:mysort(mylist:[[taro, 14], [hanako, 11], [jiro, 10]], user:_G1778)
false.

変数がどのモジュールに属するかを指定しなかった場合、userモジュールに単一化されていることに注意。これはHaskellが型推論にユーザの助けを必要とする事と同様(とまでは言えないが類似的)の理由による。この理論的背景が80年代に論理プログラミングの意味論として議論され、特に極小モデル理論が用いられた。