Вот реализация, основанная на индексах deBruijn и основанная на ответах Prolog здесь. Первая часть, перевод L [_] из Википедии в индексы деБрюйна, дает:
lambda(P*Q, W) :-
lambda(P, R),
lambda(Q, S),
simplify(R, S, W).
lambda('I', b(0)).
lambda('K', b(b(1))).
lambda('S', b(b(b(2*0*(1*0))))).
Новые предикаты в линейном упрощении - это simpleify / 2, subst2 / 4, notin / 2 и oncein / 2. shift / 4 точно такой же, как в ответах Пролога здесь. Предикат subst2 / 4 в отличие от subst / 4 вызывает упрощение / 2 для построения терминов приложения:
simplify(b(R), _, S) :- notin(R, 0), !,
shift(R, 0, -1, S).
simplify(b(R), S, T) :- oncein(R, 0), !,
subst2(R, 0, S, T).
simplify(R, S, R*S).
subst2(P*Q, J, D, W) :- !,
subst2(P, J, D, R),
subst2(Q, J, D, S),
simplify(R, S, W).
subst2(b(P), J, D, b(R)) :- !,
K is J+1,
subst2(P, K, D, R).
subst2(J, K, _, J) :- integer(J), J < K, !.
subst2(0, 0, D, D) :- !.
subst2(J, J, D, R) :- integer(J), !,
shift(D, 0, J, R).
subst2(J, _, _, K) :- integer(J), !, K is J-1.
subst2(I, _, _, I).
Предикаты notin / 2 и Oncein / 2 разделяют не более одного раза на not и ровно один раз:
notin(P*Q, J) :- !,
notin(P, J),
notin(Q, J).
notin(b(P), J) :- !,
K is J+1,
notin(P, K).
notin(J, K) :- integer(J), !,
J =\= K.
notin(_, _).
oncein(P*Q, J) :-
notin(P, J), !,
oncein(Q, J).
oncein(P*Q, J) :- !,
oncein(P, J),
notin(Q, J).
oncein(b(P), J) :- !,
K is J+1,
oncein(P, K).
oncein(J, J).
Это проблема, проблема решена:
?- lambda('S'*('S'*('K'*('S'*('K'*'S')*'K'))*'S')*('K'*'K'), X).
X = b(b(b(2*0*1)))
Пример не полностью соответствует этой абстракции скобок, здесь:
?- unlambda(b(b(b(2*0*1))), X).
X = 'S'*('S'*('K'*'S')*('S'*('K'*'K')*'S'))*('K'*'K')
person
Mostowski Collapse
schedule
19.12.2020