Prolog is an amazing programming language
- What is he amazing? I know a couple of dozen languages and for me it’s not a problem to learn another new one, I just don’t see any need anymore.
The prologue is unique. It is the only language representing the declarative programming paradigm; it is a language that has hundreds of different implementations, but they are still called Prolog, adding only prefixes and suffixes to the name; it is a living language in which no significant changes have taken place for more than 20 years; This is probably the only so popular programming language that has no application in real programming. Why Prolog?
The prologue is unique in its nature, it appeared due to a happy coincidence (themysterious structure of the world ). Sometime in the 1960s, the theory of automatic proof of theorems developed very rapidly, and Robinson proposed a resolution algorithm that allowed one to prove any valid theorem (to deduce from axioms) in a finite time (for which it is not known). As it turned out later, this is the best solution to the general problem; it is impossible to prove a theorem for a limited number of operations. In simple words, the algorithm is a detour (in the general case of an infinite) graph width, naturally, the predictability of the algorithm is practically equal to 0, respectively, for the Programming Language - this is absolutely not suitable. And at this moment Kalmarou found a brilliant narrowing of the problem, thanks to which the proof of some theorems looked like a procedural execution of a program. It is worth noting that the class of provable theorems is quite wide and is very well applicable to the class of programmable problems. That's how Prolog appeared in 1972.
')
In this article I will try to talk about Prolog as a tool for solving common logical problems. This topic will be interesting to those who already own Prolog syntax and want to understand it from the inside, as well as those who absolutely do not own the syntax of the language, but want to understand its "flavor" without wasting too much time studying syntax.
The main feature of Prolog is that it can be easily read, but it is very difficult to write, which is fundamentally different from all mainstream languages, which they say to write has become even easierone more step and you can write on the tablet, dragging the work modules as friends on Google+ , we all know that the quality of the code itself suffers greatly. It seems that every line is clear, but how the system works is beyond comprehension, even for developers, as they say, naindusili. It seems to me that in all books on teaching Prolog, they make the same mistake, starting a story about facts, relationships, inquiries, and a person develops an attitude towards the language as an Expert System or Database. Much more important is learning how to read programs correctly and read like a dozen :)
Reading programs is very simple, since there are very few special characters and keywords in the language and they are easily translated into natural language. The main mistake of the programmer is that he wants to immediately imagine how the program works, and not to read what the program describes, so it seems to me to train the unmanned brain of an ordinary person, much easier than a programmer.
In the language there are 2 concepts of predicates (conditions) and objects (they are variables and terms). Predicates express a certain condition, for example, an object is green or a number is simple; naturally, the conditions have input parameters. For example, green_object (Object) , prime_number (Number) . How many parameters are in the predicate, so is the arity of the predicate. Objects are terms, constants and variables. Constants are numbers and strings, variables express an unknown object, possibly the one you are looking for, and are denoted as strings with a capital letter. Let's leave the terms for now and consider the simplest program.
A program is a set of rules, of the form If condition1 and condition2 and ... then the condition is true. Formally, these rules are combined through AND, but a contradiction cannot be obtained, since in Prolog there is no logical negation, and in the bundle of To, there can be only one predicate (condition).
As you can see the variable name has scope - this is the rule. Mathematically true, the rule is: for any variable - “Number”, if it is simple and odd, then it is simple_ odd. Similarly, you can rephrase as: If there is a “Number”, that it is odd and simple, then it is odd_simple. Therefore, the variable name is very important! If in the left part (to: -) replace Number by Number2, the rule changes the meaning: For any Number2 and Number, if Number is simple and odd, then Number2 is simple odd. It turns out all the numbers are simple_ odd! This is the most common mistake in Prolog.
For a start, let's formally read what the rules mean:
There is a second way to read these rules, less mathematical and more natural, based on "definitions". It can be noted that in Prolog all the rules on the left (in this part) contain only one condition, which in essence is the “definition” of this condition.
For example, the 1st rule is the definition of perfect numbers. “H” is a perfect number, when “H” the number and sum of dividers “H” is equal to “H”. Identical predicates are grouped by name by combining the condition “or”. That is, you can add to the definition: “H” is a perfect number, when .., or when “H” is 1.
This method of reading is widely used, as it allows you to combine predicates into homogeneous groups and helps to understand in what order the interpreter spins the predicates in order to
check the truth of some statement. For example, it is obvious that if a predicate does not have a single definition, then it is impossible to prove the truth of the statement with it. In example No. 1, the predicate “divides_ to” is not defined.
It is an interesting fact that in Prolog there are no cycles, no assignment of variables, no type declarations, and if we also recall the terms and clipping, then the language becomes algorithmically complete.
Terms have a recursive definition as a named collection of objects. Term = 'name' (object, object, ...), example person ('Name', 'Surname'), '+' (1, 2), person (address ('Some address'), surname (' Last name '), phone (' Phone ')) . If we consider a term as a mathematical concept, then a term is a function, more precisely, a functor, that is, '+' (1, 2) means that there is an object that is equal to 1 + 2. This absolutely does not mean that 1 + 2 = 3, in Prolog - this expression is untrue, just like in the group of residues modulo 2, there 3 does not exist at all. Again, from a mathematical point of view, Variables are connected by the word For All, and if a word is necessary in the statement, then a term (functor) is used for this purpose. For any number there is a factorial number: - factorial (X, fact (X)).
From a programming point of view, a term can be explained much more simply: a term is an object with a set of attributes, attributes can be other terms or constants or variables (that is, not defined). The main difference is that all objects in Prolog are immutable, that is, it is impossible to change the attributes in them, but there is a special state - a variable.
Obviously, these statements are true for ordinary arithmetic, but why then we did not include the same obvious ones as Number + 0 = Number. The answer is simple: redundancy is very bad for any definition. Yes, it can help with calculations, a kind of premature optimization, but side effects can be contradictions in definitions, ambiguous conclusion of the statement, looping the interpreter.
Of course, reading programs helps to feel the Prolog style, but does not make it clear for what and how these definitions can be used. A full program, the examples above, can not be named because there is not enough input point. The entry point to Prolog is a query, an analogue of a query to a SQL database, or an analogue of a call to a main function in functional programming. Examples of queries: nat (Number) - find a natural number, plus (0, 0, Result) - find the result of adding 0 and 0 in the variable Result, nat (0) - check if 0 is a natural number, etc.
Of course, the results of the queries are not difficult to predict from logical considerations, but it is extremely important to understand how the program received them. Still, Prolog is not a black box, but a programming language, and unlike a database where a SQL plan is built and a query can be executed differently on different Databases, Prolog has a well-defined execution order. The fact is that in the Database we fully know what answer we want to get based on the data in the table, unfortunately looking at the Prolog program it is quite difficult to say which statements are logically deducible, therefore, it is much easier to understand how the Prolog works.
Consider the example query plus (0, 0, Result) :
1. We find a match (a kind of pattern-matching, resolution) of this request with the left part of one of the rules. For this query plus (0, Number, Number). Let us associate in turn all the arguments of the query with the rule and get: 0 = 0, 0 = Number, Result = Number. These variables involve 2 variables (Number and Result), deciding them we get that Number = Result = 0. Since this rule has no conditions, we received an answer to the question asked. Answer: yes and Result = 0.
Query nat (Number) :
1. We find the 1st coincidence with the rule, the nat (0) rule, solving the equations by correspondence, in simple terms finding the resolution, we get Number = 0. Answer: yes and Number = 0.
Request plus (Result, 0, number (0)) :
1. Find the resolution with the rule plus (0, Number, Number): Result = 0, 0 = Number, number (0) = Number, but (!) Number = 0 = number (0) - not possible because 0 matches the number (0). Hence we are looking for a resolution with the following rule.
2. Find the resolution with the rule plus (number (P1), P2, number (Res)), we get the number (P1) = Result, P2 = 0, number (Res) = number (0), from here Res = 0. This rules, there are conditions that we have to check, taking into account the results of the resolution (values of variables), plus (P1, P2, Res) -> plus (P1, 0, 0). Remember the value of the variables in the stack and form a new query plus (P1, 0, 0)
3 *. Solving the query plus (P1, 0, 0) we find the resolution with plus (0, Number, Number) and we get P1 = 0 and Number = 0.
4. Go back to the previous variables on the stack Result = number (P1) = number (0). Answer found number (0). Accordingly, now the prologue machine decided the equation X + 0 = 1.
Proper preparation of rules in the Prolog language is a very complicated thing, but if you compile them compactly, you can get not only direct answers and solutions, but also reverse ones.
Request example plus (Number, Number, Number) : answer yes, Number = 0.
Request example plus (0, 0, 0) : no answer, on the first attempt all resolutions are not met.
Request example plus (Number, Number, Number (Number)) : answer yes, Number = 1. Solution of the equation X + X = X + 1.
Try to multiply output (Number, number (0), number (0)), for this you will need to stack the variables 2 times and calculate the new query. The essence of the Prologue of the machine is such that you can refuse the 1st result, then the Prologue will return to the previous state and continue the calculation. For example, the query nat (Number) , first applies the 1st rule and returns 0, and then applies the 2nd rule + 1st rule and returns the number (0), you can repeat and get an infinite sequence of all natural numbers. Another example, query plus (Number, number (0), Number 2) , will produce a sequence of all pairs of the solution to the equation X + 1 = Y.
Unfortunately, the reasonable size of the topic did not allow me to get close to the main topic, namely, to solving complex logical problems in the Prolog language, without having a strategy to solve them. Large pieces of code on the Prologue can scare away not only beginners, but even experienced programmers. The purpose of this article is to show that programs in Prolog can be read in a natural way in a simple way, and also be executed by a simple interpreter .
The main feature of the Prologue is not a black box and not a library that solves complex logical problems, you can enter an algebraic equation in Mathematica and it will produce a solution, but the sequence of steps performed is unknown. The prolog cannot solve general logical problems (it lacks a logical “or” and “negation”), otherwise its conclusion would be non-deterministic as a linear resolution. The prologue is the golden mean, between a simple interpreter and a machine for proving theorems, a shift to either side leads to the loss of one of the properties.
In the next article I would like to tell you how the tasks of sorting, the sequence of transfusions, Miss Manners and other well-known logical problems are solved. For those who feel dissatisfied, I want to offer the following problem (who decided the first prize ):
Write a predicate that would generate an infinite sequence of natural numbers starting from 3. These should be standard numbers in the Prologue, operations on which are performed using the predicate is: X is 3 + 1 => X = 4.
The prologue is unique. It is the only language representing the declarative programming paradigm; it is a language that has hundreds of different implementations, but they are still called Prolog, adding only prefixes and suffixes to the name; it is a living language in which no significant changes have taken place for more than 20 years; This is probably the only so popular programming language that has no application in real programming. Why Prolog?
The prologue is unique in its nature, it appeared due to a happy coincidence (the
')
In this article I will try to talk about Prolog as a tool for solving common logical problems. This topic will be interesting to those who already own Prolog syntax and want to understand it from the inside, as well as those who absolutely do not own the syntax of the language, but want to understand its "flavor" without wasting too much time studying syntax.
The main feature of Prolog is that it can be easily read, but it is very difficult to write, which is fundamentally different from all mainstream languages, which they say to write has become even easier
How to read prolog programs correctly
Reading programs is very simple, since there are very few special characters and keywords in the language and they are easily translated into natural language. The main mistake of the programmer is that he wants to immediately imagine how the program works, and not to read what the program describes, so it seems to me to train the unmanned brain of an ordinary person, much easier than a programmer.
Concepts
In the language there are 2 concepts of predicates (conditions) and objects (they are variables and terms). Predicates express a certain condition, for example, an object is green or a number is simple; naturally, the conditions have input parameters. For example, green_object (Object) , prime_number (Number) . How many parameters are in the predicate, so is the arity of the predicate. Objects are terms, constants and variables. Constants are numbers and strings, variables express an unknown object, possibly the one you are looking for, and are denoted as strings with a capital letter. Let's leave the terms for now and consider the simplest program.
Program
A program is a set of rules, of the form If condition1 and condition2 and ... then the condition is true. Formally, these rules are combined through AND, but a contradiction cannot be obtained, since in Prolog there is no logical negation, and in the bundle of To, there can be only one predicate (condition).
A :- B_1, B_2. % : B_1 B_2, A
_() :- (), ().
% "" - , "" - _
As you can see the variable name has scope - this is the rule. Mathematically true, the rule is: for any variable - “Number”, if it is simple and odd, then it is simple_ odd. Similarly, you can rephrase as: If there is a “Number”, that it is odd and simple, then it is odd_simple. Therefore, the variable name is very important! If in the left part (to: -) replace Number by Number2, the rule changes the meaning: For any Number2 and Number, if Number is simple and odd, then Number2 is simple odd. It turns out all the numbers are simple_ odd! This is the most common mistake in Prolog.
A :- B_1, B_2. % : B_1 B_2, A _() :- (), (). % "" - , "" - _
A :- B_1, B_2. % : B_1 B_2, A _() :- (), (). % "" - , "" - _
Example - perfect numbers
_() :- (), ___(, ), (, ). _(1). (, ). ___(1, 1). ___(, ) :- _(, ), ____(, , ). ____(, 1, 1). ____(, , ) :- _(, ), _(, ), ____(, , ), (, , ). ____(, , ) :- __(, ), _(, ), ____(, , ).
_() :- (), ___(, ), (, ). _(1). (, ). ___(1, 1). ___(, ) :- _(, ), ____(, , ). ____(, 1, 1). ____(, , ) :- _(, ), _(, ), ____(, , ), (, , ). ____(, , ) :- __(, ), _(, ), ____(, , ).
For a start, let's formally read what the rules mean:
- If “H” is a number and for “H” and “Sum of Dividers” the condition of splinter_number is met, in other words, Sum of Dividers is the sum of divisors of the number “H”, and “H” is equal to “Sum of Dividers”, then “H” is a perfect number.
- 1 is a perfect number. Rules may have no conditions, in this case they are called facts.
- Every object "O" is equal to "O". In principle, there is a standard predicate "=", but you can completely replace it with your own.
- The fact sum_understanding_number 1 is equal to 1.
- If the sum of the dividers "Number" to the previous number "Number" is equal to "Sum", then this is the sum of dividers_non-number. Thus, it is expressed that the sum of divisors X is less than or equal to Y, since X is divided by X, therefore we take Y = X - 1.
- Next, 3 predicates determine the sum of divisors, a number less than or equal to Y (Divisor), 1st case Y equal to 1, 2nd case Number divided by Y, then divisor sum (X, Y) = divisor sum (X, Y-1) + Y , and 3rd case The number is not divisible by Y, then the divisor sum (X, Y) = the divisor sum (X, Y-1).
A program is like a set of definitions.
There is a second way to read these rules, less mathematical and more natural, based on "definitions". It can be noted that in Prolog all the rules on the left (in this part) contain only one condition, which in essence is the “definition” of this condition.
For example, the 1st rule is the definition of perfect numbers. “H” is a perfect number, when “H” the number and sum of dividers “H” is equal to “H”. Identical predicates are grouped by name by combining the condition “or”. That is, you can add to the definition: “H” is a perfect number, when .., or when “H” is 1.
This method of reading is widely used, as it allows you to combine predicates into homogeneous groups and helps to understand in what order the interpreter spins the predicates in order to
check the truth of some statement. For example, it is obvious that if a predicate does not have a single definition, then it is impossible to prove the truth of the statement with it. In example No. 1, the predicate “divides_ to” is not defined.
It is an interesting fact that in Prolog there are no cycles, no assignment of variables, no type declarations, and if we also recall the terms and clipping, then the language becomes algorithmically complete.
Terms
Terms have a recursive definition as a named collection of objects. Term = 'name' (object, object, ...), example person ('Name', 'Surname'), '+' (1, 2), person (address ('Some address'), surname (' Last name '), phone (' Phone ')) . If we consider a term as a mathematical concept, then a term is a function, more precisely, a functor, that is, '+' (1, 2) means that there is an object that is equal to 1 + 2. This absolutely does not mean that 1 + 2 = 3, in Prolog - this expression is untrue, just like in the group of residues modulo 2, there 3 does not exist at all. Again, from a mathematical point of view, Variables are connected by the word For All, and if a word is necessary in the statement, then a term (functor) is used for this purpose. For any number there is a factorial number: - factorial (X, fact (X)).
From a programming point of view, a term can be explained much more simply: a term is an object with a set of attributes, attributes can be other terms or constants or variables (that is, not defined). The main difference is that all objects in Prolog are immutable, that is, it is impossible to change the attributes in them, but there is a special state - a variable.
Example - integer arithmetic
(0). (()) :- (). (0, , ). ((1), 2, ()) :- (1, 2, ). (0, , 0). ((1), 2, 2) :- (1, 2, ), (, 2, 2).
(0). (()) :- (). (0, , ). ((1), 2, ()) :- (1, 2, ). (0, , 0). ((1), 2, 2) :- (1, 2, ), (, 2, 2).
- Determination of the nat property (natural number). 0 is a natural number, if a number is natural, then there is an object number (Number), which is also a natural. Mathematically, the term “number” expresses the function +1, from the point of view of programming “number” a recursive data structure, here are its elements: number (0), number (number (0)), number (number (number (0))).
- Attitude plus - 0 + Number = Number. If P1 + P2 = Res, then (P1 + 1) + P2 = (Res + 1).
- The ratio to multiply is 0 * Number = 0. If P1 * P2 = Res and Res + P2 = Res2, then (P1 + 1) * P2 = Res2.
Obviously, these statements are true for ordinary arithmetic, but why then we did not include the same obvious ones as Number + 0 = Number. The answer is simple: redundancy is very bad for any definition. Yes, it can help with calculations, a kind of premature optimization, but side effects can be contradictions in definitions, ambiguous conclusion of the statement, looping the interpreter.
How Prolog understands predicates and how it proves
Of course, reading programs helps to feel the Prolog style, but does not make it clear for what and how these definitions can be used. A full program, the examples above, can not be named because there is not enough input point. The entry point to Prolog is a query, an analogue of a query to a SQL database, or an analogue of a call to a main function in functional programming. Examples of queries: nat (Number) - find a natural number, plus (0, 0, Result) - find the result of adding 0 and 0 in the variable Result, nat (0) - check if 0 is a natural number, etc.
Of course, the results of the queries are not difficult to predict from logical considerations, but it is extremely important to understand how the program received them. Still, Prolog is not a black box, but a programming language, and unlike a database where a SQL plan is built and a query can be executed differently on different Databases, Prolog has a well-defined execution order. The fact is that in the Database we fully know what answer we want to get based on the data in the table, unfortunately looking at the Prolog program it is quite difficult to say which statements are logically deducible, therefore, it is much easier to understand how the Prolog works.
Consider the example query plus (0, 0, Result) :
1. We find a match (a kind of pattern-matching, resolution) of this request with the left part of one of the rules. For this query plus (0, Number, Number). Let us associate in turn all the arguments of the query with the rule and get: 0 = 0, 0 = Number, Result = Number. These variables involve 2 variables (Number and Result), deciding them we get that Number = Result = 0. Since this rule has no conditions, we received an answer to the question asked. Answer: yes and Result = 0.
Query nat (Number) :
1. We find the 1st coincidence with the rule, the nat (0) rule, solving the equations by correspondence, in simple terms finding the resolution, we get Number = 0. Answer: yes and Number = 0.
Request plus (Result, 0, number (0)) :
1. Find the resolution with the rule plus (0, Number, Number): Result = 0, 0 = Number, number (0) = Number, but (!) Number = 0 = number (0) - not possible because 0 matches the number (0). Hence we are looking for a resolution with the following rule.
2. Find the resolution with the rule plus (number (P1), P2, number (Res)), we get the number (P1) = Result, P2 = 0, number (Res) = number (0), from here Res = 0. This rules, there are conditions that we have to check, taking into account the results of the resolution (values of variables), plus (P1, P2, Res) -> plus (P1, 0, 0). Remember the value of the variables in the stack and form a new query plus (P1, 0, 0)
3 *. Solving the query plus (P1, 0, 0) we find the resolution with plus (0, Number, Number) and we get P1 = 0 and Number = 0.
4. Go back to the previous variables on the stack Result = number (P1) = number (0). Answer found number (0). Accordingly, now the prologue machine decided the equation X + 0 = 1.
Proper preparation of rules in the Prolog language is a very complicated thing, but if you compile them compactly, you can get not only direct answers and solutions, but also reverse ones.
Request example plus (Number, Number, Number) : answer yes, Number = 0.
Request example plus (0, 0, 0) : no answer, on the first attempt all resolutions are not met.
Request example plus (Number, Number, Number (Number)) : answer yes, Number = 1. Solution of the equation X + X = X + 1.
Try to multiply output (Number, number (0), number (0)), for this you will need to stack the variables 2 times and calculate the new query. The essence of the Prologue of the machine is such that you can refuse the 1st result, then the Prologue will return to the previous state and continue the calculation. For example, the query nat (Number) , first applies the 1st rule and returns 0, and then applies the 2nd rule + 1st rule and returns the number (0), you can repeat and get an infinite sequence of all natural numbers. Another example, query plus (Number, number (0), Number 2) , will produce a sequence of all pairs of the solution to the equation X + 1 = Y.
Conclusion
Unfortunately, the reasonable size of the topic did not allow me to get close to the main topic, namely, to solving complex logical problems in the Prolog language, without having a strategy to solve them. Large pieces of code on the Prologue can scare away not only beginners, but even experienced programmers. The purpose of this article is to show that programs in Prolog can be read in a natural way in a simple way, and also be executed by a simple interpreter .
The main feature of the Prologue is not a black box and not a library that solves complex logical problems, you can enter an algebraic equation in Mathematica and it will produce a solution, but the sequence of steps performed is unknown. The prolog cannot solve general logical problems (it lacks a logical “or” and “negation”), otherwise its conclusion would be non-deterministic as a linear resolution. The prologue is the golden mean, between a simple interpreter and a machine for proving theorems, a shift to either side leads to the loss of one of the properties.
In the next article I would like to tell you how the tasks of sorting, the sequence of transfusions, Miss Manners and other well-known logical problems are solved. For those who feel dissatisfied, I want to offer the following problem (who decided the first prize ):
Write a predicate that would generate an infinite sequence of natural numbers starting from 3. These should be standard numbers in the Prologue, operations on which are performed using the predicate is: X is 3 + 1 => X = 4.
Source: https://habr.com/ru/post/124636/
All Articles