Developers Club geek daily blog

1 year, 6 months ago
Language of logical programming PROLOG (further – the PROLOGUE) is represented to most of programmers something confused and of little use for practical application. At the same time, the Internet is based on the symbolic information therefore practically all modern programmers face need to process character data structures, and for this purpose and language of logical programming the PROLOGUE is intended. This language – ideal for work with character structures, text files and for creation of intellectual programs.
After long-term work with the PROLOGUE, faced modern Haskell about which all authors it is proud speak – "a high threshold of entry". In my opinion, "height" of this threshold was formed as a result of the confused syntax and a heap of the built-in procedures. One more source of this "height" — arrogance of authors of the numerous manuals who are written so as if the reader never wrote programs.
At once a wish arose back, to a "native" PROLOGUE – simple and clear. I think if to explain without heaps, type of declarative semantics, time of entry into logical programming for the "normal" programmer will not exceed 30 minutes.
I will try to describe it from the point of view of procedural programming.
The PROLOGUE has two main differences from procedural languages — a method of the organization of calculations and a method of data representation. Both of these aspects of language radically differ from traditional programming languages. But we will not forget that logical programming is implemented by the same machines about a background — Neymanovsky architecture.
Let's imagine a programming language in which all operations are reduced to a challenge of procedures. At the same time each procedure exists in several options and the program itself selects to itself the option of implementation (body) of procedure, correct, more precisely, suitable for each specific option of basic data. As suitability – each procedure call is defined, during execution of the program, by results of procedure execution, receives logical value – TRUE or FALSE. Set of procedures with an identical name and arity is called a predicate.
Each predicate in the PROLOGUE language is identified by two parameters – a name and arity – the number of parameters. For example, the predicate of inverting of lists is identified as nrev/2, and a predicate of connection of lists as append/3. No declaration of parameters or variables is required, but it is possible to limit parameters to a pattern in procedure heading. For example, in one option of a predicate the first parameter can be specified as [] – the empty list, in another – as [A, B,C] – the list from three elements, and in the third as [H|T] – any non-blank list.
If any condition in a body of procedure is not satisfied, execution stops also a procedure call, more precisely, execution of the next option of a body of procedure, stops and receives FALSE value. In this case, the interpreter of language starts the option of a body of this procedure following one after another. If all options were unsuitable, there is a return to the previous procedure and for it there is also a search of options, thus, calculation in the PROLOGUE is reduced to tree traversal of an enclosure of procedures.
Return to the previous challenge is called a bektreking (backtracking). In essence it is rollback as all values received by variables in the cancelled procedure are cancelled. The Bektreking – the unique means of this language which does not have analogs in one of other mass programming languages. The Bektreking provides complete tree traversal of a logical output that provides a basis for a solution of intellectual tasks.

Algorithm of interpretation of the program (execution of the purpose) in the PROLOGUE system.

Input: purpose p (A1,A2,…, An)

1. To find in memory procedure for a name p with arity of n.
2. To unify input parameters of the purpose with heading of the found procedure.
3. If unification of parameters took place, to execute the first purpose of a body of the found procedure.
4. If unification did not take place, to find the following option of the P/n procedure.
5. If the following option of the P/n procedure is not found, to finish work with result of FAIL.
6. If the first purpose was executed, to pass to execution of the following purpose.
7. If the following purpose was not executed, to return to the previous purpose and to execute the following option of its implementation.
8. If the current option of implementation of the P/n procedure was not executed, to pass to the following option.
9. If all purposes are executed of a body of procedure, to finish work with result of TRUE.

Due to such structure of calculations each procedure call is called the purpose which can be reached or not. Any calculation in the PROLOGUE has logical value. Calculation is called still search of an output (proof), and the PROLOGUE language – language of logical programming.
Probably, syntactically the PROLOGUE – the simplest among programming languages. The main syntax procedure is the predicate – the expression similar to a procedure call — a name and the list of arguments –
P (x1, … xn). We write names from a small letter, and variables – with big.
If to lower parts, syntax of the PROLOGUE can be described as follows:

<ПРОЛОГ-предложение> ::= <правило> | <факт> | <запрос>
<правило> ::= <заголовок> ‘:-’<тело>
<факт> ::= <заголовок> ‘.’
<запрос> ::= <тело>‘.’
<тело> ::= <цель> /’,’<цель>/’.’
<заголовок>::= <предикат>
<цель>::= <предикат> |<выражение>
<предикат>::= <имя>/ ‘(‘<терм> /’,’<терм>/ ‘)’/
<терм>::= <атом> |<предикат>|<список>
<атом>::= <переменная> |<число> |<строка>|<имя>
<список>::= <список с заголовком>| <простой список>
<список с заголовком >::= ‘[‘ <терм >/’,’<терм>/’|’ < терм>’]’
< простой список>::= ‘[‘ <терм >/’,’<терм>/’]’|‘['’]’
<выражение>::= <терм> /<оператор><терм>/
<оператор>:: = ‘is’ | '=' | ‘==' | ’\=' | ’>=' |’ =<’ | ‘=\=' |

Apparently from syntax, in the PROLOGUE there are no reserved names except for a predicate of "is", though the different built-in predicates are applied to convenience and communication with external environment.

Example – the family relations.
Let's define rules for the relations – the spouse, the child, mother, the daughter, the brother, the descendant. The family relations are set by binary and unary predicates – rules (predicates with variables) and the facts (predicates with constants). It is easy to understand rules as the family relations are clear to all. For example, the first rule says: X is mother of Y if Y is the child X and X females.

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).

The facts describe relatives of a specific 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 rule set (program) can be applied to different sets of the facts (data).
The set of possible requests is defined by the existing rule set. The heading of each rule is a basis of creation of requests.
Requests can be two types – test and search.
Examples of search queries:
Whose daughter of Kat? – daughter (X, kat).
Whose grandson of Henry? — grandchild (X, henry)
Examples of test requests:
Dick – the child of Meri? – child (mery, dick).

Main concepts of the PROLOGUE: lists, recursion, unification, bektreking. Lists – the main data structure applied in this language. Lists are a basis for the organization of all difficult calculations. One of the main properties of the list – lack of restrictions for elements and the size of the list. The enclosure of lists is also limited to nothing. The list in language is treated as structure from two elements – "head" and "tail". This separation is a basis of calculations over lists therefore the most often applied pattern of the list has an appearance [H|T].
The first element of the list can have any structure, and the second – is also the list. The empty list does not contain elements and is designated as [].
The second basic structural unit of language – a predicate has an appearance — p (A1,A2.). Predicates are convenient for grouping of data in one unit of meaning. Unlike the list, the amount of arguments of a predicate is fixed. The name of a predicate is written from a small letter, as well as all constants in 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] – not the empty list;
[] – empty list;
[A1,A2,A3] – the list from three any elements;
[A, A, A|T] – the list in which the first three elements match;
[x, 10|T] – the list in which the character constant is on the first place "x", and on the second – a numerical constant 10.
Recursiveness of structure of the list is an important element of the organization of recursive calculations. Recursive predicates have not less than two procedures – one for the general case, another – for end.
Recursiveness of lists provides a possibility of the simple formulation of algorithm of operations over lists.
Example: Calculation of length of the list.

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

Example: Inverting of the list.

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

In the PROLOGUE there are no functions therefore it is impossible to insert, for example, length of the length (L) list as argument as it becomes in all procedural languages.
At the same time, PROLOG it is possible to consider as quite imperative language in which all operations, except for a betreking, register obviously.
Unification at first sight enters a certain mysteriousness and incomprehensibility to language, but it has quite procedural explanation.
Unification is a substitution of parameters in a pattern and is applied not only to selection of input parameters, but also to automatic selection of the necessary elements of the list and a manipulation by them – adding and removals of a head element of the list.
Example: connection of 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 of [H1|T1] as the second argument has to be the list, but it will complicate a predicate as the second argument can be also the empty list.
Variables in the PROLOGUE – logical, i.e. repeated unification in one procedure is impossible. It is impossible to write L = [a, b, c], and then — L=[12]. Logicality of variables leads to unification complication as all unification in a body of one procedure cannot be reviewed in computation process, so, they cannot contradict each other.
Unification of logic variables leads to unexpected effects which have quite imperative explanation.
Example: options of use of a predicate of connection of lists.
Connection:

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

Connection test of lists:

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

Decomposition of the list:

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 character ";" means request of other candidate solution by start of a bektreking.

Subtraction of lists:

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

In the PROLOGUE it is accepted to distinguish calculations with a bektreking (nondeterministic) and without it (determined).
Example of a nondeterministic predicate: Solution of a numerical puzzle.

/*
D O N A L D
+
G E R A L D
— R O B E R T */

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,
With 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 of sum/3 executes the main operation of selection of values of digits for the set alphabetic formula. Calculation is carried out for the addition formula of two numbers of any length. In the presence of the known digits it is possible to insert them instead of variables. If length of composed is different, it is possible to insert zero at the beginning of the corresponding list.
The predicate of sum1/8 uses the first three arguments for record of result, arguments at number 4,5,6 – as working variables, the seventh argument – starting value of discharge of transfer, the eighth argument – the list of admissible values of digits.
The predicate of dl/3 executes the choice and removal of the last element of the list of variables.
The predicate of val/3 selects admissible value from the list of the remained options, at the same time the selected digit option, is removed from the list of admissible options.
If the value option for the next letter was established earlier, then it remains without changes.
The predicate of sd/5 checks option of the set three of digits of one column:

A+B+Ii = C+Io*10

If sd/5 is not executed, there is a bektreking — the last from challenges of a predicate of val/3 appropriates new variable value of E3. If any of E3 values did not approach, the bektreking proceeds on a step backwards — for E2 new value is selected, then – if any E3 E2 option, is not suitable for E1.
The predicate of sum1/8 is executed recursively before exhaustion of the input list of variables.
s/0 predicate – an example of a challenge of a predicate of sum/3 for a solution of one option of a puzzle.
Apparently from an example, the program on the PROLOGUE can be very compact, at the same time the algorithm is simple and transparent as no implicit challenges of functions are used.

It is possible to develop the program of a solution of such puzzles, for example, to make it universal – for all types of numerical rebuses, to improve input of basic data.
For this purpose it is necessary to do such operations as lexical and parsing. We will consider these operations in the second part.

This article is a translation of the original post at habrahabr.ru/post/274603/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus