この逆関数をオーバーフローさせないように修正する方法はありますか？

Question

私はhttp://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25から、この逆の機能だ：これは

?- rev([a,b,c], R). 
R = [c,b,a] 

のようなもののために動作します。しかし、私はこれで、スタックオーバーフローを取得

accRev([H|T],A,R):- accRev(T,[H|A],R). 
accRev([],A,A). 

rev(L,R):- accRev(L,[],R). 

を：

?- rev(L, [c,b,a]). 

なぜこの原因Aはありませんスタックオーバーフロー？両方の仕事？：

Answer 1

?- rev(L, [c,b,a]).

はなぜ、これは、スタックオーバーフローを引き起こすんを作るための方法はありますか？

Sssh ... Prologエンジンを改造しています。

実際には、2つの理由があります。まず、クエリが終了しません。そして、それはむしろ無効な方法でソリューションを検索します。

最初に2番目の理由に対処することで、この問題を「解決」してください。交換するのはaccRev/3の2つの句だけです。またはほとんど -

?- rev(L, [c,b,a]). 
L = [a, b, c] 

素敵に

?- rev(L, [c,b,a]). 
ERROR: Out of local stack 

：これはからの回答を変更します。 Prologはソリューションの最後に.を置かなかったことに注意してください。つまり、それは言う：これ以上のことを望む？だから、;を入力して、あなたが得る：

?- rev(L, [c,b,a]). 
L = [a, b, c] ; 
ERROR: Out of global stack 

だから我々は「ほとんど」問題を解決しました。解決策が見つかりましたが、Prologはまだ終了しません。これは、純粋なPrologプログラムの1つの特性をうまく示しています。

交換句は、解答がどのように見られるかに影響する可能性がありますが、終了には影響しません。

目標が実際に終了していることを確認するための最良の方法は、falseを追加することによって、我々が得るすべての答えを「オフ」することです：

このエラーは今どんなに非常に同じように発生していない

 
?- rev(L, [c,b,a]), false. 
ERROR: Out of global stack 

節が整理される。実際には、原因は以下のfailure-sliceに絞り込むことができます。

 
rev(L,R):- 
    accRev(L,[],R), false. 

accRev([],A,A) :- false. 
accRev([H|T],A,R):- 
    accRev(T,[H|A],R), false. 

注意単にさらに渡されR。したがって、それは何にも影響を与えません。

だから多分same_length/2は最初の考慮

、それが直接この問題を解決することができ... LとRの長さが同じであること、しかし、確認します。あなたは「効率性」にある場合

same_length([], []). 
same_length([_|L], [_|R]) :- 
    same_length(L, R). 

rev_better(L, R) :- 
    same_length(L, R), 
    rev(L, R). 

それとも、ただsame_length/2を直接折り畳むことができることを守ってください。

rev_folded(L, R) :- 
    accrev(L, [],R, R). 

accrev([], R,R, []). 
accrev([E|L], R0,R, [_|Rx]) :- 
    accrev(L, [E|R0],R, Rx).