📜 ⬆️ ⬇️

PROLOG for programmers

The logic programming language PROLOG (hereinafter - the PROLOGUE) seems to most programmers to be something confusing and unsuitable for practical use. At the same time, the Internet is based on symbolic information, therefore almost all modern programmers are faced with the need to process symbolic data structures, and after all, the logic language PROLOG is intended for this. This language is ideal for working with character structures, text files and for building intelligent programs.
After many years of working with the PROLOG, I ran into the new-fangled Haskell, about which all authors proudly say - “high threshold of entry”. In my opinion, the “height” of this threshold was formed as a result of confusing syntax and clutter of embedded procedures. Another source of this “height” is the arrogance of the authors of numerous manuals, which are written as if the reader never wrote programs.
I immediately wanted to go back, to the “native” PROLOGUE - simple and understandable. I think if you explain without piling up, such as declarative semantics, the time of entry into logic programming for the "ordinary" programmer will not exceed 30 minutes.
I will try to describe it in terms of procedural programming.
PROLOGUE has two main differences from procedural languages ​​- the method of organizing calculations and the way of presenting data. Both of these aspects of the language are fundamentally different from traditional programming languages. But let's not forget that logic programming is implemented on the same machines with the background - Neuman architecture.
Imagine a programming language in which all operations are reduced to a procedure call. Moreover, each procedure exists in several variants and the program chooses for itself the correct, or more precisely, variant implementation (body) of the procedure that is suitable for each specific variant of the initial data. How suitability is determined - each procedure call, during the execution of the program, according to the results of the procedure execution, gets a logical value - TRUE or FALSE. A set of procedures with the same name and arity is called a predicate.
Each predicate in the PROLOG language is identified by two parameters — a name and an arity — the number of parameters. For example, the predicate for inverting lists is identified as nrev / 2, and the predicate for joining lists as append / 3. No declaration of parameters or variables is required, but you can limit the parameters to a pattern in the procedure header. For example, in one variant of the predicate, the first parameter can be specified as [] - an empty list, in the other - as [A, B, C] - a list of three elements, and in the third one as [H | T] - an arbitrary non-empty list.
If some condition in the procedure body is not met, the execution is terminated and the procedure call, more precisely, the execution of the next variant of the procedure body, is terminated and gets the value FALSE. In this case, the language interpreter launches the next in order version of the body of this procedure. If all the options turned out to be unsuitable, a return to the previous procedure occurs and for it the selection of options also occurs, thus, the calculation in the PROLOGUE is reduced to bypassing the procedure nesting tree.
Returning to the previous call is called backtracking. In essence, this is a rollback, since all values ​​received by the variables in the canceled procedure are canceled. Backtracking is a unique tool of this language, which has no analogues in any of the other mass programming languages. Backtracking provides a complete traversal of the inference tree, which provides the basis for solving intelligent tasks.

Algorithm of program interpretation (goal fulfillment) in the PROLOG system.

Input: target p (A1, A2, ..., An)
')
1. Find in memory a procedure named p with the arity n.
2. Unify the input parameters of the target with the header of the procedure found.
3. If the unification of parameters has passed, perform the first goal from the body of the procedure found.
4. If the unification fails, find the next variant of the P / n procedure.
5. If the next variant of the P / n procedure is not found, finish the job with the result FAIL.
6. If the first goal is fulfilled, go to the next goal.
7. If the next goal is not fulfilled, return to the previous goal and execute the next variant of its implementation.
8. If the current implementation of the P / n procedure fails, go to the next option.
9. If all targets from the procedure body are completed, finish the work with the result TRUE.

In connection with such a structure of calculations, each procedure call is called a goal, which can be achieved or not. Every calculation in the PROLOGUE has a logical value. Computation is also called the search for inference (proof), and the PROLOGUE is called the logic programming language.
Probably syntactically PROLOGUE is the easiest programming language. The main syntax is a predicate - an expression similar to a procedure call - a name and a list of arguments -
P (x1, ... xn). Names are written with a small letter, and variables - with a large one.
If you omit the details, the syntax of the PROLOGUE can be described as follows:

<PROLOGUE>> = = rule> | <fact> | <request>
<rule> :: = <header> ': -' <body>
<fact> :: = <header> '.'
<query> :: = <body> '.'
<body> :: = <target> / ',' <target> / '.'
<heading> :: = <predicate>
<target> :: = <predicate> | <expression>
<predicate> :: = <name> / '(' <<term> / ',' <term> / ')' /
<term> :: = <atom> | <predicate> | <list>
<atom> :: = <variable> | <number> | <line> | <name>
<list> :: = <list with heading> | <simple list>
<list with title> :: = '[' <term> / ',' <term> / '|' <term> ']'
<simple list> :: = '[' <term> / ',' <term> / ']' | '[' ']'
<expression> :: = <term> / <operator> <term> /
<operator> :: = 'is' | '=' | '==' | '\ =' | '> =' | '= <' | '= \ =' |

As can be seen from the syntax, there are no reserved names in the PROLOGUE except for the predicate “is”, although various built-in predicates are used for convenience and connection with the external environment.

An example is family relationships.
We define the rules for relationships - spouse, child, mother, daughter, brother, descendant. Family relationships are given by binary and unary predicates - rules (predicates with variables) and facts (predicates with constants). The rules are easy to understand, since family relationships are clear to everyone. For example, the first rule is: X is the mother of Y if Y is a child of X and X is female.

mother (X, Y): - child (X, Y), female (X).
daughter (X, Y): - child (Y, X), female (X).
grandchild (X, Y): - child (X, Z), child (Z, Y).
descendant (X, Y): - child (X, Y).
descendant (X, Y): - grandchild (X, Z).

Facts describe relatives of a particular family.

marrow (john, meri). female (meri).
child (john, jack). child (meri, jack). child (john, kate).
marrow (jack, joan). marrow (kate, dick).
child (jack, henry). child (kat, josh).
male (john). female (mery).
male (henry). female (joan).
male (josh) male (dick).

One set of rules (program) can be applied to different sets of facts (data).
The set of possible requests is determined by the existing set of rules. The title of each rule is the basis for building queries.
Requests can be of two types - verification and search.
Examples of search queries:
Whose daughter is Kat? - daughter (X, kat).
Whose grandson is Henry? - grandchild (X, henry)
Examples of verification requests:
Dick is Meri's baby? - child (mery, dick).

The main concepts of the PROLOGUE: lists, recursion, unification, backtracking. Lists are the basic data structure used in this language. Lists are the basis for the organization of all complex calculations. One of the main properties of the list is the absence of restrictions on the elements and size of the list. The nesting of lists is also not limited by anything. The list in the language is interpreted as a structure of two elements - "head" and "tail". This division is the basis for the computation of lists, so the most commonly used list pattern is [H | T].
The first list item can have any structure, and the second one is also a list. An empty list contains no elements and is denoted as [].
The second basic structural unit of the language - the predicate has the form - p (A1, A2, ..). Predicates are convenient for grouping data into one sense unit. Unlike the list, the number of predicate arguments is fixed. The name of the predicate is written with a small letter, like all constants in the language.
Variables always begin with a capital letter. On the basis of variables it is possible to build patterns for lists.

Examples of list patterns:
[H | T] is not an empty list;
[] - empty list;
[A1, A2, A3] - a list of three arbitrary elements;
[A, A, A | T] - a list in which the first three elements are the same;
[x, 10 | T] is a list in which the symbolic constant “x” is in the first place, and the second is the numeric constant 10.
The recursiveness of the list structure is an important element in the organization of recursive calculations. Recursive predicates have at least two procedures — one for the general case, the other for the completion.
Recursiveness of lists provides the possibility of a simple formulation of the algorithm for operations on lists.
Example: Calculating the length of a list.

length ([H | T], N): - length (T, N1), N is N1 + 1.
length ([], 0).

Example: Invert list.

nrev ([H | T], L): - nrev (T, L1), append (L1, [H], L).
nrev ([], []).

There are no functions in PROLOGUE; therefore, it is impossible to insert, for example, the length of the list length (L) as an argument, as is done in all procedural languages.
At the same time, PROLOGUE can be considered as a completely imperative language, in which all operations, with the exception of betrecking, are explicitly prescribed.
Unification at first glance introduces some mystery and incomprehensibility into the language, but it has a completely procedural explanation.
Unification is the substitution of parameters into a pattern and is used not only to select input parameters, but also to automatically select the necessary list items and manipulate them - add and delete the head element of the list.
Example: join lists.

append ([H | T], L, [H | L2]): - append (T, L, L2).
append ([], L, L).

It would be more correct to write the second argument in the form [H1 | T1], since the second argument should be a list, but this will complicate the predicate, since the second argument can be an empty list.
Variables in the PROLOGUE are logical, i.e. re-unification within one procedure is impossible. You cannot write L = [a, b, c], and then L = [12]. The consistency of variables leads to the complication of unification, since all unifications in the body of a single procedure cannot be revised during the calculation process, which means that they cannot contradict each other.
The unification of logical variables leads to unexpected effects that have a completely imperative explanation.
Example: use case for list join predicate.
Compound:

append ([a, b, c], [d, e, f], L).
L = [a, b, c, d, e, f] =>
yes.

Check connection lists:

append ([a, b, c], [1,2,3], [a, b, c, 1,2,3]).
yes.

List decomposition:

append (L1, L2, [a, b, c]).

L1 = [a, b, c]
L2 = [] ->;

L1 = [a, b]
L2 = [c] ->;

L1 = [a]
L2 = [b, c] ->;

L1 = []
L2 = [a, b, c] ->;
no.

Here, the symbol “;” means a request for another solution by running backtracking.

Subtract lists:

append ([a, b], L, [a, b, c, d]).
L = [c, d].

In the PROLOGUE, it is customary to distinguish calculations with backtracking (non-deterministic) and without it (deterministic).
Example of a non-deterministic predicate: Solving a numerical puzzle.

/ *
DONALD
+
Gerald
- ROBERT * /

sum (L1, L2, L3): -
sum1 (L1, L2, L3, L1, L2, L3.0, [0,1,2,3,4,5,6,7,8,9]).

sum1 (L1, L2, L3, L11, L12, L13, Ii, Lv): -
dl (L11, L111, E1),
dl (L12, L121, E2),
dl (L13, L131, E3),
val (E1, Lv, Lv1), val (E2, Lv1, Lv2), val (E3, Lv2, Lv3),
sd (E1, E2, E3, Ii, Io),
sum1 (L1, L2, L3, L111, L121, L131, Io, Lv3).

sum1 (L1, L2, L3, [], _, _, 0, _): -! ..

dl ([H | T], [H | T1], E): - dl (T, T1, E).
dl ([H], [], H).

val (E, L, L): - nonvar (E).
val (E, L1, L2): - del (E, L1, L2).

sd (A, B, C, Ii, Io): -
C1 is A + B + Ii,
C is C1 mod 10,
Io is C1 // 10.

del (E, [E | T], T).
del (E, [H | T], [H | T1]): - del (E, T, T1).

s: -
A1 = [D, O, N, A, L, D],
A2 = [G, E, R, A, L, D],
A3 = [R, O, B, E, R, T],
sum (A1, A2, A3),
write (A1), nl,
write (A2), nl,
write (A3), nl.

The predicate sum / 3 performs the basic operation of selecting the values ​​of numbers for a given letter formula. The calculation is carried out for the formula of adding two numbers of any length. If there are known digits, you can insert them instead of variables. If the length of the items is different, you can insert zeros at the beginning of the corresponding list.
The predicate sum1 / 8 uses the first three arguments to record the result, the arguments numbered 4,5,6 as working variables, the seventh argument the initial value of the hyphenation digit, the eighth argument the list of valid digits.
The dl / 3 predicate selects and removes the last item from the list of variables.
The predicate val / 3 selects a valid value from the list of remaining options, and the selected digit option is removed from the list of valid options.
If the variant of the value for the next letter was established earlier, then it remains unchanged.
The predicate sd / 5 checks the variant of a given triple of digits of one column:

A + B + Ii = C + Io * 10

If sd / 5 is not executed, backtracking occurs — the last of the calls to the predicate val / 3 assigns the new value to the variable E3. If none of the values ​​of E3 come up, backtracking goes one step back - a new value is selected for E2, then - if no other E3 E2 variant is suitable, for E1.
The predicate sum1 / 8 is executed recursively until the input list of variables is exhausted.
Predicate s / 0 - an example of calling sum / 3 predicate to solve one variant of the puzzle.
As can be seen from the example, the program on the PROLOGE can be very compact, and the algorithm is simple and transparent, since no implicit function calls are used.

It is possible to develop a program for solving such puzzles, for example, to make it universal - for all types of numerical puzzles, to improve the input of initial data.
To do this, you need to do such operations as lexical and syntactic analysis. These operations will be considered in the second part.

Source: https://habr.com/ru/post/274603/


All Articles