Prolog中的括号抽象

问题描述

算法"A"为根据安东尼·迪勒的说法，看起来很简单:

The algorithm "A" according to Antoni Diller looks fairly simple:

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

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

Can we do this in Prolog?

推荐答案

% 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).

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

I am assuming bound formulas are b(x, F) where x is bound in 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.它有点毛茸茸，但在这里是.

I tried algorithm B too. It is a bit hairy but here it is.

这篇关于Prolog中的括号抽象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！