Prolog stands for PROgrammation en LOGique (French). Motivated by the fields of artificial intellegence (AI) and computational linguistics, Prolog was very popular in the US, Europe, and Japan when a lot of funding for the "fifth generation" project was underway. This was a massive government/industry research project in Japan during the 1980s.
Three people are credited with inventing various parts of Prolog, Philippe Roussel, Alain Colmerauer, and Robert Kowalski. David H. D. Warren invented a low-level abstract machine that defines a WAM instruction set. The WAM engine does optimizations such as first argument indexing, selection of choice-points, tail call optimization, and memory reclamation on failure.
Today, Prolog is supported by an active open source community (espcially GNUProlog). Other than the open source enthusiasts and researchers, Prolog has almost no installations in industry. Nevertheless, concepts found in Prolog are used in industry. Specialized proprietary systems use adaptations of some key Prolog concepts in their implementations.
Rule based systems such as Airline Reservations and Computerized Law systems use implmentations of theorem provers that are quite similar to Prolog's search engine. Internet-base fraud detection systems make use of unification-base pattern matching engines that borrow ideas from Prolog's unification engine.
Programming in prolog is like writing a theorem, where the Prolog system generates the proof from facts and rules written by the programmer. The heart of the Prolog engine consists of (1) a pattern matching algorithm based on "unification" (2) a specialized (in-memory) database engine to explore rules and facts and (3) a "resolution" engine to explore the search space, constructing rules to provide a proof for a given query.
Prolog has two modes, a mode for entering queries, and a mode for entering facts and rules. Here is an example of entering a GNUProlog program. The session begins with a prompt for a query, but the user immediately enters a command to switch from query mode to fact entering mode.
| ?- [user]. wears_tie(johnny). wears_tie(mike). cool(X) :- wears_tie(X).
At the query mode prompt, the programmer requests that gprolog switch to fact/rule entering mode with "[user]." The user enters two (2) facts followed by one (1) rule. The rule says, "someone, X, is cool if X wears a tie". Typing an End-of-file (^D or ^Z) returns gprolog to query mode.
Here is a transcript of some queries.
| ?- cool(johnny). yes | ?- cool(mike). yes | ?- cool(bill). no | ?- cool(X). X = johnny ? h Action (; for next solution, a for all solutions, RET to stop) ? ; X = mike yes
The last query says, "for what X can gprolog prove that X is cool?" Gprolog burps out the values it used for X as a side effect of the proving process.
Atoms include numbers, symbols, [] (the empty list). Single quotes can be used for symbols when they contain spaces. Here are some examples of atoms.
23 'an atom' another_atom []
Variables are denoted by a symbol consisting of letters, numbers and underscore characters. Variables begin with an upper-case letter or underscore. Variables are not like those of a vonNeuman archicture; you cannot assign to them repeatedly. A variable can become instantiated via unification, and thereafter cannot be assigned to another value.
Variable that start with underscore are different. Each occurance of an underscore varible (starts with _) denotes an anonymous variable different from the other anonymous variables. The use of anonymous variables becomes useful when unifying terms.
Terms are compound, made up of a functor followed by 0 ore more arguments. Unlike Scheme, prolog terms are written using the familiar mathematical notation.
foo(1, goo, []).
The notation f/n denotes a term with functor f and arity n. So, foo/3.
Terms may be nested.
bar(baz(quux(25,37), quuux(10,20))).
Prolog introduces some convenient equivalent shorthand syntaxes for readability.Infix notation is predefined for some commonly used functors; and you may create your own infix notation and precedence rules for operators you define.
==(3, 3) 3==3 cow > dog >(cow, dog) 1 + 2 +(1, 2) .(car, cdr)
The '.' functor when used with exactly two arguments creates a list construct similar to a CONS cell.
Note that lists have two representative syntaxes. The first uses '.'/2 as a CONS cell and the second uses square brackets with list elements separated by comma's. Improper lists use a '|' to separate the non-null formed tail.
[1, 2, 3] .(1, .(2, .(3, []))) .(a, b) [a | b]
Not that the dot can be used either as a functor (as with lists), or can be used to terminate predicates, rules, or facts.
Strings use double quotes and are are represented by lists of integer values for their ASCII collating sequences. Strings are compound so technically they're not atomic. Sadly, Prolog predates Unicode, and has little/no support for non-ASCII characters.
"hello" [104,101,108,108,111]
Unification involves recursively comparing the components of two terms while filling in wildcards (specified by variables).