w:240 h:200

10. Logic Programming

Nataliia Stulova

Logic programming: why?

1960s-1970s: search for new approaches in knowledge representation and reasoning for AI

  • representation: axioms in some logic

  • reasoning: inference rules to prove new theorems from axioms

    Example: first order logic

Axioms:  Oscar is a professor.

Inference rule: If A is a professor, then A gives lectures.

Theorem: Oscar gives lectures.

Logic programming: vison

Program consists of two parts:

  • database of facts (axioms)

    • what data we have about problem domain

  • set of inference rules

    • how to infer new data

Different paradigms

Logic programming
Program = Facts + Rules
or
Program = Logic + Control

Different paradigms

Logic programming
Program = Facts + Rules
or
Program = Logic + Control

Imperative programming
Program = Data structures + Algorithms

Logic programming: first steps

  • 1969 PLANNER programming language (MIT, by Carl Hewitt)

  • 1970 SHRDLU (MIT, by Terry Winograd): NL conversation program about block world

      Person: Which cube is sitting on the table?
  Computer: THE LARGE GREEN ONE WHICH SUPPORTS THE RED PYRAMID.
  Person: Is there a large block behind a pyramid?
  Computer: YES, THREE OF THEM: A LARGE RED ONE, A LARGE GREEN CUBE, AND THE BLUE ONE.
  Person: Put a small one onto the green cube which supports a pyramid.
  Computer: OK.

Logic programming: Prolog

  • 1972 Prolog (Marseille, by Alain Colmerauer et al.)
    • enables programmers to write highly declarative programs that express intuitively logical queries,
    • uses a very powerful backtracking algorithm to answer those queries.

Prolog language basic syntax (1/3)

  • variables (named or anonymous, like last one) X, Value, A12, _42, Res, _

  • numbers 1, -15, 3.1415, 0.23e-5

  • constants (AKA atoms) aa, [], 'hello', @

  • logical connectives: , and, ; or

  • comments: % full line or /* C-style inline */

Prolog language basic syntax (2/3)

  • compound terms:

    • can denote nested data structures person(name(curt), age(27))

    • can denote predicates (logical relations, coming next) and functions (relations between expressions and values, stay tuned)

Name of the compound term is called a functor.

To refer to a term we can write its functor and the number of arguments: person/2, age/1 etc.

Prolog language basic syntax (3/3)

  • facts (named relations between entities in the problem domain)
female(elizabeth).

% 'elizabeth' is a parent of 'charles'
parent(elisabeth, charles).                % here ',' is just a comma
  • rules (named relations that can be inferred from other relations)
% X is a mother of Y IF X is a parent of Y AND X is female
mother(X, Y) :- parent(X, Y), female(X).   % here ',' is a connective

Prolog programs are sets of clauses, that can be either.

Horn clauses

Prolog clauses H :- B1, ..., Bn.

are instances of Horn clauses H if B0 and B1 and ... and Bn

H is the head and B0 and B0 and ... Bn is the body of the clause.

HEAD           BODY
mother(X,Y) IF parent(X,Y) AND female(X)  % rule
female(X)   IF true                       % fact

Computation in an interpreter

Prolog program execution starts with a query (AKA goal)

marked as ?- in the interpreter window ->

A query is a statement that can be answered by expansion using facs and rules.

Running example

Let's consider the domain of genealogical relationships in the British Royal family, written as relations:

  • facts: female/1, male/1, parent/2

  • rules: mother/2, father/2

Closed world assumption

Anything that cannot be inferred with given data is assumed false.

Here this is illustrated for the query ?- female(meghan).

Computation mechanisms

Queries are answered by:

  • matching (sub)goals against facts or rules

  • unifying free variables with terms (NOT assignment)

  • backtracking when (sub)goal matching fails

Let's briefly see these three mechanisms on the family tree example.

Example goal resolution

female(diana).                             parent(diana, william).  % r1
mother(M,C) :- parent(M, C), female(M).    parent(diana, harry).    % r2

Answers to a query (initial goal) ?- mother(diana, C) are computed by expanding sub-goals in a search tree:

                      mother(diana, C) {M=diana}
                              |
                      parent(diana,C),female(diana) {M=diana}
                      / (r1)        \ (r2)
parent(diana,william),female(diana)     parent(diana,harry),female(diana)
      {M=diana, C=william}                           {M=diana, C=harry}

Query to explore values

  • to accept variable unification press ENTER

  • to explore unification options press ; for backtracking

  • use anonymous variables _ when you do not care about some values

Unification and comparison

In Prolog there is no assignment, but terms can be unified and compared using:

  • =/2 - a binary unification operator

  • ==/2 and \==/2 - binary term comparison operators

Arithmetic operations are treated in a special way, stay tuned.

Unification (1/2)

Unification is instantiating variables by pattern matching:

  • a constant only unifies with itself:
?- diana = diana.
yes
?- charles = diana.
no
  • a free variable unifies with anything:
?- parent(elisabeth, charles) = Y.
Y = parent(elisabeth, charles) ?
yes

Unification (2/2)

Unification is instantiating variables by pattern matching:

  • a term unifies with another term only if it has the same functor name and number of arguments, and the arguments can be unified recursively:
?- parent(elisabeth, X) = parent(Y,Z).
Y = elisabeth,
Z = X ? 
yes

Comparison

Comparison operators check if two terms are strictly identical (or not):

  • functors match
  • number of arguments for compound terms matches
  • free variables are shared (same name in scope or explicitly unified)

Backtracking

Prolog applies resolution in deterministic manner:

  • (sub)goals are substituted left to right

  • clauses are tried top-to-bottom

Consider the query: ?- father(F, william)

Disjunction (1/2)

Logical OR operator ; can be used directly in the rules:

is_parent(P, C) :- mother(P, C).
is_parent(P, C) :- father(P, C).

can be written for convenience as:

is_parent(P, C) :- mother(P, C) ; father(P, C).

Disjunction (1/2)

female(diana).     parent(diana, harry).       mother(diana, harry).
male(charles).     parent(charles, harry).     father(charles, harry).

is_mother(M, C) :- parent(M, C), female(M).

is_parent(M, C) :- mother(M, C) ; father(M,C).

When designing the relations about domain objects think first:

  • which way is it easier to express facts?

  • which way makes it faster to evaluate queries?

Recursion

Recursive relations contain the same term in the head and the body:

ancestor(A, D) :- parent(A, D).                 % C1: base case
ancestor(A, D) :- parent(P, D), ancestor(A, P). % C2: recursive case

Remember the left-to-right, top-to-bottom literal and clause evaluation order?

  • be sure to write base case first
  • and the recursive goal - last

Failure

Search can be controlled explicitly with fail/0 special goal.

In the first clause of the predicate printall/1 failture forces exploration of all possible variable unifications.

Note the I/O system predicates: print/1, nl/0

Cuts

Search can be also explicitly controlled by the cut operator !/0, that commits Prolog to a specific search path and controlls backtracking:

parent(C,P) :- mother(C,P), !. % mother is a valid parent
parent(C,P) :- father(C,P).

The ! operator prunes the search tree by telling Prolog to discard:

  • clauses below the clause in which the ! appears

  • all alternative solutions to the goals to the left of the !

Red and Green Cuts

  • A green cut does not change the semantics of the program. It just eliminates useless searching:
max(X, Y, X) :- X > Y, !. % mutually exclusive cases, optmization
max(X, Y, Y) :- X =< Y.
  • A red cut changes the semantics of your program. If you remove the cut, you can get incorrect results: ?- max(5,2,2).
max(X, Y, X) :- X > Y, !. % not really mutually exclusive:
max(_, Y, Y).  % this clause will succeed if comarison before cut fails

Negation as failure

By default there is no negation: remember the closed world assumption?

Negation can be implemented by a combination of a (red) cut and fail:

not(X) :- X, !, fail. % if X succeeds, we fail
not(_).               % if X fails, we succeed

If the ! is removed, the first clause will keep failing both when X succeeds and fails itself, and thus X will trivially succeed always.

Unification and comparison ...and arithmetics

Apart from usual distinction between unification and comparison arithmetic operations are treated separately:

  • is/2 is a function from its second operand to its first

  • =:=/2 and =\=/2 are arithmetic expression comparison operators

Valid goals: X is 3 + 4, 7 + 4 =\= 10 + 2, 2 + 2 =:= 3 + 1

Functions

User-defined functions are written in a relational style:

fact(0, 1).
fact(N, F) :- N > 0,
              N1 is N - 1,
              fact(N1,F1),
              F is N * F1.

Lists

Prolog lists can be written using 3 syntax flavors:

% FORMAL             CONS PAIR          ELEMENT
.(a,[])              [a|[]]             [a]
.(a,.(b,[]))         [a|[b|[]]]         [a,b]
.(a,.(b,.(c,[])))    [a|[b|[c|[]]]]     [a,b,c]
.(a,b)               [a|b]              [a|b]
.(a,.(b,c))          [a|[b|c]]          [a,b|c]

Lists consist of either an empty list [], or a non-empty list (e.g. [a | [b,c]]) consisting of the head element (a) and the tail of the list ([b,c]). Free variables are allowed.

Pattern Matching in Lists

Consider predicate for checking list membership

in(X, [X | _ ]).
in(X, [ _ | L]) :- in(X, L).

and several different queries:

No Order

Since there is no notion of input and return arguments, any argument can be both:

Resources

On logic programming:

On Prolog specifically:

On Ciao Prolog:

Have this for extended slides --- ### Roadmap (still may change) - Logic programming: why, when, how - Prolog facts and rules - SLD resolution: Searching and Backtracking - Lists and Terms - Functions, Recursion, Arithmetics - Extensions (briefly)

-- ## Logic programming in perspective ![ h:450](img/oreilly-poster-langs.png) full version of the poster in [here](https://cdn.oreillystatic.com/news/graphics/prog_lang_poster.pdf)

not covered: strings

```prolog female(elisabeth). parent(elisabeth, charles). % R1 mother(X,Y) :- parent(X, Y), female(X). parent(elisabeth, anne). % R2 ``` rule matching with variable unification for `?- mother(elisabeth, Y)` ```prolog parent(elisabeth, Y) , female(elisabeth) % X = elisabeth, Y free parent(elisabeth, charles), true % Y = charles (from R1) ``` possible backtracking on subgoal `parent(elisabeth, Y)`: ```prolog parent(elisabeth, Y) , female(elisabeth) % X = elisabeth, Y free parent(elisabeth, anne), true % Y = anne (from R2) ```

can be exercise on comparing clause and literal order

dynamic predicates left for the second lecture?