Prolog — Programming in Logic

Author(s): Ashani Sansala Kodithuwakku

Originally published on Towards AI.

“Logic will get you from A to B. Imagination will take you everywhere.”

— Albert Einstein —

Introduction

Prolog is the first declarative programming language which was invented by Alain Colmerauer and Philippe Roussel in 1972. It stands for “Programming in Logic”.

In procedural programming languages like Java, C, Python…, we instruct “how to do” something. But in declarative programming languages like Prolog, we instruct “what to do”. In Prolog, we specify the desired goal, rather than instructing the steps to achieve that goal.

Fundamental Concepts

Prolog uses “Horn Clauses” which consists of two parts: head and body. In a horn clause, the conclusion should have only one clause and no negations. Prolog uses upper-case letters for variables and lower-case letters for constants.

student(Harry).
student(harry).

Here, “Harry” is a variable and “harry” is a constant. In Prolog, we use,

Facts, Rules and Queries

They are the building blocks of Prolog, which use predicate logic expressions.

Facts

Facts declare some known things which are always true. For example,

father(harry, peter).

This fact declares that Harry is the father of Peter. It’s unconditionally true.

Rules

Rules specify things that may be true if some condition is satisfied. The format of the rules is,

conclusion :- conditions.

Rules defines the relationship based on other facts or rules. For example,

grandparent(X,Z) :- parent(X,Y), parent(Y,Z).

Here we have declared the grandparent relationship using two parent relationships. It means that the parent of Z is a child of X. So, X is the grandparent of Z.

Queries

In Prolog, queries are like questions about relations defined in the program. For example, it’s like “who is the father of Peter?”

?-parent(X, peter).

Example

Let’s consider following family tree example to understand this more clearly.

Here the summary of the family tree is Anakin and Padme have two children: Luke and Leia. Leia and Han have one child called Ben. Ben’s uncle is Luke, and his grandparents are Anakin and Padme.

Now, let’s see how to implement these relations in Prolog.

parent(padme, luke).
parent(padme, leia).
parent(leia, ben).
parent(anakin, luke).
parent(anakin, leia).
parent(han, ben).

female(padme).
female(leia).

male(anakin).
male(luke).
male(han).
male(ben).

Here I have added facts as parent relations with male and female. Now let’s add some rules.

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

grandparent(X,Z) :- parent(X,Y), parent(Y,Z).

brother(X,Y) :- parent(P,X), parent(P,Y), male(X), X\==Y.

uncle(X,Y) :- parent(P,Y), brother(X,P).

Here I have constructed some rules for relations. Mother relation has been built using parent and female facts. If someone is a parent and also is a female, we can say that she is a mother.

In grandparent relationship, two parent relations are used. Also, in brother relation, parent of both X and Y are same, and to be a brother, X should be a male.

Uncle relation has been constructed as brother of a parent.

Now we are clear about how to implement facts and rules. Let’s see how to use queries for those relationships.

?-parent(X, luke).

Here we are asking like “Who is parent of Luke?”. We get the answer:

X = padme

If we add a ‘;’ at the end, we can get different solutions for this by backtracking.

X = padme;
X = anakin.

Also, here are some more queries and answers…

?- brother(X, leia).
X = luke.

?- grandparent(X,Y).
X = padme,
Y = ben;
X = anakin,
Y = ben.

?- uncle(X, ben).
X = luke.

?- female(X).
X = padme;
X = leia.

Now we know how to write facts, rules and queries in Prolog. Let’s see how Prolog actually answer these queries.

How Queries Work

When we insert a query, Prolog consider it as a goal to be satisfied by the program. Then, the goal is matched with fact or head of a rule in the program.

When matching with the head of a rule, Prolog substitute the actual values for variables and generates sub-goals. Similarly, Prolog tries to satisfy those sub-goals one by one.

Now we know the core concepts in Prolog. But there more concepts like Prolog Data Objects, Structures, Lists, Arithmetic in Prolog, Inputs and Outputs, etc. We will learn them in upcoming articles.

Applications of Prolog

Prolog, with its foundation in formal logic and declarative syntax, is used in various applications that benefit from its strengths in pattern matching, symbolic reasoning, and logical inference.

Here are some of the key applications of Prolog:

Expert Systems

Prolog is used to develop expert systems, which are AI programs that simulate the decision-making abilities of a human expert. For example, a medical diagnosis system can be developed using Prolog by creating a knowledge base.

Natural Language Processing (NLP)

Prolog’s strength in handling symbolic information makes it ideal for NLP tasks, such as parsing, understanding, and generating human language. Prolog can be used to build chatbots, language translation systems, and information retrieval systems.

Database Querying

Prolog’s logical foundations suit complex database querying and data integration. Prolog is used in deductive databases, which extend traditional relational databases with deductive capabilities. These systems can derive new information based on existing data using logical rules.

Constraint Logic Programming

Prolog is a powerful tool for solving constraint satisfaction problems (CSPs), which involve finding values for variables that satisfy a set of constraints.

Scheduling and Planning

Prolog can be used for scheduling tasks, such as workforce scheduling, timetabling, and project planning, where constraints must be respected. Prolog helps in resource allocation problems, where limited resources must be distributed optimally according to specific constraints.

Theorem Proving and Formal Verification

Prolog is used in automated theorem proving and formal verification, which involve proving the correctness of mathematical theorems and software programs.

Conclusion

In artificial intelligence, Prolog is a key language for logic programming. Its unique approach, focusing on “what” needs to be done rather than “how,” makes it a powerful tool in artificial intelligence.

Even though LISP is also an AI programming language, it is not considered a logic programming language. So, Prolog is the only declarative programming language in AI.

References

Prolog Programming for Artificial Intelligence by lvan Bratko

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI