Beginner's Guide to Prolog

Introduction to Prolog #

What is Prolog? #

Prolog (Programming in Logic) is a declarative logic programming language. Unlike imperative languages (like C++ or Java) which specify how to solve a problem step-by-step, Prolog focuses on specifying what the problem is. You define facts and rules about a domain, and Prolog uses its built-in inference engine to deduce answers to queries based on this knowledge. This makes Prolog particularly well-suited for tasks involving symbolic computation, artificial intelligence, knowledge representation, and natural language processing. Its core mechanism involves pattern matching and unification to find solutions.

Why Learn Prolog? #

Learning Prolog offers several advantages:

• Unique Programming Paradigm: Prolog introduces a fundamentally different way of thinking about programming, enhancing your overall problem-solving skills. Understanding declarative programming complements procedural approaches.
• AI and Knowledge Representation: Prolog excels in representing knowledge and reasoning with it, making it a valuable tool for AI projects.
• Problem Solving with Logic: It encourages a more logical and structured approach to problem definition and solution.
• Relatively Easy to Learn (initially): The syntax is relatively straightforward compared to many other languages, allowing for rapid initial progress.
• Powerful Built-in Features: Prolog provides powerful built-in predicates for searching, backtracking, and list manipulation.

Setting up your Prolog environment #

To begin programming in Prolog, you’ll need a Prolog interpreter or compiler. Several options are freely available:

• SWI-Prolog: A popular and widely used, free, and open-source Prolog implementation. It’s a good choice for beginners due to its extensive documentation and community support. Download instructions can be found at [insert SWI-Prolog download link here].
• GNU Prolog: Another free and open-source Prolog system. It’s a robust option, but might have a slightly steeper learning curve than SWI-Prolog. [insert GNU Prolog download link here]
• Visual Prolog: A commercial Prolog system offering a visual development environment. This is often used for more advanced applications.

After downloading and installing your chosen Prolog system, you’ll typically need to open a Prolog console or IDE to start writing and running your programs. Consult your chosen system’s documentation for specific instructions on launching the interpreter.

Your first Prolog program. #

Let’s write a simple Prolog program that defines facts about family relationships and then queries it. Open your Prolog interpreter. Type the following lines, pressing Enter after each:

father(john, mary).
father(john, peter).
mother(jane, mary).
mother(jane, peter).

These lines define facts. father(john, mary). states that John is the father of Mary. Now, let’s ask a question:

?- father(john, mary).

Press Enter. Prolog will respond with:

true.

This indicates that the fact is true based on the knowledge base you provided. Try other queries, such as:

?- mother(jane, X).

This will find all values of X for which Jane is the mother. Prolog will respond with:

X = mary ;
X = peter.

The semicolon (;) allows you to see alternative solutions. Type a semicolon to see the next solution, or type a full stop (.) to finish the query. This simple example demonstrates how Prolog uses facts and queries to deduce information. We will explore more complex examples in the following chapters.

Basic Syntax and Concepts #

Facts #

Facts are the fundamental building blocks of Prolog programs. They represent statements about the world that are considered to be true. A fact consists of a predicate followed by a list of arguments enclosed in parentheses. The arguments represent the objects involved in the relationship described by the predicate. Facts always end with a period (.).

Example:

likes(john, apples).  % John likes apples.
is_a(dog, mammal).    % A dog is a mammal.
age(mary, 30).       % Mary's age is 30.

In these examples, likes, is_a, and age are predicates, and the terms within the parentheses are the arguments. Predicates are essentially names for relationships, and their choice is up to the programmer, although meaningful names improve code readability.

Rules #

Rules express conditional relationships. They state that something is true if certain conditions are met. A rule consists of a head and a body, separated by :-. The head is what the rule concludes, and the body specifies the conditions that must be true for the head to be true.

Example:

parent(X, Y) :- father(X, Y).
parent(X, Y) :- mother(X, Y).

This defines parent(X, Y) to be true if either father(X, Y) is true or mother(X, Y) is true. X and Y are variables (explained below).

Another example:

likes_fruit(Person) :- likes(Person, Fruit), is_fruit(Fruit).

This rule states that a Person likes fruit if they like a specific Fruit and that Fruit is indeed a fruit.

Queries #

Queries are questions posed to the Prolog system. They have the same syntax as the head of a rule, but they are preceded by ?-. Prolog attempts to find solutions that satisfy the query based on the facts and rules in the knowledge base.

Example:

?- likes(john, apples).  % Is it true that John likes apples?
?- parent(john, mary).   % Is John a parent of Mary?
?- parent(X, mary).     % Who is a parent of Mary? (X is a variable)

Prolog will respond with true. if it finds a solution, false. if not, or a series of solutions if multiple are possible, separated by ; (semicolons).

Variables #

Variables in Prolog are represented by uppercase letters or underscore followed by letters, numbers, and underscores (_, X, Y, Person, _age). They act as placeholders for values that Prolog will try to find during the unification process.

Example: (from the previous rules section)

parent(X, Y) :- father(X, Y).

Here, X and Y are variables. When the parent predicate is queried, Prolog will try to find values for X and Y that satisfy the condition father(X, Y).

Unification #

Unification is the core mechanism of Prolog. It’s the process of matching terms (facts, rule heads, query goals, and sub-goals within rules). It involves assigning values to variables to make two terms identical.

Example:

Consider the fact likes(john, apples). and the query ?- likes(john, X).. Unification will attempt to match these two. It will successfully unify the terms by assigning the value apples to the variable X.

Unification involves several steps:

1. Variable Binding: Assigning a value to a variable. Once a variable is bound to a value, that binding remains consistent within the scope of that query or rule execution.
2. Term Equality: Comparing the structure and values of terms. Only terms with the same predicate and arguments of corresponding types can unify.
3. Backtracking: If multiple possible unifications exist, Prolog will try each one sequentially. If a unification path leads to failure, Prolog backtracks to explore other possibilities.

Unification is fundamental to how Prolog searches and infers solutions to your queries. Understanding this process is crucial for writing effective Prolog programs.

Working with Lists #

List Syntax #

Lists are fundamental data structures in Prolog, used to represent sequences of elements. A list is denoted by square brackets [] and elements are separated by commas ,. An empty list is represented by [].

Examples:

• [1, 2, 3] : A list containing the numbers 1, 2, and 3.
• [a, b, c, d] : A list of characters.
• [apple, banana, orange] : A list of strings.
• [1, [2, 3], 4] : A list containing nested lists.

Head and Tail #

A crucial concept in Prolog list processing is the distinction between the head and the tail of a list.

• Head: The first element of a non-empty list.
• Tail: The remaining part of the list (excluding the head). It is itself a list.

Example:

For the list [a, b, c]:

• The head is a.
• The tail is [b, c].

The notation [Head|Tail] is used to represent a list where Head is the first element and Tail is the rest.

Common List Operations #

Prolog provides built-in predicates for common list operations. Here are some of the most important:

• member(X, List): Succeeds if X is a member of List.
• append(List1, List2, List3): Succeeds if List3 is the concatenation of List1 and List2.
• length(List, Length): Unifies Length with the number of elements in List.
• reverse(List1, List2): Unifies List2 with the reverse of List1.

List Manipulation Examples #

1. Membership:

?- member(2, [1, 2, 3]).
true.

?- member(4, [1, 2, 3]).
false.

2. Append:

?- append([1, 2], [3, 4], X).
X = [1, 2, 3, 4].

?- append(X, [3, 4], [1, 2, 3, 4]).
X = [1, 2].

3. Length:

?- length([a, b, c], L).
L = 3.

4. Reverse:

?- reverse([1, 2, 3], X).
X = [3, 2, 1].

5. Custom Predicate (Summing List Elements):

sum_list([], 0).  % Base case: empty list sums to 0
sum_list([Head|Tail], Sum) :-
    sum_list(Tail, SubSum),
    Sum is Head + SubSum.

?- sum_list([1, 2, 3, 4], Sum).
Sum = 10.

This example demonstrates recursion, a common technique for processing lists in Prolog. The sum_list predicate recursively calculates the sum of elements in a list. The base case handles the empty list, and the recursive case adds the head to the sum of the tail. These examples illustrate the power and flexibility of lists in Prolog programming. Many more complex list manipulations can be built upon these foundational operations.

Control Structures #

Cut Operator (!) #

The cut operator, written as !, is a powerful control structure in Prolog. It affects the backtracking mechanism. When a cut is encountered during execution:

1. Commit: All choice points created since the rule’s invocation are removed. This means Prolog will not backtrack to explore alternative solutions within the current rule.
2. Proceed: Execution continues normally after the cut.

Example:

member(X, [X|_]).
member(X, [_|Tail]) :- member(X, Tail).

fast_member(X, [X|_]):- !. %If X is the head, don't explore the tail
fast_member(X, [_|Tail]) :- fast_member(X, Tail).

member/2 is a standard Prolog predicate that checks for membership in a list. fast_member/2 uses a cut to optimize the search. If the element X is found as the head of the list, the cut prevents Prolog from checking the tail, making it more efficient when the element is at the beginning. Without the cut, member/2 would continue to search even after finding a match, especially relevant for larger lists. However, overuse of cuts can lead to unintended consequences, so use them judiciously.

If-Then-Else #

Prolog doesn’t have explicit if-then-else constructs in the same way as imperative languages. However, you can achieve similar functionality using the following techniques:

1. Using ; (semicolon) for “if-then-else”:

The semicolon acts as a disjunction (OR). The first goal that succeeds determines the path of execution.

check_age(Age, Message) :-
    Age >= 18, !,
    Message = 'Adult'.
check_age(_, Message) :-
    Message = 'Minor'.

This code checks the age. If Age is greater than or equal to 18, it assigns ‘Adult’ to Message and the cut (!) prevents checking the second condition. Otherwise, it assigns ‘Minor’.

2. Using conditional goals:

You can embed conditions directly within a rule’s body using logical operators like , (and) and ; (or) alongside predicates that check for conditions.

grade(Score, Grade) :-
    Score >= 90, Grade = 'A'.
grade(Score, Grade) :-
    Score >= 80, Score < 90, Grade = 'B'.
grade(Score, Grade) :-
    Score >= 70, Score < 80, Grade = 'C'.
grade(Score, Grade) :-
    Score < 70, Grade = 'F'.

This defines a grade/2 predicate to determine letter grades based on numerical scores. The Score value will only unify with one rule’s conditions.

Recursion #

Recursion is a fundamental control structure in Prolog, particularly useful for processing lists and trees. A recursive predicate calls itself within its own definition. It must have a base case (a condition that stops the recursion) to avoid infinite loops.

Example (factorial):

factorial(0, 1).    % Base case: factorial of 0 is 1
factorial(N, Result) :-
    N > 0,
    N1 is N - 1,
    factorial(N1, Result1),
    Result is N * Result1.

?- factorial(5, X).
X = 120.

This predicate calculates the factorial of a number. The base case handles N = 0. The recursive case calculates the factorial of N-1 and multiplies it by N.

Recursion is a powerful tool for elegant and concise solutions in Prolog, but it is essential to carefully design the base case to prevent stack overflow errors. Efficient base cases and clear recursive steps are vital for robust recursive predicates.

Advanced Topics (Optional) #

Backtracking #

Backtracking is Prolog’s fundamental search mechanism. When a goal fails, Prolog automatically “undoes” the choices made since the goal was called and tries alternative solutions. This is crucial for finding all possible solutions to a query, especially when dealing with multiple rules or recursive predicates.

Consider the following example:

likes(john, apples).
likes(john, bananas).
likes(john, oranges).

likes_fruit(john, Fruit):- likes(john, Fruit).

?- likes_fruit(john, Fruit).
Fruit = apples ;
Fruit = bananas ;
Fruit = oranges.

When querying likes_fruit(john, Fruit), Prolog first tries to unify likes(john, Fruit) with likes(john, apples). If this succeeds, it finds a solution (Fruit = apples). The semicolon (;) prompts Prolog to backtrack: it undoes the unification and tries the next possible unification—likes(john, bananas). This continues until all solutions have been found. The backtracking mechanism is transparent and automatic in most cases, but understanding how it works is important for debugging and writing efficient Prolog code.

Predicates and Arguments #

A Prolog predicate is a named relationship between objects (represented as arguments). The predicate’s name defines the relationship, while the arguments specify the participating objects.

The arity of a predicate is the number of arguments it takes. likes(john, apples) is a predicate with arity 2 (two arguments). age(mary, 30) also has arity 2. fact(a, b, c, d) has arity 4.

The arguments can be constants, variables, or structures (including lists). The order of arguments is significant; changing the order alters the meaning of the predicate. Proper naming conventions for predicates (e.g., using meaningful names, following consistent capitalization) are essential for code readability and maintainability.

Modules #

Modules provide a mechanism for organizing large Prolog programs. They allow you to create separate namespaces for predicates, preventing naming conflicts and improving code modularity.

:- module(my_module, [my_predicate/1]).

my_predicate(X):- writeln(X).

:- end_module.

This code defines a module my_module containing a predicate my_predicate/1. The :- module(...) declaration introduces the module. Predicates within the module are only accessible using the module’s name: my_module:my_predicate(X). Modules promote code reusability and prevent accidental overwriting of predicate definitions.

Using Libraries #

Prolog systems usually provide libraries of pre-written predicates for various tasks (e.g., string manipulation, I/O operations, arithmetic). You can use these libraries to avoid re-implementing common functions. How to import and use libraries depends on your specific Prolog system (e.g., SWI-Prolog’s use_module directive). Consult your Prolog system’s documentation for details on available libraries and their usage. For example, in SWI-Prolog you might use use_module(library(lists)). to load the lists library which provides additional predicates for list manipulation. Leveraging pre-built libraries can significantly speed up development and improve code quality.

Example Projects #

Family Tree #

This project demonstrates representing family relationships using Prolog facts and rules. We’ll define facts to represent parentage, and rules to deduce other relationships like siblings and ancestry.

Facts:

parent(john, mary).
parent(john, peter).
parent(jane, mary).
parent(jane, peter).
parent(mary, anna).
parent(peter, bob).
male(john).
male(peter).
male(bob).
female(jane).
female(mary).
female(anna).

Rules:

father(X, Y) :- parent(X, Y), male(X).
mother(X, Y) :- parent(X, Y), female(X).
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y. % \= means "not equal to"
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

Queries:

?- father(john, X). %Find children of John
?- sibling(mary, peter). %Are Mary and Peter siblings?
?- ancestor(john, anna). %Is John an ancestor of Anna?

This example illustrates how to represent complex relationships using facts and rules, allowing for flexible querying and inference.

Simple Database #

This project shows how to represent a simple database in Prolog. We’ll create a database of books with their titles, authors, and publication years.

Facts:

book( 'The Lord of the Rings', 'J.R.R. Tolkien', 1954).
book( 'Pride and Prejudice', 'Jane Austen', 1813).
book( '1984', 'George Orwell', 1949).

Rules:

author_of(Author, Title) :- book(Title, Author, _). %The underscore (_) ignores the year.
published_in(Title, Year) :- book(Title, _, Year).

Queries:

?- author_of('Jane Austen', Title).  %Find books by Jane Austen
?- published_in(Title, 1949).      %Find books published in 1949
?- book(Title, Author, Year).   % List all books with details

This example showcases using Prolog to query and manipulate data, akin to a relational database.

Pathfinding #

This project demonstrates a simple pathfinding algorithm using Prolog. We’ll represent a graph as facts, and use recursive rules to find a path between two nodes.

Facts (Graph representation):

connected(a, b).
connected(a, c).
connected(b, d).
connected(c, e).
connected(d, f).
connected(e, f).

Rules (Pathfinding):

path(Start, End, Path) :-
    path(Start, End, [Start], Path).

path(Node, End, Visited, [End|Visited]) :-
    connected(Node, End).

path(Node, End, Visited, Path) :-
    connected(Node, Next),
    \+ member(Next, Visited),  %Check if Next is not already visited
    path(Next, End, [Next|Visited], Path).

Query:

?- path(a, f, Path). %Find a path from node 'a' to node 'f'

This will return one possible path. To find all possible paths, you would need to modify the code to handle backtracking more carefully. This example illustrates how Prolog’s declarative nature and backtracking can be used to solve problems involving search and exploration. Remember to consult your Prolog system’s documentation for specifics on handling backtracking for this kind of problem. The \+ operator means “not.” The member predicate checks for list membership.