Factorial Recursion in Prolog

Left: The factorial function implemented in Prolog.

Right: A tree representation of the goal factorial(3,6).

Kodethon provides an environment to program in Prolog. Prolog is a general-purpose logic programming language. Prolog is a relatively old programming language developed in 1972 by Alain Colmerauer and Philippe Roussel. Despite its age, Prolog is a relatively obscure programming language.

Nonetheless, it is still useful. For example, in 2005, NASA used Prolog to write a natural language interface for International Space Station.1 Also, IBM coded parts of its Watson supercomputer in Prolog.

Generally, Prolog is a suitable choice for applications where objects and their relations are important. For example, parsing natural languages is relatively simple in Prolog. Creating and searching databases is also relatively easy.

Syntax

A Prolog program is a collection of clauses. There are two types of clauses, facts and rules.

A rule has the form Head :- Body. This means that Head is true if Body is true. The following are example rules.

male(james) :- true.
male(charles) :- true.
female(elizabeth) :- true.

A fact is a clause with an empty body. The following are example facts.

female(sophia).
parent(charles, james).
parent(elizabeth, james).

Alternatively, you can think of a fact as rule where the body is the built-in term true. For example, the two following clauses are equivalent.

female(sophia).
female(sophia) :- true.

Prolog has a single data type called a term. A term can be:

  • an atom,
  • a number,
  • a variable,
  • or a compound term.

An atom is a string of characters that represents an object. For example, x, red, ‘Taco’, and ‘some atom’ are all atoms. In the snippets above, sophia, charles, james, and elizabeth are all atoms.

A number is either an integer or a float. For example, 42 and 3.14 are both numbers.

A variable is a string of characters that serve as placeholders for arbitrary terms. For example, in male(X), X is a variable.

A compound term is composed of an atom called a functor and a number of “arguments”. For example, truck_year('Mazda', 1986), female(sophia), and parent(charles, james) are all compound terms.

A Complete Prolog Program

The following code is a complete Prolog program.

male(james).
male(charles).
female(elizabeth).
parent(charles, james).
parent(elizabeth, james).

This program does not print anything to the computer. It does not compute any fancy math equation but it is complete and does several things. It introduces several objects, for example, james and charles. It declares certain properties about those objects, for example, male(james). And it declares a relationship between some of those objects, for example, parent(charles,james).

Prolog Interpreters

To execute Prolog programs you need to install a Prolog interpreter, like GNU Prolog or SWI-Prolog. You can install the interpreter yourself or simply use Kodethon. Kodethon provides environments that allow you to use these interpreters.

In Kodethon, to use GNU Prolog,

  1. Select the Prolog/gnu-1.4.4 environment.
  2. In the CDE Shell, type terminal. A new window/tab will open.
  3. In the terminal window, type gprolog.

In Kodethon, to use SWI-Prolog,

  1. Select the Prolog/swi-7.4.1 environment.
  2. In the CDE Shell, type terminal. A new window/tab will open.
  3. In the terminal window, type swipl.

Loading a Prolog Program

We save the Prolog program above in a file named sample.pl.

kodethon@kodethon:~/prolog$ cat sample.pl 
male(james).
male(charles).
female(elizabeth).
parent(charles, james).
parent(elizabeth, james).

We run GNU Prolog. Then we consult the file by typing ['sample.pl'].. If the file does not contain any syntax errors, then the interpreter will output yes.

kodethon@kodethon:~/prolog$ gprolog
GNU Prolog 1.4.4 (64 bits)
Compiled Apr  4 2017, 05:52:23 with gcc
By Daniel Diaz
Copyright (C) 1999-2013 Daniel Diaz
| ?- ['sample.pl'].
compiling /home/kodethon/prolog/sample.pl for byte code...
/home/kodethon/prolog/sample.pl compiled, 5 lines read - 686 bytes written, 3 ms
(4 ms) yes
| ?-

Consulting a Prolog Program

Prolog interpreters, generally, have two modes: definition and query mode. In definition mode, you can define new facts and rules. In query mode, you cannot define new facts or rules; you can only query the collection of clauses you have defined. By default, the interpreter starts in query mode. At the prompt (| ?-), you enter a goal, also called a query.

Prolog uses SLD Resolution to determine if a given goal is a logical consequence of the program. The interpreter will report yes if it determines that the goal is satisfiable and report generated variable bindings. The interpreter will report no otherwise.

Below, for example, we enter the goal male(james). Prolog searches the facts we loaded and reports yes since it can conclude that fact from the program.

| ?- male(james).  
yes

As the second goal, we enter male(X). Using the first fact, the interpreter binds james to X. It reports the binding, and prompts the user for next action. The semicolon (;) tells Prolog to unbind X and continue searching the database for more possible unifications of X. Prolog uses the second fact to bind charles to X. It responds yes to indicate that there are no more possible unifications with X.

| ?- male(X).  
X = james ? ; 
X = charles 
yes

In the example below, we enter the goal male(elizabeth). Prolog responds with no. This fact is not in the database.

| ?- male(elizabeth).
no
| ?-

At a high level, you can see that the simple Prolog program was just a database of facts and that we can query it with a Prolog interpreter to get answers.

Summary

To summarize, in this article, we have:

  1. Introduced you to Prolog, a logic programming language.
  2. Shown you its basic syntax.
  3. Discussed two interpreters.
  4. Shown you how to load a prolog program.
  5. Shown you how to make queries.

There is a lot more to learn. Here are some resources:

  1. https://en.wikipedia.org/wiki/Prolog
  2. http://www.learnprolognow.org/
  3. https://www.cpp.edu/~jrfisher/www/prolog_tutorial/contents.html
  4. http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/
  5. https://bernardopires.com/2013/10/try-logic-programming-a-gentle-introduction-to-prolog/
  6. https://www.metalevel.at/prolog

We plan on building our own tutorial to take advatange of Kodethon’s Embed feature. Stay tuned!

Footnotes

  1. https://pdfs.semanticscholar.org/d0df/2fa0d0ebbcbeb20c922fad507c1be55371f8.pdf ↩