home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 5 / DATAFILE_PDCD5.iso / utilities / b / binprolog / !BinPro330 / progs / maplist < prev    next >
Encoding:
Text File  |  1993-12-20  |  3.2 KB  |  120 lines
  1. /*
  2. > Using the NU-Prolog library predicate mapList:
  3. >
  4. >    head(H._, H).
  5. >    convert(LL, L) :- mapList(head, LL, L).
  6. >
  7.  
  8.  
  9. Is mapList efficient enough in NU-Prolog so that you suggest its use?
  10.  
  11. I like mapList-style constructs myself but I know they
  12. are may be quite inefficient unless something nice is
  13. done by the implementation.
  14.  
  15. The best thing that can happen to mapList(Closure,I,O) is to be
  16. macro-expanded by the preprocessor to its first-order equivalent.
  17.  
  18. However if Closure is not known at compile-time, a general
  19. implementation is needed. Even if Closure is just
  20. the name of a functor this will be still slower then
  21. macro-expansion `by-hand' or `by-preprocessor'.
  22.  
  23. Unless maplist is written in C,
  24. one of the following 2 implementations (maplist0 or maplist)
  25. or their variants are likely to be used:
  26. */
  27.  
  28. % --------------------- CUT HERE --------------------------------
  29.  
  30. go:-go(10000).
  31.  
  32. % straightforward maplist
  33. maplist0(FXs,Is,Os):-
  34.   maplist1(Is,FXs,Os).
  35.  
  36. maplist1([],_,[]).
  37. maplist1([I|Is],Closure,[O|Os]):-
  38.     % suppose ground(Closure), otherwise copy_term is needed
  39.     Closure=..L1,
  40.     concat(L1,[I,O],L2),
  41.     P=..L2,
  42.     P,
  43.     maplist1(Is,Closure,Os).
  44.  
  45. % maplist with findall
  46. maplist(Closure,Is,Os):-
  47.     Closure=..L1,
  48.     concat(L1,[I,O],L2),
  49.     P=..L2,
  50.     findall(O,map1(P,I,Is),Os).
  51.  
  52. map1(P,I,Is):-memb(I,Is),P.
  53.  
  54. concat([],Ys,Ys).
  55. concat([X|Xs],Ys,[X|Zs]):-concat(Xs,Ys,Zs).
  56.  
  57. memb(X,[X|_]).
  58. memb(X,[_|Xs]):-memb(X,Xs).
  59.  
  60. % benchmarking stuff
  61. make_ints([],I,I):-!.
  62. make_ints([I0|L],I0,I):-I0<I,I1 is I0+1,make_ints(L,I1,I).
  63.  
  64. % data
  65.  
  66. plus(A,B,C):-C is A+B.
  67.  
  68. % test
  69.  
  70. time(T):-statistics(runtime,[_,T]).
  71.  
  72. test(R1=R2):-
  73.     maplist0(plus(1),[10,20,30],R1),
  74.     maplist(plus(1),[10,20,30],R2).
  75.  
  76. go(Max):-test(Ok),write(Ok),nl,
  77.     make_ints(Is,1,Max),
  78.     time(_),maplist0(plus(1),Is,_),time(T0),
  79.     maplist(plus(1),Is,_),time(T),
  80.     write([straightforward=T0,with_findall=T]),nl.
  81.  
  82. /* 
  83. Both, but especially maplist0 can get some help from
  84. call/N predicates if available but this do not change
  85. their relative timings too much.
  86.  
  87. The interesting thing I found out is that, for this benchmark at least,
  88. in BinProlog 2.10, the findall based implementation is 7 times
  89. faster than the straightforward one, while being faster in absolute
  90. terms than any of them on other (even native code!) Prologs.
  91. This actually takes advantage of the efficiency of BinProlog's
  92. `copy_once' findall but it also shows that obvious implementations
  93. are not so obvious after all.
  94.  
  95. Here are the timings for BinProlog, Quintus and Sicstus
  96. on a Sparcstation 1.
  97.  
  98. ------------ BinProlog 2.10 -----(bp -h4000)-----------
  99. [straightforward = 4217,with_findall = 650] 
  100. ------------ Quintus 3.0 ------------------------------
  101. [straightforward=5334,with_findall=8416]
  102. ------------- Sicstus 2.1_6 native --------------------
  103. [straightforward=1909,with_findall=3370]
  104. ------------- Sicstus 2.1_6 emulated ------------------
  105. [straightforward=2429,with_findall=3740]
  106. -------------------------------------------------------
  107. I am curious what's happening in other Prologs ...
  108.  
  109. I always found mapList-style predicates very convenient
  110. but I was reluctant to use their `library versions'
  111. because of lack of efficiency.
  112.  
  113. The main point is that if findall has (very) little overhead
  114. then it can be used for all the family of map-predicates
  115. in a similar way.
  116.  
  117. Paul Tarau
  118. */
  119.  
  120.