CSCI 222 Rule-Based System Documentation
Paul Bell
Data - structure Determiner System
Introduction
The
Data – structure Determiner System (DDS) was implemented using the CLIPS shell as
an aid for helping the software programmer decide what kind of data structure
would best suit their needs. The system
is by no means all-inclusive and can best be summarized as a horizontal slice
of possibilities. A data structure is
determined by constantly querying the user for information related to their
needs until a decision is reached. The
system was design using a tree like structure with nodes representing questions
and paths representing user responses.
Some of the information requested is basic functionality the structure
needs to provide, the amount of data to be stored, and the size of the
individual elements. In a Nutshell DDS will determine the type of structure and
if it should be statically or dynamically allocated. DDS was implemented to allow the user to instruct the program to
stop after a successful run or reset and run again.
Background
No
specific research into Expert Systems performing the same functionality as DDS
was performed. If any exists it was altogether missed. However a number of
different research tools were used for learning the CLIPS shell environment and
for generating the “expert” knowledge used in determining the appropriate
data-structure. The materials for using CLIPS include the tutorials found at www.eng.hull.ac.uk/teaching/57353/resources.htm,
the web page is maintained by Peter Robinson. Also the Appendix found in Peter
Jackson’s Introduction to Expert Systems on programming in CLIPS was also
referenced. Through the study of the tutorials in both references’ the basic
tools for programming this simple system were developed.
The
knowledge base used by the system was extracted from two the CLIPS programming
himself. The acquisition of knowledge
used by the programmer was generated from two main sources. The main source
providing the backbone and major substance of the knowledge comes from the CSCI
15a, 15b, 151 “Programming Algorithms and Data Structures” classes provided at
California State University Chico. In
cases were more specific materials were needed references were taken from
Robert L. Kruse and Alexander J. Ryba’s text Data Structures and Program
Design in C++. Considering the
horizontal nature of the project this was enough background material to
accomplish the scoop required for this assignment. However it should be noted a
more encompassing system would require a more expert understanding of data
structures and algorithms as well as specific references.
Description
The
system as mentioned earlier drills done to the appropriate structure by
querying the user for their specific needs. This can be seen as a tree type
design. The nodes of the tree represent questions and the tree’s paths or links
represent responses to these questions. Because of this design type the system
works well with a deep-first control. The questioning starts by determining the
primary functional need of the user. Three primary functions are considered as
follows: Storage of Data, Retrieval or Search of data, and Distance
Calculations. Sometimes a secondary or tertiary functionality is considered as
well. After the specific functionalities have been determined by the system it
then considers volume of data and size of data element as needed. Once the
system has narrowed down the user’s requirements it suggests which type of
structure to use such as a dynamic based queue or a matrix based graph as well
as number of other possibilities.
Initially
an attempt to provide error checking for all responses was planned on. However
it became quickly apparent this would require a lot of rule control not related
to the specific knowledge trying to be represented. Thus considering the scope
and intent of the project the idea was scraped after the first level of
questioning.
It
is also interesting to note since some of the queries the system needed to make
were the same but at different levels of branching. The system in turn was
developed so these types of rules were only written once and called when
needed. Specifically this is seen in the rules determining data volume and data
size.
One
last note on the systems description is the system will continue to run until
the user decides to quit. More specifically the user does not need to reload
the program file for each subsequent use of the system. Upon each complete analysis of a data
structure the user is prompted whether to start over or finish. If the user
wishes to continue a rule is fired which runs CLIPS reset command and clears
out all existing facts and forces the starting rules to fire.
Sample Run 1
This
sample run demonstrates two things in particular. One is the successful error
checking for the primary functionality rule. Second is the lack of error
checking on all other rules fired. The first rule is checked by having a check
primary function rule fire that evaluates the response of 1, 2, or 3. If the
response is incorrect the prime function fact is retracted and the start fact
is modified back to a yes condition.
This
was not to complex because all that was happening moving back to start. The difficulty in error checking for lower
facts, the situation in the run were “maybe” causes the program to halt, is in
trying to move back only one level cause considerable complexity. This run also
demonstrates an unsuccessful run because the program halts when an
unidentifiable response is given.
Sample Run 2
This
run demonstrates a typical successful run. The system drills down from primary
functionality criteria and continues to query the user for specific information. Based on the information provided the user
is advised to use a link-list based Stack data structure. This was determined
because the user required a retrieval of data, based on a priority of last in
first out, an unknown amount of data, and a large data unit size. Upon completion the system is prepared to
run again if so desired.
Limitations
The system’s limitation is based on two major things. One limitation is the lack of error detection. Because of the lack of error detection as demonstrated in sample one the program can simply halt anytime a user inputs data incorrectly. The more important limitation is horizontal nature of the system and the limited “expertise” of the expert. There are many more data structures available to programmers, which are not represented in this system and probably should be for a complete representation of expert knowledge in this domain.
Goodness
The
program is a bit dissatisfying as well as satisfying in regards to the
“goodness” of the system. The
dissatisfying part is the lack of error correction. The mere fact the program
can simply quit is annoying. This aside considering the limited scope of the
assignment and expertise the knowledge representation is quite satisfying. It
successfully demonstrates the extraction and representation of knowledge. It is
successful in doing this by simply being able to add new rules with little to
no concern for the control of the system.
Note that the control concerns were based on having created generic
rules for determining data quantity, data size, the one error checking rule,
and the reset for restarting.
Where to go from here…
The
direction in which the system should be developed from here is strongly based
on its current limitations.
First
a strong and well thought out error detection procedure should be developed.
The important thing to consider in such a design is not having the procedure
overly affect the control of the actual knowledge rules. With this successfully accomplished the next
step would be to continue developing rules to include more complex and specific
data structure analysis. The difficulty
here maybe some of the existing knowledge paths may need to be redesigned to
incorporate the other possible data structures. The positive thing is since
this is a depth first implementation based on a tree type representation the
separation of knowledge and control should be easily maintained.
How to run the program:
Load
the file from this location here.
Once
you have loaded the file DDS.CLP at the prompt type (reset) then (run)
EG:
CLIPS> (reset)
CLIPS> (run)