ループ展開

図に示すquick sortでは，qsort/3の再帰節4を実行する際に， 2回のゴール呼出／復帰が生じる。しかしこのプログラムを のように変形するとゴール呼出／復帰を1回とすることができる。

  
図 : プログラム quick sort

1. : main :- list¹( L ) , qsort²( L,S ),
   　 io :outstream³( [ print(S) , nl ] ).

2. : list( L ) :- L =⁴ [ 27,74,17,33,94 ].

3. : qsort( L, R ) :- true | qsort⁵( L,R,[] ).

4. : qsort( [ X | L ],R,R0 ) :- true | partition⁶( L,X,L2 ),
   　 qsort⁷( L2,R1,R0 ), qsort⁸( L1,R,[X | R1] ).

5. : qsort( [],R,R0 ) :- true | R =⁹ R0.

6. : partition( [ X | L ],Y,XL1,L2 ) :- X=< Y | XL1 =¹⁰ [ X | L1 ],
   　 partition¹¹( L,Y,L1,L2 ).

7. : partition( [ X | L ],Y,L1,XL2 ) :- X >=Y | XL2 =¹² [ X | L2 ],
   　 partition¹³( L,Y,L1,L2 ).

8. : partition( [],_,L1,L2 ) :- true | L1 =¹⁴ [], L2 =¹⁵ [].

  
図 : プログラム quick sortのループ展開

1. : main :- list¹( L,L,S ),
   　 io : outstream³( [ print( S ),nl ] ).

2. : list( L,A,B ) :- L =⁴ [ 27,74,17,33,94 ], qsort²( A,B ).

3. : qsort( L,R ) :- true | qsort⁵( L,R,[] ).

4. : qsort( [ X | L ],R,R0 ) :- true | partition⁶( L,X,L1,L2,L2,R1,R0 ),
   　qsort⁸( L1,R,[ X | R1 ] ).

5. : qsort( [],R,R0 ) :- true | R =⁹ R0.

6. : partition( [ X | L ],Y,XL1,L2,A,B,C ) :- X=< Y | XL1 =¹⁰ [ X | L1 ],
   　partition¹¹( L,Y,L1,L2,A,B,C ).

7. : partition( [ X | L ],Y,L1,XL2,A,B,C ) :- X >=Y | XL2 =¹² [ X | L2 ],
   　 partition¹³( L,Y,L1,L2,A,B,C ).

8. : partition( [],_,L1,L2,A,B,C ) :- true | L1 =¹⁴ [], L2 =¹⁵ [],
   　 qsort⁷( A,B,C )

このような変形をプログラムの意味を保存して行なうには，まずゴール partition⁶とqsort⁷の実行を逐次化できることが条件となるが，これに ついてはスレッド化により保証される。したがってqsort⁷の直接の left-siblingであるpartition⁶が以下の条件を満たしていることから，意味を 保存したプログラム変形が可能となる。

1. プログラム中の全てのゴールpartition/4のsuccessorはqsort/3である。

2. partition/4から節qsort/3:4が直接または間接に呼び出されることはない。

このような変形をKLIC標準配布パッケージに含まれる2種のプログラムに適用した結 果，表に示すようにqsort, pascalでは 4〜20% の速度向上が得られた。