The Logic Programming Paradigm

The Logic Paradigm

• An imperative language implementing a mapping from inputs to outputs using commands.
• In the functional paradigm the basic unit of computation is a function, and thus obviously implements a mapping.
• In the logic paradigm the basic unit of computation is a relation which is more general than mapping. A relation can have several distinct outputs for the same input. Below is a relation. Which is one to many mapping relation.

  enrolled-in relation
     Class  |  Student
    ------------------
     cp2003 |  joe
     cp3120 |  joe
     cp2003 |  mary 
     cp2003 |  michelle
        .....

• Assume also that we have a teaches relation which is one to one mapping relation.

     teaches relation 
  
     Class  |  Lecturer
    -------------------
     cp2003 |  Jinli 
     cp3210 |  Geoff

• Let's represent these relations as a set of facts using Prolog.

    enrolled-in(cp2003, joe).
    enrolled-in(cp3120, joe).
    enrolled-in(cp2003, mary).
    enrolled-in(cp2003, michelle).
    teaches(cp2003, Jinli).
    teaches(cp3210, Geoff).

A logic program can be thought of a consisting of

• a set of facts (plus assumption that these are all the facts in our modeled mini-world).
• a set of permissible deductions (proof rules)
• a method of deducting
• a goal to prove (or a query to answer)

All we have so far is a set of facts.

What are some permissible deductions? What can we ``deduce'' from these simple relation? We can make simple kinds of deductions such as as ``A Person takes-cp2003 IF they are enrolled-in cp2003."

takes-cp2003(Person) :- enrolled-in(cp2003,Person).

In this clause, the variable Person starts with an upper-case letter. It represents any person. In general, constants start with lower-case letter while variables start with an upper-case letter.

Another deduction is ``A Student is-taught-by Teacher IF the Student is enrolled-in class X and Teacher teaches class X.''

is-taught-by(Student,Teacher) :- enrolled-in(X,Student), 
                                teaches(X,Teacher).

Again, note the use of variables.

Notice that all the proof rules are of the form

   if P then Q

which is sometimes written as

   P --> Q   (P implies Q) or (not P) V Q

but which we will write the goal at the left side in Prolog:

  Q :- P.

if P is true then we can conclude that Q is true

Note that P given above could be of the form of conjunctions:

  P1 and P2 and ... and Pn

which we will write in Prolog :

  P1, P2, ... , Pn

Rules that look like this are known as Horn clauses.

• A clause is called a Horn Clause if it contains at most one nonnegated literal.
  

E.g not(brother(X, Z)) V not(child(Y,Z)) V uncle(X,Y) is a Horn clause.

But hasjob(X) V unemployeed(X) is not a Horn clause.

Notice however, that our P's and Q's are of the form

  P(X1, ..., Xn)

P is the factor in the structure and Xs are arguments. We will discuss them later.

There is an important difference between facts and rules.

• The facts like

    parent(tom, liz)
    parent(pat, liz)
    parent(bob, tom)
    parent(jane, tom)

  are something that are always, unconditionally, true.
• Rules specify things that are true if some condition is satisfied.
• Rules have:
  -- a condition part ( the right-hand side of the rule) is called body and
  -- a conclusion part ( the left-hand side of the rule) is called head.

A rule example:

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

How do we match these to individual facts? We do so through a process called unification. All the s are variables or constants that must unify or match with a head (the part to the left of the :-) of some rule or fact. So let's assume that I have the goal (or query)

  teaches(cp2003, Teacher)

Well this unifies with

   teaches(cp2003, jinli)

since cp2003 = cp2003 and Teacher = jinli (a variable unifies with anything), but not with

   teaches(cp3210, geoff)

since cp2003 != cp3210 (constants only unify with equivalent constants).

Finally, we need something, a goal, to prove. Let's have our goal be

  ? - teaches(cp2003, Teacher)

which is equivalent to asking: Who teaches cp2003?. We determine that Teacher = jinli.
How about if we ask

  enrolled-in(cp2003, Student)?

Well, now we have more than one answer: Student = joe and Student = mary.

Now let's do something a little more complicated, let's determine whom mary's is-taught-by.

  ? - is-taught-by(mary, Teacher)

In order to prove our goal, we first unify our goal

  is-taught-by(mary, Teacher)

with the head of some clause. It unifies with

  is-taught-by(mary,Teacher) :- enrolled-in(X,mary), 
                             teaches(X,Teacher).

So we now have two subgoals to prove:

  enrolled-in(X,mary)

and

  teaches(X,Teacher)

The first subgoal unifies with

  enrolled-in(cp2003,mary)

which tells us that X = cp2003. The second subgoal unifies with

  teaches(cp2003, jinli)

and

  teaches(cp3210,geoff)

which tells us that if X = cp2003 then Teacher = jinli, otherwise X = cp3210 and Teacher = geoff. We know X must unify with cp2003 to prove the first subgoal, therefore, we have proved our original goal with the proviso that Teacher = jinli. So, mary is taught by jinli.

Case Study -Prolog

Prolog is a programming language for symbolic, non-numeric computation.

It is specially well suited for solving problems that involve objects and relations between objects.

Declarative - Program defines what the problem is, rather than how to solve it. (Fourth-generation language) Variables, Values and Terms

• In Prolog all data objects are called terms. A term is either a constant, a variable or a compound term.

• Constant
  • Integers
    Eg. 15 2'1111 (binary number) 8'17 (octal)
  • Floats
    E.g 4.5E7 -0.12e+8 12.0e-9
  • Atoms
    Atoms are primitive values such a strings enclosed in `single quote'. E.g 'Algol-68'.

• Variables
  Variables may be written as any sequence of alphanumeric characters (including _) starting with either a capital letter or _;
  e.g.

  X   Value   A   A1   _3   _RESULT

• Compound Terms (or Structures)
  The structured data objects of the language are the compound terms.
• A compound term comprises a functor (called the principal functor of the term) and
• a sequence of one or more terms called arguments.
• A functor is characterized by its name starting with a lower case alphabetic, which is an atom, and its arity or number of arguments.
  For example: functor is named date of arity 3, with arguments X, Y and Z, is written
  

        date(X, Y, Z)

  The components of a structure can be any values, including substructure; thus structures are hierarchical. e.g.:
  

   person(name("susan", "Watt"),
          female,
          date(1974, may,5))

  Note that an atom is considered to be a functor of arity 0.
• Lists iLists form an important class of data structures in Prolog. They are essentially the same as the lists of LISP: a list either is the atom [] representing the empty list, or is a compound term with functor . and two arguments which are respectively the head and tail of the list.
  Notations are as follows:

  [x|xs]   or .(a, xs)    % the list's head is x and tail is xs.
  [a,b,...,z] = .(a,(b,...(z,[])...))

• Prolog is an untyped language. Numbers, atoms and structures can be used interchangeably.
• We can compare different sorts of values using ``=" relation, but such comparison will always yield false.
• Untyped is not the same as dynamically typed.
  -- In an untyped language, values such as numbers and structures are different but comparable.
  -- In a dynamically typed language, any attempt to compare such values would be a run-time type error.

Clause and Relations

In Prolog there are three types of statements: facts, rules, and queries. All these statements are clauses or, more specifically, Horn clauses.

A Prolog defines a collection of relations. Each relation is defined by one or more clause, written in the follow notation:

  A0 :- A1, A2, ...An.

The symbol `:-' means `if', and the symbol ',' means `and'. Always end with . in a program.

• The heading of a clause is a single predicate (also known as the consequent).
• The body of a clause is a sequence of 0 or more predicates, separated by comma (also known as the antecedent). These are 'calls', called queries in Prolog, to other clauses.
• If there are predicates in the body, the body is separated from head with :-.
• Clauses with 0 body predicates are facts and those with 1 or more body predicates are rules.
• Facts may be considered to be rules with the predicate True as the tail.

Queries

• Queries, in form of a clause body, are entered at the ?- prompt, and end with a .

Queries on facts:

What subject is enrolled by joe?

  entolled-in(X, joe).

X= 2003  ?
X= 3120

Whose parent is tom?

 parent(tom, X ).

 X = liz   ?

Queries on rules:

Who is taught by geoff?

  is-taught-by(X, geoff).

Answer will be:

  X= joe 

  takes-cp2003(Sam).

no.

Who is grandchild of bob?

grandparent(bob, X).

X = liz

• About this document ...