Contents
- Welcome
- Domain Specific Languages - reasoning engine
- Training, Consulting, Legacy Code support, Source Code Licensing
Welcome
To read this newsletter on the Web: Read on the Web
To unsubscribe:
Unsubscribe
To subscribe: Subscribe
In this issue we wrap up the Prolog portion of the decision tree Domain Specific Language (DSL). You can download the project here: download
In the last issue we covered the use of Prolog structures and lists for representing the decision tree knowledge. The structures were used to encode the information at each of the nodes of the trees, as well as information about the basic facts whose values would be gathered by asking the user, if and when appropriate.
This issue includes the code for the reasoning engine. It illustrates how powerful Prolog's built-in pattern-matching (unification) and search (back-tracking) mechanism are for expressing the algorithms for reasoning over custom knowledge structures.
As always, we encourage institutes of learning to purchase our education site licenses to provide access to the full Amzi! Prolog + Logic Server for all students and faculty.
Domain-Specific Languages
Reasoning Engine
In the last issue we described a way to represent the nodes of a decision tree using Prolog structures and lists. A decision node for the bank example looks like:
dtree_node(fixed_income_relevance:1, [
criteria =
( fixed_income_percentage >= 90 ),
yes = fixed_income_relevance:2,
no = fixed_income_relevance:4 ]).
The 'yes' and 'no' slots refer to the nodes to follow based on whether the criteria is true or false.
A terminal node, defining the 'fact' that the decision tree is meant to determine, looks like:
dtree_node(fixed_income_relevance:3, [
terminal,
fact = fixed_income,
value = true ]).
A 'fact' whose value needs to be obtained from the user is expressed like this:
fact(fixed_income_percentage, [
prompt = english : `What percentage is fixed income?` ]).
Using these structures, it is not difficult to write a reasoning engine that we can then ask to find the values of specific 'fact's. It will be called by asking for a fact's value.
The reasoning engine is implemented using just four predicates. In top down order they are:
- ask(FACT, VALUE) - how a user asks for a value.
- climb(TREE:NODE, X) - climb a tree
- test(CRITERIA) - test the criteria at a node
- evaluate(EXPRESSION, X) - evaluate an expression in the criteria
ask(FACT, VALUE)
First, unlike Prolog's native reasoning engine, this one will remember the values of facts that have already been determined. They'll be stored in known/2 clauses. Given that, the algorithm the reasoning engine will use to find an answer to a question a user 'ask's is:
- See if the answer is known already, if so use that.
- See if there's a decision tree that can be used to determine the value, if so use that.
- Find the definition of the fact, ask the user and remember the answer.
One of the strengths of Prolog is that the code often is very close to the logical specification of the program. This is why Prolog programs are typically 1/10 the size of the corresponding logic written in a procedural language. The predicate for the above three rules has three clauses.
% it's already known
ask(Fact,Value) :-
known(Fact,X),
!,
Value = X.
% figure it out from a decision tree
ask(Fact,Value) :-
dtree_node( DTree:_, [terminal, fact = Fact, _]),
climb(DTree:1, X),
assert(known(Fact,X)),
!,
Value = X.
% ask the user
ask(Fact,Value) :-
fact( Fact, [prompt = english:P]),
prompt(P, X),
assert(known(Fact,X)),
!,
Value = X.
Note in the first clause we see if it's known, and if so cut, meaning no need to look else where, and then we see if it's the value we wanted. This is because the user might be asking for a specific value, and the 'fact' is already known, but not with that value.
The second clause uses unification to look for a dtree_node that matches the pattern of being a terminal for the desired 'fact'. It there is one, then it starts the tree climbing algorithm with the first node of that tree.
The third clause looks for 'fact' definition and simply asks the user, saves the answer and again tests it.
climb(TreeName : Node, X)
The climb algorithm is a simple recursion:
- See if the node is a terminal, in which case we have the answer and cut because we're done.
- If the node is non-terminal, get the criteria, test it and continue climbing with either the 'yes' or 'no' node next.
The code is:
climb(DTree:N, X) :-
dtree_node( DTree:N, [terminal, fact = Fact, value = X]),
!.
climb(DTree:N, X) :-
dtree_node( DTree:N, [criteria = C, yes = YES, no = NO]),
( test(C)-> climb(YES, X); climb(NO, X) ).
It is Prolog's pattern matching unification algorithm that let's us so elegantly pick up the full criteria for a node and simply bind it to the variable 'C' which is then fed to the test/1 predicate. Recursion lets the predicate elegantly keep calling itself as it moves up the tree.
test(Criteria)
If we had decided to code the criteria in pure Prolog, we could simply 'call' it and be done. But it's not difficult to implement our own language for logic that might be a bit more friendly for the end users. It supports:
- logical ands and ors;
- comparison operators;
- mathematical operators and;
- the use of fact names directly as variables.
For example, it can handle the criteria in this node:
dtree_node(fixed_income_relevance:2, [
criteria =
( convertibles_percentage =< 70 and
asset_backed_percentage + mortgage_backed_percentage =< 90 and
equity_percentage == 0 and
cash_percentage + other_percentage =< 10 ),
yes = fixed_income_relevance:3,
no = fixed_income_relevance:4 ]).
To get the Prolog reader to accept criteria written like this, we have to define 'and' and 'or' as Prolog operators at the beginning of each file that uses them. We make them the same as the existing comma and semi-colon Prolog operators:
:- op(1000, xfy, and).
:- op(1100, xfy, or).
The logic for test/1 is:
- If it's A and B, test each side. (Note that B might be a complex term with more 'and's and 'or's.)
- If it's A or B, test each side.
- If it's a comparison operator, evaluate each side and compare.
The code is:
test((A and B)) :-
!,
test(A),
test(B).
test((A or B)) :-
!,
( test(A) ; test(B) ).
test(C) :-
C =.. [CompareOp, A, B],
evaluate(A, X),
evaluate(B, Y),
Z =.. [CompareOp, X, Y],
call(Z).
Recursion, again, is what makes the code so elegant. A complex expression, such as A and B and C and D keeps getting reduced, first unifying as A and (B and C and D). Then B and (C and D). Finally C and D.
evaluate(Expression, Value)
Finally, the last predicate in the reasoning engine is evaluate. It's logic is:
- If it's a number or string the value is what the value is.
- If it's a mathematical expression, then evaluate each side and perform the operation.
- If it's a 'fact' name, then use ask/2 to get the value.
- If it's none of those, it's an error.
Here's the code:
evaluate(N, N) :-
number(N),
!.
evaluate(S, S) :-
string(S),
!.
evaluate(C, Z) :-
C =.. [MathOp, A, B],
!,
evaluate(A, X),
evaluate(B, Y),
Exp =.. [MathOp, X, Y],
Z is Exp,
!.
evaluate(A, X) :-
ask(A, X),
!.
evaluate(A, error(no_value, A)).
And that's it.
Click here to download the full Amzi! project: download You can then import it into the Amzi! IDE and start to experiment with it. Here's what it looks like under the debugger:
Note that the query, ask(fixed_income, X) is at the bottom. In the other panes are the:
- call stack with variable bindings,
- the full variable bindings for the predicate being evaluated,
- the source code where we are with color coded port, in this case 'call', and
- outline of the predicates in this file.
Stepping through the code with the debugger clearly shows the way the recursion, unification and backtracking search all work together to make Prolog an extremely powerful tool for creating custom knowledge-base applications.
You can take this code and create your own decision trees for it, or modify the code for different types of decision trees.
The same basic architecture used here can be used for pretty much any kind of knowledge. First figure out how to represent it, and then use unification and back-tracking search to reason as you like.
Happy Logic Programming,
Dennis
Training
Consulting
Legacy Code
Source Code
Amzi! offers a number of services other than just the software.
Training
We have week long beginning and advanced onsite classes that can be used to bring your staff up to speed on Prolog programming. The courses can be customized to your specific application needs.
Consulting / Contract Programming
We provide both consulting and contract programming for knowledge-based applications. While we like working with Amzi! Prolog, we're just as happy to work with any of the other excellent Prolog implementations, and we've also built knowledge-based systems in other languages as well.
Legacy Applications
For organizations with legacy Prolog code, we can provide the ongoing maintenance and support of those systems.
Source Code Licenses
For organizations desiring to have complete control over their Prolog engine, we provide full source code licensing.
Contact Us
Contact us if you have an interest in these, or any other services Amzi! might provide. |
