# This file has a primitive rule system layered on top of Liz's frame package. It is VERY rudimentary. # A generic rule frame is defined with slots: # # Name - The name of the rule. # # IFpart - A list of Nial expressions as character strings. # These are the clauses that are anded together to form the # premise of the rule. # # THENpart - A list of Nial expressions as character strings. These # are the actions to be taken when the premise is satisfied. # # English - The English version of the rule. # # Forward - The frame names of rules that use the values that are # set by the THENpart of this rule. # # Backward - The frame names of rules that set the values that are used # by the IFpart of this rule. These are given as a list of # lists, one for each clause in the IFpart. # The assumption is that the expressions in the IFpart will be valid Nial expressions that evaluate to truth values. To assist in writing such expressions some additional operations may prove necessary. For example ownvalue and ownvalues described below. The THENpart has Nial expressions that carry out the actions required by the rule. # The following variable records the global state of the rule interpreter. It keeps track of the Context that is discussed by the rules. The Context is a single frame value. This may not prove adequate for some problems. Thiscontext IS EXTERNAL VARIABLE # The following operations are provided to give convenient access to the values in the Context frame. # The first value in the VALUE facet of Slot in the Context frame. ownvalue IS OP Slot ( first fget Thiscontext Slot "VALUE) # The list of values in the VALUE facet of Slot in the Context frame. ownvalues IS OP Slot ( fget Thiscontext Slot "VALUE) # Put Val in the list of values in the VALUE facet of Slot in the Context frame. putownvalue IS OP Slot Val ( fput Thiscontext Slot "VALUE Val) # Change Val1 to Val2 in the list of values in the VALUE facet of Slot in the Context frame. changeownvalue IS OP Slot Val1 Val2 ( fchange Thiscontext Slot Val1 Val2) # assign the value Val to the variable Var and return Truth. This is used in rules to bind variables across clauses, and between the If and THEN parts. bind IS OP Var Val (Var assign Val; l) # A simple back chaining rule interpreter: - Input The Goalrule to accomplish, and the frame that forms the context in the frame hierarchy in which the rule is to be tried. - Algorithm: Consider the clauses of the IF part: if a clause fails backward chain on the rules for that clause in the BACKWARD slot one at a time, retrying the clause. IF all the clauses succeed, then execute the THEN part. # Quiet controls debug output Quiet IS EXTERNAL VARIABLE backwardchain IS OPERATION Goalrule Context { NONLOCAL Thiscontext; IF not Quiet THEN write "chaining "on Goalrule Context; ENDIF; Savecontext gets Thiscontext; Thiscontext gets Context; Clauses gets fget Goalrule "IFPART "VALUE; Backrules gets fget Goalrule "BACKWARD "VALUE; FOR I WITH grid Clauses DO Rules gets I pick Backrules; REPEAT IF not Quiet THEN write "trying (phrase (I pick Clauses)); ENDIF; Failed gets not execute (I pick Clauses); IF not Quiet THEN write "result (not Failed); ENDIF; IF Failed and not empty Rules THEN Firstrule Rules gets [first,rest] Rules; backwardchain Firstrule Context; ELSE EXIT l ENDIF; UNTIL not Failed ENDREPEAT; IF Failed THEN IF not Quiet THEN write "exiting_loop; ENDIF; EXIT l ENDIF; ENDFOR; IF not Quiet THEN write "premise (not Failed); ENDIF; IF not Failed THEN Actions gets fget Goalrule "THENPART "VALUE; IF not Quiet THEN write "executing; ITERATE writescreen Actions; ENDIF; ITERATE execute Actions; ENDIF; Thiscontext := Savecontext; } # A switch to adjust strategy in forward chaining from depth first to breadth first search. depthfirst IS EXTERNAL VARIABLE # forwardchain is a simple forward chaining rule interpreter. It terminates when the operation finalgoal returns Truth or when no more rules are triggered. Input: The initial rules and a Context frame. Algorithm: While rules still remain and the goal is not accomplished Choose first rule. If all the clauses of the premise are true then 1. execute the actions. 2. add the rules that chain forward to the list. Continue finalgoal IS EXTERNAL OPERATION forwardchain IS OPERATION Rules Context { NONLOCAL Thiscontext; Thiscontext gets Context; WHILE not finalgoal Context and not empty Rules DO Firstrule Rules := [first,rest] Rules; IF not Quiet THEN write "chaining "on Firstrule Context; ENDIF; Clauses gets fget Firstrule "IFPART "VALUE; FOR I WITH grid Clauses DO IF not Quiet THEN write "trying (phrase (I pick Clauses)); ENDIF; Failed gets not execute (I pick Clauses); IF not Quiet THEN write "result (not Failed); ENDIF; IF Failed THEN IF not Quiet THEN write "exiting_loop; ENDIF; EXIT l ENDIF; ENDFOR; IF not Quiet THEN write "premise (not Failed); ENDIF; IF not Failed THEN Actions gets fget Firstrule "THENPART "VALUE; IF not Quiet THEN write "executing; ITERATE writescreen Actions; ENDIF; ITERATE execute Actions; ENDIF; Aheadrules gets fget Firstrule "FORWARD "VALUE; IF depthfirst THEN Rules := Aheadrules link Rules; ELSE Rules gets Rules link Aheadrules; ENDIF; ENDWHILE; } # A problem is solved by setting up a suitable frame and having one of the chainers find the solution. fdefine "STUDENT [ "NAME "IF_NEEDED ['Ask "Name'], "AREA "IF_NEEDED ['Ask "Area_of_interest'] ] ; fdefine "SOLUTION [ "UNIVLIST "VALUE [] ]; # The finalgoal for forward chaining is that the University has been selected finalgoal IS OP University ( University in fget "SOLUTION "UNIVLIST "VALUE) # init_problem is used to initialize the University frames. init_problem IS { Universities gets fget "UNIVERSITY "INSTANCE "VALUE; Universities EACHLEFT fremoveslot "STATUS; fremoveslot "SOLUTION "UNIVLIST; Val := fget "STUDENT "NAME "VALUE; IF not empty Val THEN fremove "STUDENT "NAME "VALUE Val; ENDIF; Val := fget "STUDENT "AREA "VALUE; IF not empty Val THEN fremove "STUDENT "AREA "VALUE Val; ENDIF; } # all_interests is a suboperation used by Rule2. all_interests IS OP University { Profs gets fget University "INSTANCE "VALUE; Areas gets []; FOR Prof with Profs DO Areas := Areas link fget Prof "INTERESTS "VALUE; ENDFOR; cull Areas } Direction gets "backward; Depthfirst gets Truth; Chooseschool IS { ITERATE writescreen 'Welcome to the grad school advisor:' '' 'We will help you find a graduate program in computer' 'science that suits your needs.' ''; init_problem; Name := fwant_val "STUDENT "NAME; Universities := fget "UNIVERSITY "INSTANCE "VALUE; FOR Context with Universities DO IF Direction = "forward THEN forwardchain ["RULE1] Context; ELSE backwardchain "RULE3 COntext; ENDIF; ENDFOR; writescreen link 'Universities for ' (string Name) ' are:'; write post fget "SOLUTION "UNIVLIST "VALUE; } quiet gets o;