home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 5 / DATAFILE_PDCD5.iso / utilities / h / hugs / hs / Prolog / AndrrEngne next >
Encoding:
Text File  |  1995-02-14  |  4.2 KB  |  97 lines
  1. ----------------------------------------------------------------
  2.  
  3. version = "Andorra Principle Interpreter (select deterministic goals first)"
  4.  
  5. {-
  6. By Donald A. Smith, December 22, 1994, based on Mark Jones' PureEngine.
  7.  
  8. This inference engine implements a variation of the Andorra Principle for
  9. logic programming. (See references at the end of this file.) The basic
  10. idea is that instead of always selecting the first goal in the current
  11. list of goals, select a relatively deterministic goal.
  12.  
  13. For each goal g in the list of goals, calculate the resolvents that would
  14. result from selecting g.  Then choose a g which results in the lowest
  15. number of resolvents.  If some g results in 0 resolvents then fail.
  16. (This would occur for a goal like:  ?- append(A,B,[1,2,3]),equals(1,2).)
  17. Prolog would not perform this optimization and would instead search
  18. and backtrack wastefully.  If some g results in a single resolvent
  19. (i.e., only a single clause matches) then that g will get selected;
  20. by selecting and resolving g, bindings are propagated sooner, and useless
  21. search can be avoided, since these bindings may prune away choices for
  22. other clauses.  For example: ?- append(A,B,[1,2,3]),B=[].
  23. -}
  24.  
  25. solve   :: Database -> Int -> Subst -> [Term] -> [Subst]
  26. solve db = slv where
  27.    slv           :: Int -> Subst -> [Term] -> [Subst]
  28.    slv n s [] = [s]
  29.    slv n s goals =
  30.     let allResolvents = resolve_selecting_each_goal goals db n in
  31.       let (gs,gres) =  findMostDeterministic allResolvents in
  32.           concat [slv (n+1) (u**s) (map (app u) (tp++gs)) | (u,tp) <- gres]
  33.  
  34. resolve_selecting_each_goal::
  35.     [Term] -> Database -> Int -> [([Term],[(Subst,[Term])])]
  36. --  For each pair in the list that we return, the first element of the
  37. --  pair is the list of unresolved goals; the second element is the list
  38. --  of resolvents of the selected goal, where a resolvent is a pair
  39. --  consisting of a substitution and a list of new goals.
  40. resolve_selecting_each_goal goals db n = [(gs, gResolvents) |
  41.       (g,gs) <- delete goals, gResolvents = resolve db g n]
  42.  
  43. -- The unselected goals from above are not passed in.
  44. resolve :: Database -> Term -> Int -> [(Subst,[Term])]
  45. resolve db g n = [(u,tp) | (tm:-tp)<-renClauses db n g, u<-unify g tm]
  46. -- u is not yet applied to tp, since it is possible that g won't be selected.
  47. -- Note that unify could be nondeterministic.
  48.  
  49. findMostDeterministic:: [([Term],[(Subst,[Term])])] -> ([Term],[(Subst,[Term])])
  50. findMostDeterministic  allResolvents = minF comp allResolvents where
  51.    comp:: (a,[b]) -> (a,[b]) -> Bool
  52.    comp (_,gs1) (_,gs2) = (length gs1) < (length gs2)
  53. -- It seems to me that there is an opportunity for a clever compiler to
  54. -- optimize this code a lot. In particular, there should be no need to
  55. -- determine the total length of a goal list if it is known that
  56. -- there is a shorter goal list in allResolvents ... ?
  57.  
  58. delete ::  [a] -> [(a,[a])]
  59. delete l = d l [] where
  60.    d :: [a] -> [a] ->  [(a,[a])]
  61.    d [g] sofar = [ (g,sofar) ]
  62.    d (g:gs) sofar = (g,sofar++gs) : (d gs (g:sofar))
  63.  
  64. minF               :: (a -> a -> Bool) -> [a] -> a
  65. minF f (h:t) = m h t where
  66. --   m :: a -> [a] -> a
  67.      m sofar [] = sofar
  68.      m sofar (h:t) = if (f h sofar) then m h t else m sofar t
  69.  
  70. prove    :: Database -> [Term] -> [Subst]
  71. prove db  = solve db 1 nullSubst
  72.  
  73. {- An optimized, incremental version of the above interpreter would use
  74.   a data representation in which for each goal in "goals" we carry around
  75.   the list of resolvents.  After each resolution step we update the lists.
  76. -}
  77.  
  78. {- References
  79.  
  80.    Seif Haridi & Per Brand, "Andorra Prolog, an integration of Prolog
  81.    and committed choice languages" in Proceedings of FGCS 1988, ICOT,
  82.    Tokyo, 1988.
  83.  
  84.    Vitor Santos Costa, David H. D. Warren, and Rong Yang, "Two papers on
  85.    the Andorra-I engine and preprocessor", in Proceedings of the 8th
  86.    ICLP. MIT Press, 1991.
  87.  
  88.    Steve Gregory and Rong Yang, "Parallel Constraint Solving in
  89.    Andorra-I", in Proceedings of FGCS'92. ICOT, Tokyo, 1992.
  90.  
  91.    Sverker Janson and Seif Haridi, "Programming Paradigms of the Andorra
  92.    Kernel Language", in Proceedings of ILPS'91. MIT Press, 1991.
  93.  
  94.    Torkel Franzen, Seif Haridi, and Sverker Janson, "An Overview of the
  95.    Andorra Kernel Language", In LNAI (LNCS) 596, Springer-Verlag, 1992.
  96. -}
  97.