Prolog - part 1

Language basics: clauses, database, and queries; resolution and unification Material adapted from Mark Hills’ Organization of Programming Languages

Lesson plan

• Q&A for homework 1 and 2 + lecture outline

• Logic: background, history, programming concepts

• Why care about Prolog?

• Basic concepts of logic programming

• Computing in Prolog: database

• ICE: test your SWI-Prolog installation (questions about the database)

• Computing in Prolog continued: rules and statements

• Prolog terms

• Computing in Prolog continued: resolution, unification, and queries

• Summary

Logic languages

Background

• Logic is used heavily in the design of digital circuits

• Most programming languages provide a logical (Boolean) type and operators

• Logic is also heavily used in the formal study of language semantics

History

• Starting point: First Order Predicate Logic

• Realization: Computers can reason with this kind of logic

• Impetus was the study of mechanical theorem proving

• Developed in 1970 by Alain Colmerauer and Robert Kowalski and others

Logic programming

• Based on predicate calculus

• Predicates – building blocks \(P(a_1, a_2, \ldots, a_K)\)

  • limit(f, infinity, 0)

  • enrolled(you, CS 3675)

  • These are interesting because we attach meaning to them, but within the logical system they are simply structural building blocks, with no meaning beyond that provided by explicitly-stated interrelationships

Logic programming concepts

• Operators

  • Conjunction (\(\wedge\)), disjunction (\(\vee\)), negation (\(\neg\)), implication (\(\to\))

• Universal (\(\forall\)) and existential (\(\exists\)) quantifiers

• Statements

  • Sometimes true, sometimes false, often unknown

  • Axioms – assumed true

  • Theorems – provably true

  • Hypotheses (goals) – things we’d like to prove true

Logic programming concepts

• Most statements can be written many ways

• That’s great for people but a nuisance for computers

  • It turns out that if you make certain restrictions on the format of statements you can prove theorems mechanically

  • That’s what logic programming systems do

  • Unfortunately, the restrictions that we will put on our statements will not allow us to handle most of the theorems you learned in math, but we will have a surprising amount of power left anyway

• Therefore, we insist that all statements be in the form of HORN CLAUSES consisting of a HEAD and a BODY (discussed shortly)

Why care about Prolog?

• Prolog is used in AI research

• Logic programming shows up in unexpected places: Datalog, a subset of Prolog, is used in software engineering systems for code querying, predicate logic is used in OCL

Logic programming

Declarative vs imperative programming

• Imperative programming: programs are sequences of commands telling the computer what to do

• Declarative programming: programs encode information describing the problem and the problem solution we want

  • Logic

    • Based on first-order predicate calculus

    • Logic languages do not capture the full power of predicate calculus

Logic programming is declarative: we will describe the problem, the language will try to find the solution.

Basic concepts of logic programming

First-order predicate logic

• Start with a universe of discourse, i.e., the things (we will call these objects, but these aren’t OO objects) we are talking about

• Add facts about the objects, and relationships between these objects: we will call these predicates, and each predicate will indicate if the fact or relationship is true or false for certain objects

• Use logical connectives to build more complex relationships: and, or, not, implies

• The logic is first order, which means predicates talk about objects, but not about other predicates

Objects in first order logic

Our concept of object will be based on what we are writing the program about, examples include:

• People: socrates, aristotle, john, mary

• Code constructs: variables, loops, functions, classes

• Software engineering artifacts: entries in source code repositories, items on UML diagrams

Logic programming concepts

• Programmer states a collection of axioms from which theorems can be proven

  • Prolog data consists of facts about objects and logical rules (predicates in first order logic)

    • People: man(socrates), woman(mary), studentOf(aristotle, plato), major(mary,computer science)

    • Code constructs: class(animal), subclass(dog, animal), methodOf(woof, dog), notnull(x), invariant(loop1,x)

    • Software engineering artifacts: committedBy(file1,mark), dependency(uses,c1,c2)

• User states a theorem, or goal – the language implementation attempts to find a collection of axioms and inference steps (including choices of values for variables) that together imply the goal

Logical connectives in first order logic

This just gives us ways to say more complex things:

• man(socrates) and studentOf(aristotle, plato)

• class(animal) and not methodOf(woof, animal)

• committedBy(f1,john) or committedBy(f1,mary)

Axioms

• Written in a standard form known as a Horn clause:

  • A headThis is different than the head of a list, or consequent term \(H\)

  • A body consisting of terms \(B_i\)

    \[H \leftarrow B_1,B_2,\ldots,B_n\]

  • When the \(B_i\) are all true, then \(H\) is true

  • We say “\(H\), if \(B_1, B2, \ldots , \textrm{ and } B_n\)”

• Horn clauses can be used to capture most, but not all, logical statements

Prolog

Computing in Prolog

• What is the nature of data?
  • Prolog data consists of facts about objects and logical rules
• What is the nature of a program?
  • A program in Prolog is a set of facts and rules, followed by a query

Computing in Prolog

• Prolog can be thought of declaratively or imperatively:

  • We’ll emphasize the declarative semantics for now, because that’s what makes logic programming interesting

  • We’ll get into the imperative semantics later

• Prolog allows you to state a bunch of axioms

  • Then you pose a query (goal) and the system tries to find a series of inference steps (and assignments of values to variables) that allow it to prove your query starting from the axioms

The database

Let’s see how we can represent the database for the graph shown in Figure 1.

⊕
Figure 1. An example of a connected graph: node c is connected to nodes a and h, node a is connected to node f, node f is not connected to other nodes, etc.

connected(c,a). connected(a,f). connected(d,b). connected(b,e). connected(d,e). connected(d,g). connected(g,e). connected(c,h). connected(h,f).

human(socrates). fatherof(socrates,jane). fatherof(zeus,apollo).

Rules

mortal(X) :- human(X). human(Y) :- fatherof(X,Y), human(X).

pathfrom(X,Y) :- connected(X,Y). pathfrom(X,Y) :- connected(X,Z), pathfrom(Z,Y).

• Capital letters are variables.

  • Appearing left of :- means “for all”

  • Appearing right of :- means “there exists”

More than just true or false….

Prolog can also give you a list of elements that make a predicate true (via unification)

?- fatherof(Who,apollo).

Who = zeus ;

?- pathfrom(c,X).

X = a ;

X = h ;

X = f ;

X = f ;

false.

The semicolon is entered by the user – it means to keep searching

Tracing pathfrom

?- pathfrom(c,X).

$$\rightarrow$$ pathfrom(c,Y) :- connected(c,Y).

X = a ;

When we hit semicolon, we tell it to pretend that this is false, and to keep searching. We have to throw away the connected(c,a) result, so we backtrack through our database to try again.

$$\rightarrow$$ pathfrom(c,Y) :- connected(c,Y).

X = h ;

We tell it to try again with this one, too. At this point, we no longer have any rules that say that c is connected to something.

Tracing pathfrom, II

pathfrom(c,Y) :- connected(c,Z), pathfrom(Z,Y).`

We will first find something in the database that says that c is connected to some Z, and then check if there is a path between Z and Y.

We find a and h as last time. When we check a, we check for pathfrom(a,Y), and find that connected(a,f) is in the database. The same thing happens for h, which is why f is reported as an answer twice.

Statements

• The meaning of the statement is that

mother(mary, fred).

% you can either think of this as

% a predicate asserting that mary is the mother of fred -

% or a data structure (tree) in which

% the functor (atom) mother is the root,

% mary is the left child, and fred is the right child

rainy(rochester).

Prolog terms

• A Prolog interpreter runs in the context of a DATABASE of CLAUSEs (Horn clauses) that are assumed to be true
  man(socrates). woman(mary). studentOf(aristotle, plato).

  • Each CLAUSE is composed of TERMs

    • TERMs may be CONSTANTs, VARIABLEs, or STRUCTUREs

      • A CONSTANT is either an ATOM or a NUMBER

        • Lexically, an ATOM looks like:

          • An IDENTIFIER beginning with a lowercase letter (e.g., foo, my_Const)

          • A sequence of “punctuation” CHARACTERs (e.g., +), or

          • A quoted character STRING (e.g., 'Hello, world')

          • NUMBERs resemble integers and floating-point constants of other PLs

      • A VARIABLE looks like an identifier (e.g., Foo, My_var, X)

        • VARIABLEs can be instantiated (i.e., can take on) arbitrary values at run time as a result of UNIFICATION

        • The scope of every variable is limited to the CLAUSE in which it appears
          snowy(X) :- rainy(X), cold(X).
beautiful(X) :- sunny(X), warm(X).

        • There are no declarations

        • Type checking is dynamic: it occurs only when a program attempts to use a value as an operand at run time

      • A STRUCTURE is either a LOGICAL PREDICATE or a DATA STRUCTURE

        • STRUCTUREs consist of an ATOM called the FUNCTOR and a list of ARGUMENTs
          rainy(rochester)
teaches(Scott, cs254)
bin_tree(foo, bin_tree(bar, larch))

        • Prolog requires the opening parenthesis to come IMMEDIATELY AFTER the functor, with no intervening space!

        • ARGUMENTs can be arbitrary TERMs: CONSTANTs, VARIABLEs, or (nested) STRUCTUREs.

        • Conceptually, the programmer may prefer to think of certain STRUCTUREs (e.g., rainy) as LOGICAL PREDICATES

        • We use the term “PREDICATE” to refer to the combination of a FUNCTOR and an “arity” (number of ARGUMENTs).

    • The CLAUSEs in a Prolog DATABASE can be classified as FACTs or RULEs, each of which ends with a period

      • A FACT is a Horn clause without a right-hand side. It looks like a single TERM (the implication symbol is implicit):
        rainy(rochester) .

      • A RULE has a right-hand side:
        snowy(X) :- rainy(X), cold(X).
        The token :- is the implication symbol; the comma indicates “and” Variables that appear in the head of a Horn clause are universally quantified: \(\forall\) X, X is snowy if X is rainy and X is cold

    • It is also possible to write a CLAUSE with an empty left-hand side (a QUERY, or a GOAL) QUERYs do not appear in Prolog programs In most implementations of Prolog, QUERYs are entered with a special ?- version of the implication symbol
      rainy(seattle).
rainy(rochester).
?- rainy(C).

Resolution

• Resolution: to derive new statements, a logic programming system combines existing statements, canceling like terms

  \[\begin{aligned} C&\leftarrow A,B\\ D&\leftarrow C\\ \rule{3mm}{0.15mm}&\rule{15mm}{0.15mm}\\ D&\leftarrow A,B \end{aligned}\]
  • In general, terms like \(A\), \(B\), \(C\), and \(D\) may consist not only of constants (“Rochester is rainy”) but also of predicates applied to atoms or to variables: rainy(Rochester), rainy(Seattle), rainy(X)

Resolution example

takes(jane_doe, his201).
takes(jane_doe, cs254).
takes(ajit_chandra, art302). takes(ajit_chandra, cs254).
classmates(X, Y) :- takes(X, Z), takes(Y, Z).

• Note that the last rule has a variable (Z) on the right-hand side that does not appear in the head

• Such variables are existentially quantified: for all X and Y, X and Y are classmates if there exists a class Z that they both take

• The pattern-matching process used to associate X with jane_doe and Z with cs254 is known as unification

• Variables that are given values as a result of unification are said to be instantiated

Unification

• During resolution, free variables may acquire values through unification with expressions in matching terms

  flowery(X) $$\leftarrow$$ rainy(X)
rainy(Rochester)
flowery(Rochester)

The unification rules for Prolog state that

• A constant unifies only with itself

• Two structures unify iff they have the same functor and the same arity, and the corresponding arguments unify recursively

• A variable unifies with anything

  • If the other thing has a value, then the variable is instantiated

  • If the other thing is an uninstantiated variable, then the two variables are associated in such a way that if either is given a value later, that value will be shared by both

Queries

Axioms

human(socrates).
human(Y) :- fatherof(X,Y), human(X).
mortal(X) :- human(X).

Goals

?- human(socrates). /* listed, therefore true */
?- mortal(socrates). /* not listed */

Socrates is not listed as being mortal, but mortal(socrates) unifies with mortal(X) if we replace X with socrates. This gives us a subgoal. Replace X with socrates and try it….

Queries

Replace X with socrates in this rule:

mortal(X) :- human(X).

to get

mortal(socrates) :- human(socrates).

Since human(socrates) is in the database, we know that mortal(socrates) is also true.

Summary

• Logic concepts

• Basic concepts of logic programming

• Computing in Prolog: database, rules, statements, resolution, unification, and queries

• Next time

  • Prolog programming language, part 2 of 2

• Reminders

  • Extra credit: submit questions to be considered for Quiz 2 (all material from lectures 1–4, associated textbook content, and recommended videos) – by midnight (Thursday, August 20, at 11:59 PM)

  • Quiz 2, open tomorrow, Friday, August 21, between 12:00 PM and 11:59 PM

  • Homework 1 – due tomorrow, Friday, August 21, at 11:59 PM

Back to course home