Prolog is a declarative programming language based on logical inference. It is the main example of a language in the logic programming paradigm.
Download tuProlog, a Prolog interpreter written in Java:
Extract the contents of the zip file, and double-click the file bin/2p.jar to start the Prolog interpreter. Or, cd to the bin directory and run the command
java -jar 2p.jar
in a shell window.
Note: names of symbols must be written in lower-case letters.
1 2 3
A relation is a table of facts. Here is a father relation
homer bart homer lisa homer maggie grandpa homer grandpa herb
The first item in each tuple of the relation represents a person who is a father. The second item is a person who is a child of that father.
Relations can thus be formed as a collection of explicit facts, called ground truths. Each fact is a tuple belonging to the relation. In Prolog, we specify ground truths as
relation ( list of atoms )
Here are some ground truths:
An inference rule allows new facts to be inferred from existing facts.
conclusion :- hypothesis.
Facts and inference rules may use variables. A variable is a name, in upper-case letters, which stands for some possible member of a tuple in a relation.
Example: X is Y’s paternal grandfather if there exists Z such that X is Z’s father, and Z is Y’s father:
Note that X, Y, and Z are all variables, and the comma means “and” in the sense of a logical conjunction.
We can describe a paternal grandmother in a similar way:
Here is a possible set of inference rules:
Note the definition of the inference rule defining the siblings relation:
The semicolon means “or” in the sense of logical disjunction. That is because two people are siblings if either they share the same father or mother. Also, the \= operator means “not equals”, preventing any person from being considered to be his or her own sibling. (Prolog allows the same value to be bound to multiple variables.)
We can type in a potential fact, and based on the ground truths and the available inference rules, Prolog will attempt to find a derivation that proves that the fact is true.
This query is true because a ground truth matching the query exists.
is false because this fact cannot be derived using the available ground truths and inference rules.
In general, answering a query requires constructing a chain of inferences. For example, the query
is true because the facts
are ground truths, enabling the query
to be true if marge is substituted for the variable Q in the rule defining the samemother relation. This, in turn, is sufficient to deduce that
A more interesting query
is true because
which is sufficient to deduce that
is true. Note that the query
is false, because there is no derivation for this fact.
Queries with unknowns
The real power of Prolog can be seen when a query contains one or more variables, which represent unknowns: for each variable, Prolog will attempt to find a value which can be substituted for the variable in order to make the query true.
For example, the query:
yields the answer
yes. X / grandpa Solution: paternal_grandfather(grandpa,bart)
showing that grandpa can be substituted for the variable X in order to make the query true.
Note that a query with variables could lead to multiple solutions. For example, the query
yields two solutions, one where lisa is substituted for X, and one where maggie is substituted for X.
Prolog is a declarative programming language because we never specify how we want a computation to be performed. We simply use ground truths and inference rules to describe a problem, and allow the inference algorithm to deduce a solution.
Declarative programming is nice because it allows us to specify a problem at a higher level.
Other declarative programming languages:
The language for Makefiles is especially interesting because, like Prolog, it is a logic programming language.