Prolog - examples of use (Part 2)
The first part of an article about Prolog described the structure, syntax, and interpretation of a language. Of course, non-fiction literature is interesting for a programmer, but something interactive, live, and launching is much more interesting. Therefore, in this article I propose to arm SWI-Prolog and consider solving the simplest problems on the Prolog.
Before starting, I would like to briefly answer topical questions from harabchiteli:
- Where is Prolog really used?
- Such projects exist, some were cited in the comments to the 1st article. It is important that most programmers write in Prolog not from hopelessness, but from the fact that they like Prolog. After all, Prolog cannot be used for any task, such as creating a UI or manipulating files.
- Why are there few such projects?
“Because there are very few programmers who own Prolog, not only because people did not study it, but because they did not study to write full programs.” The main reason is that people do not clearly understand in what situations it is best to use it. You can often see that the ardent supporters of the Prologue write everything on it, including handlers for the keyboard and mouse, which makes the code worse than C.
')
- Why is there no Prolog community?
- It is. Such is the specificity of the language that it is very fond of in the academic environment (most of the Prolog systems are written in various universities and vice versa almost any university writes its own Prolog), because of this, the applicability of the language also suffers. It is worth noting that the community is small, but very loyal: almost all known languages are reflected in modern languages (Lisp, ML -> F #, Scala; Smalltalk -> Java, Scala (agents), scripted -> Ruby), unlike Prologue.
I think this is enough philosophical reasoning and you can start with real examples :)
In the end, as usual, the task for the prize awaits
For this example, we need the predicate is / 2. X is 3 + 1 * 2 - calculates the expression on the right and puts in the variable on the left, it is not an assignment (!), But the statement that X = 7. Simply put, the phrase X = 7, X = 3 - has no solution because X cannot be simultaneously 7 and 3.
We also need a solution to the problem from the previous topic. The task was to write a predicate that would generate all natural numbers in a row, here’s the solution:
In fact, this is a declarative version of the standard integer / 1 predicate, which checks that the argument is an integer. The problem of the standard predicate is that it works correctly for the query: - integer (1) and does not work for the query integer (X).
The task : to write a program that would find all the perfect numbers.
The solution is obvious, we run over all integers and check whether they are perfect, this strategy is very well applicable to imperative languages, we ourselves do not notice how we immediately look for a solution search algorithm, rather than analyzing the problem. In Prolog, we should not try to describe the search for a solution to a problem, but try to describe the formulation of the problem, to do this, follow the rule:
Do not try to describe the instructions for finding a solution, assume that you have already found a solution, and your task is only to verify that a solution has been found.
Oddly enough, but this strategy works great.
We paste the source text into the file, run the interpreter and compile it (via the query: -compile ('path_to_file / perfect_numbers.pl'). Write the query : - perfect_number (X). And the interpreter gives the answer, when you press ';' produces the following. Pay Attention request may be : - perfect_number (X), X> 6. Then all the answers will be more than 6. Of course the program does not work optimally, the check itself can be simplified using simple dividers, try.
For the formulation and solution of this problem we need the concept of lists. Lists are not basic language concepts; between lists, you can draw a direct analogy with linked lists in C. We return to the definition of a term as a recursive data structure.
As many would say, the usual recursion and that the lists do not look like something especially in the Prologue there is syntactic sugar for them: nil can be written [], t (1, nil) - [1], t (1, t (2, nil) ) - [1, 2], t (1, Sublist) - [1 | Sublist], t (1, t (2, Sublist)) - [1, 2 | Sublist]. It is recommended to use syntactic sugar for lists, because the internal name of terms may differ (most often the term is called '.').
Let us return to the original problem of generating permutations. Everyone remembers perfectly well that the number of permutations is n !, but now give this task to most programmers and everyone will start to frantically recall and say that they wrote this in school and forgot how the search is done. On average, the algorithm appears after trying and tormenting after 20 minutes. With the knowledge of Prolog, this algorithm is written in 2 minutes or not written at all :)
How to solve on the prolog? We use the rule of not finding a solution, but checking that a solution has been found. Predicate perm (Source, Permutation) - where Source is source list, Permutation is permutation.
Query : -perm ([1, 2, 3], X) generates all permutations. Interestingly, the queries are symmetrical : -perm (X, [1, 2, 3]) with respect to the arguments, although this query hangs and in order for it to work it is necessary to change member_list_exclude and perm places in perm.
The generation of combinations in terms of ease of implementation is similar to the generation of permutations. We will need the predicate member / 2 - the element belonging to the list. Suppose we have 2 lists: the 1st source list, the 2nd one — the intended combination, you need to check the correctness of the combination. Elements of the combination are arranged in the order of the original list.
This example will be considered in sufficient detail and we will try to optimize the primary solution. The process of writing on Prolog is as follows: 1) the primary description of the problem and obtaining the overkill solution 2) logical optimization by rearranging the predicates on the right 3) logical optimization of introducing simplified checks or removing unnecessary conditions 4) introducing heuristics and optimizing individual cases by cutting off.
Option 1. Sorting naive : the first element of the sorted array should be minimal, the remaining elements should be sorted. The first array is source, the second array is sorted source.
It can be noted that the complexity of this algorithm is quadratic and the main problem is that every time we look for the minimum element without saving any useful information.
Note also that we are trying to determine what the 1st element of a sorted array is.
Option 2. Quick sort. Let's look at the problem from the second side and try to determine the location of the 1st list item in the sorted array (apply recursion to the original array).
You may notice that we have improved the results of sorting, since the quick sort is obviously faster than the bubble one. In order to further improve the results, we can recall the merge sort, which in any case gives O (n lg n), but unfortunately this sorting is applicable only to arrays, and not to the connected lists with which we work. The only option is to use an additional data structure for storage - a tree.
Option 3. Sort using a binary tree.
For this type of sorting, we translate the source list into a binary tree, and then, using the tree traversal on the left, we get a sorted array. The tree will be represented by the recursive term tree (Object, LeftSubTree, RightSubTree) .
Option 4. Sort using a balanced binary tree.
The problem of using a binary tree is the same as using quick sort. The method does not guarantee optimal performance. In the case of a binary tree, the tree can be unbalanced and the procedure for adding an element to it can be linear rather than logarithmic. Especially for this, the tree balancing procedures are carried out, the algorithm with the use of the AVL-tree will be shown below.
This example is not sufficiently expressive for implementation on Prolog, although it gives an idea of the programs of average size. For training, you can implement bubble sorting or sorting inserts, we leave it at the discretion of the reader.
As the next task, we consider the classical problem of states; this problem reflects the advantages of using Prolog much better. The general formulation of the problem: some containers with water are given, it is necessary to obtain a certain amount of water in a container by means of transfusions. For example, take 3 jugs with a capacity of 12 liters, 8 liters, 5 liters, fill the 1st completely, that is, 12 liters and set the task to get 6 liters . First, try to solve this school problem with a pen and a piece of paper :)
Before generating the various algorithms and trying to apply them to the task, let's first rewrite the terms in terms of the Prolog. We describe the capacity as a term sosud (Id, MaximumCapacity, CurrentCapacity) , and describe the state of the system as a list of capacities. Example [sosud (1, 12, 12), sosud (2, 8, 0), sosud (3, 5, 0)] . Now we will describe the query:
Please note that Goal = sosud (_, _, 6), that is, it does not matter to us which capacity the vessel is important for it to have exactly 6 liters.
Now that we all know, we will describe the way to verify the solution, assuming that the steps are set in the variable Steps.
Additions, it may seem that the verification of the domain is not necessary, because if the steps for transfusion are correct, then you can not verify what they describe. In fact, the completeness of verification seriously improves the chances of the program to earn correctly. It is more correct to even say so, with excessive verification, the program will work, sometimes even more optimized than without, but with insufficient verification, the program with some input data will produce absolutely wrong results or hang.
Well, the description of the program is written - you can run. No wonder the program will not work, it just hangs :) It's not as bad as it may seem, because if the program did not freeze, then it would give the correct answer. We need to figure out why it is stuck, and here we will come to the aid of an understanding of how the Prologue unfolds the rules in order to find a solution. In fact, you don’t need to have a head that can memorize up to 10 cusps to understand that every next time solve_pr_wo -> calls solve_pr_wo by recursion, it causes 2 predicates of member / 2, which always return the same 1st and 2nd vessel (the predicate does not cause backtracking and does not allow the member to select the 1st and 1st vessel). That is, the algorithm constantly pours from 1st to 2nd and back.
In order to resolve this absurdity, it immediately comes to mind to prohibit doing the same action 2 times, that is, to have a history of states, and if a state has already been encountered, then to prohibit its repeated hit. It turns out that we are narrowing the set of permissible transfusion strategies, excluding repetition. In fact, narrowing the set of strategies, we do not narrow the set of admissible states of the system, that is, solutions, which is not difficult to prove.
The full version of the program with a listing of states and the only predicate for calling a solution:
Everything works now! As an exercise, you can modify the program so that it finds transfusions in the optimal number of steps. You can experiment here on these puzzles .
Note : ardent supporters of imperative programming will notice that all we have done is going through all the states with returns (pass into depth), and without using heuristics, they will be absolutely right. The fact is that you need to think in Prolog not just by searching, but by describing the problem and describing the solution check, and you should always return to the imperativeness of the calculations for optimization, if you need it! The duality of nature is not a minus, but a plus. It is also worth noting that large Prolog systems are very well adapted for searching states with returns.
I would like to note that the tasks discussed in this article are sketches for programming in Prolog. Since most of them occupy about 10-15 lines, the Prolog programmer is able to reproduce them from memory with sufficiently frequent cutting of them. And returning to them is definitely worth it, as it reminds of the art of programming (just like a quick sort on C). More complex and more applied tasks for everyday use will be discussed later.
At the end there are 2 tasks for the prize :
Thanks for attention.
Before starting, I would like to briefly answer topical questions from harabchiteli:
- Where is Prolog really used?
- Such projects exist, some were cited in the comments to the 1st article. It is important that most programmers write in Prolog not from hopelessness, but from the fact that they like Prolog. After all, Prolog cannot be used for any task, such as creating a UI or manipulating files.
- Why are there few such projects?
“Because there are very few programmers who own Prolog, not only because people did not study it, but because they did not study to write full programs.” The main reason is that people do not clearly understand in what situations it is best to use it. You can often see that the ardent supporters of the Prologue write everything on it, including handlers for the keyboard and mouse, which makes the code worse than C.
')
- Why is there no Prolog community?
- It is. Such is the specificity of the language that it is very fond of in the academic environment (most of the Prolog systems are written in various universities and vice versa almost any university writes its own Prolog), because of this, the applicability of the language also suffers. It is worth noting that the community is small, but very loyal: almost all known languages are reflected in modern languages (Lisp, ML -> F #, Scala; Smalltalk -> Java, Scala (agents), scripted -> Ruby), unlike Prologue.
I think this is enough philosophical reasoning and you can start with real examples :)
In the end, as usual, the task for the prize awaits
Example # 1 - search for perfect numbers
For this example, we need the predicate is / 2. X is 3 + 1 * 2 - calculates the expression on the right and puts in the variable on the left, it is not an assignment (!), But the statement that X = 7. Simply put, the phrase X = 7, X = 3 - has no solution because X cannot be simultaneously 7 and 3.
We also need a solution to the problem from the previous topic. The task was to write a predicate that would generate all natural numbers in a row, here’s the solution:
ints(0). ints(X) :- ints(Y), X is Y + 1. In fact, this is a declarative version of the standard integer / 1 predicate, which checks that the argument is an integer. The problem of the standard predicate is that it works correctly for the query: - integer (1) and does not work for the query integer (X).
The task : to write a program that would find all the perfect numbers.
The solution is obvious, we run over all integers and check whether they are perfect, this strategy is very well applicable to imperative languages, we ourselves do not notice how we immediately look for a solution search algorithm, rather than analyzing the problem. In Prolog, we should not try to describe the search for a solution to a problem, but try to describe the formulation of the problem, to do this, follow the rule:
Do not try to describe the instructions for finding a solution, assume that you have already found a solution, and your task is only to verify that a solution has been found.
Oddly enough, but this strategy works great.
%% ints(0). ints(X) :- ints(Y), X is Y + 1. %% - 1) 2) perfect_number(X) :- ints(X), Y is X - 1, calculatesum_divisors_till(Sum, X, Y), Sum = X. %% 1- , 2- - , %% 3- - calculatesum_divisors_till(0, _NumberToDivide, 0). calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem = 0, Ts is Till - 1, calculatesum_divisors_till(SumPrev, NumberToDivide, Ts), Sum is SumPrev + Till. calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem > 0, Ts is Till - 1, calculatesum_divisors_till(Sum, NumberToDivide, Ts). We paste the source text into the file, run the interpreter and compile it (via the query: -compile ('path_to_file / perfect_numbers.pl'). Write the query : - perfect_number (X). And the interpreter gives the answer, when you press ';' produces the following. Pay Attention request may be : - perfect_number (X), X> 6. Then all the answers will be more than 6. Of course the program does not work optimally, the check itself can be simplified using simple dividers, try.
Example # 2 - generation of permutations.
For the formulation and solution of this problem we need the concept of lists. Lists are not basic language concepts; between lists, you can draw a direct analogy with linked lists in C. We return to the definition of a term as a recursive data structure.
%% nil list(nil). %% 1 list(t(1, nil)). %% 1, 2, 3 list(t(1, t(2, t(3, nil) ) ) ). %% %% 1. (1- ) %% _ - member(X, t(Y, _)) :- X = Y. %% 2. , member(X, t(_, Tail)) :- member(X, Tail). As many would say, the usual recursion and that the lists do not look like something especially in the Prologue there is syntactic sugar for them: nil can be written [], t (1, nil) - [1], t (1, t (2, nil) ) - [1, 2], t (1, Sublist) - [1 | Sublist], t (1, t (2, Sublist)) - [1, 2 | Sublist]. It is recommended to use syntactic sugar for lists, because the internal name of terms may differ (most often the term is called '.').
%% 1. (1- ) member(X, [X|_]). %% 2. , member(X, [_| Tail]) :- member(X, Tail). Let us return to the original problem of generating permutations. Everyone remembers perfectly well that the number of permutations is n !, but now give this task to most programmers and everyone will start to frantically recall and say that they wrote this in school and forgot how the search is done. On average, the algorithm appears after trying and tormenting after 20 minutes. With the knowledge of Prolog, this algorithm is written in 2 minutes or not written at all :)
How to solve on the prolog? We use the rule of not finding a solution, but checking that a solution has been found. Predicate perm (Source, Permutation) - where Source is source list, Permutation is permutation.
%% perm([], []). %% 1- , %% , %% %% perm(Source, [Element|Tail]) :- member_list_exclude(Element, Source, SourceExcluded), perm(SourceExcluded, Tail). %% , , 2- %% member_list_exclude %% 1- - , 2- - , 3- - member_list_exclude(X, [X|L], L). member_list_exclude(X, [Y|L], [Y|Ls]) :- member_list_exclude(X, L, Ls). Query : -perm ([1, 2, 3], X) generates all permutations. Interestingly, the queries are symmetrical : -perm (X, [1, 2, 3]) with respect to the arguments, although this query hangs and in order for it to work it is necessary to change member_list_exclude and perm places in perm.
Example # 3 - generation of combinations.
The generation of combinations in terms of ease of implementation is similar to the generation of permutations. We will need the predicate member / 2 - the element belonging to the list. Suppose we have 2 lists: the 1st source list, the 2nd one — the intended combination, you need to check the correctness of the combination. Elements of the combination are arranged in the order of the original list.
member(X, [X|_]). member(X, [_|L]) :- member(X, L). comb([], []). %% 1 : 1- comb([X|List], [X|Tail]) :- comb(List, Tail). %% 2 : , %% 1- comb([_|List], Tail) :- comb(List, Tail). Example # 4 - sorting.
This example will be considered in sufficient detail and we will try to optimize the primary solution. The process of writing on Prolog is as follows: 1) the primary description of the problem and obtaining the overkill solution 2) logical optimization by rearranging the predicates on the right 3) logical optimization of introducing simplified checks or removing unnecessary conditions 4) introducing heuristics and optimizing individual cases by cutting off.
Option 1. Sorting naive : the first element of the sorted array should be minimal, the remaining elements should be sorted. The first array is source, the second array is sorted source.
sort([], []). sort(List, [Min|SortRest]) :- min_list_exclude(Min, List, Exclude), sort(Exclude, SortRest). %% , min_list_exclude(M, [M], []). min_list_exclude(Min, [M|L], ExcludeRes) :- min_list_exclude(Ms, L, Exclude), find_result(result(M, L), result(Ms, [M|Exclude]), result(Min, ExcludeRes)). %% find_result(result(M, L), result(Ms, _), result(M, L)):- M < Ms. find_result(result(M, _), result(Ms, Exclude), result(Ms, Exclude)):- Ms =< M. It can be noted that the complexity of this algorithm is quadratic and the main problem is that every time we look for the minimum element without saving any useful information.
Note also that we are trying to determine what the 1st element of a sorted array is.
Option 2. Quick sort. Let's look at the problem from the second side and try to determine the location of the 1st list item in the sorted array (apply recursion to the original array).
sort_b([], []). sort_b([T|R], List) :- split(T, R, Less, Great), sort_b(Less, LessSort), sort_b(Great, GreatSort), append(LessSort, [T|GreatSort], List). %% 2 split(_, [],[], []). split(T, [M|R],[M|Less], Great) :- M < T, split(T,R, Less,Great). split(T, [M|R],Less, [M|Great]) :- M >= T, split(T,R, Less,Great). %% 2 append([], M, M). append([L|Left], Right, [L|Res]) :- append(Left, Right, Res). You may notice that we have improved the results of sorting, since the quick sort is obviously faster than the bubble one. In order to further improve the results, we can recall the merge sort, which in any case gives O (n lg n), but unfortunately this sorting is applicable only to arrays, and not to the connected lists with which we work. The only option is to use an additional data structure for storage - a tree.
Option 3. Sort using a binary tree.
For this type of sorting, we translate the source list into a binary tree, and then, using the tree traversal on the left, we get a sorted array. The tree will be represented by the recursive term tree (Object, LeftSubTree, RightSubTree) .
sort_tree([], nil). sort_tree([X|L], Tree) :- sort_tree(L, LTree), plus(X, LTree, Tree). %% plus(X, nil, tree(X, nil, nil)). plus(X, tree(O, L, R), tree(O, ResL, R)) :- O >= X, plus(X, L, ResL). plus(X, tree(O, L, R), tree(O, L, ResR)) :- O < X, plus(X, R, ResR). sort_t(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). append_list([], L, L). append_list([X|L], R, [X|T]) :- append_list(L, R, T). tree_list(nil, []). tree_list(tree(X, L, R), List) :- tree_list(L, ListL), tree_list(R, ListR), append_list(ListL, [X|ListR], List). Option 4. Sort using a balanced binary tree.
The problem of using a binary tree is the same as using quick sort. The method does not guarantee optimal performance. In the case of a binary tree, the tree can be unbalanced and the procedure for adding an element to it can be linear rather than logarithmic. Especially for this, the tree balancing procedures are carried out, the algorithm with the use of the AVL-tree will be shown below.
sort_btree(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). tree_list(nil, []). tree_list(tree(X, L, R, _), List) :- tree_list(L, ListL), tree_list(R, ListR), append(ListL, [X|ListR], List). sort_tree([], nil). sort_tree([X|L], Tree) :- sort_tree(L, LTree), plus_tree(X, LTree, Tree). construct_tree(A, AL, AR, tree(A, AL, AR, ADepth)) :- diff(AL, AR, _, ADepth). diff(AL, AR, ADiff, ADepth) :- depth_tree(ALs, AL), depth_tree(ARs, AR), ADiff is ALs - ARs, max_int(ALs, ARs, AD), ADepth is AD + 1. max_int(A, B, A) :- A > B. max_int(A, B, B) :- A =< B. append([], L, L). append([X|L], R, [X|T]) :- append(L, R, T). depth_tree(0, nil). depth_tree(X, tree(_, _, _, X)). plus_tree(X, nil, tree(X, nil, nil, 1)). plus_tree(X, tree(O, L, R, _), Res) :- O >= X, plus_tree(X, L, ResL), diff(ResL, R, Diff, Dep), balance_tree(tree(O, ResL, R, Dep), Diff, Res). plus_tree(X, tree(O, L, R, _), Res) :- O < X, plus_tree(X, R, ResR), diff(L, ResR, Diff, Dep), balance_tree(tree(O, L, ResR, Dep), Diff, Res). %% No rotations balance_tree(Tree, ADiff, Tree) :- ADiff < 2, ADiff > -2. %% Small right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff >= 0, construct_tree(A, BR, AR, ASubTree), construct_tree(B, BL, ASubTree, Result). %% Big right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff < 0, BR = tree(C, CL, CR, _), construct_tree(B, BL, CL, BSubTree), construct_tree(A, CR, AR, ASubTree), construct_tree(C, BSubTree, ASubTree, Result). %% Small left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff =< 0, construct_tree(A, AL, BL, ASubTree), construct_tree(B, ASubTree, BR, Result). %% Big left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff > 0, BL = tree(C, CL, CR, _), construct_tree(B, CR, BR, BSubTree), construct_tree(A, AL, CL, ASubTree), construct_tree(C, ASubTree, BSubTree, Result). This example is not sufficiently expressive for implementation on Prolog, although it gives an idea of the programs of average size. For training, you can implement bubble sorting or sorting inserts, we leave it at the discretion of the reader.
Example 5 - The task of transfusions.
As the next task, we consider the classical problem of states; this problem reflects the advantages of using Prolog much better. The general formulation of the problem: some containers with water are given, it is necessary to obtain a certain amount of water in a container by means of transfusions. For example, take 3 jugs with a capacity of 12 liters, 8 liters, 5 liters, fill the 1st completely, that is, 12 liters and set the task to get 6 liters . First, try to solve this school problem with a pen and a piece of paper :)
Before generating the various algorithms and trying to apply them to the task, let's first rewrite the terms in terms of the Prolog. We describe the capacity as a term sosud (Id, MaximumCapacity, CurrentCapacity) , and describe the state of the system as a list of capacities. Example [sosud (1, 12, 12), sosud (2, 8, 0), sosud (3, 5, 0)] . Now we will describe the query:
%% solve_pr_wo(InitialState, Goal, Steps). :- solve_pr_wo([sosud(1, 12, 12), sosud(2, 8, 0), sosud(3, 5, 0)], sosud(X, _, 6), Steps). Please note that Goal = sosud (_, _, 6), that is, it does not matter to us which capacity the vessel is important for it to have exactly 6 liters.
Now that we all know, we will describe the way to verify the solution, assuming that the steps are set in the variable Steps.
%% , %% solve_pr_wo(State, Goal, []) :- member(Goal, State). %% Sosud Sosud2 %% ResSosud, ResSosud2. %% : %% mv(sosud(1, 12, 12) -> sosud(2, 8, 0), sosud(1, 12, 4) -> sosud(2, 8, 8)). solve_pr_wo(State, Goal, [mv(Sosud -> Sosud2 , ResSosud -> ResSosud2)| Steps]) :- %% , %% member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), %% , %% 4 mv(Sosud, Sosud2, ResSosud, ResSosud2), %% replace(Sosud, State, ResSosud, State2), replace(Sosud2, State2, ResSosud2, StateX), %% solve_pr_wo(StateX, Goal, Steps). %% %% replace(ElementToReplace, InList, ElementToReplaceWith, OutList). replace(S, [S|L], X, [X|L]). replace(S, [T|L], X, [T|Ls]) :- replace(S, L, X, Ls). %% - 2 %% %% mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > 0, Current3 is Current2 + Current, Current3 =< Max2. %% mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0. Additions, it may seem that the verification of the domain is not necessary, because if the steps for transfusion are correct, then you can not verify what they describe. In fact, the completeness of verification seriously improves the chances of the program to earn correctly. It is more correct to even say so, with excessive verification, the program will work, sometimes even more optimized than without, but with insufficient verification, the program with some input data will produce absolutely wrong results or hang.
Well, the description of the program is written - you can run. No wonder the program will not work, it just hangs :) It's not as bad as it may seem, because if the program did not freeze, then it would give the correct answer. We need to figure out why it is stuck, and here we will come to the aid of an understanding of how the Prologue unfolds the rules in order to find a solution. In fact, you don’t need to have a head that can memorize up to 10 cusps to understand that every next time solve_pr_wo -> calls solve_pr_wo by recursion, it causes 2 predicates of member / 2, which always return the same 1st and 2nd vessel (the predicate does not cause backtracking and does not allow the member to select the 1st and 1st vessel). That is, the algorithm constantly pours from 1st to 2nd and back.
In order to resolve this absurdity, it immediately comes to mind to prohibit doing the same action 2 times, that is, to have a history of states, and if a state has already been encountered, then to prohibit its repeated hit. It turns out that we are narrowing the set of permissible transfusion strategies, excluding repetition. In fact, narrowing the set of strategies, we do not narrow the set of admissible states of the system, that is, solutions, which is not difficult to prove.
The full version of the program with a listing of states and the only predicate for calling a solution:
write_list([]). write_list([X|L]) :- writeln(X), write_list(L). solution :- solve_pr([sosud(1, 12, 12), sosud(2, 8, 0), sosud(3, 5, 0)], sosud(_, _, 6), [], Steps), write_list(Steps). replace(S, [S|L], X, [X|L]). replace(S, [T|L], X, [T|Ls]) :- replace(S, L, X, Ls). %% , %% , , solve_pr(State, Goal, _, [State]) :- member(Goal, State). solve_pr(State, Goal, History, [State|Steps]) :- member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), mv(Sosud, Sosud2, ResSosud, ResSosud2), replace(Sosud, State, ResSosud, State2), replace(Sosud2, State2, ResSosud2, StateX), %%% not(member(StateX, [State|History])), solve_pr(StateX, Goal, [State|History], Steps). %% mv(sosud(_Id, Max, Current), sosud(_Id2, Max2, Current2), ...,...). %% mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > 0, Current3 is Current2 + Current, Current3 =< Max2. %% mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0. Everything works now! As an exercise, you can modify the program so that it finds transfusions in the optimal number of steps. You can experiment here on these puzzles .
Note : ardent supporters of imperative programming will notice that all we have done is going through all the states with returns (pass into depth), and without using heuristics, they will be absolutely right. The fact is that you need to think in Prolog not just by searching, but by describing the problem and describing the solution check, and you should always return to the imperativeness of the calculations for optimization, if you need it! The duality of nature is not a minus, but a plus. It is also worth noting that large Prolog systems are very well adapted for searching states with returns.
Conclusion
I would like to note that the tasks discussed in this article are sketches for programming in Prolog. Since most of them occupy about 10-15 lines, the Prolog programmer is able to reproduce them from memory with sufficiently frequent cutting of them. And returning to them is definitely worth it, as it reminds of the art of programming (just like a quick sort on C). More complex and more applied tasks for everyday use will be discussed later.
At the end there are 2 tasks for the prize :
- As is well known in the functional and logical in every way they try to avoid programs with side effects, wrap them in monads, invent special concepts. The standard problem is the problem of the outside world, for example, writing data to a file, it is impossible to roll back the record to the file or to cancel sending several bytes on the socket, and therefore backtracking will not work completely correctly. Council one - do not use the Prologue for these purposes. But there are predicates that are very good and specific to Prolog, but have a side effect. Example assert (asserta, assertz): it adds a simple rule (fact) to the rule (fact) base. Example assert (prime (3)) : adds the fact that 3 is a prime number and the query : -prime (X) will now issue 3, even with an empty source program.
The task : to write a declarative version of assert , that is, when the backtracking program is returned, the fact should not remain in memory, but should work as a logical assumption.
Example of operation : the query c (X) should output one number 4 for the next program!a(X) :- b(Y), X is Y + 1 . c(X) :- my_assert(b(3)), a(X). c(X) :- b(X). - In classical mathematical logic 2, theories are given much more attention than all the rest — this is the theory of sets and the theory of predicates . There is a definite connection between them, one is expressed through the other and vice versa. For example, a predicate is a set of values on which it is true, and vice versa a set is a membership predicate. The traditional relational database theory operates on sets, and Prolog operates on predicates. In general, the task is to express an absolutely traditional operation for set theory an operation — the operation of taking the set of all subsets .
: a/1 ( , ), subset_a/1, , a.
: subset_a(X) X = [], X = [1], X = [2], X = [1, 2] ( ):a(1). a(2). subset_a(X) :- ....?
Thanks for attention.
Source: https://habr.com/ru/post/124820/
All Articles