Prolog
From Wikipedia, the free encyclopedia
| Paradigm: | Logic programming |
|---|---|
| Appeared in: | 1972 |
| Designed by: | Alain Colmerauer |
| Major implementations: | GNU Prolog, Quintus, SICStus, Strawberry, SWI-Prolog, YAP |
| Dialects: | ISO Prolog, Edinburgh Prolog |
| Influenced: | Visual Prolog, Mercury, Oz, Erlang, Strand |
Prolog is a logic programming language. It is a general purpose language, which is especially associated with artificial intelligence and computational linguistics. It consists of both a purely logical language, which might be called "pure Prolog", and a concrete language, which augments pure Prolog with a number of extralogical features.
Pure Prolog was originally restricted to the use of a resolution theorem prover with Horn clauses of the form
- H :- B1, …, Bn..
The application of the theorem-prover treats such clauses as procedures
- to show/solve H, show/solve B1 and … and Bn.
Pure Prolog was soon extended, however, to include negation as failure, in which negative conditions of the form not(Bi) are shown by trying and failing to solve the corresponding positive conditions Bi.
The name Prolog for the concrete language was chosen by Philippe Roussel as an abbreviation for "PROgrammation en LOGique” (French for programming in logic). It was created around 1972 by Alain Colmerauer with Philippe Roussel, based on Robert Kowalski's procedural interpretation of Horn clauses. It was motivated in part by the desire to reconcile the use of logic as a declarative knowledge representation language with the procedural representation of knowledge that was popular in North America in the late 1960s and early 1970s.
Much of the modern development of Prolog came from the impetus of the fifth generation computer systems project (FGCS), which developed a variant of Prolog named Kernel Language for its first operating system.
Contents |
[edit] Data types
Prolog's single data type is the term. Terms are either atoms, numbers, variables or compound terms.
[edit] Atoms
Atoms can be regarded as a special case of compound terms (of arity zero). Examples are: x, blue, 'Some atom'.
[edit] Numbers
In addition to floats and integers which are prescribed by the Prolog ISO standard, many Prolog implementations also provide rational numbers and unbounded integers. For example:
?- X is 2^200, Y is (3 rdiv 8) + (4 rdiv 9). X = 1606938044258990275541962092341162602522202993782792835301376 Y = 59 rdiv 72
[edit] Variables
Variables are denoted by a string consisting of letters, numbers and underscore characters, and beginning with an upper-case letter or underscore. Variables closely resemble variables in logic in that they are placeholders for arbitrary terms. A variable can become instantiated via unification. For example:
?- T = f(X, g(X)), X = a. T = f(a, g(a)), X = a
A single underscore (_) denotes an anonymous variable and means "any term".
[edit] Compound terms
A compound term has a functor and a number of arguments, which are again terms. The number of arguments is called the term's arity. Examples for terms are f(a,b) and p(x,y,z). Some operators can be used in infix notation. For example, the terms +(a,b) and =(X,Y) can also be written as a+b and X=Y, respectively. Users can also declare arbitrary sequences of symbols as new infix or postfix operators to allow for domain-specific notations. Special cases of compound terms:
[edit] Lists
Lists are defined inductively: 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
A sequence of characters surrounded by quotes is equivalent to a list of (numeric) character codes, generally in the local character encoding or Unicode if the system supports Unicode. For example:
?- Xs = "Πρόλογ". Xs = [928, 961, 972, 955, 959, 947]
[edit] Programming in Prolog
Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to Horn clauses, a Turing-complete subset of first-order predicate logic. Turing completeness can be shown by encoding transitions of a given Turing machine by means of a relation between states of the machine. 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 system given above fact:
is tom a cat?
?- cat(tom). Yes
what things are cats?
?- cat(X). X = tom
An example for a binary relation is
daughter_father(sally, bob).
As a general purpose language, Prolog provides various built-in predicates to perform routine activities like input/output, using graphics and otherwise communicating with the operating system. These predicates are not given a relational meaning and go beyond the purely logical subset of the language. They are only useful for the side-effects they exhibit on the system. For example, the predicate write/1 can be used for output to the screen. Thus,
write('Hello').
will display the word 'Hello' on the screen.
Functional programming can be regarded as a proper subset of logic programming since functions are a special case of relations. Due to the relational nature of many built-in predicates, they can typically be used in several directions. For example, length/2 can be used to determine the length of a list as well as to generate a list skeleton of a given length, and also to generate both list skeletons and their lengths together:
?- length(Ls, L). Ls = [], L = 0 ; Ls = [_], L = 1 etc.
Similarly, append/3 can be used both to append two lists:
?- append([a,b,c], [d,e], Ls). Ls = [a,b,c,d,e]
as well as to split a given list into parts:
?- length(Xs, 2), append(Xs, Ys, [a,b,c,d,e]). Xs = [a,b] Ys = [c,d,e]
For this reason, a comparatively small set of library predicates suffices for many Prolog programs. All predicates can also be used to perform unit tests:
?- append([x], [], [x]). Yes ?- append([x], [y] [x]). No
Such queries can be embedded in programs and allow for automatic compile-time regression testing.
[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 short for these 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
Execution of a Prolog program is initiated by the user's posting of a single goal, called the query. Logically, the Prolog engine tries to find a resolution refutation of the negated query. The resolution method used by Prolog is called SLD-resolution. If the negated query can be refuted, it follows that the query, with the appropriate variable bindings in place, is a logical consequence of the program. In that case, all generated variable bindings are reported to the user, and the query is said to have succeeded. Operationally, Prolog's execution strategy can be thought of as a generalization of function calls in other languages, the difference being that multiple clauses can match a given call. In that case, the system creates a choice-point, and continues with the goals of the first alternative. If any goal fails in the course of executing the program, chronological backtracking is used to continue execution at the most recently created alternative. For example:
sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y). parent_child(X, Y) :- father_child(X, Y). parent_child(X, Y) :- mother_child(X, Y). mother_child(trude, sally). father_child(tom, sally). father_child(tom, erica). father_child(mike, tom).
This results in the following query being evaluated as true:
?- sibling(sally, erica).
yes.
The interpreter arrives at this result as follows: Initially, the only matching clause for the query sibling(sally, erica) is the first one, so proving the query is equivalent to proving the body of that clause with the appropriate variable bindings in place, i.e., the conjunction (parent_child(Z,sally), parent_child(Z,erica)). The next goal to be proved is the leftmost one of this conjunction, i.e., parent_child(Z, sally). Two clause heads match this goal. The system creates a choice-point and tries the first alternative, whose body is father_child(Z, sally). This goal can be proved using the fact father_child(tom, sally), so the binding Z = tom is generated, and the next goal to be proved is the second part of the above conjunction: parent_child(tom, erica). Again, this can be proved by the corresponding fact. Since all goals could be proved, the query succeeds. Since the query contained no variables, no bindings are reported to the user. A query with variables, like:
?- father_child(Father, Child).
enumerates all valid answers on backtracking.
Notice that with the code as stated above, the query sibling(sally, sally) also succeeds (X = Y). One would insert additional goals to describe the relevant restrictions, if desired.
[edit] Loops and recursion
Failure-driven loops are one way to express iteration in Prolog. The idea is to force the system's implicit execution mechanism to iterate over all solutions by using the built-in predicate fail/0. For example, to print "123" on the terminal, you can post the query:
?- between(1, 3, N), write(N), fail.
This is mostly useful for predicates with side-effects such as input/output. In all other cases, iterative algorithms should be implemented by means of recursive predicates. Prolog systems typically implement a well-known optimization technique called tail call optimization (TCO) for deterministic predicates exhibiting tail recursion or, more generally, tail calls: A clause's stack frame is discarded before performing a call in a tail position. Therefore, deterministic tail-recursive predicates are executed with constant stack space, like loops in other languages. Accumulator introduction is an important technique to formulate predicates in a tail-recursive manner. For example, reversing a list can be written as:
reverse([], Acc, Acc).
reverse([L|Ls], Acc0, Acc) :-
reverse(Ls, [L|Acc0], Acc).
All elements are pushed on an accumulating list, and the base case yields the accumulated elements. Initially, the accumulating list is typically empty in queries:
?- reverse([a,b,c], [], Rs). Rs = [c,b,a]
One would therefore introduce the additional predicate:
reverse(Ls, Rs) :- reverse(Ls, [], Rs).
for this frequent use-case.
[edit] Negation
Due to the restriction to Horn clauses, negating a goal in the body of a rule is not permitted. As an approximation to general negation as known from logic, Prolog provides negation as failure. The goal "\+ illegal(X)" in the rule
legal(X) :- \+ illegal(X).
is evaluated is follows: Prolog attempts to prove illegal(X). If a proof for that goal can be found, the original goal (i.e., \+ illegal(X)) fails. If no proof can be found, the original goal succeeds. Therefore, the \+/1 prefix operator used above is called the "not provable" operator, since the query "?- \+ Goal" succeeds if Goal is not provable. This kind of "negation" is sound if its argument is ground. Soundness is lost if the argument contains variables. In particular, the query "?- legal(X)." can now not be used to enumerate all things that are legal.
\+/1 can be used to prevent sibling(sally,sally). from succeeding in the example above.
sibling(X,Y) :- parent(Z,X), parent(Z,Y), X \== Y.
\==/2 is a built-in predicate, and A \== B is equivalent to \+ (A == B). This adds the restriction that it is not enough for X and Y to share the same parent, they must also not be equal. For this particular case of negation, many Prolog systems provide a more declarative solution in the form of the built-in predicate dif/2:
sibling(X,Y) :- dif(X, Y), parent(Z,X), parent(Z,Y).
Posting the constraint dif/2 restricts its arguments to constitute distinct terms. It remains sound even when posted on arguments containing variables.
[edit] Operational considerations
Under a declarative reading, the order of rules, and of goals within rules, is irrelevant since logical disjunction and conjunction are commutative. Procedurally, however, it is important to take into account Prolog's execution strategy, either for efficiency reasons, or due to the semantics of impure built-in predicates for which the order of evaluation matters.
For example, we can write code to count the number of elements in a list.
list_length([], 0). list_length([_|Ls], Length) :- list_length(Ls, Length0), Length is Length0 + 1.
This is read as: The length of the empty list is 0, and the length of a non-empty list is one plus the length of the list without the first element. In this case, it is important that the arithmetic built-in predicate is/2 be called after Length0 has become ground, since is/2 can't work on variable arguments. That is, the order of goals matters.
Similar considerations apply to the order of clauses:
gamble(X) :- gotcredit(X), \+ gotmoney(X). gamble(X) :- gotmoney(X).
You gamble if you either got credit and no money, or you have money. Evaluation of gotmoney(X) and gotcredit(X) might be very costly - for example, it might access your Internet banking account to check your balance, which takes time. However, checking whether you can get a loan is not necessary if you know you have money, so you can first transpose the clauses:
gamble(X) :- gotmoney(X). gamble(X) :- gotcredit(X), \+ gotmoney(X).
and then use the cut operator to tell the interpreter to skip the second alternative if the first succeeds:
gamble(X) :- gotmoney(X), !. gamble(X) :- gotcredit(X), \+ gotmoney(X).
The built-in predicate !/0 ("cut") commits to the clause it appears in. In this case, the cut is said to be "green", since if gotmoney(X) succeeds in the first clause, the second clause can't succeed anyway (because gotmoney/1 can't both hold and not hold). So the green cut only serves as a hint to the Prolog system to prune a useless alternative. However, if gotmoney(X) does not hold, the second rule will be tried, and gotmoney(X) will be evaluated again. This is also useless, since gotmoney/1 is already known not to hold by this time, otherwise the second rule wouldn't have been tried in the first place. So you can change the code to
gamble(X) :- gotmoney(X), !. gamble(X) :- gotcredit(X).
The cut is said to be "red", since it changes the declarative semantics of the program. The clauses now can't be understood in isolation, and it's hard to give such programs a logical meaning. In this case, it's clearer to use if-then-else:
gamble(X) :-
( gotmoney(X) ->
true
; gotcredit(X)
).
[edit] DCGs and parsing
There is a special notation called definite clause grammars (DCGs). A rule defined via -->/2 instead of :-/2 is expanded by the preprocessor (expand_term/2, a facility analogous to macros in other languages) according to a few straight-forward rewriting rules, resulting in ordinary Prolog clauses. Most notably, the rewriting equips the predicate with two additional arguments, which can be used to implicitly thread state around, analogous to monads in other languages. DCGs are often used to write parsers or list generators, as they also provide a convenient interface to list differences. For example, to parse tokenized input like
[x, =, 2]
we can use ordinary Prolog list manipulation: We use a binary predicate which takes the input list as its first argument and whatever rest we get after the parse is complete (the rest should eventually be [] if the parse was successful). Here is 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).
This can be written more conveniently using DCG notation:
statement --> id, assign_op, digit. id --> [x]. assign_op --> [=]. digit --> [2].
and results in exactly the same code.
DCGs also work in the other direction, i.e. list generation. To generate a list of summands from a syntax tree, we can use
summands(n(N)) --> [N]. summands(A+B) --> summands(A), summands(B).
This can be used to generate a list of summands from a given syntax tree:
?- summands(n(3)+(n(4)+n(5)), Ss, []). Ss = [3, 4, 5]
[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 DCGs (assuming the input like [a, =, 3, *, b, ;, b, =, 0, ;] etc.):
sentence --> statement, sentence_r.
sentence_r --> [].
sentence_r --> statement, sentence_r.
statement --> id, [=], expression, [;].
expression --> term, expression_r.
expression_r --> [].
expression_r --> [+], term, expression_r.
expression_r --> [-], term, expression_r.
term --> factor, term_r.
term_r --> [].
term_r --> [*], factor, term_r.
factor --> id.
factor --> [D], {number(D), D >= 0, D =< 9}.
id --> [a].
id --> [b].
This corresponds to a predictive parser with one token look-ahead. The program can be used to test whether a given list is in the language generated by the grammar:
?- phrase(sentence, [a,=,1,+,3,*,b,;,b,=,0,;]). Yes
By augmenting the predicates with additional arguments to keep track of the parsed elements, an abstract syntax tree (AST) of the parsed sentence can be created in parallel to parsing it:
sentence(S) --> statement(S0), sentence_r(S0, S).
sentence_r(S, S) --> [].
sentence_r(S0, seq(S0, S)) --> statement(S1), sentence_r(S1, S).
statement(assign(Id,E)) --> id(Id), [=], expression(E), [;].
expression(E) --> term(T), expression_r(T, E).
expression_r(E, E) --> [].
expression_r(E0, E) --> [+], term(T), expression_r(plus(E0,T), E).
expression_r(E0, E) --> [-], term(T), expression_r(minus(E0, T), E).
term(T) --> factor(F), term_r(F, T).
term_r(T, T) --> [].
term_r(T0, T) --> [*], factor(F), term_r(times(T0, F), T).
factor(id(ID)) --> id(ID).
factor(digit(D)) --> [D], {number(D), D >= 0, D =< 9}.
id(a) --> [a].
id(b) --> [b].
Example query:
?- phrase(sentence(S), [a,=,1,+,3,*,b,;,b,=,0,;]). S = seq(assign(a, plus(digit(1), times(digit(3), id(b)))), assign(b, digit(0))) ;
The AST is represented using Prolog terms and can be used to apply optimizations, to compile such expressions to machine-code, or to directly interpret such statements. As is typical for the relational nature of predicates, these definitions can be used both to parse and generate sentences, and to check whether a given tree corresponds to a given list of tokens. Using iterative deepening to fairly enumerate valid sentences together with their corresponding syntax trees ("fair" means that each arbitrary but fixed sentence will be generated eventually), we obtain:
?- length(Ts, _), phrase(sentence(S), Ts). Ts = [a, =, a, (;)], S = assign(a, id(a)) ; Ts = [a, =, b, (;)], S = assign(a, id(b)) etc.
[edit] Higher-order programming
Since arbitrary Prolog goals can be constructed and evaluated at run-time, it is easy to write higher-order predicates like maplist/2, which applies an arbitrary predicate to each member of a given list, and sublist/3, which filters elements that satisfy a given predicate, also allowing for currying:
?- maplist(write, [1,2,3]). 123 ?- sublist(==(1), [a,f(b,c),1,X,1], Ns). Ns = [1, 1];
It is also often useful to convert solutions from temporal representation (answer substitutions on backtracking) to spatial representation (Prolog terms). For this purpose, Prolog has various all-solutions predicates that collect all answer substitutions of a given query in a list:
?- findall(N, between(1,5,N), Ns). Ns = [1, 2, 3, 4, 5]
This can be used for list comprehension. For example, perfect numbers equal the sum of their proper divisors:
perfect(N) :-
between(1, inf, N), U is N >> 1,
findall(D, (between(1,U,D), N mod D =:= 0), Ds),
sumlist(Ds, N).
A list of all divisors of N between 1 and N/2 is built, then they are summed over. This can be used to enumerate perfect numbers, and also to check whether a number is perfect:
?- perfect(N). N = 6 ; N = 28 ; etc. ?- perfect(12). No
[edit] Implementation techniques
For efficiency, Prolog code is typically compiled to abstract machine code, often influenced by the register-based Warren Abstract Machine (WAM) instruction set. Some implementations employ abstract interpretation to derive type and mode information of predicates at compile time, or compile to real machine code for high performance. Devising efficient implementation techniques for Prolog code is a field of active research in the logic programming community, and various other execution techniques are employed in some implementations. These include clause binarization and stack-based virtual machines.
[edit] Examples
Here follow some example programs written in Prolog.
[edit] Puzzles
Due to its implicit execution strategy, Prolog is well suited for prototyping brute-force searches, which often suffices for smaller problems and puzzles like the following:
Three couples are dancing tango at a party. Each couple is formed by one man and one woman. The three men are wearing red, green and blue suits, and the three women are also wearing red, green and blue dresses. The red suite man is dancing with the green dress woman. In no couple are the two dancers dressed the same colour.
tango(Couples) :-
Couples = [red+green, green+_, blue+_],
member(_+blue, Couples),
member(_+red, Couples),
\+ member(X+X, Couples).
Yielding:
?- tango(Cs). Cs = [red+green, green+blue, blue+red]
[edit] QuickSort
Not all Prolog programs make use of backtracking. Any deterministic algorithm can be formulated deterministically in Prolog as well. An example for this is the well-known QuickSort sorting algorithm:
- partition(Xs, Pivot, Smalls, Bigs) partitions the list Xs into elements smaller than Pivot and elements equal to or larger than Pivot
- quicksort(Xs, Ss) relates a list to its sorted version
partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
( X @< Pivot ->
Smalls = [X|Rest],
partition(Xs, Pivot, Rest, Bigs)
; Bigs = [X|Rest],
partition(Xs, Pivot, Smalls, Rest)
).
quicksort([], []).
quicksort([X|Xs], Ascending) :-
partition(Xs, X, Smaller0, Bigger0),
quicksort(Smaller0, Smaller),
quicksort(Bigger0, Bigger),
append(Smaller, [X|Bigger], Ascending).
DCG notation allows for a more concise version of quicksort/3:
quicksort([]) --> [].
quicksort([X|Xs]) -->
{ partition(Xs, X, Smaller, Bigger) },
quicksort(Smaller),
[X],
quicksort(Bigger).
[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),
format("move a disc from the ~w pole to the ~w pole\n", [A,B]),
move(M, C, B, A).
[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,_,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] Turing machine
Turing completeness of Prolog can be shown by using it to simulate a Turing machine:
turing(Tape0, Tape) :-
perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
( Rs0 == [] ->
Sym = b, RsRest = []
; Rs0 = [Sym|RsRest]
),
once(rule(Q0, Sym, Q1, NewSym, Action)),
action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
perform(Q1, Ls1, Ls, Rs1, Rs).
action(left, Ls0, Ls, Rs0, Rs) :-
( Ls0 == [] ->
Ls = [], Rs = [b|Rs0]
; Ls0 = [L|Ls], Rs = [L|Rs0]
).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
The predicate turing/2 defines a relation between initial tape contents and the contents after a given Turing machine, starting in state q0 and looking at the first cell specified in the input (or blank if no input is specified), has performed its actions and moved to its final state, qf. The atom "b" is used to denote blank tape cells. The tape cells not specified in the input and not shown in the output are to be considered as containing blank symbols. A simple example Turing machine is specified by the facts:
rule(q0, 1, q0, 1, right). rule(q0, b, qf, 1, stay).
This machine performs incrementation by one of a number in unary encoding: It loops over any number of "1" cells and appends an additional "1" at the end. Example query and result:
?- turing([1,1,1], Ts). Ts = [1, 1, 1, 1] ;
[edit] Meta-circular evaluator
Prolog is a homoiconic language and provides many facilities for reflection. Its implicit execution strategy makes it possible to write a concise meta-circular evaluator for pure Prolog code:
mi_circ(true).
mi_circ((A,B)) :- mi_circ(A), mi_circ(B).
mi_circ(clause(A,B)) :- clause(A, B).
mi_circ(A \= B) :- A \= B.
mi_circ(G) :-
G \= true,
G \= (_,_),
G \= (_\=_),
G \= clause(_,_),
clause(G, Body),
mi_circ(Body).
A simple example predicate:
natnum(0). natnum(s(X)) :- natnum(X).
The result of the interpreter interpreting itself on its execution of the query natnum(X):
?- mi_circ(mi_circ(natnum(X))). X = 0 ; X = s(0) ; X = s(s(0)) a Yes
Since Prolog code can be treated as data (represented using Prolog terms) that is easily read using built-in mechanisms (like read/1), it is easy to write interpreters that augment Prolog with domain-specific features.
[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, Mac OS X | LGPL | Yes | Yes | Yes | Yes | Yes | Yes | Yes | Yes | ISO-Prolog, plus extensions | ||
| 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 | ||||
| Strawberry Prolog | Windows, Unix | Freeware, Commercial | Yes | Yes | Yes | Yes | ISO-Prolog with extensions | ||||||
*C/Java interface can also be used for graphics and OS control.
[edit] Extensions
- Constraint logic programming is important for many Prolog applications in industrial settings, like time tabling and other scheduling tasks. Most Prolog systems ship with at least one constraint solver for finite domains, and often also with solvers for other domains like rational numbers.
- 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.
- Prolog-MPI is an open-source SWI-Prolog extension for distributed computing over the Message_Passing_Interface.
- Datalog is actually a subset of Prolog. It is limited to relationships that may be stratified and does not allow compound terms. In contrast to Prolog, Datalog is not Turing-complete.
- 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.
[edit] External links
[edit] Implementations
- WIN Prolog by Logic Programming Associates
- Open Prolog, an Apple Mac implementation.
- Ciao Prolog, open source under GPL and LGPL
- GNU Prolog, open source under GPL
- C#Prolog, interpreter written in C#, open source under GPL, C#Prolog
- YAP Prolog, open source under Artistic License
- Visual Prolog, formerly known as PDC Prolog and Turbo Prolog
- SWI-Prolog, open source under LGPL
- Strawberry Prolog, specially designed for education. Download
- AI::Prolog, a perl module that comes with a prolog command-line interpreter
- SICStus Prolog
- ECLiPSe, 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
- 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
- Common Prolog, an implementation within LispWorks KnowledgeWorks product
- ALS Prolog
- W-Prolog, a Prolog interpreter in a Java applet.
- AI::Prolog, a pure Perl Prolog interpreter loosely based on W-Prolog.
- Prolog.NET, a Prolog compiler for the .NET framework.
- EZY Prolog, a Prolog interpreter and IDE for Windows
- GraphTalk, a proprietary WAM based implementation with object extensions, designed for building of information systems.
- The Poplog system implements a version of Prolog, with POP-11, and optionally Common Lisp (CL), and Standard ML (SML), allowing mixed language programming. For all, the implementation language is POP-11, which is compiled incrementally. It also has an integrated Emacs-like editor that communicates with the compiler.
- REBOL Prolog, prolog.r at Rebol.org
[edit] 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
- Prolog minibook by Faiz ul haque Zeya
- Learn Prolog Now! by Patrick Blackburn, Johan Bos and Kristina Striegnitz
- Prolog and Logic Programming by Dr Peter Hancox
- Strawberry Prolog Help, online help
- Strawberry Prolog Tutorial by Dimitar Gelev
[edit] 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.
[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.
This article is part of a series on programming languages.
 |
|
| Preceding: | Planner |
| Subsequent: | HiLog, λProlog, Visual Prolog, OW Prolog, InterProlog, Strawberry, SWI-Prolog, Prova, Logtalk, Datalog, Oz |
