/*


         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %%   日本Ｐｒｏｌｏｇ協会  第３回情報交換会   %%
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

                                                １９９１年９月５日（木）
                                                （於）横河電機㈱  健保クラブ
              Prolog Identity 発掘講座 (No.2)
               「ａｐｐｅｎｄの除去手法」
                                                   ソフネック㈱  稲葉 輝
                                                       TEL 0422-21-0061
                                                       FAX 0422-22-1170

                  ＜参考文献＞
        ①  Ｐｒｏｌｏｇ入門    オーム社  古川康一
        ②  Ｐｒｏｌｏｇの技芸  共立出版  Leon Sterling / Ehud Shapiro
        ③  Ｐｒｏｌｏｇ        産業図書  中島秀之
        ④  プログラム変換      共立出版  淵一博  監修


＜＜要約＞＞

  リストを反転するプログラム  ”ｒｅｖｅｒｓｅ／２”  は、Ｐｒｏｌｏｇプログラ
ミングの初歩的な課題として、しばしば登場する。また、Ｐｒｏｌｏｇ処理系の効率
（Ｌｉｐｓ値）を測るプログラムとしても良く使われる。このプログラムは２つの定義
方法があり、一般的には、その効率の良さから重リストを使った定義が使われ、Ｌｉｐ
ｓ値測定ではその効率の悪さからａｐｐｅｎｄを使った定義が使われている。
  本稿では、この２つの定義が本質的に同一のアルゴリズムを内包しており、簡単な操
作で変換できることを示す。
  更に、この変換方法がａｐｐｅｎｄ／３を含むリスト処理プログラムの変換に一般化
でき、効率的なプログラムを書くうえで有効な手法であることに言及する。
  最後に、コンパイラ等のＰｒｏｌｏｇプログラム変換に応用可能であり、目的プログ
ラムの実行効率向上に役に立つ自動変換プログラムを試作する。




            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
            %%%%%%% リストの反転二つの定義方法  %%%%%%%

              ＜１＞                              ＜２＞
      reverse([],[]):-!.          %%       reverse2(L,R):- rev(L,[],R).
      reverse([A|L],R):-          %%
          reverse(L,C),           %%       rev([],L,L):-!.
          append(C,[A],R).        %%       rev([A|L],T,R):-
                                  %%           rev(L,[A|T],R).

      append([],L,L):-!.
      append([A|L],R,[A|LR]):-
          append(L,R,LR).










                                   - 1 -


＜＜効率比較＞＞

  Ｎ要素のリストの反転に要する述語Ｃａｌｌの回数はそれぞれ次のようになる。

      Ｎ      １     ２    １０   ３０ １００
     ------+------+------+------+------+------+--
    ＜１＞    3      6      66    496    5151
    ＜２＞    3      4      12     32     102
    <1>/<2>   1      1.5     5.5   15.5    50.5

  ＜１＞の定義の方法では、先頭を除いたリストを反転したリストに、除いた先頭要素
のみを要素とするリストをａｐｐｅｎｄする。ａｐｐｅｎｄはその第一引数のリスト長
の回数自己再帰がおこなわれるので、ｒｅｖｅｒｓｅの述語呼び出しの回数は、次のよ
うに、Ｏ（ｎ^2）オーダーとなる。

｛Ｎ＋（Ｎ−１）＋（Ｎ−２）＋（Ｎ−３）．．．＋１｝  ＋  （Ｎ＋１）
 ------------- append/3 の呼び出し ----------------    reverse/2の呼び出し


一方、＜２＞では反転するリストの長さ＋２、Ｏ（ｎ）オーダーで済む。

  更に重要なポイントとして、＜１＞の定義では、最後のａｐｐｅｎｄ呼び出しの部分
で初めて末尾最適化が行われフレーム／ロ−カルスタックをＰＯＰするが、その前の部
分では、スタックが深くならざるをえない。              (100List G/L= 16382/710)
  ＜２＞では消費するのはグローバルスタックのみである。(100List G/L= 617/13)

＜＜重リスト＞＞    （注：差分リストともいう）

  ＜１＞から＜２＞への変換をおこなう前に、＜２＞の定義を少々変形し、重リストと
しての考え方を明確にしておこう。（＜２＞の定義が別々の引数で表された重リストで
あるとした考え方は参考文献①②にある）
  重リストは、  ”ｄｉｆｆ（Ｘ，Ｙ）”    ”Ｘ＼Ｙ”    ”Ｘ−Ｙ”  などさまざ
まな書き方をされているが、要は２つの項を使って１つのリストを表現している訳であ
るから、どれでもよい。プログラマさえ間違わなければ、別々の引数であってもかまわ
ない。ここでは、”Ｘ−Ｙ”の記法をとる。
  なお、＜２＞の定義は累算器を使ったプログラムと見ることもできるが、ここでは触
れない。

     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     %%%%%%%%%%%%%% 重リストのおさらい  %%%%%%%%%%%%%%%%%%%%

    二つのリストの差分をもって別のリストを表現する。

    [1,2,3]-[]       ---> [1,2,3]
    [1,2,3]-[2,3]    ---> [1]
    [1,2,3]-[1,2,3]  ---> []    

   これを一般化し、Ｘ−Ｌ（ＬはリストＸのある部分以降）として表すことができる。

             <-- Ｌ-->
    [1,2,3・・・・・・10,11]-[・・・,10,11]
    |________________」 |_________」
              Ｘ     −   Ｌ           ・・・・規則-①

          X-X       ----> []           ・・・・規則-②
          X-[]      ----> X            ・・・・規則-③
    [1,2|L]-L       ----> [1,2]        ・・・・規則-④
    [1,2|L]-[2|L]   ----> [1]          ・・・・規則-⑤



                                   - 2 -


＜＜変換の前準備＞＞


    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %% ＜２＞の reverse2/2 rev/3 定義を重リストとして表現しなおす。 %%

  第３引数が解の重リスト、第２引き数が重リストの尾部と見なせるので、前後を入れ
替え  ”−”  を中置きして結合する。

  reverse2(L,R):-     >>    reverse2(L,R):- 
     rev(L,[],R).     >>       rev(L,R-[]).   ★解Ｒは尾部が空であるリスト

  rev([],L,L).        >>   rev([],L-L):-!.    ★空リストの反転は空リスト
  rev([A|L],T,R):-    >>   rev([A|L],R-T):-
     rev(L,[A|T],R).  >>      rev(L,R-[A|T]).

       ★ Lの反転を R-[A|T] とすれば、[A|L] の反転は R-T である

              _____         _________
              [2,3] -反転-> [3,2,1|T]-[1|T]
                            ====
            [A| L ]         <-- R -->
             _ ____         _________
            [1,2,3] -反転-> [3,2,1|T]-T
                            ======

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%  重リストの結合プログラム %%

      d_append(X-Y,Y-Z,X-Z).

ただしこれは、リストの尾部を変数にして解放した形式のものについて動作する。
（このプログラムの説明は参考文献③に詳しい）

     ?- d_append([1,2,3|L]-L,[4,5|M]-M,Ans).
     Ans  = [1,2,3,4,5|M]-M

 このプログラムは非常に簡単なので、インラインに展開してもよい。

    ?- [1,2,3|L]-L = X-Y , [4,5|M]-M = Y-Z, Ans = X-Z.
    Ans  = [1,2,3,4,5|M]-M

実はこれは、
    ?- X = [1,2,3|L] ,L = [4,5|M] ,Ans = X-M.

と等しい。であるから、完全リストのように全コピーをしていないのでもとのリストの
尾部が書き換えられてしまう。次の２つは、異なることに注意しよう。

    ?- X = [my,name,is],append(X,[inaba],L),append(X,[tell],R).
         L = [my,name,is,inaba]   R = [my,name,is,tell]

    ?- X = [my,name,is|T]-T,d_append(X,[inaba|P]-P,L),d_append(X,[tell|S]-S,R).
         L = [my,name,is,inaba,tell|S]-S   R = [my,name,is,inaba,tell|S]-S

  重リストの頭部への確定個数の要素追加は通常のリストと同様におこなえばよい。
                                                                 ・・・・規則-⑥

”ａ”        を重リスト  Ｘ−Ｌ  の先頭に追加  ＝＝＝＞［ａ｜Ｘ］−Ｌ
”ａ，ｂ，ｃ”を重リスト  Ｘ−Ｌ  の先頭に追加  ＝＝＝＞［ａ，ｂ，ｃ｜Ｘ］−Ｌ
”ａ”    を空の重リスト  Ｌ−Ｌ  の先頭に追加  ＝＝＝＞［ａ｜Ｌ］−Ｌ

                                   - 3 -

＜＜変換開始＞＞

Ⅰ．  ＜１＞の定義の第２引数を重リストを用いて書き換えてみよう。
     ａｐｐｅｎｄ／３は重リストの結合  ｄ＿ａｐｐｅｎｄ／３  と置き換える。

reverse([],[]):-!.   >>  reverse([],L-L).               規則②  []     => L-L
reverse([A|L],R):-   >>  reverse([A|L],R-T):-           規則①  リスト => X-T
   reverse(L,C),     >>     reverse(L,C-D),             規則①  リスト => X-T
   append(C,[A],R).  >>     d_append(C-D,[A|P]-P,R-T).  規則④  [A] => [A|L]-L

Ⅱ．  ｄ＿ａｐｐｅｎｄ／３をインラインに展開する。

reverse([],L-L).               >>   reverse([],L-L).
reverse([A|L],R-T):-           >>   reverse([A|L],R-T):-  
   reverse(L,C-D),             >>      reverse(L,C-D),
   d_append(C-D,[A|P]-P,R-T).  >>        C    - D = X-Y,   -+
                                        [A|P] - P = Y-Z,    |- 展開部分
                                         R    - T = X-Z.   -+

Ⅲ．  展開部分を事前計算する。

reverse([],L-L).               >> reverse([],L-L).
reverse([A|L],R-T):-           >> reverse([A|L],R-T):-
   reverse(L,C-D),             >>    reverse(L,R-[A|T]).  <------------------+
      %% 展開部分 %%           >>                                            |
   C    - D = X-Y,       >>      C    = X     ,  D = Y                       |
  [A|P] - P = Y-Z,       >>     [A|P] = Y = D ,  P = Z     , [A|Z] = Y = D   |
   R    - T = X-Z.       >>      R    = X = C ,  T = Z = P , [A|T] = D       |
                                 ------------               ----------       |
                                     |--------------+------------|           |
                                                    |------------------------+

  これで＜１＞から＜２＞への変換が終了した。reverse/2 の定義が重リストに変わっ
たので、呼び出し側の対応を忘れないようにしよう。一般的には、＜２＞で見たように、
重リストの尾部に空リストを渡して完全リストにしてしまう別口の述語を作る。

    reverse2(L,R) :- 
        reverse(L,R-[]).     規則② 

   この部分は、次のように分けて考えると、よく理解できるだろう。

    reverse2(L,R) :- reverse(L,R-T),T = [].
               R-T = [3,2,1|S]-S,  >>  R = [3,2,1|S], T = S
               T = [].             >>  S = T = [],    R = [3,2,1|[]] = [3,2,1]

同様の方法で他のプログラムも変換することができることを確かめてみよう。

１）  ｆｌａｔ／２  の第２節
[1] flat([A|B],C)   :- flat(A,AA),flat(B,BB),append(AA,BB,C).
[2] flat([A|B],C-T) :- flat(A,AA-AT),flat(B,BB-BT),d_append(AA-AT,BB-BT,C-T).
[3] flat([A|B],C-T) :- flat(A,AA-AT),flat(B,BB-BT),AA-AT=X-Y,BB-BT=Y-Z,C-T=X-Z.
[4] flat([A|B],C-T) :- flat(A,C-BB), flat(B,BB-T).


２）  キューへのデータ登録
[1] enqueue(Data,QueI,QueO)      :- append(QueI,[Data],QueO).
[2] enqueue(Data,QueI-T1,QueO-T2):- d_append(QueI-T1,[Data|P]-P,QueO-T2).
[3] enqueue(Data,QueI-T1,QueO-T2):- QueI-T1=X-Y,[Data|P]-P=Y-Z,QueO-T2=X-Z.
[4] enqueue(Data,QueI-[Data|T2],QueI-T2).

プログラム変換、展開／畳み込み／部分計算などは、参考文献④を熟読されるとよい。

                                   - 4 -                                   */

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%   練習問題：  左側のプログラムからａｐｐｅｎｄ／３を除去せよ  %%
%% ------------------------------------------------------------- %%
%% 通常リストによる定義           %%  重リストによる定義 （答え）%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% １： リストの結合  %% 
%% ?- append([1,2],[3,4],L).      L = [1,2,3,4]

append([],L,L):-!.                %%  d_append(X-Y,Y-Z,X-Z).
append([A|L],R,[A|LR]):-
    append(L,R,LR).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ２： リストの反転  %%
%% ?- reverse([1,2,3],L).         L = [3,2,1]

reverse([],[]):-!.                %% reverse([],L-L):-!.
reverse([A|L],R):-                %% reverse([A|L],R-T):-
    reverse(L,C),                 %%      reverse(L,R-[A|T]).
    append(C,[A],R).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ３： リストの平坦化 %%
%% ?- flat([[1,[2],3],4],L).      L = [1,2,3,4]

flat([],[]):-!.                   %% flat([],L-L):-!.
flat([A|L],C):-!,                 %% flat([A|L],C-T):- !,
    flat(A,AA),                   %%      flat(A,C-D),
    flat(L,LL),                   %%      flat(L,D-T).
    append(AA,LL,C).              %% flat(A,[A|L]-L).
flat(A,[A]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ４： クイックソート %% 
%% ?- qsort([3,4,1],L).          L = [1,3,4]

qsort([],[]):-!.                 %% qsort([],L-L):-!.
qsort([A|B],C):-                 %% qsort([A|B],C-T):-
    partition(B,A,L,R),          %%    partition(B,A,L,R),
    qsort(L,LL),                 %%    qsort(L,C-[A|D]),        
    qsort(R,RR),                 %%    qsort(R,D-T).
    append(LL,[A|RR],C).

partition([],_,[],[]).
partition([X|L],A,[X|L1],L2):- 
    X=<A,!,partition(L,A,L1,L2).
partition([X|L],A,L1,[X|L2]):- 
    partition(L,A,L1,L2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ５： キューの操作  %% 
%% ?- mkqueue(Q),enqueue(1,Q,Q1),enqueue(2,Q1,Q2),
%%    dequeue(First,Q2,Q3),dequeue(Second,Q3,Q4).
%%                                First = 1  Second = 2

mkqueue([]).                     %% mkqueue(X-X).

enqueue(Data,Q1,Q2) :-           %% enqueue(Data,Q1-[Data|T],Q1-T).
    append(Q1,[Data],Q2).

dequeue(Data,[Data|Que],Que).    %% dequeue(Data,[Data|Que]-T,Que-T).

%                                   - 5 -

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ６： バイナリソート  %%
%% ?- binary_sort([5,1,4],L).    L = [1,4,5]

binary_sort(List,Ans):-          %% binary_sort(List,Ans):-
   classify(List,Tree),          %%    classify(List,Tree),
   traverse(Tree,Ans).           %%    traverse(Tree,Ans-[]). 

classify([],_).
classify([A|L],Tree) :- 
   entry(A,Tree),classify(L,Tree).

entry(X,Tree) :- var(Tree),!,Tree = t(_,X,_).
entry(X,t(L,D,_)):- X<D,!,entry(X,L).
entry(X,t(_,_,R)):- entry(X,R).

traverse(X,[]):- var(X),!.       %% traverse(X,L-L):- var(X),!.
traverse(t(L,X,R),Ans):-         %% traverse(t(L,X,R),Ans-Tail):-
   traverse(L,LA),               %%    traverse(L,Ans-[X|RA]),
   traverse(R,RA),               %%    traverse(R,RA-Tail).
   append(LA,[X|RA],Ans).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ７： 三色旗問題  %%      参考文献①②
%%  ?- arrange([白(1),青(1),赤(1),青(2),白(2)],L).
%%  L = [赤(1),白(1),白(2),青(1),青(2)]
%%  述語 dist/4  にはａｐｐｅｎｄが含まれないが、変換する

arrange(L,Ans):-                 %% arrange(L,Ans):-
   dist(L,R,W,B),                %%    dist(L,Ans-W,W-B,B-[]).
   append(R,W,RW),
   append(RW,B,Ans).

dist([],[],[],[]):-!.            %% dist([],R-R,W-W,B-B):-!.
dist([赤(X)|L],[赤(X)|R],W,B):-  %% dist([赤(X)|L],[赤(X)|R]-T,W,B):-
   !,dist(L,R,W,B).              %%    !,dist(L,R-T,W,B).
dist([白(X)|L],R,[白(X)|W],B):-  %% dist([白(X)|L],R,[白(X)|W]-T,B):-
   !,dist(L,R,W,B).              %%    !,dist(L,R,W-T,B).
dist([青(X)|L],R,W,[青(X)|B]):-  %% dist([青(X)|L],R,W,[青(X)|B]-T):-
   dist(L,R,W,B).                %%    dist(L,R,W,B-T).

arrange_test(Ans) :- data(IN),arrange(IN,Ans).
data([白(1),青(1),赤(1),青(2),白(2)]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ８： リストの中の全リストの結合  %%
%% ?- appends([[1,2],[3,4],[5,6]],L).    L = [1,2,3,4,5,6]
%%
%% これは、ちょっと問題がある。リストの中の全重リストの結合に変わってしまう！！

appends([],[]):-!.               %% appends([],L-L):-!.
appends([A|L],Ans):-             %% appends([Ans-T|L],Ans-P):-
   appends(L,M),                 %%    appends(L,T-P).
   append(A,M,Ans).








/*                                   - 6 -                                    

＜＜ａｐｐｅｎｄ自動除去プログラム＞＞

  次にａｐｐｅｎｄの除去を自動化するプログラムを提示する。変換のポイントを明瞭
にするため、リストの結合プログラムはａｐｐｅｎｄ／３であることを前提とし、モー
ドを与えることで重リスト化する引数を明示している。
  なお、本プログラムは試作品であり、正しい変換がされないケースなどは、ぜひ筆者
まで指摘されたい。
  ヒープにアサートされている述語名／アリティと引数モードリスト（−が重リストに
なる引数）を与えて起動する。結果は、標準出力へ出される。
*/

test:- convert(append/3,[-,-,-]),  convert(reverse/2,[+,-]),
       convert(flat/2,[+,-]),      convert(qsort/2,[+,-]),
       convert(mkqueue/1,[-]),     convert(enqueue/3,[+,-,-]),
       convert(dequeue/3,[+,-,-]), convert(traverse/2,[+,-]),
       convert(arrange/2,[+,-]),   convert(dist/4,[+,-,-,-]),
       convert(appends/2,[+,-]).

%%%%%%%%%%%%%%%%%%%%% 核部分 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% append/3 の各引数を重リストに変換しながら事前計算をする %%

del_append(A,B,C):-          %% del_append(A,B,C):-
    bind(A,X-Y),             %%     bind(A,AA),bind(B,BB),bind(C,CC),
    bind(B,Y-Z),             %%     d_append(AA,BB,CC).
    bind(C,X-Z).             %%  ａｐｐｅｎｄに渡される各引数を重リストに変換し
                             %%  d_append/3  で関係づける。
                             %%  左は、インライン展開／事前計算したもの。
%% 重リストに変換 %%

bind(X,X1):- var(X),!,X = X1.
bind([],X-X):- !.                     %% この２行が append/3 とそっくりなのは、
bind([A|L],[A|S]-T):- !,bind(L,S-T).  %% 訳がある。
bind(X,X).

%%%%%%%%%%%%%%%トップレベル起動述語%%%%%%%%%%%%%%%%%%%%%

:- public convert/2.
convert(Fnc/Arity,ArgMode):-
    nl,write('/*%% SOURCE %%'),nl,listing(Fnc/Arity),write('  %% OUTPUT %%*/'),nl,
    functor(Head,Fnc,Arity),
    clause(Head,Body),
    Head=..[F|L],convert_Head(L,L1,ArgMode),Head1=..[F|L1],
    convert_Body(Body,Body1),
    write(Head1),
    ( Body1==true -> true ; write(':-'),nl,tab(4),write(Body1) ),write('.'),nl,
    fail.
convert(_,_).

%%%%%%  頭部の引数を重リスト化する
convert_Head([],[],[]):-!.
convert_Head([A|L],[A1|R],[-|M]):- !,bind(A,A1),convert_Head(L,R,M).    %%!!!!
convert_Head([A|L],[A|R],[_|M]) :- convert_Head(L,R,M).

%%%%%%% ボデイ部からａｐｐｅｎｄ／３を除去する
convert_Body(','(C,D),OUT):- !,
    convert_Body(C,CC),convert_Body(D,DD),make_body(CC,DD,OUT).
convert_Body(append(A,B,C),true):- !,del_append(A,B,C).                 %%!!!!
convert_Body(X,X).
 %%
make_body(true,X,X):-!.
make_body(X,true,X):-!.
make_body(X,Y,','(X,Y) ).
 %%                                 - 7 -

/*
%%%%%%%%%%%%
%% 実行例 %%
%%%%%%%%%%%%

?- log.
yes
?- test.

  %% SOURCE %%
append([],L,L) :-
    !.
append([A|L],R,[A|LR]) :-
    append(L,R,LR).
  %% OUTPUT %%
append(_56-_56,__29,__29):-
    !.
append([A_33|_72]-_73,_73-_103,[A_33|_72]-_103).

  %% SOURCE %%
reverse([],[]) :-
    !.
reverse([A|L],R) :-
    reverse(L,C),
    append(C,[A],R).
  %% OUTPUT %%
reverse([],_56-_56):-
    !.
reverse([A_32|L_34],_97-_99):-
    reverse(L_34,_97-[A_32|_99]).

  %% SOURCE %%
flat([],[]) :-
    !.
flat([A|L],C) :-
    !,
    flat(A,AA),
    flat(L,LL),
    append(AA,LL,C).
flat(A,[A]).
  %% OUTPUT %%
flat([],_58-_58):-
    !.
flat([A_34|L_36],_120-_122):-
    !,flat(A_34,_120-_121),flat(L_36,_121-_122).
flat(__30,[__30|_64]-_64).

  %% SOURCE %%
qsort([],[]) :-
    !.
qsort([A|B],C) :-
    partition(B,A,L,R),
    qsort(L,LL),
    qsort(R,RR),
    append(LL,[A|RR],C).
  %% OUTPUT %%
qsort([],_60-_60):-
    !.
qsort([A_36|B_38],_133-_135):-
    partition(B_38,A_36,L_42,R_44),qsort(L_42,_133-[A_36|_143]),qsort(R_44,_143-_135).


                                 - 8 -

  %% SOURCE %%
mkqueue([]).
  %% OUTPUT %%
mkqueue(_50-_50).

  %% SOURCE %%
enqueue(Data,Q1,Q2) :-
    append(Q1,[Data],Q2).
  %% OUTPUT %%
enqueue(__37,_105-[__37|_107],_105-_107).

  %% SOURCE %%
dequeue(Data,[Data|Que],Que).
  %% OUTPUT %%
dequeue(__39,[__39|_80]-_81,_80-_81).

  %% SOURCE %%
traverse(X,[]) :-
    var(X),
    !.
traverse(t(L,X,R),Ans) :-
    traverse(L,LA),
    traverse(R,RA),
    append(LA,[X|RA],Ans).
  %% OUTPUT %%
traverse(__40,_75-_75):-
    var(__40),!.
traverse(t(L_44,X_46,R_48),_127-_129):-
    traverse(L_44,_127-[X_46|_137]),traverse(R_48,_137-_129).

  %% SOURCE %%
arrange(L,Ans) :-
    dist(L,R,W,B),
    append(R,W,RW),
    append(RW,B,Ans).
  %% OUTPUT %%
arrange(__42,_125-_151):-
    dist(__42,_125-_126,_126-_127,_127-_151).

  %% SOURCE %%
dist([],[],[],[]) :-
    !.
dist([赤(X)|L],[赤(X)|R],W,B) :-
    !,
    dist(L,R,W,B).
dist([白(X)|L],R,[白(X)|W],B) :-
    !,
    dist(L,R,W,B).
dist([青(X)|L],R,W,[青(X)|B]) :-
    dist(L,R,W,B).
  %% OUTPUT %%
dist([],_84-_84,_95-_95,_106-_106):-
    !.
dist([赤(X_54)|L_56],[赤(X_54)|_112]-_113,__50,__52):-
    !,dist(L_56,_112-_113,__50,__52).
dist([白(X_54)|L_56],__48,[白(X_54)|_121]-_122,__52):-
    !,dist(L_56,__48,_121-_122,__52).
dist([青(X_54)|L_56],__48,__50,[青(X_54)|_127]-_128):-
    dist(L_56,__48,__50,_127-_128).



                                 - 9 -

  %% SOURCE %%
appends([],[]) :-
    !.
appends([A|L],Ans) :-
    appends(L,M),
    append(A,M,Ans).
  %% OUTPUT %%
appends([],_74-_74):-
    !.
appends([_113-_114|L_52],_113-_115):-
    appends(L_52,_114-_115).

yes
| ?-nolog.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% クイックソート第２節での動作トレース %%

[0]  Try   convert2( (qsort([A|B],C):- 
                         partition(B,A,L,R),
                         qsort(L,LL),
                         qsort(R,RR),
                         append(LL,[A|RR],C) ),Conv,[+,-])
 |
 |

[1]  Try    del_append(LL,[A|RR],C)
[2]  Match  del_append(LL,[A|RR],C):-bind(LL,X-Y),bind([A|RR],Y-Z),bind(C,X-Z).
[3]  Try    > bind(LL,X-Y)
[4]  Match  > bind(LL,X-Y):- var(LL),!,LL = X-Y.
[5]  Succ   < bind(X-Y,X-Y)                 %% del_append(X-Y,[A|RR],C).
[6]  Try    > bind([A|RR],Y-Z)
[7]  Match  > bind([A|RR],[A|S]-Z):- !,bind(RR,S-Z).
[8]  Try    >> bind(RR,S-Z)
[9]  Match  >> bind(RR,S-Z):- var(RR),!,RR = S-Z.
[10] Succ   << bind(S-Z,S-Z)
[11] Succ   < bind([A|S-Z],[A|S]-Z)          %% del_append(X-[A|S],[A|S-Z],C)
[12] Try    > bind(C,X-Z)
[13] Match  > bind(C,X-Z):- var(C),!,C = X-Z.
[14] Succ   < bind(X-Z,X-Z)                  %% del_append(X-[A|S],[A|S-Z],X-Z)
[15] Succ   del_append(X-[A|S],[A|S-Z],X-Z)

[16] Succ   convert2( (qsort([A|B],X-Z):- 
                           partition(B,A,L,R),
                           qsort(L,X-[A|S]),
                           qsort(R,S-Z),
                           append(X-[A|S],[A|S-Z],X-Z) ),
                       (qsort([A|B],X-Z):- 
                           partition(B,A,L,R),
                           qsort(L,X-[A|S]),
                           qsort(R,S-Z) ),    [+,-])

＜＜おわりに＞＞

  本プログラムは、日本Ｐｒｏｌｏｇ協会のネットワーク／情報交換会フォーラムに
アップロードされているので、アクセスされたい。
  ＤＥＣ−１０Ｐｒｏｌｏｇ仕様の標準的な記述であるが、処理系によっては一部変更
が必要かもしれない。
  （Ｐｒｏｌｏｇ−ＫＡＢＡでは、カンマファンクタの仕様が異なるので、
    convert_Body/2 の書換えが必要である）


                                   - 10 -                                    */


