Clipping mechanism

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:

1. When iterating through the list, if the current element is not the desired value, then do a search further.
2. When searching the list, if the current element is the desired value, then stop searching and return to the previous element.
3. If the previous rules did not work, then return the current element as the previous value.

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:

1. Rule 1 does not work: 3 is not equal to 1. Go to the second rule:
2. Rule 2 causes recursion to find_pred_value (3, [2,4,3,5,2], Previous):
   1. Rule 1 does not work: 3 is not equal to 2. Go to the second rule:
   2. Rule 2 causes recursion to find_value (3, [4,3,5,2], Previous):
      1. Rule 1 does not work: 3 is not equal to 4. The transition to the second rule:
      2. Rule 2 causes recursion: find_pred_value (3, [3,5,2], Previous):
         1. The first rule will work: 3 = 3. and done: pruning the predicate rules below and failing. Which results in exiting recursion with the result of failure.
      3. Continuation of rule 2. Failure to call recursion with the list [3,5,2] results in failure of the second rule at this level. The log goes to the third rule.
      4. Rule 3. Here is the list = [4,3,5,2]. Actions are taken: The previous one is unified with 4, the output with the cut-off of other possible solutions.
      5. Continuation of rule 2. Recursion returns a successful value of Previous = 4. There is an exit with clipping of other possible solutions.
   3. Continuation of rule 2. Recursion returns a successful value of Previous = 4. There is an exit with clipping of other possible solutions.
3. Continuation of rule 2. Recursion returns a successful value of Previous = 4. There is an exit with clipping of other possible solutions.

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.