Loop fusion

手続き型言語において、複数のループを一つにまとめる事はかなり初歩の部類に入る最適化である。一見まったく異なるループでもちょっとした変数変換で一つに出来る事に気付くのは、プログラミングを始めた頃に誰もが通る愉しみだろう。FORTRANなどのひたすらにループ（だけ）を工夫する言語では、この手の最適化はコンパイラがかなり面倒を見てくれる。だが最適化とは違う目的で、ループ融合を使う場合も存在する。

foreach (var elem in arr) { do something.. }
for (var i = 0; i < arr.length; ++i) { do something.. }
    ↓
for (var i = 0; i < arr.length; ++i) {
    var elem = arr[i];
    do something..
}

この手のアプローチは論理型言語であるPrologでも有効である、ばかりでなく別の利点も存在する。例えばリストの長さを求める述語 len/2 とリストの要素が何番目にあるのかを示す述語 nth/3 を見てみよう。

% len/2
len([], 0).
len([_|R], N) :- !, len(R, N0), N is N0 + 1.
% nth/3
nth([X|_], 1, X).
nth([_|R], N, X) :- !, N1 is N - 1, nth(R, N1, X).

?- len(L, 3).
L = [_G101, _G102, _G103].
?- nth([1,2,3], I, 2).
ERROR: is/2: Arguments are not sufficiently instantiated

代入演算子 is/2 は副作用を伴う述語であるため、未初期化変数を伴っての呼び出しは例外を送出する。失敗していない len/2 は、初期化後の呼び出しであるために単一化の双方向性が保たれている。そこで、両者を上手く融合してやれば nth/3 でも双方向性が維持出来ないかと考える。

len(L, N) :- len_aux(L, 1, N).
len_aux([], _I, 0) :- !.
len_aux([_], I, I).
len_aux([_|R], I, N) :- !, I1 is I + 1, len_aux(R, I1, N).
?- len([1,2,3], Len).
Len = 3.
?- len(List, 3).
List = [_G172, _G178, _G184].

どちらを近づけるかは恣意的ではあるが、リスト長が分かるのは要素を全て確認した後であることを考慮すれば、len/2 には個々の要素が何番目であったかの情報が既に含まれていると考える事も可能である。そこで len/2 を nth/3 に近づけていく。カウントアップ時に is/2 が例外を投げないように、今が何度目の呼び出しかを記録する。アリティと節頭部の形が変わった部分は、呼び出し元で補正する。あとは頭部の変数名を揃えると、二つの再帰は融合出来る。

nth(L, N, E) :- nth_aux(L, 1, N, E).
nth_aux([], _I, 0, _E) :- !.
nth_aux([E|_], N, N, E).
nth_aux([_|R], M, N, E) :- !, M1 is M + 1, nth_aux(R, M1, N, E).
?- nth([a, b, c], I, E).
I = 1,
E = a;
I = 2,
E = b;
I = 3,
E = c

だが注意しなければならないのは、これはあくまで小手先のテクニックに過ぎない点である。このように、一つの述語の中に複数の論理が混在することはあまり望ましくない。双方向性がいつでも必要となるわけではない。寧ろプログラムの開発過程では想像だにしない（仕様として把握しきれていない）実行パスを生み、デバッグを困難にする。必要だと判断する限りに留めるべきである。