From Wikipedia, the free encyclopedia

For the sense of an introduction, see prologue. Prolog was also the precursor to the company now known as Cyan Worlds.

Prolog

Paradigm:	Logic programming
Appeared in:	1972
Designed by:	Alain Colmerauer and Robert Kowalski
Major implementations:	GNU Prolog, Quintus, SICStus, SWI-Prolog, YAP
Dialects:	ISO Prolog, Edinburgh Prolog
Influenced:	Visual Prolog, Mercury programming language, Oz

Prolog is a logic programming language. The name Prolog is taken from programmation en logique (French for "programming in logic"). It was created by Alain Colmerauer and Robert Kowalski around 1972 as an alternative to the American-dominated Lisp programming languages. It is an attempt to make a programming language that enables the expression of logic instead of carefully specified instructions on the computer. In some ways Prolog is a subset of Planner, e.g., see Kowalski's early history of logic programming. The ideas in Planner were later further developed in the Scientific Community Metaphor.

Prolog is used in many artificial intelligence programs and in computational linguistics (especially natural language processing, which it was originally designed for). Its syntax and semantics are considered very simple and clear. (The original goal was to provide a tool for computer-illiterate linguists.) A lot of the research leading up to modern implementations of Prolog came from spin-off effects caused by the fifth generation computer systems project (FGCS) which chose to use a variant of Prolog named Kernel Language for their operating system (but this area of research is now actually almost defunct).

Prolog is based on first-order predicate calculus; however it is restricted to allow only Horn clauses. See Logic programming for a discussion of the relationship of Prolog to mathematical logic. Execution of a Prolog program is effectively an application of theorem proving by first-order resolution. Fundamental concepts are unification, tail recursion, and backtracking.

Contents 1 Data types 1.1 Atoms 1.2 Numbers 1.3 Variables 1.4 Terms 1.5 Lists 1.6 Strings 2 Facts 3 Rules 4 Evaluation 4.1 Negation 5 Execution 6 Parsing 6.1 Parser example 7 Examples 7.1 QuickSort 7.2 Towers of Hanoi 7.3 Computer Algebra 8 Comparison 9 Extensions 10 See also 11 References 12 External links 12.1 Implementations 12.2 Tutorial introductions 12.3 Advanced level programming 12.4 Conferences 12.5 Other resources

Data types

Prolog does not employ data types in the way common programming languages usually do. We may rather speak about Prolog lexical elements instead of data types.

Atoms

The text constants are introduced by means of atoms. An atom is a sequence consisting of letters, numbers and underscores, which begins with a lower-case letter. Usually, if a non-alphanumeric atom is needed, it is surrounded with apostrophes (e.g. 'an atom containing spaces').

Numbers

Most Prolog implementations do not distinguish integers from real numbers.

Variables

Variables are denoted by a string consisting of letters, numbers and underscore characters, and beginning with an upper-case letter or underscore. In the Prolog environment, a variable is not a container that can be assigned to (unlike imperative programming languages). Its behaviour is closer to a pattern, which is increasingly specified by unification.

The so called anonymous variable (explained below), a wildcard which means 'any variable', is written as a single underscore (_).

Terms

Terms are the only way Prolog can represent complex data. A term consists of a head, also called functor (which must be an atom) and parameters (unrestricted types) listed within parentheses and separated by commas. The number of parameters, the so called arity of term, is significant. A term is identified by its head and arity, usually written as functor/arity.

Lists

A list isn't a standalone data type, because it is defined by a recursive construction (using term '.'/2):

1. atom [] is an empty list
2. if T is a list and H is an element, then the term '.'(H, T) is a list.

The first element, called the head, is H, which is followed by the contents of the rest of the list, designated T or tail. The list [1, 2, 3] would be represented internally as '.'(1, '.'(2, '.'(3, []))). A syntactic shortcut is [H | T], which is mostly used to construct rules. The entirety of a list can be processed by processing the first element, and then the rest of the list, in a recursive manner.

For programmer's convenience, the lists can be constructed and deconstructed in a variety of ways.

• Element enumeration: [abc, 1, f(x), Y, g(A,rst)]
• Prepending single element: [abc | L1]
• Prepending multiple elements: [abc, 1, f(x) | L2]
• Term expansion: '.'(abc, '.'(1, '.'(f(x), '.'(Y, '.'(g(A,rst), [])))))
• The append predicate

Strings

Strings are usually written as a sequence of characters surrounded by quotes. They are often internally represented as lists of character codes, generally in the local codepage or Unicode if the system supports Unicode. ISO Prolog also allows strings to be represented as a list of one-character atoms.

Facts

Programming in Prolog is very different from programming in a procedural language. In Prolog you supply a database of facts and rules; you can then perform queries on the database. The basic unit of Prolog is the predicate, which is defined to be true. A predicate consists of a head and a number of arguments. For example:

cat(tom).

This enters into the database the fact that 'tom' is a 'cat'. More formally, 'cat' is the head, and 'tom' is the single argument. Here are some sample queries you could ask a Prolog interpreter basing on this fact:

is tom a cat?

?- cat(tom).  
     yes.

what things are cats?

?- cat(X).  
     X = tom;
     yes.

Predicates are usually defined to express some fact the program knows about the world. In most of the cases, the usage of predicates requires a certain convention. Thus, which version of the two below would signify that Bob is the father of Sally?

father(sally,bob).
father(bob,sally).  

In both cases 'father' is the head and 'sally' and 'bob' are arguments. However in the first case, Sally comes first in the argument list, and in the second, Bob comes first (the order in the argument list matters). The first case is an example of a definition in Verb Subject Object order, and the second of Verb Object Subject order. Since Prolog does not understand English, both versions are fine so far as it is concerned; however it is good programming style to stick to either convention during the writing of a single program, in order to avoid writing something like

father(bob,sally).
father(jessica,james).

Some predicates are built into the language, and allow a Prolog program to perform routine activities (such as input/output, using graphics and otherwise communicating with the operating system). For example, the predicate write can be used for output to the screen. Thus,

 write('Hello'). 

will display the word 'Hello' on the screen.

Rules

The second type of statement in Prolog is the rule, also called "clause". An example of a rule is

light(on) :- switch(on). 

The ":-" means "if"; this rule means light(on) is true if switch(on) is true. Rules can also make use of variables; variables begin with capital letters while constants begin with lower case letters. For example,

father(X,Y) :- parent(X,Y),male(X). 

This means "if someone is a parent of someone and he's male, he is a father". The antecedent and consequent are in reverse order to that normally found in logic: the consequent is written first and called the head of the rule, the antecedent is called the body. Conjunction (and) is written as ",", while disjunction (or) is written as ";". It is also possible to place multiple predicates in a body which are joined with disjunction, for example:

a :- b;c;d.

which is simply equivalent to three separate rules:

a :- b.
a :- c. 
a :- d.

What is not allowed are rules like:

a;b :- c.

that is "if c then a or b". This is because of the restriction to Horn clauses.

Evaluation

When the interpreter is given a query, it tries to find facts that match the query. If no outright facts are available, it attempts to satisfy all rules that have the fact as a conclusion. For example:

sibling(X,Y) :- parent(Z,X), parent(Z,Y).
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
mother(trude, sally).
father(tom, sally).
father(tom, erica).
father(mike, tom).

This results in the following query being evaluated as true:

?- sibling(sally, erica).
     yes.

The interpreter arrives at this result at matching the rule sibling(X,Y) by binding sally to X and erica to Y. This means the query can be expanded to parent(Z,sally), parent(Z,erica). Matching this conjunction is done by looking at all possible parents of sally. However, parent(trude,sally) doesn't lead to a viable solution, because if trude is substituted for Z, parent(trude,erica) would have to be true, and no such fact (or any rule that can satisfy this) is present. So instead, tom is substituted for Z, and erica and sally turn out to be siblings none the less. The code

parent(X,Y) :- father(X,Y).

might seem suspicious. After all, not every parent is a father. But actually this code means that any father is a parent. To infer that all fathers are male, you'd need to code

male(X) :- father(X,_).

which simply doesn't care whoever the child is (the underscore is an anonymous variable).

Negation

Typically, a query is evaluated to be false by merit of not finding any positive rules or facts that support the statement. This is called the Closed World Assumption; it is assumed that everything worth knowing is in the database, so there is no outside world that might contain heretofore unknown evidence. In other words, if a fact is not known to be true (or false), it is assumed to be false.

A rule such as

legal(X) :- \+ illegal(X).

can only be evaluated by exhaustively searching for all things illegal, comparing them to X, and if no illegal fact can be found to be the same as X, X is legal. This is called negation as failure. The \+/1 prefix operator used above implements negation as failure in ISO Prolog compilers.

Execution

Prolog is a logical language, so in theory the programmer shouldn't care about how it executes. However, sometimes it is prudent to take into account how the inference algorithm works, to prevent a Prolog program from running for an unnecessarily long time.

For example, we can write code to count the number of elements in a list.

elems([],0).
elems([H|T], X) :- elems(T, Y), X is Y + 1.

This simply says: If the list is empty, the number of elements is zero. If the list is non-empty, then X is one higher than Y, which is the number of elements in the remainder of the list without the first element.

In this case, there is a clear distinction between the cases in the rules' antecedent. But consider the case where you need to decide whether to keep gambling in a casino:

gamble(X) :- gotmoney(X).
gamble(X) :- gotcredit(X), \+ gotmoney(X).

If you have money, you keep gambling. If you've lost it all, you'll need to borrow money, or else no more gambling. gotmoney(X) might be a very costly function - for example, it might access your internet banking account to check your balance, which takes time. However, the same goes for gotcredit(X).

In theory, Prolog implementations might evaluate these rules out of order, so you might as well have written:

gamble(X) :- gotcredit(X), \+ gotmoney(X).
gamble(X) :- gotmoney(X).

This is fine, because the two options exclude each other. However, checking whether you can get a loan is not necessary if you know you have money. So in practice, Prolog implementations will check the uppermost rule first (in fact, most Prologs will always try the rules in order from the uppermost to the lowermost). You can use the cut operator to tell the interpreter to skip the second option if the first suffices. For example:

gamble(X) :- gotmoney(X),!.
gamble(X) :- gotcredit(X), \+ gotmoney(X).

This is called a green cut operator. The ! simply tells the interpreter to stop looking for alternatives. But you'll notice that if you need money it will need to check the second rule, and it will. Checking for gotmoney in the second rule is pretty useless since you already know you don't have any, otherwise the second rule wouldn't be evaluated in the first place. So you can change the code to

gamble(X) :- gotmoney(X),!.
gamble(X) :- gotcredit(X).

This is called a red cut operator, because it is dangerous to do this. You now depend on the proper placement of the cut operator and the order of the rules to determine their logical meaning. Cut-and-paste accidents lurk in dark corners. If the rules got mixed up, you might now max out your credit card before spending your cash.

Parsing

Prolog has a built in mechanism for parsing context-free grammar. Using the arrow notation one can easily define a parser in prolog that evaluates the grammatical correctness in a formal language, e.g. a programming language. The input string should first be tokenized into tokens using the Prolog list, e.g.

x = 2
[x, =, 2]

To evaluate the list we could use ordinary Prolog list manipulation. We use a binary predicate which takes the input list as its first argument and what ever rest we get after the parse is complete (the rest should be [] if parse was successful). The following example shows how it can be done:

statement(A,B) :- id(A,C), assign_op(C,D), digit(D,B).
id([x|X],X).
assign_op([=|X],X).
digit([2|X],X).

The nestling of list tails can be automated using the built in parsing mechanism, also known as arrow notation.

statement --> id, assign_op, digit.

Parser example

A larger example will show the potential of using Prolog in parsing.

Given the sentence expressed in BNF:

<sentence>    ::=  <stat_part>
<stat_part>   ::=  <statement> | <stat_part> <statement>
<statement>   ::=  <id> = <expression> ;
<expression>  ::=  <operand> | <expression> <operator> <operand>
<operand>     ::=  <id> | <digit>
<id>          ::=  a | b
<digit>       ::=  0..9
<operator>    ::=  + | - | *

This can be written in Prolog using the arrow notation (assuming the input like [a, =, 3, *, b, ;, b, =, 0, ;] etc.):

sentence      -->  stat_part.
stat_part     -->  statement ; stat_part, statement.
statement     -->  id, [=], expression, [;].
expression    -->  operand ; operand, operator, expression.
operand       -->  id ; digit.
id            -->  [a] ; [b].
digit         -->  [D], {D>=0, D=<9}.
operator      -->  [+] ; [-] ; [*].

Examples

Here follows some program examples written in ISO-PROLOG. Check this article for a standard Hello world program in Prolog and several other languages.

QuickSort

split(H, [A|X], [A|Y], Z) :-
  order(A, H), split(H, X, Y, Z).
split(H, [A|X], Y, [A|Z]) :-
  not(order(A, H)), split(H, X, Y, Z).
split(_, [], [], []).
quicksort([], X, X).
quicksort([H|T], S, X) :-
  split(H, T, A, B),
  quicksort(A, S, [H|Y]),
  quicksort(B, Y, X).

Towers of Hanoi

hanoi(N) :- move(N, left, centre, right).
move(0, _, _, _) :- !.
move(N, A, B, C) :-
  M is N-1,
  move(M, A, C, B), inform(A, B), move(M, C, B, A).
inform(X, Y) :-
  write([move, a, disc, from, the, X, pole, to, the, Y, pole]),
  nl.

Computer Algebra

This example demonstrates the power and ease-of-use of symbolic manipulation in Prolog.

/* Derivation Definition */
d(X,X,1) :- !.                                        /* d x     dx = 1                     */
d(C,X,0) :- atomic(C).                                /* d c     dx = 0                     */
d(-U,X,-A) :- d(U,X,A).                               /* d -u    dx = - d u dx              */   
d(U+V,X,A+B) :- d(U,X,A), d(V,X,B).                   /* d u+v   dx = d u dx + d v dx       */
d(U-V,X,A-B) :- d(U,X,A), d(V,X,B).                   /* d u-v   dx = d u dx - d v dx       */
d(C*U,X,C*A) :- atomic(C), C \= X, d(U,X,A), !.       /* d c*u   dx = c*d u dx              */
d(U*V,X,B*U+A*V) :- d(U,X,A), d(V,X,B).               /* d u*v   dx = u*d v dx + v*d u dx   */ 
d(U/V,X,A) :- d(U*V^(-1),X,A).                        /* d u/v   dx = d (u*v)^-1 dx         */
d(U^C,X,C*U^(C-1)*W) :- atomic(C), C \= X, d(U,X,W).  /* d u^c   dx = c*u^(c-1)*d u dx      */
d(log(U),X,A*U^(-1)) :- d(U,X,A).                     /* d ln(u) dx = u^-1 * d u dx         */

/* Integral Definition */
i(0,X,0) :- !.                                        /* Int 0   dx = 0                     */
i(X,X,(X*X)/2) :- !.                                  /* Int X   dx = (X^2)/2               */
i(C,X,C*X) :- atomic(C).                              /* Int c   dx = c*x                   */
i(-U,X,-A) :- i(U,X,A).                               /* Int -U  dx = - Int U dx            */
i(U+V,X,A+B) :- i(U,X,A), i(V,X,B).                   /* Int U+V dx = Int U dx + Int V dx   */ 
i(U-V,X,A-B) :- i(U,X,A), i(V,X,B).                   /* Int U-V dx = Int U dx - Int V dx   */
i(C*U,X,C*A) :- atomic(C), C \= X, i(U,X,A), !.       /* Int cU  dx = c (Int U dx)          */
i(X^C,X,(X^(C+1))/(C+1)) :- atomic(C), !.             /* Int x^c dx = x^(c+1)/(c+1)         */
i(U,V,U*V-A) :- d(V,U,A), !.                          /* Int u   dv = u*v - Int v du        */ 

/* Simplification Rules */
s(+,X,0,X).                                           /* x + 0 = x                          */
s(+,0,X,X).                                           /* 0 + x = x                          */
s(+,X,Y,X+Y).                                         /* x + y = x + y                      */
s(+,X,Y,Z) :- integer(X), integer(Y), Z is X+Y.       /* x + y = z             <- Calculate */
s(*,_,0,0).                                           /* anything * 0 = 0                   */
s(*,0,_,0).                                           /* 0 * anything = 0                   */
s(*,1,X,X).                                           /* 1 * x = x                          */
s(*,X,1,X).                                           /* x * 1 = x                          */
s(*,X,Y,X*Y).                                         /* x * y = x * y                      */
s(*,X*Y,W,X*Z) :- integer(Y), integer(W), Z is Y*W.   
s(*,X,Y,Z) :- integer(X), integer(Y), Z is X*Y.       /* x * y = z             <- Calculate */

/* Simplification Definition */
simp(E,E) :- atomic(E), !.
simp(E,F) :- E =.. [Op, La, Ra], simp(La,X), simp(Ra,Y), s(Op,X,Y,F).

Comparison

Comparision of Prolog Implementations

Platform			Features							Toolkit			Prolog Mechanics
Name	OS	Licence	Native Graphics	Unicode	Object Oriented	Native OS Control	Stand Alone Executable	C Interface*	Java Interface*	Interactive Interpreter	Debugger	Code Profiler	Syntax
DOS-PROLOG	MS-DOS	Shareware	TRUE	TRUE		TRUE	TRUE				TRUE		Edinburgh Prolog
Open Prolog	Mac OS	Freeware									TRUE
Ciao Prolog	Unix, Windows	GPL					TRUE	TRUE	TRUE	TRUE	TRUE		ISO-Prolog
GNU Prolog	Unix, Windows	GPL				TRUE	TRUE	TRUE		TRUE	TRUE		ISO-Prolog
Visual Prolog	Windows	Freeware, Commercial	TRUE	TRUE	TRUE	TRUE	TRUE	TRUE			TRUE
SWI-Prolog	Unix, Windows, Mac OS X	LGPL	TRUE	TRUE			TRUE	TRUE	TRUE	TRUE	TRUE	TRUE	ISO-Prolog, Edinburgh Prolog

^*C/Java interface can also be used for graphics and OS control.

Extensions

• HiLog and λProlog extend Prolog with higher-order features.
• Visual Prolog, also formerly known as PDC Prolog and Turbo Prolog. Visual Prolog is a strongly-typed object-oriented dialect of Prolog, which is considerably different than standard Prolog. As Turbo Prolog it was marketed by Borland, but it is now developed and marketed by the Danish firm PDC (Prolog Development Center) that originally produced it.
• OW Prolog has been created in order to answer Prolog's lack of graphics and interface.
• InterProlog, a programming library bridge between Java and Prolog, implementing bi-directional predicate/method calling between both languages. Java objects can be mapped into Prolog terms and vice-versa. Allows the development of GUIs and other functionality in Java while leaving logic processing in the Prolog layer. Supports XSB, SWI-Prolog and YAP.
• Prova provides native syntax integration with Java, agent messaging and reaction rules. Prova positions itself as a rule-based scripting (RBS) system for middleware. The language breaks new ground in combining imperative and declarative programming.
• Logtalk is an open source object-oriented extension to the Prolog programming language. Integrating logic programming with object-oriented and event-driven programming, it is compatible with most Prolog compilers. It supports both prototypes and classes. In addition, it supports component-based programming through category-based composition.
• Datalog is actually a subset of PROLOG. It is limited to relationships that may be stratified such that solutions on a large knowledge base return in finite time.

See also

• Planner

References

• Ivan Bratko, PROLOG Programming for Artificial Intelligence, 2000, ISBN 0201403757.
• Robert Kowalski, The Early Years of Logic Programming, CACM January 1988.
• ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva.
• Alain Colmerauer and Philippe Roussel, The birth of Prolog, in The second ACM SIGPLAN conference on History of programming languages, p. 37-52, 1992.

External links

Implementations

• WIN Prolog by Logic Programming Associates
• Open Prolog, an Apple Mac implementation.
• Ciao Prolog, open source under GPL and LGPL
• GNU Prolog, also known as gprolog, open source under GPL
• YAP Prolog, open source under Artistic License
• Visual Prolog, formerly known as PDC Prolog and Turbo Prolog
• SWI-Prolog, open source under LGPL
• AI::Prolog, a perl module that comes with a prolog command-line interpreter
• SICStus Prolog
• ECLiPSe Prolog
• Amzi! Prolog
• B-Prolog
• TuProlog, open source under LGPL
• XSB, open source under LGPL
• MINERVA - commercial ISO-Prolog compiler in 100% Java
• Trinc Prolog
• Strawberry Prolog
• hProlog
• ilProlog, a component of the DMax software stack
• CxProlog
• NanoProlog, a WAM based minimal Prolog system
• BinProlog
• Quintus Prolog, the industrial standard implementation
• Allegro Prolog, an implementation within Allegro Common Lisp
• ALS Prolog
• W-Prolog, a Prolog interpreter in a Java applet.
• EZY Prolog, a Prolog interpreter and IDE for Windows
• GraphTalk, a proprietary WAM based implementation with object extensions, designed for building of information systems.
• Poplog, a free, open source, multi-language software development environment providing incremental compilers for a number of interactive programming languages, including prolog

Tutorial introductions

• Prolog Tutorial by J.R.Fisher
• Visual Prolog Tutorial
• Runnable examples by Lloyd Allison
• Visual Prolog Examples
• Logic Programming and Prolog (2ed) by Ulf Nilsson and Jan Maluszynski
• Prolog Programming A First Course by Paul Brna
• Adventure in Prolog, online book by Amzi! Inc.
• On-line guide to Prolog Programming by Roman Bartak
• Learn Prolog Now! by Patrick Blackburn, Johan Bos and Kristina Striegnitz

Advanced level programming

• Richard O'Keefe, The Craft of Prolog, ISBN 0-262-15039-5.
• Building Expert Systems in Prolog, online book by Amzi! Inc.

Conferences

• ICLP International Conference on Logic Programming
• INAP International Conference on Declarative Programming and Knowledge Management (former Intl. Conf. on Applications of Prolog)

Other resources

• comp.lang.prolog FAQ
• Prolog: The ISO standard
• Prolog Development Center