Lecture
Mechanism clipping and recoil (mechanism of Cuting and Backtracking) ProLog . Differences between ProLog and algorithmic programming languages.
Ability to produce multiple solutions
The distinctive ability of ProLog is that when searching for solutions on the ProLog a whole list of suitable values is given. Therefore, in the ProLog, one predicate can be represented by a whole set of rules, each of which can produce an answer. Example. Let there be the following description of the predicate “number_more”:
number_more (A, 3): - A <3.
number_more (A, 5): - A <5.
number_more (A, 8): - A <8.
Then call the ProLog solver
Goal number_more (4, More).
Will give answers: More = 5, 8.
In other words, according to the rules in the predicate “number_more”, the number 4 is two numbers 5 and 8. Here you can see that the rule set works like a case branching structure in algorithmic languages. Predicates that can produce multiple values are called indefinite (nondeterm). Predicates that produce only one value are called determ. In addition to the indefinite predicates in the ProLog, they also use the mechanism of uncertainty facts. Example.
have (debts, bad).
have (flat, good).
have (children, ok).
Then call the ProLog solver
Goal to have (What, good).
The answer will be: What = apartment, children
Backtracking
Now we introduce the concept of rollback (Backtracking). A rollback is an attempt by ProLog to find the next solution to the problem. Rollback is caused by failure in some place of the program, which leads to ProLog to try to find the next solution. Rolling back comes to a place where it is possible to calculate another solution. In this case, all bound variables that were bound below the point where another solution is possible are released. When calling the ProLog solver, a rollback is created by the ProLog itself to return all the solution values. Example.
database - knowledge
have (string, string)
predicates
show (string)
clauses
Show (How): -
% is variable here What will be freed each time
% contact new value
have (What, How),
nl, write (What, "to have", How).
Goal
% load knowledge with facts to have () from knowledge file.txt
consult ("knowledge.txt", knowledge),
% call the predicate issuing several answers
show (good).
ProLog Answers:
the apartment is good
children have a good
Clipping (Cut)
Now we introduce the concept of clipping. A cut-off in the ProLog is a mechanism that prohibits iteration of the rules of a given predicate that are below the current rule and prohibits a rollback mechanism. Clipping is indicated by a “!”. Example. If you rewrite the previous predicate “number_big” as:
number_more (A, 3): - A <3,
!
number_more (A, 5): - A <5,
!
number_more (A, 8): - A <8,
!
Then call the ProLog solver
Goal number_more (4, More).
Will give the answer: More = 5.
This happens because in each predicate rule, after checking for more, the clipping operator "!" Is in progress, which prohibits the ProLog from subsequent rollback and searching for other answer options.
An example of using the mechanism of rollback and clipping.
The mechanism of rollback and clipping can be seen in the following example. Suppose we have a list of values in which we need to find a certain value and give the value before it. Since ProLog is a logical language, the problem is solved by creating a set of rules:
Description in the language The ProLog of the predicate that performs these rules will be:
1. find_pred_value (Value, [Element | List], Previous): -
not (Value = Element),
!,% cut-off iteration of the predicate rules below
find_value (Value, List, Previous),
!
2. to find_pred_value (Value, [Value | _], _): -
!,% cut-off iteration of the predicate rules below
fail.
3. find_pred_value (_, [Previous | _], Previous): -!.
Knowing that in the ProLog, you can use the order of the rules as a way to select a sequence of bypassing the rules, and knowing the effect of the clipping mechanism, you can rearrange rules 1 and 2 in places and remove the mismatch check. Then we get the following description of the predicate:
domains
Number = integer
N List = Number *
predicates
find_pred_value (Number Value, NList, Number Previous)
clauses
find_value (Value, [Value | _], _): -
!,% cut-off iteration of the predicate rules below
fail.
find_value (Value, [_ | List], Previous): -
find_value (Value, List, Previous),
!.% cut-off issue of other answers
find_value (_, [Previous | _], Previous): -
!.% cut-off issue of other answers
The resulting description consists of three rules and performs the following actions. The first rule compares the current element with the desired value, and if they are equal, then a) the cutting off of the predicate rules located below from participation in the search occurs, b) failure is caused, which causes the recursion to stop. The second rule does the enumeration of all elements of the list by calling itself, that is, it causes recursion. At the same time, there are no cut-offs in the rule before the recursion call, and if the recursion call fails, then control passes to the predicate rule below. If the recursion call succeeds, the clipping ("!") Is called, and then the exit from the predicate. The third rule returns the current element as the previous value that precedes the desired value, causing clipping and exiting the predicate. The action of the predicate, see an example. Give the ProLog solver a string:
Goal find_red_value (3, [1,2,4,3,5,2], Previous).
The ProLog makes the first call to the predicate:
ProLog Reply Previous = 4.
Now let's see what happens if we remove clipping in the second rule:
domains
Number = integer
N List = Number *
predicates
% declare that the predicate is undefined
nondeterm find_value (Number Value, List List, Number Previous)
clauses
find_value (Value, [Value | _], _): -
!,% cut-off iteration of the predicate rules below
fail.
find_value (Value, [_ | List], Previous): -
% there is no clipping in this rule
% indicating the possibility of a rollback to this place
% to select the next answer
find_value (Value, List, Previous).
find_value (_, [Previous | _], Previous): -
!.% cut-off issue of other answers
That ProLog will produce several results:
Previous = 4, 2, 1.
This becomes possible as the ProLog rollback mechanism is enabled and in the second rule it is possible to issue an answer at each recursion step.
Comments
To leave a comment
Presentation and use of knowledge
Terms: Presentation and use of knowledge