Prolog is a logic programming language. The name Prolog is taken from programmation en logique (French for "logic programming"). It was created by Alain Colmerauer around 1972. It was an attempt to make a programming language that enabled the expression of logic instead of carefully specified instructions on the computer. 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 computerilliterate linguists.) A lot of the research leading up to modern implementations of Prolog came from spinoff 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. Prolog is based on predicate calculus (more precisely firstorder predicate calculus); however it is restricted to allow only Horn clauses. Execution of a Prolog program is effectively an application of theorem proving by firstorder resolution. Fundamental concepts are unification, tail recursion, and backtracking. Data types
Prolog does not employ data types in the way usual in the common programming languages. 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 lowercase letter. Usually, if nonalphanumeric atom is needed, it is surrounded with apostrophes (e.g. '+' is an atom, + is an operator).
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 uppercase letter. In the Prolog environment, a variable is not a container that can be assigned to (unlike procedural programming languages). Its behaviour is closer to a pattern, which is increasingly specified by unification. The so called anonymous 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). The number of parameters, 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):  atom [] is an empty list
 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), [])))))
Strings Strings are usually written as a sequence of characters surrounded by quotes. They are often internally represented as lists of ASCII codes.
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). Stores the Prolog fact that 'tom' is a 'cat'. More formally, 'cat' is the head, and 'tom' is the 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; no. 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 Pat is the father of Sally? father(sally,pat). father(pat,sally). In both cases 'father' is the head and 'sally' and 'pat' are arguments. However in the first case, Sally comes first in the argument list, and in the second, Pat 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(pat,sally). father(jessica,james). Some predicates are built in 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 statements in Prolog is rules. 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 ancedent and consequent are in reverse order to that normally found in logic. It is possible to place multiple predicates in a consequent, joined with conjunction, for example: a,b,c : d. which is simply equivalent to three separate rules: a : d. b : d. c : 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 given the prolog code sibling(X,Y) : parent(Z,X), parent(Z,Y). father(X,Y) : parent(X,Y), male(X). mother(X,Y) : parent(X,Y), female(X). parent(X,Y) : father(X,Y). parent(X,Y) : mother(X,Y). mother(trude, sally). father(tom, sally). father(tom, erica). father(mike, tom). male(tom). female(trude). male(mike). 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 (colloquially; substituting) 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 mother(X,Y) : parent(X,Y), female(X). parent(X,Y) : father(X,Y). Might seem suspicious. After all, not every parent is a father. But it is true that any father is a parent. On the other hand, someone is only someone's mother if she is both that person's parent and female. 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 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) : NOT 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 By Failure.
Execution Prolog is a logical language, so in theory you 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 unnecessarily long. For example, we can write code to count the number of elements in a list. elems([],0). elems([HT], 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 nonempty, 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), NOT 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. But the same goes for gotcredit. In theory, prolog implementations might evaluate these rules out of order, so you might as well have written; gamble(X) : gotcredit(X), NOT gotmoney(X). gamble(X) : gotmoney(X). Which 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 rule you wrote first. 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), NOT 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. Cutandpaste accidents lurk in dark corners. If the rules got mixed up, you might now max out your credit card before spending your cash.
Examples Here follows some program examples written in ISOPROLOG. Check this wikipedia article for a standard Hello world program in Prolog and several other languages.
QuickSort split(H, [AX], [AY], Z) : order(A, H), split(H, X, Y, Z). split(H, [AX], Y, [AZ]) : not(order(A, H)), split(H, X, Y, Z). split(_, [], [], []). quicksort([], X, X). quicksort([HT], S, X) : split(H, T, A, B), quicksort(A, S, [HY]), quicksort(B, Y, X). Towers of Hanoi hanoi(N) : move(N, left, centre, right). move(0, _, _, _) : !. move(N, A, B, C) : M is N1, 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 easiness 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(UV,X,AB) : d(U,X,A), d(V,X,B). /* d uv 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^(C1)*W) : atomic(C), C \= X, d(U,X,W). /* d u^c dx = c*u^(c1)*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(UV,X,AB) : i(U,X,A), i(V,X,B). /* Int UV 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*VA) : 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). Implementations Extensions  Visual Prolog ( http://www.visualprolog.com/ ), also formerly known as PDC Prolog and Turbo Prolog. Visual Prolog is a stronglytyped 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 Created in order to answer Prolog's lack of graphics and interface.
References  Runnable examples (http://www.csse.monash.edu.au/~lloyd/tildeLogic/Prolog.toy/Examples/)
 A Prolog interpreter in a Java applet (http://ktiml.mff.cuni.cz/~bartak/prolog/testing.html)
 Prolog: The ISO standard (http://pauillac.inria.fr/~deransar/prolog/docs.html)
 Prolog Tutorial (http://cs.wwc.edu/~cs_dept/KU/PR/Prolog.html)
 Alain Colmerauer's and Philippe Roussel's account of the birth of Prolog (http://www.lim.univmrs.fr/~colmer/ArchivesPublications/HistoireProlog/19november92.pdf)
The following are major programming languages used by at least several thousand programmers worldwide:
