home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 5 / DATAFILE_PDCD5.iso / utilities / b / binprolog / !BinPro330 / progs / choice < prev    next >
Encoding:
Text File  |  1994-09-03  |  6.3 KB  |  261 lines
  1. /* The predicates are called:                             */
  2.  
  3. /*    o  "choice_point(N)"    - creation of choice points    */
  4. /*    o  "choice_point0ar(N)  - same, with 0 arg             */
  5. /*    o  "baktrak1(N)"        - deep backtracking            */
  6. /*    o  "baktrak2(N)"        - shallow backtracking         */
  7.  
  8. /*  N is the number of loop iterations executed  */
  9. :-write('run with -h1000 -s6000'),nl.
  10.  
  11. go:-go('BMARK_choice:').
  12.  
  13. go(Mes):-N=10000,
  14.   statistics(global_stack,[H1,_]),
  15.   statistics(local_stack,[S1,_]),
  16.   statistics(trail,[TR1,_]),
  17.   statistics(runtime,[T1,_]),
  18.   choice_point(N),
  19.   baktrak1(N),
  20.   baktrak2(N),
  21.   statistics(runtime,[T2,_]),T is T2-T1,
  22.   statistics(global_stack,[H2,_]),H is H2-H1,
  23.   statistics(trail,[TR2,_]),
  24.   statistics(local_stack,[S2,_]),S is S2-S1,TR is TR2-TR1,
  25.   write(Mes=[time=T,stack=S,heap=H,trail=TR]),nl.
  26.  
  27. p:-[choice].
  28.  
  29. /* predicate to test creation of choice points without backtracking */
  30. /* suggested value for N: 1000 */
  31. /* results for  Cprolog N=1000 */
  32. /* Tloop=5.95 Tcompens=0.98 Tnet=4.97 Klips=4.02 */
  33.  
  34. choice_point(N):-statistics(runtime,[T1|_]),
  35.         cre_CP(N), statistics(runtime,[T2|_]),
  36.         compens_loop(N), statistics(runtime,[T3|_]),
  37.         print_times(T1,T2,T3,N,20).
  38.  
  39. /* predicate choice_point, but with zero argument  */
  40. /* suggested value for N: 1000 */
  41. /* results for Cprolog: N=1000 */
  42. /* Tloop=3.55 Tcompens=0.98 Tnet=2.57 Klips=7.7  */
  43.  
  44.  
  45. choice_point0ar(N):-statistics(runtime,[T1|_]),
  46.         cre_CP0ar(N), statistics(runtime,[T2|_]),
  47.         compens_loop(N), statistics(runtime,[T3|_]),
  48.         print_times(T1,T2,T3,N,20).
  49. /* Predicate to test the (deep) backtracking mechanism. */
  50. /* suggested value for N: 1000 (interp), 2000(comp) */
  51. /* results for Cprolog: N=1000  */
  52. /* Tloop=9.63 Tcomp=1 Tnet=8.63 Klips=2.32  */
  53.  
  54. baktrak1(N)
  55.      :- statistics(runtime,[T1|_]),
  56.         deep_back(N),
  57.         statistics(runtime,[T2|_]),
  58.         compens_loop(N),
  59.         statistics(runtime,[T3|_]),
  60.         print_times(T1,T2,T3,N,20).
  61.  
  62.  
  63. /* Predicate to test the (shallow) backtracking mechanism */
  64. /* suggested value for N: 1000 (interp), 2000 (comp) */
  65. /* results for Cprolog: N=1000  */
  66. /* Tloop=3.63  Tcomp=0.95 Tnet=2.68 Klips=7.45 */
  67.  
  68. baktrak2(X)
  69.      :- statistics(runtime,[T1|_]),
  70.         shallow_back(X), statistics(runtime,[T2|_]),
  71.         compens_loop(X), statistics(runtime,[T3|_]),
  72.         print_times(T1,T2,T3,X,20).
  73.  
  74.  
  75. /* compensation loop, used to measure the time spent in the loop  */
  76. compens_loop(0).
  77. compens_loop(X) :- Y is X - 1, compens_loop(Y).
  78.  
  79. /* loop to test choice point creation   */
  80. cre_CP(0).
  81. cre_CP(N):-M is N-1, ccp1(0,0,0), cre_CP(M).
  82.  
  83. cre_CP0ar(0).
  84. cre_CP0ar(N):-M is N-1, ccp1, cre_CP0ar(M).
  85.  
  86. /* loop to test deep backtracking       */
  87. deep_back(0).
  88. deep_back(X) :- pd(_,_,_), Y is X - 1, deep_back(Y).
  89.  
  90. /* loop to test shallow backtracking */
  91. shallow_back(0).
  92. shallow_back(X) :- ps(_,a,b), Y is X - 1, shallow_back(Y).
  93.  
  94.  
  95. print_times(T1,T2,T3,X,I) :-        /* prints the results */
  96.         TT1 is T2 - T1,
  97.         TT2 is T3 - T2,
  98.         TT is TT1 - TT2,
  99.         write('T overall loop:   '),write(TT1), nl,
  100.         write('T compens loop:   '),write(TT2), nl,
  101.         write('T net:            '),write(TT),nl,
  102.         write('Lips:            '),
  103.         Li is I * X,
  104.         Lips is 1000*Li // TT,
  105. %        KLips is Lips / 1000,
  106.         write(Lips),nl,nl.
  107.  
  108. /*  ccp1 creates 20 choice points */
  109. /* ccp1 is the beginning of a set of predicates  */
  110. /* composed of 2 clauses each. Every invokation of nd0 will create */
  111. /* a sequence of 20 choice points. The body of the clauses are     */
  112. /* limited to one goal, thus avoiding a creation of environment    */
  113. /* when the clause is activated. nd0, and its successors, have     */
  114. /*   three arguments to comply with our average static analysis    */
  115. /*   results made on more than 30 real Prolog programs.            */
  116. /* ccpXX exists with 3 arguments, and 0 args. */
  117.  
  118. ccp1(X,Y,Z):-ccp2(X,Y,Z).
  119. ccp1(X,Y,Z).
  120. ccp2(X,Y,Z):-ccp3(X,Y,Z).
  121. ccp2(X,Y,Z).
  122. ccp3(X,Y,Z):-ccp4(X,Y,Z).
  123. ccp3(X,Y,Z).
  124. ccp4(X,Y,Z):-ccp5(X,Y,Z).
  125. ccp4(X,Y,Z).
  126. ccp5(X,Y,Z):-ccp6(X,Y,Z).
  127. ccp5(X,Y,Z).
  128. ccp6(X,Y,Z):-ccp7(X,Y,Z).
  129. ccp6(X,Y,Z).
  130. ccp7(X,Y,Z):-ccp8(X,Y,Z).
  131. ccp7(X,Y,Z).
  132. ccp8(X,Y,Z):-ccp9(X,Y,Z).
  133. ccp8(X,Y,Z).
  134. ccp9(X,Y,Z):-ccp10(X,Y,Z).
  135. ccp9(X,Y,Z).
  136. ccp10(X,Y,Z):-ccp11(X,Y,Z).
  137. ccp10(X,Y,Z).
  138. ccp11(X,Y,Z):-ccp12(X,Y,Z).
  139. ccp11(X,Y,Z).
  140. ccp12(X,Y,Z):-ccp13(X,Y,Z).
  141. ccp12(X,Y,Z).
  142. ccp13(X,Y,Z):-ccp14(X,Y,Z).
  143. ccp13(X,Y,Z).
  144. ccp14(X,Y,Z):-ccp15(X,Y,Z).
  145. ccp14(X,Y,Z).
  146. ccp15(X,Y,Z):-ccp16(X,Y,Z).
  147. ccp15(X,Y,Z).
  148. ccp16(X,Y,Z):-ccp17(X,Y,Z).
  149. ccp16(X,Y,Z).
  150. ccp17(X,Y,Z):-ccp18(X,Y,Z).
  151. ccp17(X,Y,Z).
  152. ccp18(X,Y,Z):-ccp19(X,Y,Z).
  153. ccp18(X,Y,Z).
  154. ccp19(X,Y,Z):-ccp20(X,Y,Z).
  155. ccp19(X,Y,Z).
  156.  
  157. ccp20(X,Y,Z).
  158. ccp20(X,Y,Z).
  159.  
  160. ccp1:-ccp2.
  161. ccp1.
  162. ccp2:-ccp3.
  163. ccp2.
  164. ccp3:-ccp4.
  165. ccp3.
  166. ccp4:-ccp5.
  167. ccp4.
  168. ccp5:-ccp6.
  169. ccp5.
  170. ccp6:-ccp7.
  171. ccp6.
  172. ccp7:-ccp8.
  173. ccp7.
  174. ccp8:-ccp9.
  175. ccp8.
  176. ccp9:-ccp10.
  177. ccp9.
  178. ccp10:-ccp11.
  179. ccp10.
  180. ccp11:-ccp12.
  181. ccp11.
  182. ccp12:-ccp13.
  183. ccp12.
  184. ccp13:-ccp14.
  185. ccp13.
  186. ccp14:-ccp15.
  187. ccp14.
  188. ccp15:-ccp16.
  189. ccp15.
  190. ccp16:-ccp17.
  191. ccp16.
  192. ccp17:-ccp18.
  193. ccp17.
  194. ccp18:-ccp19.
  195. ccp18.
  196. ccp19:-ccp20.
  197. ccp19.
  198.  
  199. ccp20.
  200. ccp20.
  201.  
  202.  
  203. /*  deep backtracking */
  204. /*  The call to pd creates a choice point, and invokes a      */
  205. /*  call to q. It will fail and there will be a backtracking  */
  206. /*  step  to try the next clause defining pd. pd has 21       */
  207. /*  clauses,thus failure                                      */
  208. /*  occurs 20 times                                           */
  209.  
  210. pd(X1,X2,_) :- q(X1,X2,a).
  211. pd(X1,X2,_) :- q(X1,X2,a).
  212. pd(X1,X2,_) :- q(X1,X2,a).
  213. pd(X1,X2,_) :- q(X1,X2,a).
  214. pd(X1,X2,_) :- q(X1,X2,a).
  215. pd(X1,X2,_) :- q(X1,X2,a).
  216. pd(X1,X2,_) :- q(X1,X2,a).
  217. pd(X1,X2,_) :- q(X1,X2,a).
  218. pd(X1,X2,_) :- q(X1,X2,a).
  219. pd(X1,X2,_) :- q(X1,X2,a).
  220. pd(X1,X2,_) :- q(X1,X2,a).
  221. pd(X1,X2,_) :- q(X1,X2,a).
  222. pd(X1,X2,_) :- q(X1,X2,a).
  223. pd(X1,X2,_) :- q(X1,X2,a).
  224. pd(X1,X2,_) :- q(X1,X2,a).
  225. pd(X1,X2,_) :- q(X1,X2,a).
  226. pd(X1,X2,_) :- q(X1,X2,a).
  227. pd(X1,X2,_) :- q(X1,X2,a).
  228. pd(X1,X2,_) :- q(X1,X2,a).
  229. pd(X1,X2,_) :- q(X1,X2,a).
  230. pd(X1,X2,_).
  231.  
  232. q(X1,X2,b).
  233.  
  234.  
  235. /*   shallow backtracking */
  236. /*   The ps predicate fails 20 times. The shallow backtracking   */
  237. /*   will not restore all current state registers in Prolog      */
  238. /*   systems which perform this optimisation, while others will. */
  239.  
  240. ps(_,X,X).
  241. ps(_,X,X).
  242. ps(_,X,X).
  243. ps(_,X,X).
  244. ps(_,X,X).
  245. ps(_,X,X).
  246. ps(_,X,X).
  247. ps(_,X,X).
  248. ps(_,X,X).
  249. ps(_,X,X).
  250. ps(_,X,X).
  251. ps(_,X,X).
  252. ps(_,X,X).
  253. ps(_,X,X).
  254. ps(_,X,X).
  255. ps(_,X,X).
  256. ps(_,X,X).
  257. ps(_,X,X).
  258. ps(_,X,X).
  259. ps(_,X,X).
  260. ps(_,_,_).
  261.