Prolog is an amazing programming language

    - Why is he amazing? I know a couple of dozen languages ​​and it’s not a problem for me to learn another new one, I just don’t see the need.

    The prologue is unique. This 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 occurred for more than 20 years; this is probably the only such popular programming language that has no use in real programming. Why Prolog?

    The prologue is unique in nature, it appeared due to a happy coincidence (the mysterious structure of the world) Once, in the 60s, the theory of automatic proof of theorems developed very rapidly and Robinson proposed a resolution algorithm that allowed him to prove any valid theorem (derived 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 the theorem in a limited number of operations. In simple words, an algorithm is a bypass (in the general case of an infinite) graph in width, it is natural that the predictability of the algorithm is almost 0, respectively, for the Programming Language - this is absolutely not suitable. And at that 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 wide enough and 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 of interest to those who already own the Prolog syntax and want to understand it from the inside, as well as those who absolutely do not know the language syntax, but want to understand its “highlight” without spending too much time studying syntactic constructions.


    The main feature of Prolog is that it can be easily read, but it’s very difficult to write, which is fundamentally different from all mainstream languages ​​that say so, it became even easier one more step and you can write on the tablet, dragging work modules as friends on Google+, from this we all know the very quality of the code suffers. It seems that every line is understandable, but how the system works beyond comprehension, even for developers, as they say, was inspired. It seems to me that in all Prolog training books, they make the same mistake when starting a story about facts, relationships, queries, and a person develops a relationship to the language as an Expert System or Database. It is much more important to learn to read programs correctly and read like that with a dozen :)

    How to read prolog programs correctly


    Reading programs is very simple, because the language has very few special characters and keywords 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 read what the program describes, so it seems to me to train the foggy brain of an ordinary person is much simpler than a programmer.

    The concepts

    In the language there are 2 concepts of predicates (conditions) and objects (they are also variables and terms). Predicates express a condition, for example, an object is green or a prime number, it is natural that conditions have input parameters. For example green_object (Object) , prime_number (Number) . How many parameters are in the predicate, such is the arity of the predicate. Objects are terms, constants and variables. Constants - these are numbers and strings, variables - express an unknown object, possibly searched for, and are designated as strings with a capital letter. 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 it is impossible to obtain a contradiction, since there is no logical negation in the Prolog, and only one predicate (condition) can be present in the To link.

    A :- B_1, B_2. % правило читается как : Если B_1 и B_2, то A
    нечетное_простое(Число) :- простое(Число), нечетное(Число).
    % Если "Число" - простое и нечетное, то "Число" - нечетное_простое


    As you can see, the name of the variable has a 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 this: If there is a "Number" that it is odd and simple, then it is odd_simple. Therefore, the name of the variable is very important! If on the left side (before: -) you replace Number with Number2, then the rule will change the meaning: For any Number2 and Number, if Number is prime and odd, then Number2 is simple odd. It turns out all the numbers are prime_ odd! This is the most common mistake in the Prolog.

    A :- B_1, B_2.  % правило читается как : Если B_1 и B_2, то A 
    нечетное_простое(Число) :- простое(Число), нечетное(Число).
    % Если "Число" - простое и нечетное, то "Число" - нечетное_простое
    



    Example - Perfect Numbers

    совершенное_число(Ч) :- число(Ч), сумма_делителей_без_числа(Ч, СуммаДелителей), 
                равно(СуммаДелителей, Ч).
    совершенное_число(1).
    равно(Объект, Объект).
    сумма_делителей_без_числа(1, 1).
    сумма_делителей_без_числа(Число, Сумма) :- число_предыдущее(Число, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее).
    сумма_делителей_числа_до_числа(Число, 1, 1).
    сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- делится_на(Число, Делитель), 
                 число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, СуммаПред, Предыдущее),  сложить(СуммаПред, Делитель, Сумма).
    сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- не_делится_на(Число, Делитель), 
                число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее).
    



    To begin with, we formally read what the rules mean:
    1. If "H" is a number, and for "H" and "Sum of Dividers" the condition is sum_divisers_without_number, in other words, Sum of Divisors is the sum of dividers of the number "H", and "H" is equal to "Sum of Divisors", then "Ch" is a perfect number.
    2. 1 is a perfect number. Rules may not have conditions, in which case they are called facts.
    3. Every object “O” is equal to “O”. In principle, the standard predicate "=" exists, but you can completely replace it with your own.
    4. The fact that the sum_of_divisers_without number 1 is 1.
    5. If the sum of the dividers "Number" to the previous number "Number" is equal to "Sum", then this is the sum of dividers_without number. Thus, the sum of the divisors of X is less than or equal to Y, since X is divided by X, so we take Y = X - 1.
    6. Then 3 predicates determine the sum of the divisors, the number is less than or equal to Y (Divider), the 1st case Y is equal to 1, the 2nd case the Number is divided by Y, then the sum of the dividers (X, Y) = the sum of the dividers (X, Y-1) + Y , and the 3rd case, the Number is not divided by Y, then the sum_of dividers (X, Y) = the sum_of dividers (X, Y-1).


    A program - as a set of definitions

    There is a second way to read these rules, less mathematical and more natural, based on “definitions”. You can see that in the Prolog all the rules on the left (in part) contain only one condition, which in essence is a “definition” of this condition.
    For example, the first rule is the definition of perfect numbers. “H” is the perfect number when “H” is the number and the sum of the dividers “H” is “H”. Identical predicates are grouped by name, combined with the condition "or". That is, you can add to the definition: “H” is a perfect number when .., or when “H” is 1.

    This reading method is widely used, since it allows combining predicates into homogeneous groups and helps to understand in what order the interpreter spins predicates in order to
    verify the truth of a statement. For example, it is obvious that if a predicate has no definition, then it is impossible to prove the truth of a statement with it. In example No. 1, the predicate "divides_on" has no definition.

    An interesting fact is that in the Prolog there are no loops, no assignment of variables, no type declarations, and if you remember about terms and clipping, 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 the term as a mathematical concept, then the term is a function, or rather a functor, that is, '+' (1, 2) - means that there is such an object that is equal to 1 + 2. This absolutely does not mean that 1 + 2 = 3, in Prolog - this expression is not true, just like in the group of residues modulo 2, there 3 does not exist at all. Again, from a mathematical point of view, the Variables are connected by the word For Everyone, and if the statement requires the word exists, 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, you cannot 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).
    


    1. Determination of the properties of nat (natural number). 0 - a natural number, if the number is natural, then there is an object number (Number), which is also natural. Mathematically, the term "number" expresses the function +1, from the point of view of programming the "number" is a recursive data structure, here are its elements: number (0), number (number (0)), number (number (number (0))).
    2. Ratio plus - 0 + Number = Number. If Ch1 + Ch2 = Res, then (Ch1 + 1) + Ch2 = (Res + 1).
    3. The ratio is multiplied - 0 * Number = 0. If R1 * R2 = Res and Res + R2 = Res2, then (R1 + 1) * R2 = 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 the calculations, a kind of premature optimization, but side effects can be contradictions in the definitions, ambiguous conclusion of the statement, looping of the interpreter.

    How Prolog understands predicates and how it proves statements


    Of course, reading programs helps to feel the Prolog style, but it does not make clear why and how these definitions can be used. A full-fledged program, the examples given above, can not be called because there is not enough entry point. The entry point to the Prolog is a query, an analog of a query to an SQL database, or an analog 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, query results are not difficult to predict for logical reasons, but it is extremely important to understand how the program received them. Still, the Prolog is not a black box, but a programming language, and unlike the database where the SQL plan is built and the query can be performed differently on different Databases, the Prolog has a very specific execution order. The fact is that in the Database we quite 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 inferred, so it’s much easier to understand how the Prolog interpreter 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 request, plus (0, Number, Number). We correlate all the request arguments with the rule in turn and get: 0 = 0, 0 = Number, Result = Number. 2 variables participate in these equations (Number and Result), having solved them we get that Number = Result = 0. Since this rule has no conditions, we got the answer to the asked question. Answer: yes and Result = 0.

    Request nat (Number) :
    1. Find the 1st match with the rule, nat (0) rule, solving the equations by correspondence, in other words, finding the resolution, we get Number = 0. Answer: yes and Number = 0.

    Request plus (Result, 0, Number (0)) :
    1. We find a resolution with the rule plus (0, Number, Number): Result = 0, 0 = Number, number (0) = Number, but (!) Number = 0 = number (0) - it is not possible since 0 matches the number (0). Therefore, we are looking for a resolution with the following rule.
    2. We find the resolution with the rule plus (number (R1), R2, number (Res)), we obtain the number (R1) = Result, R2 = 0, the number (Res) = the number (0), hence Res = 0. This rules, there are conditions that we must check, taking into account the results of the resolution (values ​​of variables), plus (P1, P2, Res) -> plus (P1, 0, 0). We store the value of the variables on the stack and form a new request plus (Ч1, 0, 0)
    3 *. Solving the plus (Ch1, 0, 0) request, we find the resolution with plus (0, Number, Number) and we get Ch1 = 0 and Number = 0.
    4. We return on the stack to the previous variables Result = number (Ч1) = number (0). The answer is found number (0). Accordingly, the prologue machine has now solved the equation X + 0 = 1.

    Properly compiling rules in the Prolog language is a very complicated thing, but if you compose them compactly, you can get not only direct answers and solutions, but also inverse ones.

    Example request plus (Number, Number, Number) : answer yes, Number = 0.

    Example request plus (0, 0, 0) : no answer, at the first attempt all resolutions are not executed.

    Example request plus (Number, Number, Number (Number)) : answer yes, Number = 1. Solving the equation X + X = X + 1.

    Try to draw the output for multiply (Number, number (0), number (0)), for this you need to push variables 2 times into the stack and calculate a new query. The essence of the Prolog of the machine is that you can refuse the 1st result, then the Prolog will return to the previous state and continue the calculation. For example, the query nat (Number) , first applies the 1st rule and gives 0, and then applies the 2nd rule + 1st rules and gives the number (0), you can repeat and get an infinite sequence of all natural numbers. Another example, the query plus (Number, number (0), Number2) , will produce a sequence of all pairs of solutions to the equation X + 1 = Y.

    Conclusion


    Unfortunately, the reasonable size of the topic did not allow me to get to the main topic, namely to solve complex logical problems in the Prolog language, without having a strategy for solving them. Large chunks of Prolog code can scare away not only beginners, but even experienced programmers. The purpose of this article is to show that Prolog programs can be read in a natural language in a simple way , as well as executed by a simple interpreter .
    The main feature of the Prolog is not a black box or a library that solves complex logical problems. In Mathematica, you can enter an algebraic equation and it will give a solution, but the sequence of steps is unknown. The prologue cannot solve general logical problems (it lacks a logical “or” and “negation”), otherwise its conclusion would be non-deterministic as a linear resolution. A prologue is the golden mean, between a simple interpreter and a machine for proving theorems, a shift in any direction leads to the loss of one of the properties.

    In the next article I would like to tell how sorting problems are solved, about the sequence of transfusions, Miss Manners and other well-known logical problems. For those who feel unsatisfied I want to offer the following task (who decided the first prize ):
    Write a predicate that would generate an infinite sequence of natural numbers starting with 3. These should be standard numbers in Prolog, operations on which are performed using the predicate is: X is 3 + 1 => X = 4.

    Also popular now: