Search Top Index
HELP NEWPSYS A.Sloman Jan 1991 LIB NEWPSYS This library program makes available a forward-chaining production- system interpreter with a number of advantages over LIB * PSYS and LIB * PRODSYS, including generality, flexibility and efficiency. It is written in such a way as to be readily tailorable by users, who may wish to alter parts of the code. However, a collection of global control variables makes a wide variety of behaviours possible. Extensive use is made of the Pop-11 pattern matcher. See HELP * MATCHES. CONTENTS - (Use <ENTER> g to access required sections) -- Introduction -- Defining a condition-action rule (define :rule ....) -- Adding extra checks to the rule compiler -- psys_new_rule(<name>, <conditions>, <actions>, <type>) -- psys_delete_rule(<name>, <type>) -- psys_pr_rule(<name>, <list>) -- Rule record format -- Rule instance format -- Conditions may be simple or complex -- Types of conditions -- -- Simple conditions (patterns) -- -- OR conditions -- -- NOT conditions -- -- WHERE CONDITIONS -- -- NOT_EXISTS and IMPLIES conditions -- -- ALL conditions (for meta-rules) -- Actions -- Instantiation of actions -- "popval" list elements -- "apply" list elements -- Built-in action types -- -- [<data item>] -- -- [ADDALL [<data item>] [<data item>] ...] -- -- [SAY <message>] -- -- [EXPLAIN <message>] -- -- [STOP <message>] -- -- [NOT <pattern>] -- -- [POP11 <procedure>] -- -- [POP11 <procedure name>] -- -- [POP11 <pop11 instructions>] -- -- [PUSH <item> <word>] -- -- [POP <word>] -- -- [DEL <integer> <integer> ...] -- -- -- WARNING count only SIMPLE conditions for <integer> -- -- [REPLACE <integer> <data item>] -- -- [REPLACE <pattern> <data item>] -- -- [MODIFY <integer> <key> <value> <key> <value> ...] -- -- [MODIFY <pattern> <key> <value> <key> <value> ....] -- -- [NULL .....] -- -- [RULE TYPE <ruletype> <name> [<conditions>] [<actions>]] -- -- [RULE <name> [<conditions>] [<actions>]] -- -- SAVE and RESTORE actions -- -- [FAIL <message>] -- -- [PAUSE] -- -- [READ <question> <??constraint??> <data item> <??explanation??>] -- -- READ actions in detail -- -- READ action constraints -- -- [MENU <menu> <action list> <??explanation??>] -- -- Structure of the <menu> vector -- -- Structure of the menu [<options>] list -- -- Structure of the menu [<mappings>] list -- -- Printing out menus: psys_print_menu(message, options) -- -- The menu <action list> -- -- -- Example of a MENU action -- -- [ADDALL <data item> <data item> ...] -- User-defined action keywords and psys_action_type -- Interactive commands -- Rule manipulating procedures -- Global variables -- psys_rules (list of rules) -- psys_database -- psys_show_conditions (boolean) -- Example of psys_show_conditions trace output -- psys_chatty (boolean or integer) -- psys_repeating (boolean) -- psys_walk (boolean) -- psys_pausing (boolean) -- psys_allrules (boolean, or 1) -- psys_recency (boolean) -- psys_sortrules (false or procedure) -- psys_remember (false or list) -- psys_debugging (boolean) -- psys_get_input (boolean for asynchronous input) -- psys_backtrack (boolean) -- psys_memlim (false or integer) -- psys_max_conditions (integer) -- psys_eval(action) -- psys_eval_list(actions) -- psys_finish(rules, database) -- A format for defining psys_sortrules -- Selecting on the basis of specificity -- Sorting on the basis of the most recent condition made true -- Turning tracing of individual rules on or off -- Extended example: factorial -- Extended example TEACH * PSYSRIVER -- Extending ved_mcp to cope with new syntax -- psys_copy_modify (DANGER) -- See Also -- Introduction ------------------------------------------------------- LIB NEWPSYS defines a forward-chaining production system interpreter, called psys_run, which is invoked with two arguments, a list of rules (defined below) and an initial (possibly empty) working memory, a list of lists. Each rule is defined by a list of conditions to be tested against the contents of the working memory, and a list of actions to be performed if all the conditions are satisfied. It is possible to have different rule-sets, with different sets made "current" at different times. On each cycle of the interpreter, all rules in the current rule-set that have all their conditions satisfied are found (or, if the variable psys_allrules has the value FALSE, then only the first such rule is found), and if there are two or more such "applicable" rules a user-definable selection procedure is run to determine which rule or set of rules should have their actions executed. There are several control variables that control the search strategy, the amount of trace printing, and the interaction with the user, including a limited "explanation" facility. It is possible either to specify that all rule activations should be traced interactively, by setting the global variable psys_walk TRUE, or else to selectively trace or untrace individual rules if psys_walk is FALSE. A typical invocation of the system would first define a collection of rules (using the syntactic form described below), held in the list psys_rules, and set up an initial working memory, held in the list psys_database, and then give the command psys_run(psys_rules,psys_database) It is possible to have additional lists of rules, and some of the rules may perform actions that switch the current rule-set. The package provides a wide range of facilities for testing and debugging, and for tailoring the behaviour to different requirements, including limiting the size of the working memory, varying the strategy for selecting the most appropriate rule if several are applicable, allowing all applicable rules to run on each cycle, giving "canned" text for explanations, preventing the same rule from being used more than once if satisfied on the same data, allowing simple backtracking, and so on. There is a rich collection of built-in action types, including the powerful REPLACE action, and actions PUSH and POP for convenient manipulation of stacks in the working memory. In addition users can define their own action types, or else directly invoke Pop-11 procedures in actions. There is a simple default syntax procedure for defining rules. However, the mechanisms are easily extendable to use a different syntax or do far more checking. In order to get an overview of the mechanism it may be useful to look at the extended example in TEACH * PSYSRIVER and the factorial example below, before reading the detailed description that follows. -- Defining a condition-action rule (define :rule ....) --------------- Although it is possible to create a rule using the primitive constructor -conspsysrule- (see LIB * NEWPSYS), or the procedure -psys_new_rule-, described below, a convenient syntax is provided for defining a rule, giving it a name, and automatically adding it to the list psys_rules. A rule definition using this syntax looks like this: define :rule <name> in <ruleset> <conditions> ; <actions> enddefine; or define :rule <name> <conditions> ; <actions> enddefine; Where <conditions> is a sequence of lists, and <actions> is a sequence of lists, as described below. <ruleset> should be an identifier whose value is a list of rules. If "in <ruleset>" is missing, the <ruleset> defaults to psys_rules. Note that the separator between <conditions> and <actions> is a semi-colon in the format given above. This format allows VED's commands on current procedures to be used, e.g. <ENTER> mcp, jcp, and lcp. (See HELP * MARK). However, the syntax is flexible in that users can specify that the separator should be some other symbol. In fact any word in the user assignable list -psys_condition_terminators- is acceptable, and the default value contains ";", "-->" and "==>". So for example, the format define :rule <name> <conditions> --> <actions> enddefine; will work, though the previously mentioned VED commands will no longer automatically work on the "current" rule. (See the section below on extending ved_mcp to cope with this.) An example define :rule rule3 in diagnose [patient ?x] [temperature high]; [say ?x is very ill] [?x needs aspirin] enddefine; This will create a rule and add it to the list of rules -diagnose-, or replace a rule called "rule3" if there is one already in that list. If "in diagnose" left out, the list -psys_rules- is used instead. When a rule definition in this form is first compiled the rule is added to the end of the list (psys_rules or some other list). So rules are stored in the list in the order of their definition. However, if a rule definition is edited and re-compiled, the new version replaces the old in the same place in the list. -- Adding extra checks to the rule compiler --------------------------- There are two user-definable procedures used in reading in rule definitions. They are used to read in the list expressions defining conditions and actions, respectively: psys_readcondition() -> list; The default version is defined simply to call -listread- and return the result. psys_readaction() -> list; The default version calls -listread- and returns the result unless it starts with "POP11" in which case, if necessary, it compiles the procedure in the tail of the list. See POP11 actions below. (SHOWLIB * NEWPSYS/psys_readaction for full details) Users can redefine these to do extra syntax checking in rule definitions, e.g. if all conditions and all actions have to have certain formats. At present they do no checking, apart from requiring a list expression for each condition or each action. Because the internal structure of the lists is not checked, errors (e.g. wrong format for a "MODIFY" action) will be detected only at run time. Checking action formats can be achieved by re-defining -psys_readaction-. A possible extension of this package would be to redefine these two procedures to allow an English-like notation for expressing rules or actions. (Other languages could be used instead of English.) -- psys_new_rule(<name>, <conditions>, <actions>, <type>) ------------- Given a word, a list of conditions, a list of actions, and a word that names a ruleset, this procedure does exactly the same as the "define :rule" form, i.e. it updates an existing rule in psys_rules, or creates a new one at the end. -- psys_delete_rule(<name>, <type>) ----------------------------------- <name> should be the name of a rule that is in the list that is the value of the word <type>. If the location of a rule in the list is to be changed, the rule must first be removed from the list using psys_delete_rule. This can be done in an action of a rule, e.g. [NULL [popval psys_delete_rule(?name)]] or [NULL [apply psys_delete_rule ?name]] (See explanation of NULL actions, "popval" elements and "apply" elements, below). It would also be possible to define a new action type of the form [DELETERULE ?name] as shown below in the section on "User-defined action keywords". -- psys_pr_rule(<name>, <list>) --------------------------------------- or psys_pr_rule(<name>) The second argument, <list>, should be a list of rules. If it is not provided it defaults to psys_rules. This procedure gets the rule of that name from the list and prints it out in a format that allows it to be recompiled. -- Rule record format ------------------------------------------------- Each rule is a record of type "psysrule", with four fields, psys_rulename, psys_conditions, psys_actions and psys_ruletype. -- Rule instance format ----------------------------------------------- When a rule is found to be applicable, because all its conditions are satisfied, a rule instance, or rule activation, record is created. This is a record of type "psysactivation". The record has the following fields: psys_ruleof The rule record, an object of the type described above. psys_varsof A list of words occurring as variables in the conditions of the rule. psys_valsof A list of the values bound to the variables as a result of matching all the conditions to establish applicability. psys_foundof A list of the items in psys_database (the working memory) found to correspond to the conditions of the rule (excluding WHERE conditions psys_recof This is a vector of numbers, recording "recency" information for the rule instance. There is one number for each condition. The number is 0 if it is a WHERE condition or a NOT condition or an ALL condition. Otherwise it is a number >= 1 giving the relative "age" of the item in the database found to match the condition. The vector will be empty ({}) if psys_recency is false. (See information about psys_forevery, below.) For example, if the conditions of the rule were [Father ?x ?y] [WHERE isfemale(y)] [Mother ?y ?z] Then the psys_varsof field would contain the list [z y x], the psys_valsof field might contain [joe mary tom], the psys_foundof field [[Father tom mary] [Mother mary joe]] and the psys_recof field the vector {5 0 2} indicating that [Father tom mary] was the fifth most recent item added to the database and [Mother mary joe] the second. This information allows a variety of recency-comparing algorithms to be defined for ordering or selecting applicable rules. WARNING: if a condition of type [ALL ?<variable>] is used to extend the conditions using patterns extracted from the database, as described below, this may also extend the psys_varsof and psys_valsof lists in instances of the rule. -- Conditions may be simple or complex -------------------------------- Every rule has a (possibly empty) sequence of conditions determining when it is applicable. A condition may be simple or complex. A simple condition is just a pattern to be matched against the database, e.g. [size ?object ?x] [temperature ?t] A complex condition may have additional elements, including the key words described below, namely "NOT", "OR", "WHERE", "NOT_EXISTS", "IMPLIES", described below. A simple condition, i.e. a pattern, is a list, some of whose elements may be variable names preceded by "?" or "??", of the type used by the Pop-11 pattern matcher described in HELP * MATCHES and HELP * SYSMATCH. Patterns may contain embedded patterns, e.g. [parts ?object == [?partnum == size 5 ==] == ] which would access objects with parts, containing at least one part with attribute size 5, and will b ind the variables object and partnum if such an object exists. Restriction procedures may also be used, e.g. ?x:isinteger, as described in HELP * MATCHES. The Pop-11 syntax using "^" and "^^" to insert the value of a variable is NOT supported in LIB NEWPSYS conditions and actions, since these require too much re-creation of list structures when rules are run. Instead two facilities are provided: First: the whole sequence of conditions has to be true simultaneously with the same bindings for the same variables. Thus the following can be used to identify two people, x and z, such that x is paternal grandfather of y (as in forevery - see HELP * FOREVERY) [father ?x ?y] [father ?y ?z] I.e. it is not necessary to express the second condition as [father ^y ?z] Second: WHERE conditions, described below, can be interspersed among ordinary conditions. These allow Pop-11 expressions to be evaluated in order to control testing for applicability. For example the following conditions will be satisfied by two people, a, and b, such that b is twice as old as a. [age ?a ?x1] [age ?b ?x2] [WHERE x2 = 2 * x1] Note that in a WHERE condition, variables (e.g. x1 and x2 above) are used with whatever values they have got from previous conditions, and do not need to be prefaced with "?". However, words that are not variables need to be explicitly quoted, e.g. [man isat ?place] [?thing isat ?place] [WHERE thing /= "man"] In addition "popval" elements, explained below, allow portions of an action to be evaluated. -- Types of conditions ------------------------------------------------ Every condition is a list specifying conditions that must all be satisfied if the actions are to be executed. A <condition> takes one of the following forms: -- -- Simple conditions (patterns) [<pattern>] True if [<pattern>] matches something in psys_database, the working memory (consistently with variable bindings so far). Any unbound variables will become bound if the condition is satisfied. <pattern> may have any of the forms described in HELP MATCHES -- -- OR conditions [OR [<pattern>] [<pattern>] [<pattern>] ...] True if one of the patterns matches something in the database. For each successful match it will try to match remaining conditions in the list, until all the remaining conditions match. NB: at present "OR" can only be followed by a list of patterns to be matched against the database. I.e. OR is followed by simple conditions, and complex conditions are not allowed, e.g. conditions using "NOT" or "IMPLIES". Because OR has this restriction, an OR condition actually functions as a simple condition in relation to various comments made below about restrictions on conditions. In particular, variables bound in an OR condition will be accessible in subsequent conditions and in ACTIONS. -- -- NOT conditions [NOT <pattern>] True if [<pattern>] does NOT match anything in the working memory. Initially unbound variables in the pattern may receive spurious values as a result of partial matches. Like "OR", this can include only a simple conditions, i.e. a pattern to be matched against the database, not complex condition. (NOT_EXISTS, defined below, can have arbitrary conditions, including complex conditions.) Warning, although a NOT condition may contain variables, those variables should not be used (in the same rule) in subsequent conditions or in actions, as the values of the variables will be undefined if the NOT condition succeeds. -- -- WHERE CONDITIONS [WHERE <Pop-11 expression>] True if the Pop-11 expression evaluates to something non-false. WHERE conditions may contain some variables (indicated by "?" and "??") which have been bound in a previous pattern. E.g. a list of conditions might be something like [age ?person1 ?n1] [age ?person2 ?n2] [WHERE ?n1 > ?n2] However, the variables in a WHERE condition need not have "?", so the above could be replaced by the following, with a slight increase in efficiency. [age ?person1 ?n1] [age ?person2 ?n2] [WHERE n1 > n2] WHERE conditions do not have to come at the end of a condition sequence. E.g. the above might be followed by [cousin ?person1 ?person2] in a rule that is applicable to a pair of cousins such that the first is older than the second. Allowing WHERE conditions to occur early in a conditionlist makes it possible to avoid wasted effort finding matches that are later going to be rejected. If the Pop-11 expression in a WHERE condition causes an error, e.g. because not all the variables have appropriate kinds of values, then this is equivalent to the WHERE expression being false. (The errors are trapped. Such trapping is turned off by psys_debugging) -- -- NOT_EXISTS and IMPLIES conditions A particularly powerful type of condition allows a rule to be fired only if some generalisation is true. For example if you want a rule to fire if all known adult males are teachers you could use a condition of the following form: [NOT_EXISTS [male ?x] [adult ?x] [NOT teacher ?x]] Because this can be hard for non-logicians to interpret, the following format is also accepted for the special case of a NOT_EXISTS condition that has only one NOT condition. [IMPLIES [ [male ?x] [adult ?x] ] [NOT teacher ?x]] Note 1: Notice that "IMPLIES" is followed by only TWO components, the first being a LIST of conditions (i.e. the antecedents of the implication), and the last a single condition, the consequent. Note 2: NOT_EXISTS can have any number of conditions. If there is only one condition and that is simply a pattern, then it is equivalent to a "NOT" condition, though slightly less efficient. Unlike "NOT", "NOT_EXISTS" can be followed by any type of condition, simple or complex, whereas NOT can be used only with simple conditions. E.g. the following is legal [NOT_EXISTS [OR [<pattern1>] [<pattern2>] ...] ] whereas the corresponding "NOT" condition would not work. WARNING: although the patterns in a NOT_EXISTS or IMPLIES condition may contain variables, and these variables may be repeated in other patterns in the same complex condition, the same variables should not be used (in the same rule) outside these conditions, as their values will be undefined. -- -- ALL conditions (for meta-rules) [ALL ? <variable1>] This form of condition is provided to allow a list of patterns to be dug out of the database and then checked as if they were part of the list of conditions of the rule. Suppose, for example, that there is a goal in the database of the form [goal [BlockA ison ?block] [?block ison =]] ] Than a rule that is to check whether that goal is satisfied might have the following two conditions [goal ?goallist] [ALL ?goallist] The first condition will dig out the goal. The second will check whether it is satisfied and if so bind the list of database items to the variable instances. Both the variable ?goallist and variables that occur in it can be used in actions of the rule. An example of this mechanism is shown in TEACH * PSYSRIVER -- Actions ------------------------------------------------------------ Actions, like conditions, may be simple or complex. Complex conditions are lists which start with a known keyword (e.g. READ, SAY, MENU, DEL, MODIFY, POP11 etc -- all defined below). If there is no such initial keyword, the action is taken as a data-item, i.e. a list to be added to the working memory psys_database. Actions, like conditions, may include variables (preceded by "?" or "??") that have been bound by testing the conditions of the rule against the working memory. Any such variables will be replaced by their values before the actions are performed. (See the section on instantiation, below.) However, no such variable should be used in an action unless it also occurs in a simple condition, since it is only from a satisfied simple condition that a variable can acquire a value. Complex conditions like [NOT ...] [WHERE ....] [NOT_EXISTS ....] cannot bind variables. The exception is an OR condition or ALL condition, which can. Actions may also include "popval" elements or "apply" elements, to be evaluated before the action is performed, as described below. Complex actions corresponding to initial keywords may either be of a built-in type or a user-defined type, as explained below. -- Instantiation of actions ------------------------------------------- Before rule actions are executed they are instantiated. This means that any variables preceded by "?" or "??" that have been bound in the conditions of the rule are replaced by their values. Unbound variables and their prefixes are left uninstantiated. In addition "popval" and "apply" list elements are interpreted. The former by compiling and executing them, the latter directly. They are described below. -- "popval" list elements --------------------------------------------- Any element of an action, embedded at any depth may be a list of the form: [popval <Pop-11 expression>] i.e. a list whose first element is "popval". During instantiation the <Pop-11 expression> is first instantiated, which will replace any bound variables and evaluate any embedded "popval" or "apply" elements. After that the expression is given to the Pop-11 function -popval- to be compiled and executed. Any results produced will be spliced into the enclosing action. E.g. the following could be an action. [remember [popval ?x + ?y]] ?x and ?y should already have values. If the values were 2 and 3 respectively then this action would add the following to the working memory. [remember 5] The use of "?" is optional. So [remember [popval x + y]] Would have the same effect. Notice that the value of the expression is not put in an embedded list, unless the expression evaluates to a list. E.g. an action of the form [... [popval 10//3 ] ...] evaluates to [... 1 3 ...] not to [... [1 3] ...] -- "apply" list elements ----------------------------------------------- The popval mechanism is very general because it allows an arbitrary Pop-11 expression to be compiled and run. However, because it requires the compilation of a procedure it can be slow, and will add to garbage collection time. In some cases it is more efficient, though less readable, and less general, to use "apply". An "apply" list element is of the form [apply <procedure name> <arg1> <arg2> .... ] Variables that are to be instantiated must be preceded by either "?" or "??". The named procedure will be applied to all the arguments. So in the previous examples, instead of [remember [popval x + y]] use [remember [apply + ?x ?y]] And instead of [... [popval 10//3 ] ...] use [... [apply // 10 3]...] -- Built-in action types ---------------------------------------------- An <action> is one of the following (this list may be extended): -- -- [<data item>] [<data item>] is added to the working memory (Where <data item> does not start with any of the keywords indicated below.) -- -- [ADDALL [<data item>] [<data item>] ...] All the items are added to the database, in the order given. This means that the last one will be the most recent, which may be important if "recency" information is used for selecting rules. -- -- [SAY <message>] [<message>] is printed out. It can be a mixture of "canned" strings, variables preceded by "?" or "??", [popval...] or [apply...] elements, or embedded lists. The variables that have been bound will be replaced before printing. -- -- [EXPLAIN <message>] This is exactly like SAY actions except that if psys_explain_trace is false then it is ignored. For example this can be used to suppress verbosity during development. -- -- [STOP <message>] This is exactly like a SAY action, except that after the <message> is printed out the production system run is halted. -- -- [NOT <pattern>] All items matching <pattern> are removed from the working memory. -- -- [POP11 <procedure>] -- -- [POP11 <procedure name>] -- -- [POP11 <pop11 instructions>] In the first two cases the procedure is run. In the current implementation, if the user defines the action to be of the form [POP11 <pop11 instructions> ] then when the rule containing this is read in the instructions are compiled to a procedure and the action is just a two element list, containing the word "POP11" and the procedure. So it is possible to use this form to handle conditional actions efficienctly, instead of having separate rules for each case. An example might be: vars temp; ;;; declare any variable used globally in a POP11 action. define :rule temperature [temperature ?temp]; [POP11 psys_add( if temp == 98 then [temperature normal] elseif temp < 98 then [temperature low] else [temperature high] endif) ] enddefine; This could be expressed more clearly as three separate rules, but in some cases the loss in efficiency might be important. Note that the two procedures psys_eval(<action>) and psys_eval_list(<action list>) are available for use in the body of a POP11 action. The <actions> can be any items of the sort that can occur as actions of a rule, for example [POP11 if ... then psys_eval([DEL 2]) endif] would be equivalent to the action [DEL 2] Similarly [POP11 if .... then psys_eval_list([.....]) ....endif ] The only use for these procedures arises when the POP11 code calls the actions indirectly, e.g. inside a conditional. -- -- [PUSH <item> <word>] This assumes that there is in the database a list of the form [<word> ....] This is replaced with [<word> <item> ...] If psys_copy_modify is false, the old list-links are used, otherwise the old item is removed and a new one constructed. However, in either case the tail of the original list (represented by ....) is re-used. -- -- [POP <word>] This assumes that there is in the database a list of the form [<word> <item> ....] This is replaced with [<word> ...] I.e. the first item after the stack name (<word>) is removed. If psys_copy_modify is false, the old list-links are used, otherwise the old database item is removed and a new one constructed. However, in either case the tail of the original list (represented by ....) is re-used. NB Don't confuse POP actions and POP11 actions. -- -- [DEL <integer> <integer> ...] For each <integer> N, delete from the working memory the item that matched the N'th simple condition of the rule (i.e. excluding WHERE conditions, NOT conditions ALL conditions and other complex conditions). -- -- -- WARNING count only SIMPLE conditions for <integer> A common cause of errors is to count complex conditions in selecting the integers in DEL, REPLACE, or MODIFY actions (see belwo). -- -- [REPLACE <integer> <data item>] This is equivalent to [DEL <integer>][<data item>], but may be a little clearer to read in some contexts. Note the warning above about how to interpret the integer. -- -- [REPLACE <pattern> <data item>] This is equivalent to two actions [NOT <pattern>] [<data item>] Warning: don't use variables in <data item> that are assumed to be bound in the <pattern>. If instantiated variables are to be used, then they must be bound in the conditions of the rule. -- -- [MODIFY <integer> <key> <value> <key> <value> ...] If the integer is N, this is equivalent to a command to remove the database item that matched the N'th SIMPLE condition, and replace it with a new copy in which the item following the occurrence of <key> is replaced by an occurrence of <value>, for each <key> <value> pair in the action. For example, if the first condition of a rule is [monkey == holds ?x ==] then the action [MODIFY 1 holds bananas] would mean that whatever matched x would be replaced by the word "bananas". This is useful when it is necessary to modify part of a database item whose complete structure is not known. If the first condition of the rule is of the form [NOT ...] and the second condition is [monkey == holds ?x ==], then the [MODIFY 1 ..] action would refer not to the [NOT ...] condition, since it is a complex condition, but to the [monkey ...] condition, which is simple (a pattern). See comment on DEL actions above. WARNING: do not use two MODIFY commands with the same <integer> in the actions of the same rule. E.g. don't do: [MODIFY 2 age 20] [MODIFY 2 wife mary] The second modify action will not find the original database item to modify. Instead do [MODIFY 2 age 20 wife mary] This is more efficient in any case as it requires the modified item to be searched for in the database only once. WARNING: if one of the <key>s happens to be identical with one of the <value>s in the database item, then the item following the <value> may get replaced, causing obscure bugs. Checking for this would slow things down and require restrictions on formats used. -- -- [MODIFY <pattern> <key> <value> <key> <value> ....] As above, except that the modification is done to everything that matches the <pattern>. Warning: do not expect variables bound in the pattern to provide values for other variables in the action. See the comment on REPLACE actions. -- -- [NULL .....] If an action starts with "NULL" nothing is done, apart from instantiating it. This instantiation means that it can include variables that will be bound and [popval ...] items or [apply ...] items that will invoke Pop-11 procedures, e.g. to display the database or do some book-keeping. E.g. [NULL [popval psys_database ==>]] will simply print out the whole database. An equivalent alternative might be: [POP11 psys_database ==>] See POP11 actions below. -- -- [RULE TYPE <ruletype> <name> [<conditions>] [<actions>]] or -- -- [RULE <name> [<conditions>] [<actions>]] This creates a new rule (added to the front of the list of name <ruletype>), or a new definition of an old rule if it already exists in the list. If "TYPE <ruletype>" is not specified then it defaults to "psys_rules". WARNING: if the new rule is to include any variables preceded by "?" or "??" then make sure their names are different from any variables occurring in the rule containing the [RULE ...] action. For example the following detects any item containing an even number in the database, removes it, and creates a new rule that will abort the process if another even number turns up. define :rule check_even [== ?x:isinteger ==] [WHERE x mod 2 = 0]; [DEL 1] ;;; delete it [RULE [popval gensym("rrr")] ;;; new rule name [[== ?y:isinteger ==] [WHERE y mod 2 = 0]] ;;; conditions [[STOP Found even number ?y]]] ;;; actions enddefine; -- -- SAVE and RESTORE actions It is possible to save or restore either the working memory, or the ruleset using these actions. The formats available are as follows: [SAVE RULES <name>] Equivalent to: psys_rules -> valof(<name>) [SAVE DATA <name>] Equivalent to: psys_database -> valof(<name>) [RESTORE RULES <name>] Equivalent to: valof(<name>) -> psys_rules [RESTORE DATA <name>] Equivalent to: valof(<name>) -> psys_database These actions can be combined, as follows: [SAVE DATA <name1> RULES <name2>] [RESTORE DATA <name1> RULES <name2>] If the ruleset is changed using [RESTORE RULES ...] any remaining rules in the currently applicable list are run. -- -- [FAIL <message>] This prints out <message> (after suitable instantiation - see SAY actions above), then restores the state to just before the last rule was activated. This may enable some other rule to fire. This is a difficult mechanism to use sensibly, and works only if psys_backtrack is true - otherwise the information required for a FAIL action is not saved. It is not clear that this is a useful facility. -- -- [PAUSE] This action will pause till the user presses the RETURN key, unless the variable psys_pausing has the value false. It is equivalent to a READ action of the form: [READ '' [==] []] This means that interactive commands can be given during the pause, as explained in the section on Interactive commands below. -- -- [READ <question> <??constraint??> <data item> <??explanation??>] The <constraint> is optional and may be omitted. The <explanation> is also optional and may be omitted. The forms of the elements of READ actions are described below. When a READ action is executed, the <question> is printed out, and the user types something in which is tested against the <constraint> (if provided). <question> may be a string or list or any other object that can be printed out. <data item> should be a list. It may contain the word "ANSWER", in which case that will be replaced by whatever the user types in, and the resulting <data item> will be added to the database, unless it is the empty list. The <constraint>, if present, should take one of the forms below, and if omitted it defaults to [==], which will match anything The <explanation> should be a vector containing strings, words or lists, which, if requested, will be printed out suitably instantiated. Strings are printed without alteration. A word is replaced by its current value. A list will be evaluated using psys_value, which will replace variables of the form ?x or ??x with their values, and lists of the form [popval <expression>] as explained below. So a READ action ending with an explanation may have the form: [READ ['Does' ?patient 'feel ill, well or soso?'] ;;; question [OR ill well soso] ;;; possible answers [patient feels ANSWER] ;;; to go in database {'Because how' patient 'feels is relevant to the diagnosis'}] A more detailed account of READ actions follows. -- -- READ actions in detail The READ action of the above form does the following: (1) <question> is printed out, (2) A line is read in (using -readline-), but with an opportunity for the user to ask questions as explained in the section on interactive commands below. (3) The answer is matched against <constraint> and if it matches then (4) It is inserted in place of every occurrence of "ANSWER" in <data item> and the latter is added to the database, unless it is empty. If the match fails at (3) the process restarts from (1). An empty action as in [READ <message> []] is useful for ensuring that the program pauses and gives the user the chance to invoke the interactive commands described below. -- -- READ action constraints If the constraint in a READ action is of the form [:<word>] then that implies that only one item should be typed in, and <word> is the name of a procedure that must be applied to that item and return a non-false result. E.g. in order to insist on an integer, use the constraint [:isinteger] If the constraint is of the form [OR <item1> <item2> ...] then the user's input must be a single item identical with one of <item1> <item2> etc. If the constraint is of the form [LOR <item1> <item2> ...] then the user's input must be a list identical with one of <item1> <item2> etc. So the following two constraints are equivalent [OR a b c] [LOR [a] [b] [c]] However the second format allows [] to be one of the options, so that an empty reply is acceptable where a default can be used. If the user is to type in several items separated by spaces, and these are to be put in a list satisfying some condition, then the constraint could be of the form [?? <variable> : <word>] where <word> is the name of a procedure, which will be applied to the list and should return true or false. E.g. if the procedure -isnumberlist- has been defined so that it checks whether its argument is a list of numbers or not and returns -true- or -false-, then the constraint might be something like: [??numbers:isnumberlist] In that case the value of the variable "numbers" can be used in subsequent actions. Instead of an answer to the question the user may type "show", "why", or one of the other options specified in the section on interactive commands below. The default READ facility makes use of -readline- so all answers have to be typed on one line. (See HELP * READLINE) -- -- [MENU <menu> <action list> <??explanation??>] This is analogous to a READ action, except that it can offer users the option of a menu of answers to choose from, so that the user need simply reply by typing in a letter or number instead of having to type in the whole thing. As with READ actions, the <explanation> is also optional and may be omitted. The format for explanations is as described above for READ actions. When a MENU action is executed, the <menu> is printed out, and the user types something in which is tested to make sure it is one of the options provided in the menu. If it is, the appropriate action from the <action list> is executed. The <menu> and <action list> must have related structures as follows. The <menu> is a vector of two or three elements of the following form {[<message>] [<options>] [<mappings>]} Where the last item is optional: it is useful only in the case where the action list is of the first form indicated below. The <action list> must be either a list containing a single action (in the form of a list, possibly including the word "ANSWER") or else a list mapping options to actions, as explained below. -- -- Structure of the <menu> vector In more detail the structure of a <menu> vector is this: The first element of the vector, [<message>] is a list of words or strings that can be printed to pose a question, prior to printing out the menu of possible answers. If the words are preceded by "?" or "??" they are assumed to be variables and their values are substituted instead. Any embedded "popval" elements or "apply" elements are evaluated as described above. So a possible example would be ['How does' ?patient 'feel today?'] -- -- Structure of the menu [<options>] list The second element of the <menu vector> [<options>] is a list of lists, one list for each option. Each list starts with a letter or number, to be typed to select that option and continues with information to be printed out to describe the option. An example of the options list might be: [[1 very ill] [2 very well] [3 soso] [4 dont know]] -- -- Structure of the menu [<mappings>] list The third element of the <menu> vector, [<mappings>] is a list showing what value should be assigned to the variable ANSWER corresponding to each selection made. The list is of the form [<key> <value> <key> <value> <key> <value> ....] where the <key> may be either a single item or a list of items, but each <value> must be an ATOMIC object, i.e. a word or a number that can be tested using "==". For example the list of mappings might be: [ 1 ill 2 well [3 4] unknown] So if the user typed 1 the word "ill" would be assigned to ANSWER, if the user typed 2 the word "well" whereas if the user typed either 3 or for the word "unknown" would be used. -- -- Printing out menus: psys_print_menu(message, options) The printing of a menu is done via the user-definable procedure psys_print_menu, which is given the message list and the options list as its arguments. The user responds by typing in one of the menu options, or one of the interactive commands described below (e.g. ".why", ".data" etc.). If no acceptable response is provided the program prints the menu out again. -- -- The menu <action list> When an appropriate menu option has been selected by the user, the program performs the appropriate action chosen from the action list. The <action list> has one of the following formats [[<action>]] e.g. [[Patient needs ANSWER]] or [<key> [<action>] <key> [<action>]...] where each <key> is an item, or a list of alternative items, that the user may have typed in, or may have been derived from what the user typed in, on the basis of [<mappings>], e.g. [ ill [?patient needs treatment] [well unknown] [?patient needs tests] ] In the first format, with a list containing a single action, the <action> may, as with READ actions, include the word "ANSWER", which will then be replaced either by what the user typed in, or by the item related to what the user typed in, according to the <mappings> list, described above. Each <action> can be any action type that can occur in a rule, including a further MENU action. WARNING: If the mappings list is provided, then each <value> must be an ATOMIC object, i.e. a word or number, not a list or string or vector. Then each <key> in the <actions> list should either be one of those <values> or a list of those <values>. The following would not work as expected: Options list: [[1 very ill] [2 very well] [3 soso] [4 dont know]] Mappings list: [1 [very ill] 2 [very well] [3 4] unknown] Actions list: [ [very ill] [?patient needs treatment] [[very well] unknown] [?patient needs tests] ] If the user typed in "1" the list [very ill] would be provided as the value from the mappings list, but this would not be matched against the first item in the actions list, rather it would be compared with the word "very" and with the word "ill", and the test would fail. If the value 2 were typed in by the user, then the mappings list would produce the value [very well] and this would not be recognised as a member of the second list of keys, because "lmember" is used, for speed, and it uses the test "==" not "=". So for communication between bits of a MENU action use words or numbers, not complex objects like lists or strings or vectors. -- -- -- Example of a MENU action The following example assembles the items discussed above: [MENU { ;;;<message list> ['How does' ?patient 'feel today?'] ;;; <options list> [[1 very ill] [2 very well] [3 soso] [4 dont know]] ;;; <mappings list> [ 1 ill 2 well [3 4] unknown] } ;;; action list allowing keys "ill" "well" "unknown" [ ;;; single key ill [?patient needs treatment] ;;; two possible keys associated with the same action [well unknown] [?patient needs tests] ] ;;; explanation {'Because how' patient 'feels is relevant to the diagnosis'}] An equivalent MENU action, not using a <mappings lsit> would be: [MENU { ['How does' ?patient 'feel today?'] [[1 very ill] [2 very well] [3 soso] [4 dont know]] ;;; no <mappings list> } ;;; action list using the numbers directly as keys [ 1 [?patient needs treatment] [2 3 4] [?patient needs tests] ] {'Because how' patient 'feels is relevant to the diagnosis'}] Yet another equivalent would be [MENU { ['How does' ?patient 'feel today?'] [[1 very ill] [2 very well] [3 soso] [4 dont know]] [1 treatment [2 3 4] tests] } ;;; Single action format, using "ANSWER" [ [?patient needs ANSWER] ] {'Because how' patient 'feels is relevant to the diagnosis'}] As the last two examples show, there is usually no point having a <mappings> list in the menu vector unless it is required to associate the user's choice with a value for ANSWER to be inserted in some data base item. -- -- [ADDALL <data item> <data item> ...] If the keyword is "ADDALL" the rest of the action should be a list of lists, which will all be added to the database, in that order. (I.e. the last item will be the newest item for subsequent rules.) -- User-defined action keywords and psys_action_type ------------------ Users can define new complex action types associated with new keywords. To define a new action keyword "REPORT" do something like this: define doREPORT(rule_instance, action); .... enddefine; "doREPORT" -> psys_action_type("REPORT"); Then any action starting with the word REPORT will invoke this procedure, by applying it to the current rule_instance (i.e. the current activation of the rule containing the action that starts with the keyword) and the instantiated action from the rule's action list. Storing the name, rather than the procedure, in the property psys_action_type allows the procedure to be redefined, or traced, during program development, without the need to replace the old version in the property. The test for whether an action is user-defined is done before recognising built-in types. This makes it possible for a user-defined type to over-ride the built in action type. I.e. after instantiating the action, as described above, the program first looks to see whether the initial word of the action has been associated with a procedure using the user-assignable property psys_action_type, in which case the procedure is run with the current rule and the current action as arguments. Otherwise, it checks to see whether the action is one of the built-in forms listed below. -- Interactive commands ----------------------------------------------- During execution of READ actions and at interaction pauses resulting from -psys_walk- being true or a rule being traced (as described below), the user has the option of typing in any of the following interactive commands, all of which start with a dot or colon to indicate that what is typed in is not an answer to a question. (The full effects of these commands cannot be understood without reading later sections of this file describing the effects of variables like psys_show_conditions, psys_chatty, etc. .show This causes information about the current rule and the current action from that rule to be printed out. The printing is done by the user-definable procedure psys_displayrule(action, rule_instance) which is given the current (instantiated) action, and the current rule instance from which it comes. (The form of a rule instance is defined above.) .why This causes an explanation of the current action to be printed out, if provided (i.e. in a READ action, as explained above). If "why" is typed again, repeatedly, then information about previously activated rules is printed out, until there are no more rules. This "repeated why" option works only if the user has made the global variable psys_remember a list initially (e.g. []), rather than false. Otherwise the information about previous interactions will not be stored for interrogation in this way. For the current READ action "why" will cause a user-provided explanation string to be printed out, if it is given in the fourth element of the READ action. Otherwise psys_displayrule is used to print out the action and the context, in answer to "why". .data This causes information in the working memory, psys_database, to be printed out. .data <pattern> This causes all the data that match the pattern to be printed out. .trace <rule names> Causes tracing to be switched on for the named rules, like psys_trace, described below. .untrace <rule names> Causes tracing to be switched off for the named rules, like psys_untrace, described below. .untrace all Causes tracing to be switched off for all rules, and psys_walk made false. .show_conditions .show_conditions true Causes psys_show_conditions to be made true, so that testing of rule conditions is shown in detail. .show_conditions false Turns the above off .chatty .chatty true Either of these makes psys_chatty true .chatty false This makes psys_chatty false .chatty <integer> This assigns the integer to psys_chatty .walk This makes psys_walk true .walk false This makes psys_walk false :<Pop-11 expression> If the user types a colon followed by a Pop-11 expression, then the Pop-11 expression is executed and if there is any result it is printed out. This may be useful during debugging. ? (or any unrecognised command) This causes a help message to be printed out, listing the commands available. -- Rule manipulating procedures --------------------------------------- Each rule is represented by a three element structure: the name, which is a word, the conditions, a list of lists, and the actions, another list of lists. A rule is created by psys_consrule(<name>,<list of conditions>,<list of actions>) The following three procedures each takes a rule and returns the appropriate item. The last two have updaters. psys_rulename psys_conditions psys_actions All three components are returned by psys_destrule(rule) -> actions -> conditions -> name; The syntactic form define :rule <name> <conditions>; <actions> enddefine; reads the <name>, the <conditions> and the <actions> checking that the latter are all lists, and puts the new rule at the end of the list psys_rules (see below). If there is already a rule with this name then its conditions and actions are replaced by the new ones. Thus this syntax makes it easy to edit and recompile a rule (unlike the library package LIB PRODSYS). If there is already a rule with the <name> then this replaces its conditions and actions. If there isn't a new rule is appended to psys_rules. -- Global variables -------------------------------------------------- There are several global variables that users may find useful, along with procedures for manipulating them. -- psys_rules (list of rules) ----------------------------------------- This is a list of rules to which new rules are appended by the define :rule .... enddefine syntax, as described above. It is possible in principle to manipulate several lists of rules, by temporarily saving and restoring the value of psys_rules. The procedure psys_rule_named(<word>, <list>) -> <rule> psys_rule_named(<word>) -> <rule> Searches down the given <list> for the rule with the name. If not provided, <list> defaults to psys_rules. A list of the form of psys_rules is required as first argument to psys_run. -- psys_database ------------------------------------------------------ This is used as the working memory when rules are running. It is the second argument of psys_run, and is accessed by a collection of procedures partly analogous to the Pop-11 database procedures described in HELP * DATABASE. psys_add(item); Adds item to psys_database psys_present(pattern); Returns false or the first item in psys_database matching pattern psys_flush(pattern); Removes everything in psys_database that matches the pattern. If psys_copy_modify is false then the removal is non-constructive, i.e. database list links are re-used (to save garbage collections). psys_forevery(patternlist, proc); "proc" is a procedure that takes two arguments, a vector and a number, used for getting "recency" information about the items satisfying the conditions of an action. The vector is a vector of integers giving the locations of items in the database that satisfied conditions in the rule. The number says how many such numbers are recorded in the vector. E.g. if the vector is { 3 1 9 2 ....} and the number is 4, then that says that the first condition matched the third most recent item in the database, the second condition matched the most recent item, the third one matched the 9th most recent and the fourth one matched the second most recent. Note that WHERE, NOT and ALL conditions get the number 0. (See the information about psys_recof, above.) For every possible way of matching the patterns in paternlist psys_forevery runs the procedure proc with the pattern variables set. This is used to find all possible ways of instantiating the conditions of each rule, in order to build a list of possible applicable rules, to be sorted by psys_sortrules. psys_allpresent(patternlist) -> false or found_list This is defined as follows define psys_allpresent(patternlist) -> found; lvars patternlist, found; define lconstant procedure report_success( vec, num ); ;;; return the items found. lvars vec, num; ncrev(psys_found); exitfrom(psys_allpresent) enddefine; psys_forevery(patternlist, report_success); false -> found; enddefine; -- psys_show_conditions (boolean) ------------------------------------- If -psys_show_conditions- is true then whenever a rule is about to be tested, its name and all its conditions are printed out, then as each condition in turn is checked the result is printed. The printout can be a little confusing because newpsys will try all possible ways of matching conditions to the database. Indentation indicated by vertical bars is used to show the dependencies. If the conditions are C1, C2, C3, then information about whether C1 is satisfied is prefixed with "|". After C1 has been satisfied, information about C2 is printed out preceded by "||". If C2 is satisfied, then each information about satisfaction or non-satisfaction of C3 is prefixed with "|||". After that, any further reports on tests for a different way of satisfying C2 will be prefixed with "||". When all those have been exhaused, additional ways of satisfying C1 will be tested, and results prefixed with "|". If any are successful then new attempts will be made on C2, prefixed with "||", and so on. For every combination of conditions that is satisfied, the variables in the conditions will be printed out with the values assigned to them by the matcher in satisfying the conditions. (See example below.) Further trace information is controlled by psys_chatty and psys_walk. -- Example of psys_show_conditions trace output ----------------------- The file TEACH PSYSRIVER describes a newpsys program that makes a plan for getting man, fox, chicken and grain across a river. One of the rules is called "complete_move" in the rule_set called "solve_rules". It has two conditions to be satisfied: [complete_move ?move] and [state ?state] If psys_show_conditions is set true the following illustrates the printout when this rule is tested for applicability: ----------------------------------------------------------------------- ** [Checking conditions for: complete_move in solve_rules] ;;;rule ** [[complete_move ? move] [state ? state]] ;;;conditions |** [SUCCESS [complete_move [move chicken]]] ||** [SUCCESS [state [[chicken isat right] [fox isat left] [grain isat right] [man isat right]]]] |||** CONDITIONS SATISFIED: Variables bound: |||** state = [[chicken isat right] [fox isat left] [grain isat right] [man isat right]] ; move = [move chicken] ; ----------------------------------------------------------------------- In this case no other ways of satisfying the conditions will be attempted because psys_allrules is set -false- and the first applicable rule instance is therefore selected. A more complex example showing the attempt to find different ways of satisfying the conditions follows. The rule being tested is "move_thing" in the rule_set "solve_rules". It has seven conditions, one of them an OR condition, whose first disjunct fails, while its second succeeds in one case. The program tries to find something at the same side of the river as the man (in this case the right side). The first candidate is the man, but this falses the thing /= "man" test to fail. The second candidate is the grain, and that fails because the last move in the history list was moving the grain, so it eventually tries the third candidate, the chicken, and the rule is shown to be applicable, with "thing" bound to "chicken", etc. ----------------------------------------------------------------------- ** [Checking conditions for: move_thing in solve_rules] ** [[man isat ? place] [? thing isat ? place] [WHERE thing /== " man "] [OR [opposite ? place ? other] [opposite ? other ? place]] [state ? state] [NOT tried [move ? thing] ? state] [NOT history [[move ? thing] =] ==]] |** [SUCCESS [man isat right]] ||** [SUCCESS [man isat right]] ;;; trying thing = "man" |||** [Tested WHERE [thing /== " man "]] |||** [Result is: <false>] ||** [SUCCESS [grain isat right]] |||** [Tested WHERE [thing /== " man "]] |||** [Result is: <true>] ||||** [SUCCESS [opposite right left]] |||||** [SUCCESS [state [[chicken isat right] [fox isat left] [grain isat right] [man isat right]]]] ||||||** [SUCCESS [NOT tried [move grain] [[chicken isat right] [fox isat left] [grain isat right] [man isat right]]]] |||||||** [FAILED [NOT history [[move grain] =] ==]] |||||** [FAILED [state ? state]] ||||** [FAILED [opposite ? place ? other]] ||||** [FAILED [opposite ? other ? place]] ||||** [FAILED [OR [opposite ? place ? other] [opposite ? other ? place]]] ||** [SUCCESS [chicken isat right]] ;;; trying thing = "chicken" |||** [Tested WHERE [thing /== " man "]] |||** [Result is: <true>] ||||** [SUCCESS [opposite right left]] |||||** [SUCCESS [state [[chicken isat right] [fox isat left] [grain isat right] [man isat right]]]] ||||||** [SUCCESS [NOT tried [move chicken] [[chicken isat right] [fox isat left] [grain isat right] [man isat right]]]] |||||||** [SUCCESS [NOT history [[move chicken] =] ==]] ||||||||** CONDITIONS SATISFIED: Variables bound: ||||||||** state = [[chicken isat right] [fox isat left] [grain isat right] [man isat right]] ; other = left ; thing = chicken ; place = right ; As this example illustrates, making -psys_show_conditions- true can produce an enormous amount of printout. But this is sometimes essential for debugging. -- psys_chatty (boolean or integer) ----------------------------------- The variable psys_chatty controls trace printing while rules are running, as follows, depending on whether its value is false, true, or an integer. if false, there is no trace printing (though rules can print things out using SAY actions). if true, causes minimal useful information to be printed out during running if the value is divisible by 2 then the list of rule-instances already activated is printed out on every cycle, if psys_repeating is false and the list is to be remembered. if the value is divisible by 3 then all WHERE and ALL tests are printed out if the value is divisible by 5 then the database is printed out on every cycle if the value is divisible by 7 then checks on applicability conditions for rules are printed out. (Compare psys_show_conditions) if the value is divisible by 11 then the list of applicable rules found is printed on every cycle if the value is divisible by 13 then information is printed out concerning items added to or removed from the psys_database, and truncation of the database is announced whenever its length exceeds psys_memlim if the value is divisible by 17 and psys_walk is false then every rule that is activated is printed out, without an interactive pause. Default value of psys_chatty is false. For example, to make checks on applicability conditions printed out, and every rule that is activated printed out do 7 * 17 -> psys_chatty; The value of psys_chatty can be altered interactively as explained above. -- psys_repeating (boolean) ------------------------------------------- Default is true. If this is set false the system will not trigger the same rule on the same psys_database items twice. Use of this option requires all rules that are fired to be remembered in association with the database items that triggered them. The actual database items are remembered for comparison with future items that make the condition in the rule true. This means that if rule R1 runs once with database item [r a b] making its condition true, then it may run again later if a new item [r a b] is added to the database. Setting psys_repeating false adds to the memory load of the program as well as requiring additional tests. See also the WARNING in connection with psys_copy_modify. In some cases, careful ordering of rules can make it unnecessary for psys_repeating to be made false. -- psys_walk (boolean) ------------------------------------------------ If this is set true then the system pauses before doing each action of a rule that has been selected, and invites questions, using the procedure psys_interact, which allows questions to be asked. In particular ".show" displays the current rule and the action from that rule. See additional information about Interactive commands above. The default value for psys_walk is false. In order to distinguish pauses due to psys_walk being true from the pauses when real questions are being asked, a different prompt is used, namely: Walking> -- psys_pausing (boolean) --------------------------------------------- If this is not false then PAUSE actions will work. If it is false they are ignored. -- psys_allrules (boolean, or 1) -------------------------------------- If true, run all the rules whose conditions are true, not just the first rule found. More generally, if the list of conditions of a rule can be satisfied in more than one way (e.g. the pair [father ?a ?b][mother ?b ?c] may have several instances), then all the instantiations of the rule will be found by psys_applicable on each cycle. These will be put into a list along with all applicable instantiations of other rules. The procedure psys_sortrules can be defined to sort such a list of applicable rules, as explained below. Trace -psys_applicable- to see which applicable rule instances are found on each cycle. If the value of psys_allrules is the integer 1, only one rule will be run on each cycle. Nevertheless, all applicable rules will still be given to psys_sortrules, and the first instance, after sorting, will be run. This is useful for debugging - in order to show all the applicable rules. Alternatively psys_allrules can be made true, and psys_sortrules can be made to return a list of only one rule. The default for psys_allrules is false. This means that only the first applicable rule that is found will be executed on each cycle. If the rule has more than one applicable instance (i.e. more than one way of matching the conditions against items in working memory), it is not defined which one will be selected. -- psys_recency (boolean) --------------------------------------------- If this is made true, then items in the list of possible rule activations given to psys_sortrules have an extra field representing the recency of addition to the database of all items matching conditions. Thus if the conditions C1, C2 and C3 match the fourth the first and the seventh items in psys_database, then the recency representation will be a vector of three numbers {4 1 7} If the condition is of type NOT or WHERE, no particular database item makes it trule, so the corresponding number in the vector of numbers will be 0. -- psys_sortrules (false or procedure) -------------------------------- The default for this is false. If non-false, it is assumed to be a user-defined procedure that sorts rules that are applicable. This makes sense only if psys_allrules is non-false. psys_sortrules is given a list of possible rule activations and returns a list of possible rule activations. A possible rule activation is represented as a vector consisting of four or five elements. If psys_recency is false there are only four elements in each rule, namely: - a rule whose conditions are satisfied - a list of variables bound when the conditions were satisfied, - a list of the corresponding values of the variables. - a list of the database items matching the conditions If psys_recency is true then there is an extra element, a vector of the type described above in connection with psys_recency. Example definitions of psys_sortrules, corresponding to different search strategies are given below. -- psys_remember (false or list) ---------------------------------------- If this is non-false, then in psys_run it is given a list as value, and then all activated rule-instances are added to the front of the list, in the form of a rule_instance record of the type described under psys_sortrules. The Default is false. psys_remember is used in connection with requests for explanations. (A very primitive explanation facility). It is also used if psys_repeating is false. -- psys_debugging (boolean) ------------------------------------------- If true, extra information is printed out, and Pop-11 error messages that are caused in WHERE conditions are not suppressed. Default is false. -- psys_get_input (boolean for asynchronous input) -------------------- If psys_get_input is true, then if user types anything during execution the whole line (terminated by RETURN) is read in as a list using readline() and added to the working memory. Then if appropriate it may trigger a rule on the next cycle. The test for whether there is any input waiting to be read in is carried out after each rule is activated. For example, suppose the variable is true, and the user types a line consisting of the character "d", followed by a space, followed by additional words etc, then if there is a rule of the form below it will be activated before the next rule, if selected by psys_sortrules: define :rule process_input [d ??rest]; ;;; delete the item [DEL 1] [SAY message ??rest received] [READ 'OK?' []] enddefine; This will then pause on the READ action, allowing the user to interrogate the database, etc. -- psys_backtrack (boolean) ------------------------------------------- If true this enables backtracking to be done using the [FAIL..] action, as described above. It defaults to false. -- psys_memlim (false or integer) ------------------------------------- If made an integer > 0 then every time anything is added to psys_database its size is truncated to the length of psys_memlim by psys_add. -- psys_max_conditions (integer) -------------------------------------- This integer defaults to 30 and represents the maximum number of conditions that a rule can have. It is used only if psys_recency is true. If it is changed lib newpsys will have to be re-compiled. However, it can be set before lib newpsys is compiled. -- psys_eval(action) -------------------------------------------------- -- psys_eval_list(actions) -------------------------------------------- These two procedures are explained above in connection with the [POP11 ...] action type. -- psys_finish(rules, database) --------------------------------------- The user-definable procedure psys_finish is invoked by psys_run on completion. It is given the current values of psys_rules and psys_data as arguments. So it can be used to print out the final value of the working memory, or perhaps store it in a file, etc. Usually psys_rules will be no different from the original list given to psys_run, but in principle it is possible for programs to modify it, so the final value is also made available to psys_finish. -- A format for defining psys_sortrules ------------------------------- Different search (conflict resolution) strategies can be defined for selecting between applicable rules by making psys_allrules true or 1, and defining the procedure psys_sortrules appropriately. If one of the criteria for ordering possible rules is the recency with which their conditions have become true, then psys_recency should be true in order that the recency information be recorded in the list of possible rules. All possible search strategies can be defined using a procedure psys_sortrules, of the following form, where psys_better is defined according to the preference strategy, as indicated below. define psys_sortrules(possibles) -> possibles; ;;; possibles is a list of applicable rule instances syssort(possibles, psys_better) -> possibles; if psys_allrules == 1 then ;;; truncate possibles list to length 1 [] -> back(possibles) endif enddefine; The procedure psys_better will be applied to two rule instances at a time, and can use the following procedures to access their components: psys_ruleof psys_varsof psys_valsof psys_foundof psys_recof; -- Selecting on the basis of specificity ------------------------------ This is one way to define psys_better so that it gives priority to rules with most conditions satisfied, would be to assign the following to it. define psys_more_specific(instance1, instance2); lvars instance1, instance2; listlength(psys_conditions(psys_ruleof(instance1))) >= listlength(psys_conditions(psys_ruleof(instance2))) enddefine; If the two rules have the same number of conditions, then the first rule found will come first. -- Sorting on the basis of the most recent condition made true -------- In order to ensure that recency information is recorded in the possibilities list do true -> psys_recency; Then define the sort procedure something like this define psys_youngest(instance) -> num; ;;; Given a rule instance find the "age" of the most recently ;;; added item making one of its conditions true. lvars n, instance, num=9999999; for n in_vector psys_recof(instance) do unless n == 0 then min(num, n) -> num endunless endfor enddefine; define psys_more_recent(instance1, instance2); ;;; given two rule instances return true if the first has the ;;; most recent enabling condition lvars instance1, instance2; psys_youngest(instance1) <= psys_youngest(instance2) enddefine; A more complex rule could compare the two recency vectors until there is a difference, and if there isn't one then use specificity, for instance define psys_more_recent(instance1, instance2) -> boolean; ;;; given two rule instances return true if the first has the ;;; most recent enabling condition lvars instance1, instance2, vec1, vec2, num1, num2, boolean; define ages_list(vec) -> list; ;;; produce a sorted list of the non-zero numbers in vec lvars vec, list; [%appdata(vec, procedure (num); lvars num; unless num == 0 then num endunless endprocedure)%] -> list; sort(list) -> list enddefine; for num1, num2 in ages_list(vec1), ages_list(vec2) do if num1 > num2 then false -> boolean; return() elseif num2 < num2 then true -> boolean; return() endif endfor; ;;; No difference in ages list, so compare specificity psys_more_specific(instance1, instance2) -> boolean enddefine; Naturally there is no uniquely best strategy: it is up to the user to define one. -- Turning tracing of individual rules on or off ---------------------- If psys_walk is true, all rules will be traced. However, if it is false, information about individual selected rules can be provided, including interactive pauses before each action, by using the following facilities. psys_trace(<list of rule names>) Specifies that those rules should be traced. What this means is that the program will print out a message stating when the rule is being checked for applicability, and will indicate if its conditions are not satisfied. If they are satisfied and the rule is selected to be run, then during execution it will pause before each action, allowing the kind of interactive interrogation described above in the section on user interaction. psys_untrace(<list of rule names>) This undoes the effect of psys_trace. However individual rules will still be stepped through if psys_walk is set true. psys_untrace("all") Unsets tracing on all rules. -- Extended example: factorial ---------------------------------------- This example computes the factorial of a number typed in by the user. It is fairly fast, but can generate a lot of garbage if given a large number (e.g. 1000), so it is best to set popmemlim and popminmemlim as high as possible. (See HELP *POPMEMLIM) The following code can be marked and executed: uses newpsys; ;;; First clear list of rules [] -> psys_rules; ;;; The first rule detects the termination condition - when the counter ;;; value in the database is set to the number whose factorial is to be ;;; computed, represented as [fact ?x] define :rule f1 [fact ?x] [counter ?x] [total ?y]; [STOP the answer is ?y] enddefine; ;;; Rule f2 increments the counter and does the multiplication define :rule f2 [counter ?x] [total ?y] ; [MODIFY 1 counter [popval x + 1]] [MODIFY 2 total [popval y * x]] enddefine; ;;; Rule f3 starts the process by asking the user for the number ;;; whose factorial is to be found, and stores it as [fact ANSWER]. define :rule f3; ;;; This must be last rule if psys_repeating is true ;;; Start things off by getting the input to factorial [READ 'What number is the input?' [:isinteger] [fact [popval ANSWER + 1]] ;;; next bit printed out in response to "why" {'I need a number to compute factorial'}] ;;; Initialise the database [total 1][counter 1] enddefine; true-> psys_repeating; ;;; OK because rule f3 is last. true -> psys_walk; ;;; Make it false for a quicker answer! false-> psys_backtrack; ;;; Saves unnecessary storage. ;;; (Prevents use of FAIL actions) false -> psys_allrules; ;;; Prevent repeated firing of f3 if any ;;; other rule is applicable. false-> psys_chatty; ;;; Make it true for more tracing false -> psys_remember; ;;; Saves storage, but prevents "why" questions ;;; going back to earlier rule activations. false-> psys_copy_modify; ;;; Maximise efficiency. Can be risky psys_run(psys_rules, []); ;;; End of example NOTE By replacing the two separate database items [counter ?x] [total ?y] with a single item [counter ?x total ?y] it is possible to speed this program up significantly. Rule f2 would need to be altered to use a single [MODIFY ....] action instead of two actions. -- Extended example TEACH * PSYSRIVER --------------------------------- This teach file defines a production system that can solve the river-crossing problem described in TEACH * RIVER. It includes a complete solution that can be run once LIB NEWPSYS has been compiled. -- Extending ved_mcp to cope with new syntax -------------------------- As explained above, if rule definitions use something other than ";" to separate conditions from actions, the built in VED utilities for operating on the current definition will not work. This can be fixed as follows. If all occurrences of "define" and "enddefine" defining rules and top-level procedures start at the beginning of a line, then the following will re-define the procedures for finding and marking the beginnings and ends of definitions: define ved_mbp; ;;; mark beginning of definition vedcharright(); ;;; take cursor past the beginning of line veddo('\\@adefine '); ;;; search back for beginning vedmarklo(); ;;; mark it enddefine; define ved_mep; ;;; Mark end of definition if vedcolumn == 1 then vedcharleft() endif; veddo('/@aenddefine'); vedmarkhi(); enddefine; After that, rule definitions like the following can be compiled using ved_lcp, or <ESC>-c in VED, as long as "-->" is in the list psys_condition_terminators and the initial and final lines are not indented. define :rule test_rule [condition 1] [condition 2] --> [action 1] [action 2] enddefine; -- psys_copy_modify (DANGER) ------------------------------------------ This defaults to true. If it is set false, then changes to the database are made without copying. I.e. the list-links in the database are re-used, reducing the frequency of garbage collections. This applies in particular to psys_flush and to MODIFY, REPLACE and DEL actions. WARNINGS: (a) if this variable is set false then it is possible for data saved by one rule to be corrupted by the action of another. (b) this variable cannot be set false if psys_repeating is set false, since the latter requires databse items to be remembered. The program attempts to minimise potential damage caused by making this variable false. In particular, if a rule adds something constant to the database then if psys_copy_modify is false, then a copy of the constant list is added, since otherwise later modification of the list could alter the rule itself! -- See Also ----------------------------------------------------------- Further features are described in comments in the program library file. To examine it SHOWLIB * NEWPSYS TEACH * PSYSRIVER - described above. TEACH * PSYS - a very primitive production system interpreter TEACH * PRODSYS - a more complex one, though not as flexible is LIB NEWPSYS, and much slower. TEACH * EXPERTS - an introduction to expert systems and expert system shells --- C.all/help/newpsys --- Copyright University of Sussex 1991. All rights reserved. ----------