Hw2 code instructions

Note:  These are provided in case they are helpful; you are free to do the design on your own, provided the system uses exhaustive depth-first search.

 

1.      Define a variable rules, set to be a list of the rules you defined in hw1.

2.      Define a variable wm to be the initial working memory consisting of the assertions you defined in hw1.

3.    Write a procedure substitute which takes a substitution and a pattern and returns the pattern with the variables from the substitution substituted into it. A substitution is just a list of 2-element lists, each representing a variable binding. The first element of each sublist is the variable's name (we'll include the leading "?", but some sources do not). The second is its binding. For example, given the substitution [('?y', 'mary'), ('?x', 'john')] and the pattern '?x gave (son-of ?y) ?z' the result would be 'john gave (son-of mary) ?z'.

 As another example, given the substitution [('?y', '?z'), ('?z', '?x')] and pattern 'drop arnold (class ?y 563)', the result would be 'drop arnold (class ?x 563)'. 

Notice in the second example that the procedure should continue to replace variables until this is no longer possible. To make matters simple, we assume that cycles are not possible in the substitution. Thus you would never have [('?y', '?x') ('?x', '?y')] as a substitution. You may use the following procedure to test whether an string is a variable, that is, whether it is a symbol beginning with “?”. Notice that the ? is left on in the substitution.

def is_var (string):

      if (string[0] == '?'):

            return True

      return False

 

4.    Write a procedure unify which takes two patterns and a substitution and returns either an updated substitution (possibly the empty list) or False.

5.    Forward chaining using depth-first search requires a procedure to expand a state. (We can represent nodes in the search tree as states rather than complete paths.) Each state will consist of a list of antecedents still to be matched and a substitution. Write the state-expanding procedure, match_antecedent. It takes a state (a list of remaining antecedents and a substitution) and a working memory and returns all possible new states which can be reached by matching the first antecedent in the list. It uses unify to attempt to match the antecedent against each pattern in the working memory.

 

def match_antecedent (anteceds, wm, sub):

      antec = anteceds[0]

      def ma_helper (states, wm_left):

            # If wm_left is empty return states.

            # Otherwise attempt to unify antec with next pattern in wm_left in the context of sub.

            #

            # If unification fails, call ma_helper on the same list of states and the rest of wm_left.

            #

            # If unification succeeds, call ma_helper with the new state combined onto states and

            # the rest of wm_left.

            # (The new state includes the remaining antecedents and whatever new substitution

            # resulted from the unification.)

      return ma_helper ([], wm)

 

    NOTE: Yes, we have a function inside a function.

 

6.    Write a procedure execute which takes a substitution, the right-hand side of a rule (one or more consequents), and a working memory. execute applies the substitution to each of the consequents in the right-hand side, using substitute; for each pattern generated by substitute, checks whether it is already in working memory; and if it is not, adds it to an accumulated list of new patterns. execute returns the list of new patterns (which is not added to the working memory yet).

7.    Write a procedure match_rule which takes the name of a rule, the left-hand side of a rule (a list of antecedents), the right-hand side of the rule (a list of consequents), and a working memory. match_rule uses exhaustive depth-first search to find all possible ways to satisfy the rule using patterns in the working memory. It maintains a queue of states (each consisting of a set of antecedents left to match and a current substitution). It removes the first state from the queue, checks to see whether this is a goal state (that is, whether there are no more antecedents), and if so, attempts to create new patterns by applying execute to the right-hand side using the substitution in the state. If the state is not a goal state, it is expanded using match_antecedent, and the new states are appended onto the front of the queue. Since this is exhaustive search, we do not stop when a goal state is found but continue until all states in the queue are tried. match_rule returns the list of new patterns to be added to working memory as a result of matching the rule. The list will be empty if either the rule fails to be matched or all of the instantiated consequents which result are already in the working memory. Here is a template for match_rule.

 

def match_rule (name, lhs, rhs, wm):

      #print some useful messages here

      def mr_helper (queue, new_wm):

           # Each state in queue is

           # (anteceds-left, subs)

                        # if the queue is empty, return new_wm

 

                        # else examine the first item in the queue (call it state1)

                        #      If state1 has no antecedents, state1 is a goal state (the rule is matched);

                        #      call "execute" on rhs using the substitution in state1

 

                        #            But don't stop here (this is exhaustive):

                        #            return  mr_helper applied to the rest of the queue, appending

                        #            whatever new WM assertions "execute" returned.

 

                        #      Else if state1 has antecedents, apply "match_antecedent" to them

                        #      along with wm and the substitutions in state1.

       

                        #            If "match_antecedent" returns no new states, return mr_helper on rest of

                        #            the queue without changing states.

 

                        #            Else return mr_helper on the updated queue,

                        #            i.e., the old one with the new states found

                        #            by "match_antecedent" replacing state1

      return mr_helper (match_antecedent (lhs, wm ,[]), [])

    NOTE: "return mr_helper" means to call mr_helper and explicity return its result.

8.    Write a procedure match_rules which takes a list of rules and a working memory, calls match_rule on each of the rules, and returns a list of new patterns resulting from matching rules.

9.    Write a procedure run_ps which takes a list of rules, a working memory, and a truth value (for the question mode) and calls match_rules repeatedly, appending the new patterns that are returned onto the working memory, until no new patterns are found on an iteration. run_ps returns the updated working memory.