%%   知識情報処理実習 r6の練習問題 解答例

% 1.
ocr_a(a).
ocr_a(f(T)) :- ocr_a(T).

test6_1_1 :- ocr_a(f(f(f(a)))).
test6_1_2 :- ocr_a(f(f(f(b)))).

/* 文法の定義をプログラムとして記述するのは誤り．
文法はあくまでもデータに対する規則であり，
プログラムはそれに基づいて定義されたデータを解析するものでコンパイラと同じ．
*/

% 2.
subst(a,c).
subst(f(T1),f(T2)) :- subst(T1,T2).
subst(T,T).

test6_2_1(X) :- subst(f(f(a)),X).
test6_2_2(X) :- subst(f(f(b)),X).

% 3.
n_functors(a,0).
n_functors(b,0).
n_functors(f(T),N) :- n_functors(T,N1), N is N1+1.

test6_3(X) :- n_functors(f(f(f(a))),X).

% 4.
subst2(a,c).
subst2(f(T1),f(T2)) :- subst2(T1,T2).
subst2(g(X1,Y1),g(X2,Y2)) 
    :- subst2(X1,X2), subst2(Y1,Y2).
subst2(T1,T1).

test6_4(X) :- subst2(f(g(1,f(a))),X).