Prolog でスタック言語を作る

Prolog で簡単なスタック言語を作ってみた。組み込み関数は以下の通り。

- dup: スタックの先頭を複製してスタックに積む
- swap: スタックの最初の2つを入れ替える
- pop: スタックの最初の要素を取り除く
- add: スタックの最初の2つを取り除いてそれらを合計したものを積む
- if: スタックの先頭の真偽値に応じて2つ目ないし3つ目の関数を実行
- cons: スタックの最初の要素を2つ目の要素（リスト）にconsする
- emptyp: スタックの最初の要素を取り除き、それが空リストだったらtrue、それ以外だったらfalseをスタックに置く
- car: スタックの先頭要素（リスト）を取り除き、そのcarを積む
- cdr: スタックの先頭要素（リスト）を取り除き、そのcdrを積む
- app: スタックの先頭要素（関数）を適用する
- papp: スタックの先頭要素（関数）を2つ目の要素にだけ部分適用する

これが実行例。

?- exec([], [12,dup], X).

X = [12, 12] ;

No
?- exec([], [12,34,swap], X).

X = [12, 34] ;

No
?- exec([], [12,34,pop], X).

X = [12] ;

No
?- exec([], [12,34,add], X).

X = [46] ;

No
?- exec([], [12,true,[dup,add],[34,swap],if], X).

X = [24] ;

No
?- exec([], [12,false,[dup,add],[34,swap],if], X).

X = [12, 34] ;

No
?- exec([], [nil,12,cons,34,cons], X).

X = [[34, 12]] ;

No
?- exec([], [nil,emptyp], X).

X = [true] ;

No
?- exec([], [nil,12,cons,emptyp], X).

X = [false] ;

No
?- exec([], [nil,12,cons,34,cons,car], X).

X = [34] ;

No
?- exec([], [nil,12,cons,34,cons,cdr], X).

X = [[12]] ;

No
?- exec([], [12,34,[add],app], X).

X = [46] ;

No
?- exec([], [12,34,[add],papp], X).

X = [[34, add], 12] ;

No
?- exec([], [12,34,[add],papp,app], X).

X = [46] ;

No
?- exec([], [12,34,[add],papp,papp], X).

X = [[12, 34, add]] ;

No
?- exec([], [12,34,[add],papp,papp,app], X).

X = [46] ;

No

実装コード。非常にシンプルで、殆ど仕様そのまま。Prolog すごい。

exec(S, [], S).
exec(S1, [H|T], S2) :- value(H,I), !, exec([I|S1], T, S2).
exec(S1, [H|T], S2) :-
  P =.. [H, S1, S3],
  call(P),
  exec(S3, T, S2).

value(X,X) :- number(X).
value(X,X) :- is_list(X).
value(true,true).
value(false,false).
value(nil,[]).

dup([H|T],[H,H|T]).
swap([X,Y|Z],[Y,X|Z]).
pop([H|T],T).
add([X,Y|Z], [S|Z]) :- S is X+Y.
if([_,X,true|Y], Z) :- exec(Y,X,Z).
if([X,_,false|Y], Z) :- exec(Y,X,Z).
cons([X,Y|Z],[[X|Y]|Z]).
emptyp([[]|T],[true|T]) :- !.
emptyp([_|T],[false|T]).
car([[X|Y]|Z],[X|Z]).
cdr([[X|Y]|Z],[Y|Z]).
app([X|Y],Z) :- exec(Y, X, Z).
papp([X,Y|Z], [[Y|X]|Z]).