prolog - Prolog での定節文法再帰のカウント

Question

次の Prolog 定句文法があります。

s-->[a],s,[b].
s-->[].

これにより、[a,a,b,b] のような単語は [a,b,a,b] のような単語とは反対に受け入れられます。一言で言えば、文法は明らかにa^nb^nです。ここで、n をユーザーに返したいと思います。n の計算方法を教えてください。

Answer 1

s(X)-->[a],s(Y),[b],{X is Y+1}.
s(0)-->[].

DCG の非端末にパラメータを与える必要があります。X is Y + 1 が使用されたため、命令型プログラミング言語の代入とまったく同じように等価が機能しないことに注意してください。

出力例:

s(X,[a,b,b,b],[]).
false.

s(X,[a,a,a,b,b,b],[]).
X = 3 ;
false.

Answer 2

@thequarkおよび@LittleBobbyTables による回答は、グラウンド文字列で使用すると正常に機能します。

しかし、次のクエリのように、長さが制限されていない場合はどうなるでしょうか?

?- phrase(s(3),_).               % expected: success   
%                                  observed: no answer(s)

?- phrase(s(-10),_).             % expected: failure
%                                  observed: no answer(s)

上記のようなクエリが普遍的に終了することを確実に望んでいます! clpfdを使って書きましょう:

:- use_module(library(clpfd)).

s(0) --> [].
s(N) --> {N#>0,N#=N0+1},[a],s(N0),[b].

サンプルクエリ:

?- phrase(s(N),[a,a,a,a,b,b,b,b]).
N = 4 ;                          % works like in the other answers
false.

?- phrase(s(3),Xs).
Xs = [a,a,a,b,b,b] ;             % now, this works too!
false.                           % (terminates universally)

?- phrase(s(-10),_).             % fails, like it should
false.

Answer 3

s(N, M) --> [a], {N1 is N + 1}, s(N1, M), [b].
s(N, N) --> [].
s(N) --> s(0, N).

使用法：

?- phrase(s(N), [a,a,a,b,b,b]).
N = 3