Jump to content

Prolog

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 66.174.92.169 (talk) at 21:36, 5 June 2007 (→Negation). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

For the sense of an introduction, see prologue. Prolog was also the precursor to the company now known as Cyan Worlds.
Prolog
ParadigmLogic programming
Designed byAlain Colmerauer
First appeared1972
Major implementations
BProlog,GNU Prolog, Quintus, SICStus, Strawberry, SWI-Prolog, YAP-Prolog
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.

History

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.

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.

Data types

Prolog's single data type is the term. Terms are either atoms, numbers, variables or compound terms.

Atoms

Atoms can be regarded as a special case of compound terms (of arity zero). Examples are: x, blue, 'Some atom'.

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

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".

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:

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

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]

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.

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.

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.

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.

Negation In Prolog

Prolog has historically been poor at handling negative logical statements. If a prolog problem cannot be expressed as a series of positive statements various special Prolog programming techniques are required.

Non-Monotonic Issue In Prolog

Human mental processes must deal with a notoriously "non-monotonic" world. This means that human thought processes are forced to resolve conflicting information sources. Mother told Bob he must "always be frugal", yet a week later, father told Bob that he must show his generosity with friends.

If we create a Prolog program that carefully describes facts and rules about the movement of chess pieces, there is a problem if later a new, conflicting chess rule is officially introduced.

When LATER rules or facts contradict the existing rules and facts, a Prolog application system must have a special strategy for scoring conflict resolution (the non-monotonic issue). Simplistic Prolog applications are written to examine each new fact and reject if new contradicts older, existing facts ... but this type of programming is of limited use in a world where facts are constantly changing.

Prolog excels at reshuffling and re-organizing new, changed facts, if programmed to handle "non-monotonic" input. By contrast, most standard computer databases will accept false data entry without checking if new data fits in logical harmony with existing data.

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)
     ).

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]

ordinary Prolog list manipulation can be used. Here is a binary predicate that takes the input list as its first argument and unifies its second argument with whatever rest is left after the parse is complete (nil after complete parse): 

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. For example, to generate a list of summands from a syntax tree: 

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]

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) ; var(D)), between(0, 9, D) }.

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) ; var(D)), between(0, 9, D)}.

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 also 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.

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

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.

Examples

Here follow some example programs written in Prolog.

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 suited 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]

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).

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).

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) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|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] ;

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.

Dynamic programming

A Prolog program can modify its own clause database at run time. This can make programs harder to understand and also slower than purely logical versions. In some cases though, dynamic updates of the database are very useful and can improve efficiency considerably, in particular for dynamic programming problems. As an example, consider the task of finding the longest common subsequence of two lists. A naive solution is: 

lcs([], _, []) :- !.
lcs(_, [], []) :- !.
lcs([X|Xs], [X|Ys], [X|Ls]) :- !, lcs(Xs, Ys, Ls).
lcs([X|Xs], [Y|Ys], Ls) :-
    lcs([X|Xs], Ys, Ls1), lcs(Xs, [Y|Ys], Ls2),
    length(Ls1, L1), length(Ls2, L2),
    (   L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).

In Prolog systems that support tabling, such as BProlog and XSB, this exponential-time program can be turned into a solution with polynomial runtime by just adding a declaration like: 

:- table lcs/3.

This advises the system to store intermediate results for this predicate. The same effect can be achieved manually in other Prolog systems by using the clause database for memoization. This requires only very few and purely mechanical changes to the original program: 

:- dynamic stored/1.

memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).

lcs([], _, []) :- !.
lcs(_, [], []) :- !.
lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)).
lcs([X|Xs], [Y|Ys], Ls) :-
    memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)),
    length(Ls1, L1), length(Ls2, L2),
    (   L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).

Example query: 

?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls).
Ls = [m, j, a, u]

Comparison of implementations

Platform Features Toolkit Prolog Mechanics
Name OS Licence Native Graphics Compiled Code 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 Yes Edinburgh Prolog
Open Prolog Mac OS Freeware Yes
BProlog Unix, Windows, Mac OS X Free for academic uses Yes Yes Yes Yes Yes Yes Yes Yes Yes ISO-Prolog, plus event-handling, CLP(FD), and tabling
Ciao Prolog Unix, Windows, Mac OS X LGPL Yes Yes Yes Yes Yes Yes Yes Yes Yes ISO-Prolog, plus extensions
GNU Prolog Unix, Windows, Mac OS X GPL Yes Yes Yes Yes Yes Yes ISO-Prolog
Visual Prolog Windows Freeware, Commercial Yes Yes Yes Yes Yes Yes Yes Yes
SWI-Prolog Unix, Windows, Mac OS X LGPL Yes 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 Yes ISO-Prolog with extensions
YAP-Prolog

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

See also Prolog standards compliance.

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.
Wikibooks has a book on the topic of: Prolog

Implementations

Tutorial introductions

Advanced level programming

Conferences

Other resources

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.

Template:Step

Retrieved from "https://en.wikipedia.org/w/index.php?title=Prolog&oldid=136156339"