http://perlhobby.googlecode.com
Writing a simple expert system in Prolog

Petrea Stefan



Definition - Expert system

An expert system is software that attempts to reproduce the performance of one or more human experts,
most commonly in a specific problem domain, and is a traditional application and/or subfield of artificial intelligence.
(This definition is the one which is found on wikipedia,the reader may consult [2] for more information)


Statement of the problem

Developing a Natural Language Processing system in Prolog. The system should be 
able to enter into a dialogue with the user about a certain domain: computing and
math courses. The system will accept input sentences from the user and
react according to the type of the sentence. When the user enters a declarative
sentence (not a question) the system understands it and adds it to its knowledge
base.
When the user enters a question (i.e. a sentence ending with ' ? ', the
system must answer.
Hence all punctuation marks are ignored except '?').
A sample dialogue: (blue represents the user, black represent a system response)

com 401 is a computing course.
I understand
com 401 is a 400 level course.
I understand
is com 401 an advanced course?
no
all 400 courses are advanced courses.
I understand
is com 401 an advanced course?
yes
does com 401 have a prerequisite?
no
com 270 is the prerequisite of com 401.
I understand
does com 401 have a prerequisite?
yes

Solution to the problem


For this implementation we will choose SWI-Prolog as the compiler(it can be downloaded here ).
So,the user will have to make some statements or ask questions.
The goal here is to get the sentence the user writes and decompose it into words.
Also,it is necessary that we write a grammar that accepts some particular types of sentences and questions
(accepting all questions and all sentences requires a very complex grammar,we don't aim that high,instead we focus on
solving the problem stated above).
It is important that the grammar will accept a sentence and afterwards find a way to represent it in a very simple form,
so that later we can use the knowledge gathered in order to answer questions(the system will answer questions by yes/no answer).

We could make use of a operator/predicate that will represent the knowledge for us by asserting at run-time
the facts indicated by it's arguments and in this way storing them in the knowledge database of Prolog
(asserting in the context of Prolog means adding facts to the knowledge base).
We will accept as arguments simple predicates with no arguments but also predicates that have arguments.
In the latter case we will concatenate the name of the predicate with it's arguments in order to form something easy to represent.
Afterwards it will dinamically add this to the knowledge base.

expression
what is added to the knowledge base
meaning
X is_a Yfact(Y(X))X is of type Y
[X,Y] is_a Z
fact(Z(X_Y))
X_Y is of type Z
X is_a [Y,Z]
fact(Y_Z(X))X is of type Y_Z


The implementation for "is_a" follows.

Who is_a What :-
%writeln('who = '),writeln(Who),
%writeln('what= '),writeln(What),
(is_list(Who) -> concat_atom(Who,'_' ,K) ; K=Who),
(is_list(What) -> concat_atom(What,'_',V) ; V=What),
Fact =.. [fact,V,K],
dynamic('fact'/2),
assertz(Fact).

When we'll ask questions,we will also need to use an operator.
Let's name this operator "is_really" and it will have 2 arguments "Who" and "What".
It will need to consult the database in order to find out if that particular fact about "Who" and "What" is true and
if not,find a way to deduce it from the available facts.
The way it will deduce it will be "If V is of type X and X is of type K then V is of type K".
When this is the case we will also store in the database "V is of type K" so we will be able to reuse it at a later time.
As with the "is_a" operator we will also concatenate the elements of Who or What together if Who or What are lists.
Who is_really What:-% this where the question is evaluated and an answer in the form YES/NO is given
writeln('who = '),writeln(Who),
writeln('what= '),writeln(What),
(is_list(Who) -> concat_atom(Who,'_' ,K) ; K=Who),
(is_list(What) -> concat_atom(What,'_',V) ; V=What),
Fact =.. [fact,K,V],
Fact1 =.. [fact,K,X], % transitivity
Fact2 =.. [fact,X,V],
write('checking -> '),write(Fact),
dynamic('fact'/2),
(
(
(
call(Fact) ;
( call(Fact1),call(Fact2),asserta(Fact) )%memoize
),
writeln('YES'),!,fail
);
writeln('NO'),!,fail
).
Usually in prolog we use operators and we also specify precedence for them,but in this case precendence won't matter as we'll
use them in separate expressions.

There will also be a DCG grammar(DCGs are internally difference lists,this can be read in more detail in [1])
which will parse the questions and the sentences.
The general form of one rule in the grammar is(this is also described in more detail in [4]):

Pred --> Pred1,Pred2,...,Predn,{...}

So Pred is one predicate that is identified and it is decomposed in Pred1...Predn and if this rule succeeds the block {...} gets executed.
The following will be the most important rules for our statements and questions:

s --> object(N,M) , [is] , [a] ,object(X,Y) , [.] ,{[N,M] is_a [X,Y]}.
s --> object(Who) , [is] , [a] ,object(X,Y) , [.] ,{Who is_a [X,Y]}.
s --> object(A,B) , [is] , det(_) , noun([Y]) , [of] , object(C,D) , [.] , { [A,B] is_a [Y,C,D] }.
s --> object(Who) , [is] , [a] ,object(What) , [.] ,{Who is_a What}.
s --> object(N,M) , [is] , [a] , level(X) , noun(Y),[.],{ [level,X] is_a [N,M] , write('last rule') }.
s --> [all] , num(X) , [courses] , [are] , adj([P]) , [courses] , [.] , { [P,course] is_a [level,X] }.

q --> [is] , object(N,M) , det(X) , adj([P]) , noun([Q]) , [?] , { [N,M] is_really [P,Q]}.
q --> [does] , object(N,M) , [have] , [a] , noun([Q]) , [?] , { [Q,N,M] is_really H }.

To ensure proper behaviour of the program we will also provide some tests below.
A predicate named start will be written in order to provide a shell for the user to write questions/statements and get
answers.
As a means for debugging you can see all the facts in the database by using
listing(fact)
(this command will list the fact predicates which are at that moment in the knowledge base).

The complete source code follows :

getUserReply(R):-
readSentence(R).

readSentence(Words) :- get0(C),
read_rest(C,Words).

read_rest(46,['.']) :- !.
read_rest(63,['?']) :- !.

read_rest(C,Words) :- ( C=32 ; C=10 ) , !,
get0(C1),
read_rest(C1,Words).

read_rest(44,[','|Words]) :- !,
get0(C1),
read_rest(C1,Words).

read_rest(C,[Word|Words]) :- lower_case(C,LC),
% we will need this because we concat_atoms and we will end up with variables unless we use lower case
read_word(LC,Chars,Next),
name(Word,Chars),
read_rest(Next,Words).

read_word(C,[],C) :- ( C=32 ; C=44 ; C=10 ;
C=46 ; C=63 ) , !.

read_word(C,[LC|Chars],Last) :- lower_case(C,LC),
get0(Next),
read_word(Next,Chars,Last).

lower_case(C,C) :- ( C < 65 ; C > 90 ) , !.
lower_case(C,LC) :- LC is C + 32.




/*
*
* default answers of the expert systems
* 1) no
* 2) yes
* 3) I understand
*
*/



:- op(100, xfx, 'is_a'). % this operator will be used to store data from the statements in the knowledge database
:- op(100, xfx, 'is_really'). % this operator will be used for evaluating the questions

Who is_a What :-
%writeln('who = '),writeln(Who),
%writeln('what= '),writeln(What),
(
(is_list(Who) -> concat_atom(Who,'_' ,K) ; K=Who),
(is_list(What) -> concat_atom(What,'_',V) ; V=Who)
),
Fact =.. [fact,V,K],
system_mode(on),
redefine_system_predicate('$fact'(_,_)),
dynamic('fact'/2),
assertz(Fact).

Who is_really What:-% this where the question is evaluated and an answer in the form YES/NO is given
writeln('who = '),writeln(Who),
writeln('what= '),writeln(What),
(
(is_list(Who) -> concat_atom(Who,'_' ,K) ; K=Who),
(is_list(What) -> concat_atom(What,'_',V) ; V=What)
),
Fact =.. [fact,K,V],

Fact1 =.. [fact,K,X], % transitivity
Fact2 =.. [fact,X,V],
write('checking -> '),write(Fact),
dynamic('fact'/2),
(
(
(
call(Fact) ;
( call(Fact1),call(Fact2),asserta(Fact) )%some memoization
),
writeln('YES'),!,fail
);
writeln('NO'),!,fail
).




s --> object(N,M) , [is] , [a] ,object(X,Y) , [.] ,{[N,M] is_a [X,Y]}.
s --> object(Who) , [is] , [a] ,object(X,Y) , [.] ,{Who is_a [X,Y]}.
s --> object(A,B) , [is] , det(_) , noun([Y]) , [of] , object(C,D) , [.] , { [A,B] is_a [Y,C,D] }.
s --> object(Who) , [is] , [a] ,object(What) , [.] ,{Who is_a What}.
s --> object(N,M) , [is] , [a] , level(X) , noun(Y),[.],{ [level,X] is_a [N,M] , write('last rule') }.
s --> [all] , num(X) , [courses] , [are] , adj([P]) , [courses] , [.] , { [P,course] is_a [level,X] }.

q --> [is] , object(N,M) , det(X) , adj([P]) , noun([Q]) , [?] , { [N,M] is_really [P,Q]}.
q --> [does] , object(N,M) , [have] , [a] , noun([Q]) , [?] , { [Q,N,M] is_really H }.

object(X,Y) --> [X] , [Y] , { adj(X) , noun(Y) }.
object(X,Y) --> [X] , [Y] , { number(Y) }.
num(X) --> [X], { number(X) }.


object(X) --> [X].

det([X]) --> [X] , { det(X) }.
noun([X]) --> [X] , { noun(X) }.
adj([X]) --> [X] , { adj(X) }.

level(X) --> [X] , [level] , { number(X) }.

adj(advanced).
adj(basic).
adj(computing).
noun(course).
noun(courses).
noun(level).
verb(is).
verb(are).
verb(have).
det(the).
det(a).
det(an).
%number % predicate to be used when in need of numeral
noun(prerequisite).
pronoun(all).



%
% to end the conversation with the expert system use "end."
%
% the system will write messages if what the user has written was a question or statement
% and it will reply nothing otherwise(error)
%


start:-
repeat,
getUserReply(X),
write(X),
(
(X =@= [ 'end','.' ] , !);
(last(X,'.'),s(X,[]),writeln('[I understand]'));
(last(X,'?'),q(X,[]))
),
fail.


%statement tests
test1:-
s([com,400,is,a,computing,course,.],[]).
test2:-
s([com,401,is,a,400,level,course,.],[]).
test3:-
s([com,270,is,the,prerequisite,of,com,401,.],[]).
test4:-
s([all,400,courses,are,advanced,courses,.],[]).


%question tests
test5:-
test1,
q([is,com,401,an,advanced,course,?],[]).

test6:-
test2,
test4,
q([is,com,401,an,advanced,course,?],[]).
test7:-
test3,
q([does,com,401,have,a,prerequisite,?],[]).








Bibliography

[1] Patrick Blackburn , Johan Bos ,Kristina Striegnitz  -
"Learn Prolog Now!"
[2] Ivan Bratko - "Prolog Programming for Artificial Intelligence" (in particular chapter 14)
[3] Cheng Hu - "Text Statistics Tool Box For Natural Language Processing"
[4] SWI-Prolog Reference Manual
[5] Regular expression engine using DCG
[6] Al Roth,  Dr. Dobb's Journal - "The Practical Application of Prolog"