|
|
|
flex toolkit - Details
Frames and Slots
Frame hierarchies are similar to object-oriented hierarchies. They allow data to be stored in an abstract manner within a nested hierarchy with common properties automatically inherited through hierarchy. This avoids the unnecessary duplication of information, simplifies code and results in more readable and maintainable systems.
Frames are complex data structures comparable to records in databases and can consist of any number of attributes or slots (comparable to fields). Frames provide a convenient way of storing related pieces of knowledge and/or data, and are far more powerful than conventional records as they can be organised into a structured hierarchy with information inherited from frame to frame through the hierarchy.
As with database records, frames may have any number of fields. These are called attributes and are far more powerful than conventional records. This is due to the following reasons:
- they can incorporate mechanisms for dealing with default values
- they can be organised into a hierarchy, with information inherited through the hierarchy
- they can have procedures or demons attached which can monitor and respond to changes in the values of frame attribute.
Instances are used to represent represent specific instances of object frames, (whereas frames are used to represent general objects or classes). In formal terms there is very little to distinguish a frame representing a class of objects from an instance representing a specific instance of an object frame. Instances appear as leaf nodes in the frame hierarchy and can have only a single parent-frame.
frame feline; default legs are 4. frame cat is a feline; default habitat is house and default meal is kit_e_kat. instance sylvester is a cat. instance sammy is an instance of cat.
Here, by default, both sylvester and sammy will live in a house, eat kit_e_kat and have 4 legs.
Flex supports three kinds of linkage within frame hierarchies:
- single parent-child - where frames only have one parent and one child, and
- multiple children - where frames have more than one child, and
- multiple parents - where they have more than one parnet.
An example hierarchy of NHS doctors is shown below:
NHS employment
____________|_____________
| |
practitioner service officer service
________|______________________
| | |
assistant practitioner bed fund principal practitioner
frame 'NHS employment'.
frame 'officer service' is a kind of 'NHS employment'.
frame 'practitioner service' is a kind of 'NHS employment'.
frame 'assistant practitioner' is a kind of 'practitioner service'.
Another hierarchy is shown below for container where barrels have multiple parents:
container metal cylinder
________|_______ _________|________
| | | |
box drum welded cylinder extruded cylinder
|______________|
|
barrel
frame container.
frame box is a kind of container.
frame drum is a kind of container.
frame barrel is a kind of drum, 'welded cylinder'.
Attributes
Attributes are the names of the fields which make up a frame. This makes referring to fields more natural than the usual alpha-numeric references. For example, the characteristics of a barrel may be referred to using the attribute names, liquid contents and capacity. Attributes have associated slot values which are used to hold the data values of frame attributes. These can be initially defined using default values, which are then used in the absence of further information. This is often referred to as default reasoning.
frame 'oil barrel' is a kind of barrel ;
default 'liquid contents' is oil and
default capacity is 35 and
default material is 'galvanised steel'.
Example: To reflect that barrels are drums which, in turn, are containers which are normally metalic and heavy, we can write the following:
frame container ;
default purpose is storage.
frame drum is a kind of container ;
default material is metal and
default weight is heavy.
frame barrel is a kind of drum.
The default value for an attribute can be given in terms of a calculation, or, access function, which is then performed whenever the attribute is accessed.
frame 'oil barrel' is a kind of barrel ;
default height is 10 and
default area is 20 and
default volume is its height times its area.
Slot values can be any valid term, even the name of other frames. This is known as attribute-chaining and allows data to be accessed indirectly like a pointer mechanism.
A default value is overridden by a current value. Current values are acquired dynamically during a session, normally through assignment or as answers to questions.
methane_level := high
the kettle's temperature becomes 45
add X's contents to Y's contents
You can even introduce new attributes when creating a new instance of a class. This is a very powerful feature, but one which should be used sparingly, as it can complicate the readability of a program. You can also change default values dynamically which means that you can build complex modelling environments in flex, as well as standard expert systems.
Inheritance
Flex has very powerful inheritance facilities, similar to those found in OOPs. By default, flex uses single inheritance, but also supports multiple specialised and negative inheritance. With these, flex enables you to inherit different attributes from different frames to represent those 'exceptional cases' that seem to proliferate in the real world.
Multiple inheritance allows frames to inherit alternative values for an attribute through backtracking, whereas single inheritance stops on finding a value.
Specialised inheritance allows frames to overide normal single inheritance and inherit information from any arbitrary slot in any arbitary frames.
frame mammal.
frame carnivore ;
default meal is meat.
frame feline is a mammal ;
inherit meal from carnivore.
Note: the above example does not imply that felines are carnivores.
Negative inheritance allows individual attributes in frames to suppress the normal inheritance of values from parent frames higher up the hierarchy.
frame cat ;
default tail is furry.
frame manx is a cat ;
do not inherit tail.
The inheritance search algorithm will determine in what order different levels of the hierarchy are searched for inherited values. There are two available:
- depth first - which visits individual branches of the frame hierarchy to exhaustion before considering alternative branches, and
- breadth first - which visits all ancestors at a given level before moving upwards to the next level.
The inheritance strategy can also be controlled in terms of:
- the amount of effort to be used, ie. how far up the hierarchy to search, and
- whether to consider the root frame before or after any ancestor frames.
Data-driven procedures
A powerful paradigm offered by flex is that of data-driven programming. This is supported through procedural attachment, where you can attach procedures (i.e. code) to frames (i.e. data). These procedures lie dormant are then automatically invoked whenever that slot's value is updated or accessed, or a new sub-frame is created. This technique enables applications to automatically react to a change in state as found in OOPS systems.
The procedures which can be attached to slot values are:
- demons which are activated when a condition is reached,
- watchdogs which prevent access under specified conditions and
- constraints which limit the value that a slot can take.
Demons are attached to an attribute of a frame and activated whenever the value of that slot changes.
demon oil_stock_level
when the liquid_content of any barrel changes from X to Y
then compute_new_stock_level( X, Y )
and report_on_future_orders.
Watchdogs check the access rights to an attribute and are activated before access to the current value of the attribute is allowed.
watchdog account_security
when the credit_rating of account is requested
then check the user`s authority is above 7
otherwise report_illegal_access_attempt.
Constraints are attached to an attribute and restrict the value that a slot may take. If the value is invalid then the update fails.
constraint maximum_stock_level
when the stock_level of some oil changes to X
then check that X is less than any oil`s minimum
otherwise invoke_oil_stock_transfer.
The launch procedure can be attached to frames and is invoked whenever a new instance of the frame is created.
launch oil_stock_level
when Container is a new barrel
and the liquid_contents of Container is crude_oil
then the Container's seal becomes welded.
Rules
Knowledge and expertise can be expressed as if-then rules, where the if part contains the pre-conditions and the then part the action or conclusion. Rules are linked or chained together by an inference engine which matches the conditions of one rule to the conclusions of another. This engine can chain either forwards or backwards:
- forward chaining - to go from existing data and a set of rules to produce new data. This is often referred to as data-directed reasoning and indicated by the keyword rule.
- backward chaining - to prove a particular goal or hypothesis by testing for specified data. This is often referred to as goal-directed reasoning and indicated by the keyword relation.
The main thrust of the flex rule engine is forwards. In forward chaining, you start with an intial set of rules and a database of facts. You then cycle through the rulebase looking for a rule whose if conditions can be satisfied and add it to your conflict set. You then select a rule from this conflict set to fire, which involves executing its then part. This often changes the fact base, which means that different rules may now fire, so giving a different conflict set. You may also update the order of the rule agenda ready for the next cycle. You then repeat this cycle until you either produce an empty conflict set (no rules will fire), or satisfy some specified early-termination condition. Trying to ascertain if a rule's pre-conditions can be satisfied may involve some local backward chaining process, so causing the two engines to be interleaved.
Rules must have a name, condition(s) to be satisfied and concluding action(s) to peform if the rule is fired. They may also have explanations and scores. To allow rules to be as general and abstract as possible, variables may be used in rules.
rule name
if condition(s)
then action(s) ;
( because explanation ),
( score value ).
Legislation provides a good example of how complex texts can be represented in frames and rules. Reg 73 of the NHS Superannuation legislation states:
"Where a practitioner is entitled to reckon less than a year of contributi ng service otherwise than as a practitioner and where an officer with previous service as a practitioner has less than one year of employment reckonable as service otherwise than as a practitioner, such service otherwise than as a practitioner shall, except where regulation 72 applies, be treated as service as a practitioner."
Most of this can be represented in a rule as follows:
rule officer_service
if the applicant`s title is principal_practitioner
and the applicant`s reckonable_non_practitioner_service
is less than 365
and regulation_72_does_not_appy
then the applicant`s nominal_practitioner_service becomes
the applicant`s practitioner_service plus
the applicant`s non_practitioner_service.
Rulesets
The ruleset construct allows you to group rules together to form stratified rule bases and as well as control the forward-chaining engine. Within a ruleset you can specify:
- the selection algorithm to be used to determine which rule is selected when the conditions of more than one rule succeed
- the update algorithm to be used to update the rule agenda after a rule has been fired
- the termination conditions to determine how to halt the session early (rather than run-out of rules to fire)
The ruleset also supports other options, namely the ability to nominate failure and initiation procedures to be associated with that forward-chaining session. Large rule bases can be grouped into discrete rulesets and dynamically loaded into or out of the agenda. This helps debugging and maintenance, and provides for more efficient control strategies.
Selecting rules
When all the conditions of a rule are satisfied, the rule is said to be triggered and ready to fire. Rules are automatically tried according in the order in which they occur in the rule agenda. The simplest method of selecting a rule to fire is first come first served, fcfs. This method of rule selection fires the first rule it finds which has satisfiable conditions. As fcfs stops checking rules once it has found a rule that can be fired, it is a very simple but efficient method of rule selection. A more sophisticated approach is to use a conflict-resolution scoring scheme ( crss ) to decide which rule to fire.
You can attach static or dynamic 'weights' to rules using a score clause to indicate the relative importance of rules.
rule empty_master_into_slave if the master is not empty and the slave contains more than the master's spare capacity then fill the master from the slave score master's contents + slave's contents.
Having assigned these scores, you can invoke the conflict resolution scoring system, crss, to select a rule from the conflict set in one of two ways:
- select the rule with the highest score
- select the first rule to reach a threshold value
When the threshold facility is used in conjunction with the conflict resolution scoring system, the selection process stops as soon as a satisfied rule attains the threshold value.
ruleset set1 contains r1, r2, r3 ; select using conflict resolution with threshold( 7 ).
In addition, you can define your own algorithm to implement rule selection.
Agenda updates
flex provides various algorithms for updating the current rule agenda, namely:
- fixed - no change to rule agenda at all,
- front - promote rule fired to front of agenda,
- back - demote rule fired to back of agenda
- cycle - view agenda as a cyclic queue,
- possibles - remove any unsatisfied rules,
- once - only fire any rule once,
- atn - completely replace agenda with new agenda
ruleset set1 contains all rules ; update ruleset by cyclic rotation of rules.
In addition, you can nominate their own bespoke update algorithm.
You can specify some actions to be executed prior to starting a forward-chaining session.
ruleset set1 contains all rules ; initiate by doing action1 and action2.
You can also specify what should happen if the action part of the selected rule fails.
ruleset set1 contains all rules ; when a rule misfires do procedure1.
The forward chaining session will normally terminate when no more rules can be satisfied. However, you can specify early termination conditions to be used stop the session earlier:
ruleset group1 contains all rules ; terminate when condition1 and condition2.
Backward chaining rules in flex are called relations. They have a single conclusion that is true, if all the conditions can be proven. Backward chaining is often referred to as goal-driven, and is closely linked to the notion of provability. Relations are similar to Prolog clauses, and use the built-in execution engine of the Prolog run-time system which is left-to-right, depth-first with backtracking. However, they differ in that expressions are dereferenced and evaluated rather than treated as absolute literals or atoms.
relation name(Argument) if condition(s). relation 'there is some oil' if the stock of the refinery is greater than 0 and the refinery's status is open.
Unlike forward chaining rules, relations can have multiple definitions, ie. more than one way of succeeding.
Questions and Answers
Expert systems typically require a lot of interaction with the end-user. flex contains its own question and answer sub-system based on menu-driven dialog screens. The user interface facilities provided in flex allow the rapid development of sophisticated interaction with the user through:
- Questions which produce pop-up windows for menus and user input with facilities to customise answers, and
- GUI building predicates supporting user-defined forms and menus with sophisticated I/O controls.
Questions describe the manner in which information is to be extracted from the user. flex provides two built-in standard question facilities at the KSL level, namely:
- menus where the user selects off a pre-determined menu
- input where the user inputs freely from the keyboard
Menu questions can be single or multiple choce. Single choice menu questions are indicated by the words choose one of and will produce a menu and which restricts the user to making only one selection.
question current_status Please indicate your current job title ; choose one of officer, assistant, head.
Multiple choice menu questions are indicated using the phrase choose some of to generate a scrolling menu and allows the user to select as many menu items as desired.
question previous_positions What jobs have you held in the past ; choose some of trainee, assistant, head.
Questions defined with the input tag will accept user input direct from the keyboard.
question 'age of applicant' Please enter the age of the applicant ;input integer.
The integer tag indicates the type of input to accept. Other pre-defined types are: name, number and set. You can supply a user defined routine for constraining the input.
question date_of_birth What is your date of birth ? ; input X such that date_validation( X ) .
Where date_validation will be a bespoke user-defined routine to verify the input date.
Questions can be fully customised with the programmer having complete control over how the question is presented and how the answer is to be extracted. Customised questions use secondary procedures to generate and control the bespoke user-interface.
question user_details answer is K such that dialog73( K ).
Where dialog73 is a user-defined program, like a flex action or Prolog relation, which creates and manages some bespoke user interface.
The answers to questions are stored as global variables with the same name as the question.
question starter Please choose a starter for your meal ; choose one of pate, soup, melon, avocado.
Questions can be invoked through two different directives. The ask directive forces the question to be asked repeatedly, whereas the answer to directive forces a question to be asked only if it has not been already asked. Given the above statement, we can invoke the question with either of the following directives:
ask starter the answer to starter is ...
Once the question has been answered by the user, the global variable starter will contain one of the values pate, soup, melon or avocado.
Explanations
Rules and questions can have explanations attached as because clauses which are used whenever the user asks why a question is being asked or how a conclusion was reached. There are also file browsing routines so that explanations can be extracted from large pre-structured text files. There are two ways of attaching explanations or help facilities to questions and rules:
- because - provides a single line of canned text
- browse file - invokes a file browser
Simple explanations take the form of canned text. The examples below will cause the single line of text, The job title effects the pension to be displayed on the screen whenever help is requested.
question 'current status' Please select the members current job title ; choose one of officer, assistant, principal ; because The job title affects the pension. rule 'check status' if the applicant's job is officer and the applicant's age is greater than 65 then ask_for_gradingbecause The job title affects the pension.
More complex explanations can be extracted from structured help files.
question 'current status' Please select the members current job title ; choose one of officer, assistant, principal ; browse file status. rule 'check status' if the applicant's job is principal and the applicant's age is greater than 65 then check_principal_function browse file status.
Groups
A group is a means of gathering several names together under one collective heading. It has three primary uses:
- to group together rules into a single rule module
- as a type declaration with a built-in ordering of names
- as a means of collecting items for use in a question
group 'configuration rules' check1, check2, pack1, pack2. group colours black, blue, green, cyan, red, magenta, yellow, white. group 'fuzzy ordering' impossible, improbable, possible, probable, definate.
Items can be gathered together into a group and then fed into a menu styled question. This is useful for single-choice and multiple-choice questions.
question colour_choice Please select a colour ; choose one of colours.
Functions
A function is evaluated at run-time by replacing the left-hand side of the equality with the right-hand side of the equality. In addition, any conditional statements are evaluated before the replacement takes place.
function fibonacci( N ) = if N > 1 then fibonacci ( N-1 ) + fibonacci( N-2 ) else 1. function father( X ) = Y where parent( X, Y ) and male( Y ).
Commands
A command consists of a do statement which includes a series of directives and control statements.
for... from... to... do... end for while... do... end while repeat... until... end repeat if... then... else... end if
Actions
An action is a collection of directives to perform. Only one definition of each action is allowed.
action 'check configuration' ; do 'initialisation procedure' and invoke ruleset 'configuration rules' and 'confirm results'.
Extending the KSL
The Knowledge Specification Language, KSL, can be extended in two different ways:
- Synonyms allow specified text to be used in place of other text, numeric values or formulae for convenience.
- Templates mean that high-level program specifications can be written in complete English sentences and rules are written in a natural and intuitive way.
Synonyms can be used instead of frequently used terms or expressions. Rather than use explicit literal numbers in rules, we can use names which has two main advantages:
- It conveys more meaning and helps make for a more readable and understandable rulebase.
- It allows us to group together re-ocurring values under a single name and then quickly update all of them when these values change.
For instance, to keep a changing value in one location to ease updating of the system, you could state:
synonym 'current pension rate' 12500.
Synonyms can contain formulae. For instance the weight of anything can be referred to in terms of its volume and density (which are assumed as frame attributes)
synonym weight its volume times its density.
Templates allow arbitary sentences or phrases to be used without needing underscores or quotes. Templates can support negation, and include optional parameters.
A simple template has a single word (i.e. atomic) name and is followed by the phrase to be used in the flex program. For instance, to include a statement about the length of service of a member of a pension scheme in any rule or frame, we can simply write exactly what we want to say:
template service the length of service of the member.
Negations can be written with the use of templates:
template ppprincipal practitioner.
template rnps reckonable non practitioner service.
template reg72 regulation 72 applies ;
regulation 72 does not apply.
template nps nominal practitioner service.
rule officer_service
if the applicant's title is principal practitioner
and the applicant's reckonable non practitioner service
is less than 365
and regulation 72 does not apply
then the applicant's nominal practitioner service becomes
the applicant's practitioner service plus
the applicant' s non practitioner service.
The ^ symbol can be used to indicate an argument position within a template.
template before ^ is prior to ^.... and the applicant's start_date is prior to the scheme's date
Variables
There are two types of variables available in flex:
- local variables - which take a value only for the period that the definition in which they appear is being processed.
- global variables - which are in effect slot values of the frame named global and are available throughout the program - their values do not have to be passed as parameters between relations as they are accessible globally.
Local variables begin with an uppercase letter and have scope only for the statement they are defined in.
relation 'there is some' X if Container is some barrel whose 'liquid contents' is X and whose level is greater than 0.
Global variables are used to hold the answers to questions and can be used to store values which can then be referred to by any KSL statement.
frame global ; default 'price of oil' is $25.
Prolog
Prolog is a symbolic programming language based on logic. Developed in the 70s in Europe, it was adopted by the Japanese as the core language for their Fifth Generation Research Program. Prolog is a type-free programming language with dynamic data structures and transparent memory management (i.e built-in garbage collection). This frees the programmer from worrying about the implementation of data. Prolog has its own built-in inference engine and Prolog procedures (or predicates) can be viewed as backward chaining rules. This has contributed to Prolog's association with knowledge-based and expert systems.
Prolog also supports recursion and has a comprehensive set of list processing routines. Prolog uses a fast pattern matcher ( unification ) to help solve symbolic problems with automatic backtracking for searching large solution spaces. Prolog is now in widespread use in industry and the ISO Prolog standard was published in 1995. The Prolog Management Group was formed in 1993 to promote and highlight the various commercial applications of Prolog.
When using KSL to define your programs, you can easily include any calls to Prolog or flex predicates (templates would be used to allow English sentences to be used):
relation process_each_period_of_employment if every_instance( practitioner, List ) and the applicant`s superannuation_cut_off_date is Date and accumulate_income(List, '01/01/80', Date, Total).
Prolog is ideally suited for defining your own specialist routines which no shell could possibly forsee as a specialist requirement.
Interfacing to external code and data
Flex has direct access to Prolog, which in turn has support for procedures written in C, C++ and Pascal. This is platform specific, but, for instance, under Windows NT and 95, there is extensive support for DLLs and DDE. LPA Prolog also has a comprehensive set of formatted I/O routines for accessing external structured data files. There are various dedicated database interfaces, for example, again Windows NT and 95, a generic SQL-based interface that works with any ODBC-compliant commercial database. This ability to integrate rules and data is essential in fielded systems.
Development facilities
At development time there are a range of aids and support facilities provided by flex. These differ from platform to platform but generally include:
- frame-browser - to interactively browse frames and instances
- intelligent syntax analyser - to help correctly formulate KSL sentences
- frame-graph - to graphically display and interact with the frame hierarchy
Prolog has its own interactive source-level single-step symbolic debugger. This is extended to the KSL. Facts, rules and slot values can be selectively spied and monitored. Forward-chaining can be traced so that certain information is written to the current output stream at each iteration of the forward-chaining cycle. There is also a comprehensive run-time error-handler for reporting any run-time errrors at the appropriate level.and other run-time support facilities.
Run-time engine and support
Flex has been used in numerous commercial applications and the run-time system has shown itself to be reliable and efficient. These include advisory decision support systems, business modelling environments, diagnostic systems, scheduling and planning systems, legislative help system, and many more. Unlike many other development systems, there are NO built-in limits on the number of rules, relations, frames, instances, questions, etc. Technical support is available from various sources including flex vendors and consultants.
Flex as a dynamic toolkit
As mentioned in this document, most of the facilities flex provides are available programatically. This includes basic ideas like adding new fames and instances, but also extends to adding new rules, new slots, new default values, as well as to modifying exisiting ones. This means that flex is far more powerful that standard expert systems tools, and can be used to build your own modelling and meta-modelling environments.
History and availability
Flex is a mature product, and was initially developed by Logic Programming Associates Ltd (LPA) in 1988 for 640K MS-DOS PCs. This accounts for its efficient and compact run-time system. Flex is now available from LPA for Windows (NT, 95 and 3.1), Macintosh and MS-DOS machines, and has been licenced to other Prolog providers (ISL, Quintus) on Unix. This means that flex is available as a portable solution across a wide range of different hardware and operating platforms. Flex is used by TeamWare as a core technology within their ProcessWise business process re-engineering tools and has also been adopted by the Open University as basis for their course, AI for Technology. Flex has also been used by numerous commercial companies within internally deployed solutions.