11. Logic Programming Applications

Nataliia Stulova

Green and red cuts revised: optimize the search

Geen cuts (discarding solutions we do not need)

E.g., personnel management software: one address is enough

• pay attention to variable unifications
• pay attention to declarative semantics
• solutions with and without green cuts should match

Green and red cuts revised: optimize the search

Red cuts (manipulating the search in a wrong way, avoid)

E.g., for a given year return a number of days (but forgot to account for unification in the head)

queries that will succeed: ?- days_in_year(4, 365). ?- days_in_year(a, D)

Think sets, use lists

A lot of Prolog computations is producing sets of possible solutions to a query/goal, like with printall/1

Lists are the native data structure that most intuitively represents sets.

Lists and aggregates

A number of system predicates is available to return sets of answers collected with backtracking:

• setof/3 (and bagof/3)

Lists and aggregates

A number of system predicates is available to return sets of answers collected with backtracking:

• setof/3 (and bagof/3)
• findall/3
• findnsols/4

Ciao Aggregates

Higher-order

Processing parallel lists is very common, especially when using higher-order predicates like maplist/N

HO predicates accept other predicates (inc/2, sum/3) as arguments natively in Prolog, just make them visible in the scope (interpreter, module).

Ciao HO predicates

Higher-order

Processing parallel lists is very common, especially when using higher-order predicates like filter/3, partition/4

Logic Programming + Relational Databases = Deductive Databases

Origins: the 1977 Symposium on Logic and Data Bases

Deductive databases have the advantage of making inference (deduction) of additional facts based on relations (facts and rules) already present in the database.

• data representation: relations (based on Horn clauses)

• query language: Datalog

Datalog VS Prolog

• recursion is allowed
• negation is allowed, but only for facts
• clause order does not matter
• not cut !/0 operator to control search
• function symbols not allowed - cannot construct complex terms (e.g. person(name(elisabeth), age(inf), ...) has to be expressed as person(elisabeth, inf, ...))
• queries are made on finite sets of values, so termination is guaranteed

Datalog queries and database operations

consider relations P(x,y), Q(x,y,z):

• intersection I(x,y) :- P(x,y), Q(x,y,_). (logical AND)
• union U(x,y) :- P(x,y). ; U(x,y) :- Q(x,y,_). (logical OR)
• difference D(x,y) :- P(x,y), not Q(x,y,_).
• projection Px(x) :- P(x,_).
• selection S(x,y) :- Q(x,y,_), x > 10.
• product PR(x,y,z,v,w) :- P(x,y), Q(z,v,w).
• join J(x,y,z) :- P(x,y), Q(y,z,_).
• ...

Datalog systems - few examples

logicblox.com - a commercial implementation of Datalog used for web-based retail planning and optimization

datomic.com - a transactional database with a flexible data model, elastic scaling, and rich queries

... and many more systems with Datalog components

Constraint satisfaction problems

In the fields of artificial intelligence and operations research there is a need in answering questions in different domains that specify a number of constraints for an answer:

• route planning with time or price budget
• diet meal preparation accounting for calories intake
• solving chess problems (e.g. N-queens)
• map coloring

Constraint satisfaction problems are typically solved using a form of search.

Constraint Logic Programming (CLP)

CLP is an extension of logic programming that includes constraint satisfaction in the computations:

CLP = Prolog + Solver(for a given domain)

Some domains:

• finite (CLPFD) - e.g. the familty tree
• rational numbers (CLP(Q))
• real numbers (CLP(R))

CLP(R) in Ciao 1/2

As a language extension CLP functionality is available as a library that defines special operators: .=./2 (equals), .<./2 (less than), etc.

Example: vector dot product
$(x_1,\ldots,x_N)\cdot(y_1,\ldots,y_N)=\\{x_1}\cdot{y_1}+\ldots+{x_N}\cdot{y_N}$

CLP(R) in Ciao 2/2

Another example: solving systems of linear equations

$3x + y = 5\\x+8y=3\\$

To solve this system we reuse the dot product relation for each equation

Ciao Language Extensions

Program correctness: testing and verification

Two (complementary) approaches to checking correctness of program behavior

Testing

• at run time
• for specific inputs (e.g. min(-2,5,-2))

Verification

• at compile or run time (or both)
• for classes of inputs (e.g., min(+,-,-))

Software verification

• define properties in a domain of interest: memory addresses, numeric ranges of array indices, dangling pointers, energy consumption constratins...

• write program specifications using these properties (often in some formal laguage)

• check the specifications with some technique: code instrumentation, theorem proving, logical inference

Specification examples

Horn clause-based program verification

• programming language and its specification are based on same formal representation

• nowadays a number of mature analysis techniques and tools exist for logic programs analysis and verification

• for several high-level languages (C/C++, Java) their intermediate representation (produced by the compiler) can be straightforwardly translated to Horn clauses

Example: factorial (1/2)

Consider the factorial function in XC, a dialect of C for microcontroller programming:

Properties of interest: energy consumption estimates.

Example: factorial (2/2)

ISA (instruction set architecture) instructions for the XC program and respective Horn clause representation with a specification

Some HC-based verification tools

for Java, XC, C and C++ the Ciao preprocessor - CiaoPP - offers abstract interpretation-based analyses over several domains: types, variable instantiation, bounds on computational and energy costs etc

JayHorn is a software model checking tool for Java that tries to find a proof that certain bad states in a Java program are never reachable.

IBM Watson

"We required a language in which we could conveniently express pattern matching rules over the parse trees and other annotations"

Natural Language Processing With Prolog in the IBM Watson System

Languages and grammars (1/2)

Every language has a grammar - a set of elements and rules on combining those elements.

Consider English language and some of its elemets (parts of speech):

• articles: definite the, and indefinite a and an
• nouns: proper alice, and common cat, fish, bat
• pronouns: she, whose, their
• verbs: play, eats
• ...

Languages and grammars (2/2)

We need to add some rules to combile language elements:

$sentence \rightarrow noun\_phrase, verb\_phrase\\ noun\_phrase \rightarrow article, noun\\ verb\_phrase \rightarrow verb, noun\_phrase$

Let's try to build sentences with the elements we have defined so far:

Sentences as lists

We can express sentences as lists of elements provided by Prolog facts and rules:

Why lists? Sentences can be of arbitrary length and designing terms for each possible structure is not feasible.

Grammar in Prolog v1

We can both parse and generate sentences with this implementation

However, this is a computation-heavy implemetnation.

Alternative specialized representation:
difference lists

Difference lists

Prolog's special way of representing lists for language parsing and generation tasks:

• X-X is the empty list []
• [a,b,c]-[] is the list [a,b,c]
• [a,b,c,d]-[d] is the list [a,b,c]
• [a,b,c|T]-[T] is the list [a,b,c] - with a free tail

Think of it as a literal difference between the first and the second list.

Definite clause grammars

In addition to difference lists, Prolog has a special notation for grammar representation, that implicitly uses difference lists:

s --> np, vp.

is an expansion of a difference lists version:

s(A-C) :- np(A-B), vp(B-C). (or s(S-[]) :- np(S-VP), vp(VP-[]).)

which is in turn a from of:

s(S) :- np(NP), vp(VP), append(NP,VP,S).

Grammar in Prolog v2

Notice how we still need to provide the two list arguments in the query ?-s([a,cat,eats,a,fish],[]).