手続きという高階論理

Prologのコードには宣言的解釈と手続き的解釈が存在する。そして後者の立場を取るときには注意が必要である。手続きとは、暗黙的に時刻を引数に伴う要素から成る、高階論理（或いは関数）だからである。John MAEDAの有名なプログラムを例に挙げよう。

10 PRINT "Hello World!"
20 GOTO 10

想像してみよう、貴方がもしBASICインタプリタの中の人ならば、このプログラムはまさに貴方の運命である。その結末が如何なるものか、貴方には知りえない。だがもし、貴方がコンパイラであればどうだろうか？それはつまり、コードの外に居るということである。

% basic/1
basic(10) :- write('Hello World! ').
basic(20) :- goto(10).
goto(CP) :- retract(cp(_)), assert(cp(CP)).

BASICの各ステップはライン番号（仮想的な時刻）を引数にとる論理である。そして一連のステップから構成されるBASICルーチン、つまり手続きはそれのみでは目的を達し得ない。何故ならライン番号の制御について何も言及出来ないからである。そこでコードの外側で、時間を統べる仕組みが要るのである。

tick :- retract(cp(CP1)), CP2 is CP1 + 1, assert(cp(CP2)).
run :- retractall(cp(_)), assert(cp(0)), run(0).
run(CP1) :- basic(CP1), tick, cp(CP2), run(CP2).
run(_) :- tick, cp(CP), run(CP).

だがしかし、コンパイラだからと言ってやはりコードの運命を知るのは困難であることに違いは無い。何故ならライン番号以外の動的な要素が、コンパイラには教えられていないためである。仮にこれらの情報全てが与えられた（制限された）とすれば、そのコードはチューリング完全性を失い、計算の停止可能性は知りうるのである。それは大域的情報を局所構造に全て落とし込むことでもある。