効率的なProlog: 実践ガイド

Efficient Prolog: A Practical Guide (filetype:pdf)
こういったTips集が書籍でもネットでも手に入り辛くなっているのもProlog不人気の一因であろう。これを読むと論理的というより処理系の実装レベルの話に思えるかもしれない（事実そう書いてある）のだが、計算機の効率とは要はそういう事なのであって、Prologも他の言語と同様である。

``効率的なProlog: 実践ガイド''のまとめ

1.宣言的であると同様に手続き的に考える

時にはホーン節を手続き的に考えることで、無限ループを回避出来る
ancestor(A,C):-ancestor(A,B),ancestor(B,C). は宣言的には正しいが、
手続き的に読めば ancestor(A,B) が ancestor(A,C) と単一化してループする
ancestor(A,C):-parent(A,B),ancestor(B,C). は手続き的に正しい

2.狭く探す

a(X)が1000候補、b(X)が10候補の述語の場合
a(X),b(X) よりも b(X),a(X) の方が検索する幅が狭い

3.単一化で済ます

length(L,N),N=3 よりも length(L,3)
length(L,3) よりも has_tree([_,_,_])
後述する理由から単一化で処理する方が速い

4.assert/retractは避ける

知識ベースの変更は遅い、さらにプログラム全体の論理が変わり誤動作を生む
一時的な情報は引数に渡し、assertは知識ベースの拡張（学習）に使う

5.トークン化を理解する

Prologプログラムの内部表現は他の言語とかなり異なる
プログラムは知識ベースのデータであり、数値かアトムか構造で構成される
数値は整数/小数のバイナリ表現
構造は参照スロットの配列と配列の長さおよび配列の先頭への参照
アトムはシンボルテーブルに登録された表現文字列への参照（ハッシュキー）
特にアトムは同じ表現なら全て同じ参照で実装されるので、
f('This atom contains a long long sentence of which ..',
  'This atom contains a long long sentence of which ..',
  'This atom contains a long long sentence of which ..').
という構造は f(a,b,c) より小さな実装となる可能性が高い

6.ストリング処理は避ける

文字列は数値（ASCIIやUNICODEなど）のリストとして表現される
リストは構造の一種で "abc"=[97,98,99]=.(97,.(98,.(99,[]))) のように実装される
ただしリスト構造は多くの処理系で上手く実装（最適化）される

7.末尾再帰を使う

ゴールの最後かつ、候補の最後かつ、サブゴールの他の候補が無い所で再帰する
こうするとバックトラック用にスタックを消費することなく再帰出来る
カットを使うとなお良い

8.並びを気にする

f(a,x).
f(b,x).
f(c,x).
は
f(x,a).
f(x,b).
f(x,c).
より早い、これは末尾再帰述語のヘッドの並びにも影響する

9.モード宣言を使う

変数のインスタンス化の向きは、宣言出来るなら行う
:- mode capital_of(+,-).
capital_of(georgia,atlanta).

10.リストの頭で済ます

リストの効率が良いのは（直接参照が効く）先頭の要素に限る
そうでない部分の単一化はバックトラックの可能性がある
末尾再帰のつもりでそうなっていない場合に注意
有名な例はリストの逆順を定義する述語である
reverse([],[]).
reverse([H|T],Result):-reverse(T,ReversedT),append(ReversedT,[H],Result).
上記は末尾再帰でなくコンシングが多発する
fast_reverse(List1,List2):-fr(List1,[],List2).
fr([Head|Tail],SoFar,Result):-fr(Tail,[Head|SoFar],Result).
fr([],SoFar,SoFar).

11.コンシングを避ける

Prologに限った事ではないが、新しくオブジェクトを作るにはコストがかかる
append等のリスト処理で、再帰のたびにコンシングするのは非効率である
差分リスト f([a,b|X],X) を使うことでコンシングを回避出来る
差分リストとはLISPのRPLACDである、ただしRPLACA相当の作業はコンシングを起こす

12.まとめ

High-level languageでも最適化時にはLow-levelを考える