home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / hugs101o.zip / Progs / HUGS / Demos / Expert / Match.hs < prev    next >
Text File  |  1995-02-14  |  3KB  |  71 lines
  1. {------------------------------------------------------------------------------
  2.                                    MATCHING
  3.  
  4. This module provides a `match' function which implements the famous unification
  5. algorithm. It takes a pair of `patterns', ie structures with variables in them,
  6. matches them against each other, and extracts information about the values
  7. which variables must have in order for the match to be successful. For example,
  8. if `X has stripes' is matched against `Y has Z' then the match is successful,
  9. and the information X=Y and Z=stripes is gleaned. The information about
  10. variables is stored using the `Environment' type; a table which maps variable
  11. names to phrases. The exports from this module are the `Environment' type and
  12. the `match' function.
  13. ------------------------------------------------------------------------------}
  14.  
  15. module Match where
  16. import Result
  17. import Table
  18. import Knowledge
  19.  
  20. -- The `Environment' type stores information about variables. The `subst'
  21. -- function is used whenever a phrase contains variables about which
  22. -- information may be known. The variables in the phrase are (recursively)
  23. -- substituted by their values in the given environment.
  24.  
  25. type Environment = Table String Phrase
  26.  
  27. subst env (Term x ps) = Term x [subst env p | p<-ps]
  28. subst env (Var x) =
  29.    if fails lookup then (Var x) else subst env (answer lookup) where
  30.    lookup = find env x
  31.  
  32. -- The `match' function substitutes any known information about the variables
  33. -- in its argument patterns before comparing them with `compare'.  The
  34. -- `matchList' function deals with a list of pairs of patterns which need to be
  35. -- matched. The information gleaned from each pair is used in matching the
  36. -- next, and the final result contains all the information.
  37.  
  38. match env p1 p2 = compare env (subst env p1) (subst env p2)
  39.  
  40. matchList env [] = success env
  41. matchList env ((p1,p2):pairs) =
  42.    if fails res then res else matchList (answer res) pairs where
  43.    res = match env p1 p2
  44.  
  45. -- The `compare' function is the heart of the algorithm. It compares two
  46. -- phrases and updates the given environment accordingly. For normal terms, it
  47. -- compares the joining words. If these are equal, then it compares
  48. -- corresponding pairs of subphrases. If one or other of the phrases is a
  49. -- variable, then it makes a suitable entry in the environment.
  50.  
  51. compare env (Term x1 ps1) (Term x2 ps2)
  52.    | x1 == x2  = matchList env (zip ps1 ps2)
  53.    | otherwise = failure "no match"
  54. compare env (Var x) (Var y)
  55.    | x /= y    = success (update env x (Var y))
  56.    | otherwise = success env
  57. compare env (Var x) p
  58.    | not (occurs (Var x) p)  =  success (update env x p)
  59.    | otherwise = failure "occurs check failed"
  60. compare env p (Var x) =
  61.    compare env (Var x) p
  62.  
  63. -- The `occurs' check makes sure that a variable does not itself occur in the
  64. -- phrase which it is being set equal to. For example, if X were being set
  65. -- equal to `the animal eats X', then there would be no solution for X,
  66. -- indicating some sort of logical error.
  67.  
  68. occurs v (Term x ps) = or [occurs v p | p<-ps]
  69. occurs (Var y) (Var x) = y == x
  70. occurs p (Var x) = False
  71.