lambda - Prolog 中的括号抽象

Question

根据 Antoni Diller 的算法“A”看起来相当简单:

http://www.cantab.net/users/antoni.diller/brackets/intro.html

我们可以在 Prolog 中做到这一点吗？

Answer 1

% associate formulas to left
associate_left(F, A, B) :-
    append(A, [B], F).

% apply algorithm
reduce(b(_, []), []).
reduce(b(A, B), 'K'(B)) :- atom(B), dif(A, B).
reduce(b(A, A), 'I').
reduce(b(A, [F]), R) :- reduce(b(A, F), R). % uncessary paranthesis case
reduce(b(A, F), 'S'(Pr, Qr)) :-
    associate_left(F, P, Q),
    reduce(b(A, P), Pr),
    reduce(b(A, Q), Qr).

我假设绑定(bind)公式是 b(x, F)，其中 x 绑定(bind)在 F 中。

?- reduce(b(x, [x]), A).
A = 'I' 

?- reduce(b(x, [y]), A).
A = 'K'(y) 

?- reduce(b(x, [u, v]), A).
A = 'S'('K'(u), 'K'(v)) 

您链接中的示例

?- reduce(b(x, [u, v, [w, z, x], [x, z, y], [z, x, [y, x]]]), A).
A = 'S'('S'('S'('S'('K'(u), 'K'(v)), 'S'('S'('K'(w), 'K'(z)), 'I')), 'S'('S'('I', 'K'(z)), 'K'(y))), 'S'('S'('K'(z), 'I'), 'S'('K'(y), 'I'))) 

我也试过算法B。有点毛但是here是的。