Prolog, introduction

A rather lively discussion of the previous article ( http://habrahabr.ru/blogs/programming/47416/ ) showed that the prologue topic was of interest to the community.
In order to interest the reader even more and at the same time make it easier for him to start working with this language, I decided to write some initial data on the prologue.

Briefly main features.

Data types
')
Numbers

?- A = 12, B = -0.5e4. A = 12, B = -5000.0. ?- number ($ A ), number ($ B ). true . % , - 

Immediately you need to make an important reservation. All variables (unknowns) are denoted with a capital letter .

Atoms

?- A = abc , B = 'Hello World' . A = abc , B = 'Hello World' . ?- atom ($ A ), atom ($ B ). true . % , - 

Strings

?- S = " " . S = [1055, 1088, 1080, 1074, 1077, 1090, 32, 1084, 1080|...]. 

It is seen that the lines are lists of character codes, i.e. all the same operations apply to them as to the lists, but more on that later.

Lists

?- A = [], B = [ a , foo , 123, [[[[[1,2,42]], bar ]]], "" , A ], C = [ A , B ]. A = [], % B = [ a , foo , 123, [[[[[1|...]], bar ]]], [1055, 1088, 1080, 1074|...], []], C = [[], [ a , foo , 123, [[[[...]|...]]], [1055, 1088|...], []]] 

We see that the lists
1) may be heterogeneous (contain any combination of the above (and below-) listed types)
2) can be nested

Structures

?- A = aaa ( bb ), B = aaa ( bbbbbb , 123, [456, c ]), C = ccc ( ddd ( eee ), fff , g ( h ( i ( j ( kkkkk ))))). A = aaa ( bb ), B = aaa ( bbbbbb , 123, [456, c ]), C = ccc ( ddd ( eee ), fff , g ( h ( i ( j ( kkkkk ))))) 

An example is more meaningful:

?- Family = family ( father ( bill , age (37)), mother ( ann , age (34)), children ([ son ( john , age (10)), daughter ( jill , age (8))])). Family = family ( father ( bill , age (37)), mother ( ann , age (34)), children ([ son ( john , age (10)), daughter ( jill , age (8))])) 

Examples are more complicated:

?- A = aaa ( foo , bar , "" , [12, 13], 123.4e34), B = bbb ( cc , A , [ A , fff ( A )]), C = foo ( foo ( foo ( foo ( bar )))), D = (+(2, *(3, -(7, 2)))). A = aaa ( foo , bar , [1072, 1073, 1074], [12, 13], 1.234e+036), B = bbb ( cc , aaa ( foo , bar , [1072, 1073, 1074], [12, 13], 1.234e+036), [ aaa ( foo , bar , [1072, 1073, 1074], [12, 13], 1.234e+036), fff ( aaa ( foo , bar , [1072, 1073, 1074], [12, 13], 1.234e+036))]), C = foo ( foo ( foo ( foo ( bar )))), D = 2+3* (7-2) ?- C = cc (1, C ), cc (1, cc (1, B )) = C , C = B . % B C = cc (1, **), % , B = cc (1, **).

The structure in the prolog is represented by a functor (the name of the structure, what's up to the brackets) and parameters (what's in the brackets). The number of parameters is called the arity of the functor.
As you can see, the structure can also be nested.
The last request may not be completely clear, but should become clear in the process of reading the article.

Note that between these types there is a deep connection, for example, lists are nothing but the more beautiful (syntactic sugar) use of the functor "."

?- A = (.(1,.(2, .( aa , .( bbb , []))))). A = [1, 2, aa , bbb ]. 

Looking ahead to say that you can break the list on the head and tail

?- [ a , b , c , d ] = (.( H , T )). H = a , T = [ b , c , d ]. 

Although no one does this, in view of the fact that to construct lists from the head and tail (as well as the inverse transformation, i.e. separation of the list into head and tail) there is a more convenient syntax of the form [H | T].

?- [ a , b , c , d ] = [ H | T ]. H = a , T = [ b , c , d ]. ?- Head = , Tail = [, , , , , , , , ], List = [ Head | Tail ]. Head = , Tail = [, , , , , , , , ], List = [, , , , , , , , |...]. ?- A = [ a | [ b | [ c | [ d | [] ] ] ] ]. % haskell , ? ) A = [ a , b , c , d ]. ?- [ A , B , C | Tail ] = [1,2,3,4,5,6]. A = 1, B = 2, C = 3, Tail = [4, 5, 6]. 

The syntax equivalence can be confirmed by a query.

?- [ H | T ] = (.( H , T )). true . % .. H T . 

As you can see, at first glance, the not quite familiar behavior of the "=" sign appears here, namely that it works "in both directions". And this is a very important point. The fact is that in the prologue the sign "=" denotes not the usual (imperative) equality (assignment), but unification (which in other languages is called pattern matching), but the left and right part matching and, in the case of a successful comparison, specification of unknown values .
The phrase may look a bit abstruse, it is easier to explain with an example.

?- aaa = bb . false . % ( ) ?- aaa = aaa . true . % ?- aaa ( bbb ) = aaa ( bbb ). true . % ( ) ?- aaa ( bbb ) = aaa ( B ). B = bbb . % + ?- aaa ( bbb ) = aaa ( B , C ). false . % , , B ?- aaa ( bbb , C ) = aaa ( B , ccc (1)). C = ccc (1), B = bbb . % + ?- [1,2] = [1,2,3,4]. false . % ?- [1,2 | T ] = [1, B ,3,4]. T = [3, 4], B = 2. % + 

Having dealt a bit with the concept of unification, it becomes clear why

?- A = 2, A = 5. false . 

After completing the first unification, the prologue system associates unknown A with the number 2. Thus, the second unification will be nothing but 2 = 5, i.e. comparison of numbers 2 and 5 which of course will end in failure since the numbers are not equal. Thus, in a prolog, variables can be specified only once (for this reason, for example, attempts of imperative programming like N = N + 1 in the prolog do not make sense, this is usually done through recursion).
To accurately understand the meaning of the last query, it is necessary to clarify the meaning of the functor ",". Yes, don't be surprised, "" this is really a functor (namely, an infix operator with arity 2). You can verify this by running queries.

?- call ((,), A = 2, A = 5). false . 

but

?- call ((,), A = 2, A = B ). A = 2, B = 2 

which is equivalent to

?- A = 2, A = B . A = 2, B = 2. 

there is no contradiction here, and the system simply specifies the meanings of the unknowns.

However, we were distracted. The operator "," means nothing more than a logical "AND". It is clear that if we tell the system that a certain number is equal to 2 and (at the same time) it is equal to 5, then we, obviously, are the times, of which the system informs us. For logical "OR" operator ";" is provided.

?- A = 2; A = 5. A = 2 ; A = 5. 

Actually, the response of the system is not surprising. She answered exactly what we told her, namely that the unknown number is either 2 or 5.

However, if we specify our request (an unknown number is either 2 or 5 and at the same time it is even), then the response of the system will gain unambiguity

?- ( A = 2; A = 5), A mod 2 = : = 0. A = 2 ; false . 

Observant may ask, what then is false at the end - did unification really fail? Here we come to the second feature of the prologue, which is not peculiar to almost any other programming language (except Mercury =)), namely backtracking or, if to say in Russian, bust with return. Specifically for the last example, the system argues as follows - let's say A = 2, check for A mod 2 =: = 0 - this is done -> matching is successful - specification is performed (A = 2), then rollback (return) to the first part of the statement takes place and hypothesis A = 5 is checked, it crashes and therefore the system shows false.
Looking ahead, I note that you can cancel the return (after the first successful match) with the help of the clipping operator "!"

?- ( A = 2; A = 5), A mod 2 = : = 0, ! . A = 2. % 

Let's try to do an arithmetic calculation.

?- A = 2 + 3 * 5. A = 2+3*5. 

here we are in for confusion. It turns out that the system perceives arithmetic operations as an ordinary combination of functors (however, observant ones could notice this higher). Really request

?- A + B * C = (+( A , *( B , C ))). true . 

shows that it is. What then to do? However, it turns out that there is a special predicate is / 2 (“/” usually denotes the arity of a predicate), which performs an arithmetic operation.

?- A = 2 + 3 * 5, B is A . A = 2+3*5, B = 17. 

or simply

?- B is 2 + 3 * 5. B = 17. 

So far we have been working interactively to “taste” the prologue to the taste. Usually, prolog programs, like programs in any other language, are a file with the text of a program. It is common practice to download this file to an interactive environment using the consult ('file') command. (or its syntactic sugar - [file].) and subsequent requests to the program, i.e. to the facts and predicates in it certain.
A prolog machine using the 2 basic mechanisms described above (unification with specification + backtracking) calculates the necessary result.

A prologue program is usually a collection of facts and predicates. More on these concepts.
The fact is a certain relationship, or rather a copy of such a relationship, for example

% dog ( sharik ). % , - dog ( tuzik ). % --//-- % cat ( pushok ). cat ( druzgok ). % hamster ( pit ). % man ( bill ). man ( george ). man ( barak ). man ( platon ). man ( sokrat ). % woman ( ann ). woman ( kate ). woman ( pam ). % dead ( sharik ). dead ( platon ). dead ( sokrat ). % age ( sharik , 18). % - 18 age ( tuzik , 10). % --//-- age ( pushok , 5). age ( druzhok , 2). age ( bill , 62). age ( george , 62). age ( barak , 47). age ( sokrat , 70). age ( platon , 80). age ( ann , 20). age ( kate , 25). age ( pam , 30).

Predicates, on the other hand, are relations that are accompanied by some additional conditions (something like: “the relationship is valid if the following conditions are met ...”). These same conditions are written through the operator ": -". Let us write some predicates for our database of facts.

% animal ( X ) :- dog ( X ); % cat ( X ); % hamster ( X ). % % : X - , X - , - , - . % human ( X ) :- man ( X ); % woman ( X ). % % ( ) living ( X ) :- animal ( X ); human ( X ). % ( ) alive ( X ) :- living ( X ), \+ dead ( X ). % old ( X ) :- ( animal ( X ) -> age ( X , Age ), Age > = 10 % , 10 - ; human ( X ), age ( X , Age ), Age > = 60 % , 60 - ), \+ dead ( X ). % , - % - - young ( X ) :- alive ( X ), \+ old ( X ).

It is useful to note that fact is in fact also a kind of predicate, moreover, the above 3 facts of a woman (...) can be written by one predicate

woman ( X ) :- X = ann; X = kate; X = pam . 

or even

woman ( X ) :- member ( X , [ ann , kate , pam ]). 

but still, for reasons of expressiveness, facts should be applied where it is logical.

Requests to the system, familiar with the given program:

1 ?- human ( ann ). true . ?- human ( tuzik ). false . ?- human ( Who ). Who = bill ; Who = george ; Who = barak ; Who = platon ; Who = sokrat ; Who = ann ; Who = kate ; Who = pam . 

Or so (get a list immediately):

?- bagof ( H , human ( H ), Humans ). Humans = [ bill , george , barak , platon , sokrat , ann , kate , pam ]. ?- alive ( sokrat ). false . ?- alive ( pit ). true . % ?- young ( Y ). Y = pushok ; Y = druzgok ; Y = pit ; Y = barak ; Y = ann ; Y = kate ; Y = pam . % ?- young ( H ), man ( H ). H = barak ; false . 

And even

% , 2 ?- living ( X ), living ( Y ), age ( X , AgeX ), age ( Y , AgeY ), AgeX = : = 2 * AgeY . X = tuzik , Y = pushok , AgeX = 10, AgeY = 5 ; X = ann , Y = tuzik , AgeX = 20, AgeY = 10 ; false . 

I would like to especially note how the prologue predicates differ from the functions (methods) of an imperative language.
Firstly, they can, in the general case, be “multi-input”, which is a direct consequence of the properties of the unification concept considered, and secondly, they can “return simultaneously a whole set of values”, which is a consequence of backtracking (it’s more correct to say that a predicate can leave several return points).
Indeed, consider the trivial predicate.

same ( A , B ) :- A = B . 

This predicate allows actually 3 ways of application:

% ?- same ( A , abc ). A = abc . % ?- same ( abc , A ). A = abc . % ?- same ( abc , abc ). true . ?- same ( abc , aaa ). false . 

note also that this predicate can be written as a fact:

same ( A , A ). 

A more illustrative example in this regard is the append predicate (addition of lists).

% 8 ?- append ([ a , b ], [ c , d , e ], L ). L = [ a , b , c , d , e ]. % ?- append ( L1 , [ c , d , e ], [ a , b , c , d , e ]). L1 = [ a , b ] ; false . ?- append ([ a , b ], L2 , [ a , b , c , d , e ]). L2 = [ c , d , e ]. % , [ a , b , c , d , e ] [ a , c ] ?- append ([ a , c ], L2 , [ a , b , c , d , e ]). false . % ?- append ( " " , "" , " " ). true . ?- append ( " " , "" , " Habrahabr" ). false . % , ?- append ( L1 , L2 , [ a , b , c ]). L1 = [], L2 = [ a , b , c ] ; L1 = [ a ], L2 = [ b , c ] ; L1 = [ a , b ], L2 = [ c ] ; L1 = [ a , b , c ], L2 = [] ; false . % ?- B = [ c , c , c , separator , d , d , separator , e , e , e , e ], append ( L1 , [ separator | L2 ], B ). B = [ c , c , c , separator , d , d , separator , e , e |...], L1 = [ c , c , c ], L2 = [ d , d , separator , e , e , e , e ] ; B = [ c , c , c , separator , d , d , separator , e , e |...], L1 = [ c , c , c , separator , d , d ], L2 = [ e , e , e , e ] ; false .

And all this using only one predicate!

To summarize, it can be noted that the program on the prologue is at the same time a database (not a relational one, of course, but allowing virtually any functional dependency) (facts) and the query infrastructure to this database (predicates), which allows to build new data from the database relationships, dependencies, or get some result associated with the data (however, the facts may be absent).
At the same time, the queries themselves (predicates) are able to have rather intricate logic or even perform computational tasks. To finally plunge the reader, we add that predicates can dynamically generate facts and even other predicates. The difference from the imperative programming paradigm that is probably familiar to the reader is in the declarative essence of the programs obtained.
The reverse side of this flexibility of the concept, of course, is the speed (which the commentators of the previous post on the prologue rightly pointed out, although the commercial implementations of the prolog have quite good performance).
However, the seductive side of this approach is the possibility of extremely expressive (albeit perhaps not fast) solving symbolic calculations, text parsing and complex data structures (including grammars), search tasks, expert systems, artificial intelligence tasks on the prologue. .

One day, while walking across the expanses of the refal community site (another interesting programming language, sometimes ideologically echoing the prologue), I came across a comparison between Refal and Java using the example of solving a specific problem http://wiki.botik.ru/Refaldevel / ForJavaProgrammer (the original source itself is here http://nuclight.livejournal.com/111696.html ). For interest, I wrote the solution on the prologue (the writing took ~ 10 min).

ischar ( H , [ H ]). % . matches ([], []) :- ! . % , "?" % "" matches ([ H | T ], [ H1 | T1 ]) :- ( H = H1 ; ischar ( H , "?" ) ), matches ( T , T1 ), ! . matches ([ H | T ], T1 ) :- ischar ( H , "*" ), % , * append ( _ , T2 , T1 ), % T2 T1 matches ( T , T2 ), ! . % 

and verification (I omit the rest of the test cases due to the fact that very long lines burst the page of the site)

check :- matches ( "ASDFAASDASDAAASDASDASD" , "ASDFAASDASDAAASDASDASD" ), matches ( "*" , "ASDFAASDASDAAASDASDASD" ), matches ( "A?DF?A*ASD*ASDA?DASD" , "ASDFAASDASDAAASDASDASD" ), \+ matches ( "ASDFAASDADAAASDASDASD" , "ASDFAASASDAAASDASDASD" ). 

Run the scan:

?- check . true . % 

The full text of the programs is available here .

And last, recommendations and tips.

1) All examples are given for the SWI-Prolog dialecate (in my humble opinion - the most sane and close to the classical prologue). However, I recommend using version 5.7.3 (beta) available here http://prolog.cs.vu.nl/download/devel/bin/ (file w32pl573.exe for win) or 5.6.X. In version 5.7.4 there is a small error when working in the prolog-console ( https://mailbox.iai.uni-bonn.de/mailman/public/swi-prolog/2009/000904.html ).
2) File Download:

?- [ file ]. 

multiple files:

?- [ file1 , file2 , file3 ]. 

3) Help by predicate:

?- help ( is ). 

?- apropos ( test ). 

4) editing the current uploaded file (a handy editor with highlight, by the way, written in the prologue).

?- edit . 

edit another file

?- edit ( file ). 

5) Step-by-step debugging (console):

?- trace , do_smth_with ( arg ). 

graphic:

?- gtrace , do_smth_with ( arg ). 

That's all for today. Thank you for reading =).

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

All Articles

Prolog, introduction

More articles: