CS 4341 Project #2: Frames

Write a set of routines that will build and access Frame representations of knowledge. Demonstrate that you have tested the routines, and show the system working on a simple example involving inheritance, defaults, and triggering attached actions doing inference. Attached actions can activate a rule base to do the inferencing. This capability should be demonstrated.

A frame is essentially a list of attribute--value pairs, with additional characteristics. Frames are to be organized in a hierarchy. Frames can be Generic or Individual, depending on what they represent. The relationships between frames can be IS-A to indicate that an Individual frame is an instance of a Generic frame, and A-KIND-OF to indicate that a Generic frame is a subtype (subclass) of a more general Generic frame. For example,

Fido  ---IS-A---->  Dog  ---A-KIND-OF---->  Animal.

where Fido is an individual and Dog and Animal are generic.

The attribute--value pairs are referred to as Slots. These can be viewed as fields in a record. Each slot has the attribute name, a value if one is known, an optional default value, and one or two types of optional attached actions, or Demons. These will be described in more detail below.

The operations you are to implement must include the creation (FCREATE) of a new frame with its insertion into the hierarchy (The user specifies where it is to go. Having the program reason it out is a MS thesis.), the retrieval (FGET) of a value from a slot in a frame, the insertion (FPUT) of a value into a slot in a frame. Retrieval is not destructive.

You should also implement a routine that sets, using (FSETPARAMS), parameters that affect the way the defaults and actions are used. You may need a routine to find (FGETPARAMS) the current settings of the parameters in case you want to change them temporarily.

Insertion may involve more than just putting the value into the slot. If that slot, or any slot higher in the hierarchy with the same name, has an action attached that is of type IF-ADDED, then that action will be triggered, i.e., executed. Only execute the first such action that is found. This approach is similar to the most-specific-first rule selection strategy.

Consequently, IF-ADDED actions can be triggered by simple situations and can be used to make simple deductions. An action may be to start up a rule-based system with RHS actions that can include frame operations. For example, setting (FPUT)ing Surgery-Done to Yes may trigger an action to deduce what type of surgery was done and then to store that, and the fact that drugs were given recently, in a frame.

Retrieval may involve more than just obtaining the value from the slot. First of all, notice that a frame need not contain the slot being requested, but a higher frame may not only have that slot but also contain a value. For example, the fact that animals are alive only needs to be stored as a slot in the animal frame. Every subordinate frame can inherit that value.

In the case that there is no value for that attribute, an action can be triggered. If that slot, or any slot higher in the hierarchy with the same attribute name, has an action attached that is of type IF-NEEDED, then that action will be executed. Only execute the first such action that is found. The value of the FGET is the value of the IF-NEEDED action.

Another possible action that can occur when trying to retrieve a non-existent value is that a default value will be returned. If that slot, or any slot with the same name that is higher in the hierarchy, has a DEFAULT value attached, then that value is returned as the value of the FGET.

Actions can be any procedure/function. They should have access to variables that provide useful knowledge, such as, for the IF-ADDED case, the frame name, the slot name, and the value added.

It will probably be appropriate to think of both the FGET and the FPUT as recursive functions. That is, if you can't FGET it from this frame then try to FGET it from the frame above. Termination will be caused by reaching the top of the hierarchy, or by obtaining a value.

Question 1: Why must FPUT be recursive?

Use parameters to control the order in which IF-ADDED, IF-NEEDED, and DEFAULT features are tried. You should at least include the following 2 strategies {get VALUE, else DEFAULT, else IF-NEEDED, else try next frame up}, and {get VALUE, else IF-NEEDED, else DEFAULT, else try next frame up}. More difficult is doing each one all the way to the top of the hierarchy, before trying the next method.

Question 2: Does this correspond to N inheritance or Z inheritance? Implement both if possible, controlled by a parameter. Try some examples!

Notice that if the slot doesn't exist in this frame the only option one has is to look in the next frame higher.

A sample portion of a frame system is given below.

You should try to connect the frame system to the rule-based system from the previous project.

Question 3: Should IF-NEEDED demons start forward or backward chaining? IF-ADDED? Explain.

TYPE:           generic 
NAME:           thing 

TYPE:           generic 
NAME:           animal 
A-KIND-OF:      thing 
ALIVE:          yes 

TYPE:           generic 
NAME:           dog 
A-KIND-OF:      animal 
LEGS:           DEFAULT:     4 
OWNER:          IF-ADDED:    check-if-kind-to-dogs 
COAT:           IF-NEEDED:   try-to-deduce-from-breed 
NOISE:          bark 

TYPE:           individual 
NAME:           fido 
IS-A:           dog 
LEGS:           -- 
OWNER:          -- 
NOISE:          growl

Optional

Implement IF-REMOVED demons and demonstrate their use.

Questions

Several questions are scattered throughout this document -- you should answer them in a file, such as answers.txt, which should be submitted (see next).

Submitting your project

It is a good idea to place different modules into separate files. You should also resubmit your inference engine from project 1 so that it can be run from this project. The submitted files should be self-explanatory. Submit them using turnin together with examples of your system running. Use an assignment of "proj2" to turnin, as in

/cs/bin/turnin submit cs4341 proj2 *.*

Grading

This project will be graded based on:

Correctness (40%): Does the project do what was asked? Were all the questions in the problem statement answered correctly?
Documentation (25%): Is the code understandable? Is the overall approach described well?
Examples (25%): Is every feature exercised? No bugs? Lots and lots of examples?
Style (10%): Original or unusual features. Doing more than was asked, or doing it much better than is expected.

Originality

You might find potentially relevant code from various sources: previous CS 4341 students, textbooks, /cs/cs4341/, etc. While it is perfectly legal to look at the work of others, the project team must submit its own work. Simply changing variable and function names from others' work is not considered original and is likely to be detected.

Exception: For this and subsequent projects, you are allowed to use the pattern-matching code in /cs/cs4341/ai3/match.lsp, provided that you so state.

CS 4341 Home Page

CS 4341 Projects

[CS] WPI CS Home Page

[WPI] WPI Home Page