4.3 Answering Questions with Prolog
Prolog is used to perform two different, but related, tasks: describing a domain, and enquiring about it. In its simplest form the first task is done by writing the Prolog program in one or more files, which can then be read by a Prolog interpreter, while the second task may be managed using a Prolog interpreter prompt.
This section describes how one may retrieve information using Prolog, and what a Prolog interpreter does to provide the information.
4.3.1 Matching
A question to the Prolog interpreter, also known as agoal, takes on the form of a predicate, or a combination of predicates, and it may contain both atoms and variables. The Prolog interpreter will try to make a match between the goal and the predicates given in the Prolog program.
A goal and a predicate match if they are either identical of if variables within them can be instantiated so they become identical. If this can be made the interpreter either returns yes or the necessary values of any variables used in the goal that will result in a match. If no match can be found, the interpreter returnsno.
Consider a Prolog program consisting of these three facts only:
precipitation(rain).
weather(cloudy).
temperature(21).
If the goalprecipation(rain)is given to the interpreter, it will return yes, since a match can be made between the goal and the first fact in the program.
Asking precipation(P) will have the interpreter return P = rain, since in-stantiating the variableP with the valuerainwill make the match. The goal wind(breeze)will not match any of the facts in the program and the answer is no. The same answer is returned if the goal is set toweather(sunny), although a predicate named weatheris part of the program.
Multiple goals can be given at the prompt. The goals are separated by a comma, if all goals should be fulfilled, or a semi-colon if matching one of the goals is
46 The Prolog Approach
sufficient.
The Prolog program above, describing the weather, can e.g. be used to deter-mine whether one wants to ride the bike to work. Suppose the precipitation can be described using the atoms snow, rain, sleet, and fog. Now the goal precipitation(snow); precipitation(rain); precipitation(sleet)would get the answer yes if either of the sub-goals can be matched. If only the combination of sleet and snow would make the bike stay at home, the goal precipitation(snow), precipitation(sleet)should be used.
4.3.2 Working with Prolog
Several Prolog interpreters exist for working with Prolog on a standard PC. The one used in this work is B-Prolog, which offers a prompt interface for asking question about the Prolog program. For more information about B-Prolog see Appendix E.
When working with B-Prolog the clauses are given in a number of files, which are consulted by the Prolog interpreter, before it can provide information about their contents. Suppose a file describes theguidance relation using the following clauses:
guidance(sa2, command).
guidance(sa3, command).
guidance(stinger, ir).
guidance(stinger, uv).
At the Prolog prompt the goalguidance(Threat, Guidance)is given. In nat-ural language this should be interpreted as the question: ”which threats are using which guidance system?” The interpreter then produces the answer:
Threat = sa2
Guidance = command ?
The question contains two variables, Threat and Guidance, and the answer given is the first match found. The question mark at the end of the answer is the Prolog prompt. To get further matches, a semi-colon can be entered at this prompt, and the interpreter then provides the next match:
Threat = sa3
4.3 Answering Questions with Prolog 47
Guidance = command ?
When no more matches can be made the interpreter repliesnowhen a semi-colon is entered.
Asking the question guidance(stinger, Guidance), with the single variable Guidance, produces the following answers (notice the semi-colon after the first two answers):
Guidance = ir ?;
Guidance = uv ?;
no
When asking a question without using variables, or using only anonymous vari-ables, Prolog will simply answeryesorno, depending on whether or not a match can be found.
4.3.3 Search Trees
To understand how the Prolog interpreter infer the answers to give, it may be helpful to use a graphical representation of the Prolog program, or parts hereof.
The graphical representation described here shows thesearch tree, and it reflects the interpreter’s internal representation of the Prolog program.
A search tree has two types of nodes: AND nodes and OR nodes. The nodes are drawn with edges to their children, who are also AND/OR nodes. An arc is drawn across the edges connecting the AND node with its children. Parent nodes are drawn above children nodes, and the edges are not directed. Figure 4.2 shows both an AND and an OR node.
A
B C D
(a) AND node
A
B C D
(b) OR node
Figure 4.2: AND and OR nodes in a search tree.
48 The Prolog Approach
Using the AND and OR nodes a Prolog program can be drawn as a tree. While this tree does not show special constructions, such as directives or structures, it gives the possibility to interpret relations at a glance.
The Prolog predicate below is used in the Prolog-based DSSto determine the lethal distance to a threat, based on the kind of countermeasure that should be used in mitigating the threat.
lethal_dist(Threat, Dist) :-use_cm(Threat, chaff), Dist > 500,
Dist < 5000
;
use_cm(Threat, flares), ir_mode(preemptive)
;
use_cm(Threat, flares), ir_mode(reactive), Dist > 100,
Dist < 1000.
The search tree of this predicate is shown in Figure 4.3. Suppose an enquiry using the goal lethal dist(sa5, 1250) is made. A match is found at the root node, if either of its children nodes matches. The SA-5 threat is usingRF
guidance, which can be mitigated using chaff. This means that the left branch is the only one that needs to be investigated. The left child node is an AND node which will only return a match if Dist > 500(its left node) andDist <
5000(its right node). Since the distance is 1250 (second argument in the goal), both of these will be matched, and the interpreter will returnyes.
When given a goal the Prolog interpreter will traverse the search tree. Prolog distinguishes between AND nodes and OR nodes. For an AND node to return a match, all of its children must match, while for OR nodes it is sufficient if one of its children provides a match. A node with a single child node may be interpreted as either an AND node or an OR node; it will return a match if the single child node match.
4.3.3.1 Tracing
In e.g. debugging a Prolog program one would benefit from knowing what the Prolog interpreter do to find its answers. To help with this the Prolog command
4.3 Answering Questions with Prolog 49
Figure 4.3: A graphical representation of thelethal distpredicate.
traceis convenient. After this command is given, the interpreter will write all of its calls to the screen, indicating if they exit with a match or fails.
Extend the weather example from Section 4.2.2 with the following rule and facts:
% Clothes to wear
Using the tracecommand, followed by the what to wear(C) goal, results in the following trace output:
50 The Prolog Approach
Exit: (2) it_is_warm ? Call: (5) weather(sunny) ? Exit: (5) weather(sunny) ? Call: (6) precipitation(_82c) ? Fail: (6) precipitation(_82c) ? Exit: (1) weather_is_good ? Call: (7) is_clean(_72c) ? Exit: (7) is_clean(t_shirt) ? Call: (8) t_shirt\=trousers ? Exit: (8) t_shirt\=trousers ? Exit: (0) what_to_wear(t_shirt) ? C = t_shirt ? yes
The result above states, that if the weather is good, i.e. the temperature is above 15◦C, the sun is shining, and there is no precipitation, one should wear a t-shirt, provided it is clean.
The commandnotracestops the tracing of the Prolog interpreter.
4.3.3.2 Cuts
When the Prolog interpreter traverses a search tree, it may backtrack and search for another match, when a match is found or when no match is found at the bottom of the search tree. The cut operator,!, is introduced to prevent Prolog from backtracking, when a match is found. The interpretation of the cut is, that all branches to the right of the! are removed from the search tree, when it is met.
Let the is cleanfact, as introduced previously, be changed to:
is_clean(t_shirt).
is_clean(shorts) :- !.
is_clean(trousers).
The search tree for this fact can be seen in in Figure 4.4. In trying to find a match to the goalis clean(C)the interpreter will first seek a match in the left branch, successfully returningC = t shirt. If asked to look for more matches, the second branch is tried, returning C = shorts. Since the second instance of the fact contains a cut, all branches to the right of the second branch, i.e.
the branch with the trousers atom, are cut from the search tree. Asking