Prologメタ巡回インタプリタ

Lispの専売特許じゃないよ

有名なMITの教科書、SICPではSchemeでSchemeインタプリタと書くという題材があります。自分の仕組みを使って自分自身を記述するというのがなんとも不思議です。ブートストラップのような不思議さです。これはLispのもつ単純な仕組みがなせる業ですが、PrologもLispと同等以上の自己記述能力があります。N-Prologのテスト、デバッグもかねてPrologでPrologインタプリタを書きました。ISO-Prologの範囲内ですのでどの処理系でも動くと思います。

動作例

consultしたらprolog.で起動します。

N-Prolog Ver 4.46
?- ['./tests/meta'].
yes
?- prolog.

?>

節を登録してみましょう。

?> assert((foo(vX) :- write(vX))).
yes
?> listing(foo).
foo(vX) :-
    write(vX).
yes
?> foo(4).
4yes
?>

変数が普通と違います。vX,vYのように表現しています。これは通常のアトムのようにするためです。変数は連想リストとして処理するためです。

内部の探索

メタ巡回インタプリタの心臓部分はresolve/3です。

resolve(true,Env,Cont) :- !.
resolve((P, Q),Env,Cont) :- 
    connect(Q,Cont,Cont1),
    resolve(P,Env,Cont1).
resolve((P; Q),Env,Cont) :- 
    !, resolve(P,Env,Cont) ; resolve(Q,Env,Cont).

% is builtin
resolve(Goal,Env,Cont) :-
    functor(Goal,is,2), 
    arg(1,Goal,X),
    arg(2,Goal,Y),
    eval(Y,Y1,Env),
    unify(X,Y1,Env,Env1),
    resolve(Cont, Env1, true).
% other builtin
resolve(Goal,Env,Cont) :-
    predicate_property(Goal, built_in), !,
    deref(Goal,Goal1,Env),
    call(Goal1),
    resolve(Cont, Env, true).    
% predicate
resolve(Head,Env,Cont) :-
    clause(Head, true),
    resolve(Cont,Env,true).
% clause
resolve(Head,Env,Cont) :-
    functor(Head, F, N),
    functor(Copy, F, N), 
    clause(Copy, Body), 
    unify(Head, Copy, Env, Env1),
    connect(Body,Cont,Body1),
    resolve(Body1, Env1, true).

第一引数は実行しようとする述語です。第二引数のEnvは変数環境です。第３引数のcontは継続、continuationです。変数環境は連想リストです。vX=2, vY=3ならば [[vX,2][vY,3]]となります。継続はその述語を実行し終えたあとに続いて実行する連言です。

P :- P1,P2,P3. このような節があったとしてP,Qを実行しようとします。するとP,QはP,P2,P3,Qに置き換えられて実行が継続されます。ロビンソンのSLDという方法を実現しているものです。

心臓部はresolve/3なのですが、補助部品がいくつかあります。unify(X,Y,Env,Env1)はEnv環境においてX,YのUnifyを試みます。成功した場合には新たな変数環境がEnv1に返されてます。

• connect（X,Y,Z) 連言Xと連言Yとを連結してZに返されます。これにより継続をします。

• deref(X,Y,Env) XをdereferenceをしてYに返します。X中に変数が含まれている場合には束縛されている値に変換されています。

• eval(X,Y,Env) 式Xを環境Envにおいて評価してYに返します　!+2 -> 3 のように計算してくれます。

フルコードはgithubにおいてあります。今のところ１７０行程度です。この程度でも基本的なPrologの動作をします。そしてこれをジックリと読みますとPrologインタプリタの仕組みが見えてくることでしょう。PrologインタプリタはLispよりもずっとずっと複雑な動作をします。しかし、その仕組みがなんとなく見えてこないでしょうか。

自作の価値

私は中学生の頃に真空管をつかったアンプを自作したものでした。できたものの、雑音を拾ってしまいとても使えたものではありませんでした。しかし、そのおかげでアンプの仕組みが良く理解できました。その中身がわかると心底うれしい気持になるものです。

どうぞ、みなさんもPrologを使うだけでなく作ってみてください。楽しい経験になると思います。