A joyful and pleasant journey in the wonderful world of Answer Set Programming, with practice

The goal of this humble tutorial is to introduce Answer Set Programming (aka ASP) in ~30 minutes to beginners in declarative languages to show how to implement expert systems.

Introducing Answer Set Programming

Unlike imperative languages, declarative languages as ASP are not designed to depict algorithms, namely sequences of operations to perform to solve a problem, but to depict the problem itself and let a solver find solution(s) if there is any. ASP is more specifically used to solve Logical Problems, modeled using Predicates Logics.

Tools required for this tutorials

An ASP solver, such as DLV or CLASP
A text editor, your favorite one is the best

The dark art of propositional calculs

Let's jump now directly into a simple example of problem to be solved using ASP. Adlane, 11 years old and Bernadette, 2 years younger than Adlane, are respectively the son and daughter of Charles, who is their dad and 28 years older than Adlane, and Denise their mom 2 years younger than Charles. Charles himself is the son of Emmanuel, his 27 older dad, and Fatima, his mom, 4 years younger than Emmanuel. How to represent such family through predicates and automatically enumerate Adlane's grandparents? Finally, who is the oldest ?

We will first enumerate all the characters, using unary predicates:


					people(adlane).

					people(bernadette).

					people(charles).

					people(denise).

					people(emmanuel).

					people(fatima).

Those predicates are true, no matters the rest of the problem. In the same way, we will depict their relationships, using 2-arity predicates :


					is_son_of(adlane,charles).

					is_son_of(adlane,denise).

					is_daughter_of(bernadette,charles).

					is_daughter_of(bernadette,denise).

					is_son_of(charles,emmanuel).

					is_son_of(charles,fatima).

People familiar with ontologies might be familiar with 2-arity predicates as using such predicate to connect two elements can be used to depict knowledge in the same way as a triple store in ontology databases.

Let's now implement the predicate is_grandson_of, such that "a people A is the grandson of a people B iff A is the son of a people C is the son or daughter of B. In ASP we can write such predicate as :


					is_grandson_of(A,B):- is_son_of(A,C), is_son_of(C,B).

					is_grandson_of(A,B):- is_son_of(A,C), is_daughter_of(C,B).

Please notice a couple of elements here. First you can see the symbol ":-" that somehow can be understood as "if". This symbol means that the left part (head of the rule) is true if the right part (body of the rule) is true. Please note that it is a "if" and certainly not "iff" nor "if and only if". In the example shown above, A is the grandson of B if A is the son of C and C the son of B OR if A is the son of C and C the daughter of B. The second detail is that variables starts with a capital letter, where atoms starts with a small letter.

Negations

They are two negations in ASP : the strong and weak one.

Strong (or classical) negation is noted in ASP with the minus symbol "-" such negative formula is true only if the following formula is false
Weak (or default) negation is noted in ASP using the "not" keyword and not A is true only if A is false OR in unknown

To illustrate the use of negation, let's add few more people in the familly: Guillaume, another grandson of Emmanuel and Henry, guillaume's dad and Emmanuel's son.


					people(guillaume).

					people(henry).

					is_son_of(guillaume,henry).

					is_son_of(henry,emmanuel).

We would like to infer now all the cousins in the family. To do so, we can use various definitions. Let's explore few alternatives using different types of negations.

Alternative 1: using classical negation

A first intuitive definition of cousins might be "people sharing at least one grandparent, without being siblings". To implement that, we may directly implement relations such as.


					-siblings(guillaume,adlane).

					-siblings(guillaume,bernadette).

					-siblings(A,B):- -siblings(B,A).

					

					cousins(A,B):- is_grandson_of(A,C), is_grandson_of(B,C), -siblings(A,B).

                                        cousins(A,B):- is_granddaughter_of(A,C), is_grandson_of(B,C), -siblings(A,B).

                                        cousins(A,B):- is_granddaughter_of(A,C), is_granddaughter_of(B,C), -siblings(A,B).

					cousins(A,B):- cousins(B,A).

The main drawback of such approach is the need to declare every pair of people not being siblings, which will lead to combinatorial explosion if the familly gets bigger. To avoid such issue, we can look for the second alternatve.

Alternative 2: using default negation

Instead of declaring pairs of people not being siblings, we can declare siblings and check if such relation exists to see if they are cousins.


                                	siblings(adlane,bernadette).

                                        siblings(A,B):- -siblings(B,A).


					cousins(A,B):- is_grandson_of(A,C), is_grandson_of(B,C), not siblings(A,B), A!=B.

                                        cousins(A,B):- is_granddaughter_of(A,C), is_grandson_of(B,C), not siblings(A,B), A!=B.

                                        cousins(A,B):- is_granddaughter_of(A,C), is_granddaughter_of(B,C),  not siblings(A,B), A!=B.

                                        cousins(A,B):- cousins(B,A).

Alternative 3 : exercice

We explored two possibilities to declare siblings (or non-siblings) but knowing already their parents, can you write a rule able to infer siblings and then list every cousins?

Arithmetic comparison

ASP also proposes arithmetic comparators