prologサンプルコードをふと書いてみる

なんとなく。コードはSWI-Prologでチェックした。

granpa.pl

father(ieyasu, hirotada).
father(hirotada, kiyoyasu).
granpa(GC, GP) :- father(GC, C), father(C, GP).

granpa(ieyasu, X).でX=kiyoyasuになるだけ。

fact.pl

fact(0, 1).
fact(In, Result) :-
  In > 0,
  Pre is In - 1,
  fact(Pre, PreFact),
  Result is In * PreFact.

階乗。fact(10, X).でX=3628800

append.pl

append([], R, R).
append([H|T], R, [H|A]) :- append(T, R, A).

リストの連結。append([1,2,3], [4,5,6], X).でX=[1,2,3,4,5,6]、append(X, [4,5,6], [1,2,3,4,5,6])でX=[1,2,3]、append(X, Y, [1,2,3,4,5,6])でX, Yが6パターン返るなど。

eval.pl

%% example
%% consult(eval).
%% eval([], [apply, [lambda, x, [ref, x]], 10], Result).

eval(Env, [lambda, Arg, Body], [closure, Env, Arg, Body]).
eval(Env, [apply, Operator, Operand], Result) :-
        eval(Env, Operator, [closure, CEnv, Arg, Body]),
        eval(Env, Operand, Val),
        ext(CEnv, Arg, Val, ExtEnv),
        eval(ExtEnv, Body, Result).
eval(Env, [ref, Var], Result) :-
        get(Env, Var, Result).
eval(_Env, Const, Const) :-
        \+ is_list(Const).

ext(OldEnv, Var, Val, [[Var, Val] | OldEnv]).

get([], _Var, not_found).
get([[Var, Val] | _Rest], Var, Val) :- !.
get([[Name, _Val] | Rest], Var, Result) :-
        Name \= Var,
        get(Rest, Var, Result).

ラムダ式(の抽象構文木)のevaluator(環境版)。コメントのとおりにするとResult=10。

同じものをリストではなく、データ構造を使って書いたもの:

%% example
%% consult(eval).
%% eval(nil, apply(lambda(x, ref(x)), 10), Result).

eval(Env, lambda(Arg, Body), closure(Env, Arg, Body)).
eval(Env, apply(Operator, Operand), Result) :-
        eval(Env, Operator, closure(CEnv, Arg, Body)),
        eval(Env, Operand, Val),
        ext(CEnv, Arg, Val, ExtEnv),
        eval(ExtEnv, Body, Result).
eval(Env, ref(Var), Result) :-
        get(Env, Var, Result).
eval(_Env, Const, Const) :-
        number(Const).

ext(OldEnv, Var, Val, cell(Var, Val, OldEnv)).

get(nil, _Var, not_found).
get(cell(Var, Val, _Rest), Var, Val) :- !.
get(cell(Name, _Val, Rest), Var, Result) :-
        Name \= Var,
        get(Rest, Var, Result).