2016-12-15 6 views
4

期待される応答を返した後に、ERROR: Out of global stackで終了するのはなぜですか?CLP(FD)で任意の長さのリストを生成するときの非終了

?- L #>= 0, L #=< 3, length(X, L). 

L = 0, 
X = [] ; 
L = 1, 
X = [_G1784] ; 
L = 2, 
X = [_G1784, _G1787] ; 
L = 3, 
X = [_G1784, _G1787, _G1790] ; 
ERROR: Out of global stack 

更新:W.r.t. @ジョーンズの答え、私はを理解しようとしていますなぜは、それが必ずしも解答を見つけるとは限りません。となります。つまり、問題が無関係ならば、ラベル付けまで答えは等しくなるはずはないでしょうか?ですから、私の質問は、コードを修正するよりも、回答を出す(そして終わらない)仕組みに関連しています。

答えて

4

問題は長さ/ 2述語が不変であることです。スタックオーバーフローの不確実性について理解するための記事があります。@matの1つの良い質問は、Steadfastness: Definition and its relation to logical purity and terminationです。簡単な言葉で言えば、不変性は、述語が最後にパラメータを評価する性質です。あなたの例では

あなたは制約を与えることがあります。

L #>= 0, L #=< 3 

が、length(X, L). Lでは、最後に評価されます。だから、length(X, L)には無限の選択ポイント(すべてのリストXを調べます)があり、すべてのリストXについてLが評価され、Lが制約を満たしていれば答えを返し、次のリストを調べます無限ループにつながります。

あなたはトレースモードに次のように見ることができます:

Call: (8) length(_G427, _G438) ? creep 
    Exit: (8) length([], 0) ? creep 
    Call: (8) integer(0) ? creep 
    Exit: (8) integer(0) ? creep 
    Call: (8) 0>=0 ? creep 
    Exit: (8) 0>=0 ? creep 
    Call: (8) integer(0) ? creep 
    Exit: (8) integer(0) ? creep 
    Call: (8) 3>=0 ? creep 
    Exit: (8) 3>=0 ? creep 
X = [], 
L = 0 ; 
    Redo: (8) length(_G427, _G438) ? creep 
    Exit: (8) length([_G1110], 1) ? creep 
    Call: (8) integer(1) ? creep 
    Exit: (8) integer(1) ? creep 
    Call: (8) 1>=0 ? creep 
    Exit: (8) 1>=0 ? creep 
    Call: (8) integer(1) ? creep 
    Exit: (8) integer(1) ? creep 
    Call: (8) 3>=1 ? creep 
    Exit: (8) 3>=1 ? creep 
X = [_G1110], 
L = 1 ; 
    Redo: (8) length([_G1110|_G1111], _G438) ? creep 
    Exit: (8) length([_G1110, _G1116], 2) ? creep 
    Call: (8) integer(2) ? creep 
    Exit: (8) integer(2) ? creep 
    Call: (8) 2>=0 ? creep 
    Exit: (8) 2>=0 ? creep 
    Call: (8) integer(2) ? creep 
    Exit: (8) integer(2) ? creep 
    Call: (8) 3>=2 ? creep 
    Exit: (8) 3>=2 ? creep 
X = [_G1110, _G1116], 
L = 2 ; 
    Redo: (8) length([_G1110, _G1116|_G1117], _G438) ? creep 
    Exit: (8) length([_G1110, _G1116, _G1122], 3) ? creep 
    Call: (8) integer(3) ? creep 
    Exit: (8) integer(3) ? creep 
    Call: (8) 3>=0 ? creep 
    Exit: (8) 3>=0 ? creep 
    Call: (8) integer(3) ? creep 
    Exit: (8) integer(3) ? creep 
    Call: (8) 3>=3 ? creep 
    Exit: (8) 3>=3 ? creep 
X = [_G1110, _G1116, _G1122], 
L = 3 ; 
Redo: (8) length([_G1110, _G1116, _G1122|_G1123], _G438) ? creep 
    Exit: (8) length([_G1110, _G1116, _G1122, _G1128], 4) ? creep 
    Call: (8) integer(4) ? creep 
    Exit: (8) integer(4) ? creep 
    Call: (8) 4>=0 ? creep 
    Exit: (8) 4>=0 ? creep 
    Call: (8) integer(4) ? creep 
    Exit: (8) integer(4) ? creep 
    Call: (8) 3>=4 ? creep 
    Fail: (8) 3>=4 ? creep 

あなたが最初の呼び出しlength([_G1110|_G1111], _G438)、例えば見ることができるように、それは最初からLを評価しませんが、それは最初の引数に依存して、算出し、制約をチェックします。

2

これは、lengthを実行しても、それはまだバインドされていない変数だからです。

  • 制約のドメインが結合していない変数が
  • あなたは明示的に変数は、その変数に

にラベルを付け、実際の値で統一された単一の値

  • に縮小されています。それはまではありません単一の値にバインドされます。

    次の操作を行うことによって、あなたの例を修正することができます:

    ?- L #>= 0, L #=< 3, label([L]), length(X, L). 
    

    は、あなたがそれを見ることができる最初のポイントを確認するには、次の変数は単一の値に拘束されているため

    ?- L #>= 1, L #=< 1, length(X, L). 
    

    も動作します。

  • 関連する問題