Theoretical Introduction: Logic Programming

This article gives a short introduction in logic programming concepts, which are needed to write the source code of an agent.

For a general understanding of logic programming it can be helpful to start by considering Prolog, in detail we recommend SWI-Prolog, because there are many applications and good tutorials to understand the main mechanism of logic programming.

Design Time

When discussing logic programs, we are talking about a symbolic definition. We are writing source code in symbols, facts and rules. The difference between imperative programming and a logic program is that the latter does not define how the problem should be solved. It only defines the facts and rules needed to calculate the solution. In a more general way it defines the constraints which are needed to solve the problem. Based on this definition, the runtime creates an internal structure to solve the problem.

In LightJason’s agent developing process, you have to write an agent script in our AgentSpeak(L++) programming language which describes the behaviour of the agent. The script describes what and when the agent should do. This process is named design time, because you design the behaviour without knowledge about the real execution process. During design time there are some concepts to understand related to the structure of our logic programming language, which are shown in the following.

Note: The following sections are also covered in our knowledge base.
For more information see → Terms, → Atoms, → Literals, → Variables, → Facts and Beliefs, → Rules and → Unification.

Terms

In short: Everything is a term.

All elements within the AgentSpeak(L++) code are terms, forming the building blocks of a super (generic) data structure. In our framework we distinguish two different types of terms:

• Raw terms are terms with a native Java data type. In such a term any Java data structure can be stored, but it cannot be used by the normal behaviour mechanisms of the logic programming language. Unification and assignments are nonetheless possible on these raw data structures.
• Other terms like literals are structured objects which are described in the following.

In LightJason an inheritance model exists to build a software architecture for these structured elements. The root element is the ITerm interface and the ITerm inheritance diagram shows the structure of the relations.

Atoms & Literals

The simplest structural elements of a logic programming language are atoms which are part of literals. In the Prolog definition and consequently also in AgentSpeak(L++) all literals and atoms begin with a lower-case letter. Additionally, atoms can also contain slashes / and minus - characters. For clarification see the following example:

We would like to define that the sun is shining

sun( shining() )

The word sun and the word shining are atoms, the whole structure sun(shining()) is named literal.

Another example is a time definition:

We would like to say it is currently 2 o’clock post meridiem (pm)

time( current( hour(2), minute(0), period( pm() ) ) )

You can see that a literal can store a list of other literals or values inside the brackets.

Based on the first example a negation is also possible:

We would like to say it is currently not raining

~raining()

The tilde ~ in front of a atom defines the strong negation

Variables

Variables are specialised terms to store information during runtime. They can be used to define literals with a placeholder and (in contrast to atoms or literals) begin with an upper-case letter.

Based on the time example we added some variables to extract the hour, minute and period part of the literal

time( current( hour( Hour ), minute( Minute ), period( Period ) ) )

Note: The upper-case variables Hour, Minute and Period can be assigned to values automatically. This mechanism is called unification.

Within a logic programming language exists a specialised variable which is just the underscore _. This variable can be sloppy named as trash can. You can use this special variable for defining a variable whose value should be ignored.

In contradistinction to the time example above, we would like to ignore the period, i.e. the am()/pm() part, so we say, that we would like to get the current time and ignore the 12-hour clock period.

time( current( hour( Hour ), minute( Minute ), period( _ ) ) )

With this definition we can get a very flexible structure for extracting some information from the literals.

Beliefs and Facts

Based on the definition of variables and literals we are defining a fact as a literal without variables. A fact is a literal which defines a state or an information (independent from whether the information is correct or wrong). In relation to a multi-agent system a belief is a fact about the knowledge or the environment. So the fact defines a state or a point of view of an object without any information about the correctness.

Rules

Rules, in contrast to literals, variables and facts, are an executable structure. Rules can be seen as static functions in a logic programming language with some additional structure.

One of the most famous examples for rules in logic programs is the Fibonacci sequence. Mathematically this sequences is defined as $$F_n = F_{n-1} + F_{n-2}$$ $$F_0 = 0$$ $$F_1 = F_2 = 1$$ For the value $n=5$ the sequence is calculated as $$F_5 = F_4 + F_3 = (F_3 + 1) + (1+1) = ((1+1)+1) + (1+1) = 5$$ Based on this calculation you can see that each function element $F_n$ which is not defined as $1$ gets resolved in a recursive way. A Prolog rule, which calculates the Fibonacci number of any input can be written as follows:

fibonacci(0,0).
fibonacci(1,1).
fibonacci(2,1).
fibonacci(N,R) :-
    N > 1,
    N1 is N-1,
    N2 is N-2,
    fibonacci(N1,R1),
    fibonacci(N2,R2),
    R is R1 + R2
.

One of the most important aspect of a Prolog program is, that the exit conditions are written first. The last item in the rule is the calculation to be made, iff no other condition can be matched. The last rule can be read in the following way (the comma is pronounced as a logical and):

If (N is greater than 1) and (N1 can be set to N-1) and (N2 can be calculate to N-2) and (the rule fibonacci(N1,R1) can be successfully executed) and (the rule fibonacci(N2,R2) can be successfully executed) and (R can be calculated to R1 + R2) then the rule will be finished successful

The order of the rule is very important, because Prolog tries to find a rule, which can be matched successfully, the first rule that matches will be used. Variables will be set during runtime and the values will be passed back as a reference, which is named side effect. In imperative programming languages these side effects are undesired, but can be very helpful in logic programming languages.

But an advice regarding writing such rules: In the worst-case, the logic programming runtime will have to check all possibilities to calculate a solution. The system tries to find a successful solution with a backtracking algorithm. This can be a NP-complete problem and so a solution cannot be calculated efficiently.

Runtime

In the section design time we talked about a symbolic representation of data. We can define such data in the agent script and during the execution of the agent we would like to modify the data. From an abstract point of view, we are talking about deductive reasoning, that means in a slopping sentence: We are generating new knowledge, based on the current knowledge of the agent.

The description of the figure is that we are modelling the $\Delta$ during design time with any kind of facts. During runtime, the agent can modify the knowledge and generate implicit knowledge about the environment which is based on the previous knowledge $\Delta$. The implicit knowledge is named $belief(\Delta, \rho)$

Unification

Unification is the process for setting values from one literal into the variables of another literal, e.g. determining the current value of Colour in light(Colour).

Note: Colour is a variable!

Based on the previous time example the procedure can look as follows:

We have two literals, one literal with values and another literal with variables

time( current( hour( 2    ), minute( 0      ), period( pm() ) ) )
time( current( hour( Hour ), minute( Minute ), period( _    ) ) )

Based on this structure the systems tries to transfer the values from the first literal into the variables of the second literal such that both literals are equal. If it is not possible, the unification process will fail. During a successful execution the variable Hour stores the value $2$ and the variable Minute the value $0$.

The runtime of the logic programming language tries to find an executable structure so that all unification components and rules can be finished successfully. The unification process can be used to generate new literals based on existing literals. In combination with rules the system can solve complex reasoning structures. If the system cannot find any possibility to solve the problem, the logic program will be stopped with a failure. The goal of the runtime is to find a successful solution.