Prolog

From Wikipedia, the free encyclopedia

You have new messages (last change).
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, Philippe Roussel and Robert Kowalski
Major implementations: GNU Prolog, Quintus, SICStus, SWI-Prolog, YAP
Dialects: ISO Prolog, Edinburgh Prolog
Influenced: Visual Prolog, Mercury, Oz, Erlang, Strand

Prolog is a logic programming language. The name Prolog was chosen by Philippe Roussel as an abbreviation for "PROgrammation en LOGique”. It was created by Alain Colmerauer, Philippe Roussel 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). 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

[edit] Data types

Prolog's single data type is the term. Terms are either atoms, numbers, variables or compound terms. Compound terms have a functor and a number of arguments, which are themselves terms.

[edit] Atoms

Atoms can be regarded as a special case of compound terms (of arity zero).

[edit] Numbers

In addition to floats and integers, many Prolog implementations also provide rational numbers and unbounded integers.

[edit] 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 (_).

[edit] Compound terms

A compound term is identified by its functor and arity, usually written as functor/arity.

[edit] Lists

Lists are defined recursively: The atom 'nil' (denoted as []) is a list. A compound term with functor . (dot) and arity 2, whose second argument is a list, is itself a list. There exists special syntax for denoting lists: .(A, B) is equivalent to [A|B]. For example, the list .(1, .(2, .(3, []))) can also be written as [1,2,3].

[edit] 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 character encoding or Unicode if the system supports Unicode. ISO Prolog also allows strings to be represented as a list of one-character atoms.

[edit] Recursion

Unlike other programming languages, Prolog does not provide loop constructions. Iterations, however, can be achieved through the use of recursion. Two kinds of recursion exist: tail recursion and non-tail recursion.

[edit] Tail recursion

A function f can be defined with tail recursion as:

f(x): if c(x) then g(x) else f(h(x))

where:
- c(x) is some kind of condition on the value of x;
- g(x) are functions defined with one argument not defined in term of the function f.

Such a statement can be written in Prolog this way:

f(X, Z) :- c(X), g(X, Z).
f(X, Z) :- h(X, Y), f(Y, Z).

Tail recursion is important and preferable over non-tail recursion since it can be implemented as an iteration, which is computed using constant stack space in a machine.

[edit] Non-tail recursion

Non-tail recursion can be defined with the statement:

f(x): if c(x) then g(x) else k(x, f(h(x)))

This means the value of the recursive call is modified after its computation. In Prolog, this function can be implemented as:

f(X, Y) :- c(X), g(X, Y).
f(X, Y) :- h(X, X1), f(X1, Y1), k(X, Y1, Y).

Non-tail recursion uses a linear space in the stack and is therefore avoided in case it is not necessary. In some cases it is possible to optimize the implementation. Consider the scheme:

f(n): if n = 0 then a else k(n, f(n - 1))

It can be written in Prolog using a non-tail recursion:

f(0, a).
f(X, Y) :- X1 is X - 1, f(X1, Y1), k(X, Y1, Y).

This code requires linear space in the stack for storing temporary results of recursive calls. Using an accumulator the code above can be written using a tail recursion:

f(X, Y) :- f(X, 1, a, Y).
f(X, M, ACC, ACC) :- M > N.
f(X, M, ACC, Y) :- M <= N, k(M, ACC, ACC1), M1 is M + 1, f(N, M1, ACC1, Y)

[edit] Programming in Prolog

Prolog programs describe relations between things. Relations are defined by clauses. For efficiency, Prolog is restricted to Horn clauses, a Turing-complete subset of first-order predicate logic. Clauses with empty bodies are called facts. An example of a fact is

cat(tom).

which is equivalent to the rule

cat(tom) :- true.

Here are some sample queries you can ask a Prolog interpreter given this fact:

is tom a cat?

?- cat(tom).  
     yes.

what things are cats?

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

An example for a binary relation is

daugther_father(sally, bob).

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.

[edit] Rules

If a clause's body is not empty, it is called a rule. An example 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_of(X,Y) :- parent_of(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 a comma (","), while disjunction (or) is written as semi-colon (";"). 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 syntactic sugar for the three separate rules:

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

Due to the restriction to Horn clauses, the following is not allowed:

a;b :- c.

[edit] 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). Note that this example has a bug. It will also evaluate sibling(sally, sally) to true, as it can bind X=sally, Y=sally, as of course they both share the same parent.

[edit] 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 and 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, and is sometimes called the "not provable" operator, since the query "?- \+ Goal" succeeds if Goal is not provable.

Negation can be used to correct the sibling/2 term above, to make it return false for sibling(sally,sally).

sibling(X,Y) :- parent(Z,X), parent(Z,Y), \+ X=Y.

Here the negation operator adds a restriction that it is not enough for X and Y to share the same parent, they must not refer to the same entity.

[edit] 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.

[edit] 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.

[edit] 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      -->  [+] ; [-] ; [*].

[edit] Implementation techniques

Prolog code is typically compiled to variants of Warren Abstract Machine code to execute at reasonable efficiency. Some implementations employ Abstract interpretation to derive type and mode information of predicates at compile time. Devising efficient implementation techniques for Prolog code is a field of active research in the logic programming community.

[edit] Examples

Here follows some program examples written in ISO-PROLOG.

[edit] QuickSort

  • split(A,B,C,D) states that C and D are the subsequences of B, where everything in C is at most A, and everything in D exceeds A
  • quicksort(A,S,[]) states that S is A sorted.
  • quicksort(A,S,X) states that S is A sorted, with X appended
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).

[edit] Towers of Hanoi

This example simulates the Towers of Hanoi problem of moving discs from a left pole to a right pole.

hanoi(N) :- move(N, left, right, centre).
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 '),
  write(X),
  write(' pole to the '),
  write(Y),
  write(' pole'),
  nl.

[edit] 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).

[edit] Comparison of 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 Yes Yes Yes Yes Yes Edinburgh Prolog
Open Prolog Mac OS Freeware Yes
Ciao Prolog Unix, Windows GPL Yes Yes Yes Yes Yes ISO-Prolog
GNU Prolog Unix, Windows GPL Yes Yes Yes Yes Yes ISO-Prolog
Visual Prolog Windows Freeware, Commercial Yes Yes Yes Yes Yes Yes Yes
SWI-Prolog Unix, Windows, Mac OS X LGPL Yes Yes Yes Yes Yes Yes Yes Yes ISO-Prolog, Edinburgh Prolog
tuProlog JVM LGPL Yes Yes Yes Yes Yes Yes ISO-Prolog

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

[edit] Extensions

  • HiLog and λProlog extend Prolog with higher-order programming features.
  • F-logic extends Prolog with frames/objects for knowledge representation.
  • 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 from 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.

[edit] External links

Wikibooks
Wikibooks Programming has more about this subject:

[edit] Implementations

[edit] Tutorial introductions

[edit] Advanced level programming

[edit] Conferences

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

[edit] Other resources

[edit] References

  • Michael A. Covington, Donald Nute, Andre Vellino, Prolog Programming in Depth , 1996, ISBN 0-13-138645-X
  • Michael A. Covington, Natural Language Processing for Prolog Programmers, 1994, ISBN 0-13-629213-5.
  • Leon Sterling and Ehud Shapiro, The Art of Prolog: Advanced Programming Techniques, 1994, ISBN 0-262-19338-8
  • Ivan Bratko, PROLOG Programming for Artificial Intelligence, 2000, ISBN 0-201-40375-7.
  • 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.
Preceding: Planner
Subsequent: HiLog, λProlog, Visual Prolog, OW Prolog, InterProlog, SWI-Prolog, Prova, Logtalk, Datalog, Oz
Retrieved from "http://en.wikipedia.org../../../p/r/o/Prolog.html"