1 {------------------------------------------------------------------------------
    2                                    SEARCHING
    3 
    4 The `solve' function is the logical inference mechanism which allows the expert
    5 system to search for solutions to goals, by making deductions from the stored
    6 definitions and from the answers to the questions which it asks the user. This
    7 is essentially the same as the inference mechanism which is built into logic
    8 programming languages, with two main differences.  The first is that the search
    9 algorithm has to be programmed explicitly, and the second is that interaction
   10 with the user cannot be handled as a side effect; questions are returned as
   11 part of the result, and answers are fed in as part of the argument.
   12 ------------------------------------------------------------------------------}
   13 
   14 module Search where
   15 import Result
   16 import Table
   17 import Knowledge
   18 import Match
   19 
   20 -- A call to `solve' returns a list of solutions and questions of type
   21 -- `Solution'. Each solution will be preceded by the questions to which `solve'
   22 -- needs answers in order to form that solution, and the answers to these
   23 -- questions are passed to `solve' in its database argument. A solution
   24 -- consists of an environment giving information about variables, and a list of
   25 -- variable names which are not mentioned in the environment and are therefore
   26 -- available for general use. In particular, the search procedure often calls
   27 -- for a copy of a goal to be made using fresh variables, and the `freshCopy'
   28 -- function performs this, returning a modified solution along with the copy.
   29 
   30 data Solution = Soln Environment [String] | Question String
   31 
   32 freshCopy (Soln env vs) p =
   33    ((Soln env (drop n vs)), subst tab p) where
   34    tab = updateList newTable (zip xs [Var v | v <- take n vs])
   35    xs = vars p
   36    n = length xs
   37 
   38 -- The arguments to `solve' are: a database of stored definitions and
   39 -- information gained from answers to questions, a partial solution
   40 -- representing the information gained about variables so far in the search,
   41 -- and a goal to be satisfied. The first equation allows questions which are
   42 -- generated deep within the search to be passed up and out in the main
   43 -- solution stream. Compound goals are solved by solving the two subgoals and
   44 -- combining the solutions. In the case of `and', information gained in each
   45 -- solution to the first subgoal is used in solving the second. A simple goal
   46 -- (a relation) is solved either by consulting the stored definitions, or by
   47 -- asking the user a question, depending on the verb in that relation.
   48 
   49 solve db (Question q) g = [Question q]
   50 
   51 solve db soln (Term "or" [g1,g2]) =
   52    solve db soln g1 ++ solve db soln g2
   53 
   54 solve db soln (Term "and" [g1,g2]) =
   55    concat [solve db res g2 | res <- solve db soln g1]
   56 
   57 solve db soln g =
   58    if not (null rs) then lookUp db soln g rs else ask info soln g
   59    where
   60    (defs,info) = db
   61    rs = relevant defs g
   62 
   63 -- To `lookUp' a simple goal using the list of rules `rs', a fresh copy of each
   64 -- rule is made (to avoid name clashes with variables about which information
   65 -- is already known), and `try' is used to see if the left hand side of the
   66 -- rule matches the goal. If it does, the goal on the right hand side of the
   67 -- rule is used to continue the search for solutions.
   68 
   69 lookUp db soln g rs =
   70    concat [try db soln' g r' | (soln',r') <- copies] where
   71    copies = [freshCopy soln r | r<-rs]
   72 
   73 try db (Soln env vs) g (Term "if" [p,newg]) =
   74    if fails m then [] else solve db (Soln (answer m) vs) newg
   75    where
   76    m = match env g p
   77 
   78 -- If the solver must ask a question then that question is returned in the list
   79 -- of solutions. The answer is then looked up in the table `info' of
   80 -- questions-and-answers passed as an argument. If the answer is `yes', then
   81 -- the current partial solution is returned. This assumes that questions
   82 -- contain no variables, eg `the animal has stripes?'. Note that, as with other
   83 -- interactive i/o functions, `ask' must return the question before testing the
   84 -- answer.
   85 
   86 ask info (Soln env vs) g =
   87    Question sp :
   88    if ans then [Soln env vs] else [] where
   89    ans = answer (find info sp)
   90    sp  = showPhrase (subst env g)
   91         -- SLPJ Nov 99
   92         -- I've hauled out sp as a common sub expression; it was
   93         -- duplicated before.  If we don't haul it out, it's a matter
   94         -- of chance whether GHC spots it or not, and that makes the
   95         -- numbers wobble around a lot.