Prolog
Prologue ( from French: en Programmation Logique, dt: "Programming in Logic ") is a programming language that was largely developed by French computer scientist Alain Colmerauer the early 1970s and a declarative programming allows. It is the main logic programming language.
First implementations differed in their syntax strongly from one another, but the Edinburgh dialect sat down soon by a quasi standard. However, he was not formally defined until 1995 based on an ISO standard was (ISO / IEC 13211-1 ), which is also called ISO -Prolog.
The first Prolog interpreter was implemented in Marseille in ALGOL W. The first approach to a compiler came from David HD Warren from Edinburgh. This had as a target language of the logic processor Warren's Abstract Machine and therefore allowed neither dynamic changes nor a port resettable predicates in other programming languages. The first fully usable compiler, which allowed both, was developed by Preben Folkjaer in Munich. He used a different, coming from the Vienna University of Technology, intermediate code that was compiled incrementally; predicates have been changed, the compiled program was deleted and recompiled the next time.
- 4.1 solving a math puzzle
- 4.2 Processing of hierarchical structures
- 4.3 Planning Systems
- 4.4 Einstein's riddle
Basic principle
Prolog programs consist of a database whose entries are called facts and rules. The user formulates queries to the data base. The Prolog interpreter uses the facts and rules in order to systematically find an answer. A positive result means that the request is logically derivable. A negative result is only that due to the data base without derivation can be found. This is closely related to the closed world assumption together ( see below).
The typical first program in Prolog is not like in procedural programming languages , a Hello World example, but a database with pedigree information.
The following example represents the pedigree of a small family. The first fact in the form of a statement man ( tobias ). reads as: Tobias is a man. father ( tobias, frank ). defines the Fact: Tobias is the father of Frank.
Man ( adam ). man ( tobias ). man ( frank ). woman ( eva ). woman ( daniela ). woman ( Ulrike ). father ( adam, tobias ). father ( tobias, frank ). father ( tobias, ulrike ). mother ( eva, tobias ). nut ( daniela, frank ). nut ( daniela, ulrike ). In a Prolog interpreter can be provided to the data base now interactive requests. Running a Prolog program that means places a request. The system responds with either yes. or no, depending on whether the request could be proved. The interpreter indicated by the command prompt - that he expects a request?:
? - Man ( tobias ). yes. ? - Man ( henry ). no A request with a variable provides additional assignments in response to which the request is true. We call such a variable assignment unification and says the variable is unified with the value. Variables in Prolog tokens that begin with a capital letter:
? - Woman (X). X = eva X = daniela X = ulrike no is the answer to the answers previously issued reduced Facts list.
The interpreter provides only positive responses to requests that are explicitly defined or folgerbar (closed world assumption ). Thus, for example about heinrich no information in the data base:
? - Man ( henry ). no ? - Woman ( heinrich ). no In addition to facts can be formulated in Prolog rules. The control operator: - is to be read as an inverted Implikationspfeil. example:
Grandfather (X, Y ): - father (X, Z), father (Z, Y). The rule states: X is the grandfather of Y if there is a Z such that X is the father of Z and Z is father of Y. Thus, the paternal grandfather defined. A second rule for the maternal grandfather looks like this:
Grandfather (X, Y ): - father (X, Z), nut ( Z, Y). The operator ", " in this rule defines a conjunction and reads "and". The term left of the implication operator is also called Head or consequence. If two rules (as above) the same consequence follows this, at least when in a rule, the precondition is satisfied ( disjunction ).
By the definition of rules and facts can be closed that are not explicitly available in the data base:
Boolean algebra
The logical AND is represented by a comma:
? - True, true. true. ? - True, false. false. ? - False, true. false. ? - False, false. false. The logical OR is represented by a semicolon:
? - True, true. true. ? - True, false. true. ? - False: true. true. ? - False; false. false. comparisons
? - 3 < 4 true. ? - 3 > 4 false. ? - Anton anton ==. % == Checks whether the pattern matches to the left and right true ? - 3 == 1 2. % Pattern does not match false. ? - 3 =: = 1 2. % =: = Is the numerical comparison true. ? - 3 = \ = 4 % = \ = means not equal true. ? - 3 = < 4 % = < means less than / equal; '<= ' Is not allowed true. ? - 3 > = 4 %> = means greater than / equal false. regulate
% If X is the father of Z and Z is the father of Y, then X is grandfather of Y grandfather (X, Y ): - father (X, Z), father (Z, Y). % Adam is the father of Tobias father ( adam, tobias ). % Tobias is the father of Frank father ( tobias, frank ). % Query whether Adam is the grandfather of Frank? - Grandfather ( adam, frank ). true. symmetric relation
% The couple X And Y if and only a couple, % If a couple Y and X exists couple (X, Y ): - couple (Y, X). % Anton and berta are a couple couple ( anton, berta ). % Query whether berta and anton are a couple? - Couple ( berta, anton ). true. arithmetic
Prolog knows the basic arithmetic operations, ie addition , subtraction -, * scalar, division / and modulo mod. Assigning a value to a variable is done with the keyword is.
Lists
Lists are recursive data structures composed of a header ( HEAD) and a remainder (tail ). The rest can here again consist of lists.
% Head is the number 1 % Tail is the number 2 [1,2] % Head is the string 'one' % Tail is the string 'two' [ 'one', 'two' ] % Lists can also be mixed [1, 'two' ] % Head is the number 1 % Tail is the list [ 2,3] [1,2,3] To check whether a certain element is contained in a list, the built-in function is used member:
Member (X, L): - L = [ H | T], % the list L consists of a head and a tail ( X = H; % If the element X is equal to the Head is, give 'true' back, or member (X, T) % check if the element X is contained in the tail list. ). ? - Member (2, [' anton ', ' berta ', ' caesar ']). false. ? - Member ( ' berta ', [' anton ', ' berta ', ' caesar ']). true. Loading scripts
A Prolog script is loaded consult with the function, which accepts a physical path to a prolog script:
? - Consult ( ' myPrologScript.pl '). % Load the script true. other techniques
Decisive for the Prolog programming are the techniques of recursion and the use of lists.
When recursion in most programming only an additional variant for the iteration, it is the only way to produce loops in the Prolog programming. Does one need in the above example, a general ancestor relation, which is implemented as follows ( ";" shows in the clause or the disjunction of the logical "or" ):
% X is then a parent of Y, % If X is the mother of Y or % If X is a father of Y. parent (X, Y ): - parent (X, Y); father (X, Y). % X is then an ancestor of Z, % If X is a parent of Z. ancestor (X, Z ): - parent (X, Z). % X is then an ancestor of Z, if % X is a parent of Y and % Y is an ancestor of Z ancestor (X, Z ): - parent (X, Y), ancestor (Y, Z). This can be read as follows: X is an ancestor of Z, if X is a parent of Z is (rule 1 ) or there is a Y, the ancestor of Z, while X is parent of Y (Rule 2 ) (It was here parent instead of mother or father used. )
Also lists are a crucial part of Prolog. Most Prolog implementations bring for many basic functions ( " concat " = appending values , "count" = number of values , etc.), but also allows all define themselves. In an imaginary family structure, the number of children must be variable, yes. The following would be possible:
Family ( heinz, jutta, [ peter, laura ] ). family ( carl, gertrude, []). Then let, for example, with a query show all men without children:
? - Family (X, _, []). X = karl Where X is the variable whose different values are to be output. The underscore _ is in Prolog anonymous variable, which causes each value is prologue here allow. The square brackets stand for the empty set, which represents the non-existent children.
Another property and specificity over other programming languages is that Prolog is able, during the term to expand its existing database or to delete. An example of deleting a single element:
? - Car ( bmw, X). results (initially ) the usual way:
X = red; X = blue; No The query:
? - Car color ( bmw, X). would the first time:
X = blue; No only the second time:
No supply, as the information:
Car ( bmw, red). car ( bmw, blue). were deleted from the database. Also - the car ( bmw, X) now provides only No. To erase all the same elements ( ie, for example auto ( ) ) to be used once you retractall () for outputting asserta () ( top of the database) and assertz () ( below in the database).
Examples
Solving a math puzzle
ABB - CD = EED - * FD EF = CE === EGD * FH =? A to H are each a number from 0 to 9, where it is not clear which number corresponds to which letter. Wanted is the number that must appear next to the question mark. This problem is very easily solved in Prolog. One first writes a rule that causes A to H will later be occupied with all possible combinations from 0 to 9 ( permutation ):
Gene (A, B, C, D, E, F, G, H ): - permutation ([A, B, C, D, E, F, G, H, _, _ ] [ 0,1,2, 3,4,5,6,7,8,9 ] ). Now just need the five resulting equations (ABB - CD = EED, FD EF = CE, ABB - FD = EGD, CD - EF = FH and EED * CE = EGD * FH = X ) can be written in Prolog syntax:
Gl1 (A, B, C, D, E): - (( A * 100 B * 10 B ) - (C * 10 D)) =: = (E * 100 10 * E D). gl2 (C, D, E, F): - (( F * 10 D) (E * 10 F )) =: = (C * 10 E). GL3 (A, B, D, E, F, G ) - (( 100 * A B * 10 B ) - ( F * 10 D) ) =: = ( D * 100 * 10 D G ). gl4 (C, D, E, F, H): - (( C * 10 D ) - ( E * 10 F )) =: = (F * 10 H). GL5 (C, D, E, F, G, H, X) - (( E * 100 * 10 E D) * (C * 10 D )) =: = ( (E * 100 10 * G D ) * ( F * 10 H) ), X is ( (E * 100 10 * G D ) * ( F * 10 h)). Interested only X, a resolution rule is applied, the outputs brings together everything and X:
Spoon: - tions (A, B, C, D, E, F, G, H), gl1 (A, B, C, D, E), gl2 (C, D, E, F), GL3 (A, B, D, E, F, G), GL4 (C, D, E, F, H), GL5 (C, D, E, F, G, H, X ), write ( X). Now, if the query spoon. input, the solution is discharged. As you can see, you need to solve this problem almost no programming knowledge about grinding or the like, but is a just the facts and what result you needed. The prologue is in the abstraction hierarchy for exactly that reason about imperative and object -oriented languages .
Processing of hierarchical structures
A common task in programming is the processing of hierarchical structures, such as SGML or XML. Especially for XML prolog constitutes a very effective and expressive alternative to the common processing XSLT language.
A typical XML tree as
[element ( book, [title = ' Peer Gynt '], [ element ( author, [ name = ' Henrik Ibsen ' nat = ' Norwegian '], []), ...]) ] A very simple paradigm (lower three clauses ) allows you to go through every tree recursively. The following examples delete (top clause with delete) and concatenate (second clause from above with concat ) certain tags. The first unifier is the operation ( delete or concat ), the second the structure to be processed, and the third the specified day, the fourth of the result tree. append is a command for concatenating lists.
Transform ( delete, [element ( deltaG, _, _) | Siblings ], deltaG, ResTree ): - transform ( delete, Siblings, deltaG, ResTree ). transform ( concat, [ Item1, Item2 | Siblings ], ConTag, ResTree ): - Item1 = element ( Contag, Attr, children1 ) Item2 = element ( Contag, _, children2 ) append ( children1, children2, Children), transform ( concat, [element ( ConTag, Attr, Children) | Siblings ], ConTag, ResTree ). transform ( _, [], _, []). transform ( Trans, [element ( CTAG, Attr, Children) | Siblings ], Day, ResTree ): - \ Day = CTAG, transform ( Trans, Children, Day, ResChildren ) transform ( Trans, Siblings, Day, ResSiblings ) ResTree = [element ( CTAG, Attr, ResChildren ) | ResSiblings ]. transform ( _, [ atom ], _, [ atom ] ): - atomic ( atom). The performance by the BackTracker in the operation delete on a tag like that is to be deleted, so this away and the neighbors are still being sought. An example command is for example transform ( delete, Tree, author, ResTree ). , Of all the authors removed.
Similarly, by transform ( concat, Tree, paragraph, ResTree ). all juxtaposed paragraphs are fused together. This end, their contents are concatenated, it creates a new paragraph structure and these further processed.
Planning systems
Planning systems looking for a way to get from an initial state to a desired goal state. They can be used for the search of roads or traffic connections, but also for more general problems. First, the most common approach for a blind depth-first search (ie, it is unknown whether the individual step also leads closer to the target ):
(Target, target, status list ): - write ( state list), nl. / * Target reached, terminate the recursion and output * / off ( start, finish, condition list): - / * There is a path from start to finish, if ... * / operator ( Op), / * ... there is an operator ... * / apply (op, start) / * ... which is applicable in the initial state, ... * / fuehrt_zu ( Op, Start, New), / * ... leads from there to a new state ... * / not (member ( new, state list) ) / * ... who was never there ( preventing loops) ... * / permissible ( New), / * ... and is legal to ... * / away (new, target, [ New | List state ] ). / * ... And there is a path from there to the destination. * / Only the predicates operator, applicable fuehrt_zu and permissible, as well as the description of a state are to formulate specific problems. Is called the predicate with a state list that contains the initial state.
Depending on the type of problem can be a lot easier and / or omit; for a path search in a road network results eg
(Target, target, location list ): - write ( town list ), nl. / * Target reached, terminate the recursion and output * / off ( start, finish, location list ): - / * There is a path from start to finish, if ... * / street (Start, New), / * ... there is a road from the start to a new place ... * / not (member ( new, local list) ) / * ... in which one was not ( prevent loops), ... * / away (new, target, [ New | Place List ] ). / * ... And of which there is a path to the goal. * / In real problems, a blind search is seldom sufficient; one uses a breadth-first search, in which all determined from the start of achievable new states, evaluated with a heuristic function and only the best ( Heuristic search) or a sorted list of the best ( Best -first search) to be pursued. ( The simple heuristic search may result in not always the optimal solution is found, as certain solution steps that were incorrectly rejected as unfavorable, would arise as a better solution. ) The art is in the correct problem-specific formulation of the heuristic function. In many cases helps the A- heuristic, which is the sum of previously incurred for and estimated remaining work to the target ( eg distance traveled straight-line distance to destination ):
(Target, target, location list, path): - write ( town list ), nl, write (path), nl. / * Target reached, terminate the recursion and output * / off ( start, finish, location list, path): - / * There is a path from start to finish, if ... * / * ... there's findall (place, street ( start site), new list ), / a list of achievable new places ... * / review ( new list, start, track, target, list Evaluated ), / * ... and rated each of which ... * / sort (Rated list, sortedlist ), / * ... by sorting the list ... * / member ( [_, $ total, New] sortedlist ), / * ... the best is sought, ... * / not (member ( new, local list) ) / * ... in which one was not, ... * / away (new, target, [ New | Place List ], $ total ). / * ... And of which there is a path to the goal. * / Each element of the structure rated list [ heuristic value, total distance, location]; for calculating the A- heuristics, the previous track, the last place and the destination ( distance) are required.
Einstein's riddle
This is a version of the Zebra puzzle. It was allegedly written by Albert Einstein in the 19th century. Einstein, the remark often attributed to only 2% of the world's population are able to solve the mystery. However, there is no indication of any authorship. Here it is supposed to represent an example of a problem which is solved with Prolog.
Question: Who owns the fish belong to?
Notes:
- The Brit lives in the red house.
- The Swede keeps dogs as pets.
- The Dane drinks tea like.
- The green house is immediately to the left of the white house.
- The green house owner drinks coffee.
- The person who smokes Pall Mall rears birds.
- The man living in the center house drinks milk.
- The owner of the yellow house smokes Dunhill.
- The Norwegian lives in the first house.
- The man who smokes Blends lives next to the one who keeps cats.
- The man who keeps horses lives next to the man who smokes Dunhill.
- The Winfield smoker likes to drink beer.
- The Norwegian lives next to the blue house.
- The German smokes Rothmans.
- The man who smokes Blends has a neighbor who drinks water.
Solution:
First four simple auxiliary predicates for list processing:
First (E, [E | _ ] ). mid (M, [_, _, M, _, _ ] ). left (A, B, [A, B | _ ] ). left (A, B, [ _ | R] ): - left (A, B, R). in addition to ( A, B, L): - left (A, B, L); left (B, A, L). Solution predicate:
Run: - X = [_, _, _, _, _ ], / * There are (side by side ) 5 ( unknown ) Houses * / member ( [ red, brit, _, _, _ ], X), / * The Brit lives in the red house * / member ( [_, swede, _, _, dog ], X), / * The Swede keeps dogs as pets * / member ( [_, dane, tea, _, _ ], X), / * The Dane drinks tea like * / left ( [ green, _, _, _, _ ], [white, _, _, _, _ ], X), / * The green house is on the left of the white house * / member ( [ green, _, coffee, _, _ ], X), / * The green house owner drinks coffee * / member ( [_, _, _, Pall Mall, bird ], X), / * The person who smokes Pall Mall rears birds * / mid ( [_, _, milk, _, _ ], X), / * The man living in the center house drinks milk * / member ( [ yellow, _, _, dunhill, _ ], X), / * The owner of the yellow house smokes Dunhill * / first ( [_, norwegian, _, _, _ ], X), / * The Norwegian lives in the first house * / next to ( [_, _, _, marlboro, _ ], [ _, _, _, _, cat ], X), / * The man who smokes Blends lives next to the one who keeps cats * / next to ( [_, _, _, _, horse ], [ _, _, _, dunhill, _ ], X), / * The man who keeps horses lives next to the man who smokes Dunhill * / member ( [_, _, beer, winfield, _ ], X), / * The Winfield smoker likes to drink beer * / next to ( [_, norwegian, _, _, _ ], [blue, _, _, _, _ ], X), / * The Norwegian lives next to the blue house * / member ( [_, German, _, rothmans, _ ], X), / * The German smokes Rothmans * / next to ( [_, _, _, marlboro, _ ], [ _, _, water, _, _ ], X), / * The man who smokes Blends has a neighbor who drinks water * / member ( [_, N, _, _, fish ], X), / * The one with the Nationality N has a fish * / write ( X), nl, / * output of all houses * / write (' The ' ), write ( N), write (' has a pet fish .'), nl. / * Answer to the question * / Definite Clause Grammar
To write rules for parsers, most Prolog systems have implemented a preprocessor. It allows the rules to write in a more readable form, which conform to the rules in the form that is used to describe a context-free language. The preprocessor adds placeholders and generates the above mentioned Prolog logic formulas. Passing other attributes, it is possible with Definite Clause Grammars more complex languages than to describe context-free.
Prologue, from a logical point of view
A Prolog program is an ordered list of so-called Horn clauses, a restricted form of first order predicate logic. The assumption that the system a request ( query ), it attempts to prove this on the basis of this data base by means of resolution. The result of a query is yes or no its real effect develops a Prolog program, strictly speaking, due to side effects that occur during the proof search. So can a Prolog system as a very efficient - albeit limited - automatic theorem prover to be understood. The only built- in Prolog search strategy in finding evidence is depth-first search with backtracking.
Areas of application
In the 1980s, the language played an important role in the construction of expert systems. The language is still used today in the fields of computational linguistics and artificial intelligence. For example, natural language processing components through his appearance on Jeopardy! become known AI system Watson written in Prolog. There are also some commercial applications in the area of system management, in which asynchronous events (events) based on proprietary extensions are processed by means of Prolog or. An example of this is the product of the Tivoli Enterprise Console (TEC ) of IBM, which is based on IBM Prolog.