8. Logic Programming¶

¹ Lecture Notes¶

Prolog¶

Developed in the 1970s by Alain Colmerauer and Phillipe Roussel.
The name is from “PROgramming LOGic”.
It is a declarative language that aligns with predicate calculus (logic proofs).
It is good for: AI, Natural language processing, Databases.
It is not good for: Numerical computation, Graphics, complex IO.
Prolog consists of:
- Facts: likes(john, mary). define statements that are always true.
- Rules: snowy(X) :- rainy(X), cold(X). define relationships between facts where :- means “implies”.
- Queries: ?- likes(john, mary). ask questions about facts and rules.
All variables are capitalized, and all constants are lowercase.
Prolog Data types:
- Terms:
  - Atoms: john, mary, likes. must start with a lowercase letter or be enclosed in single quotes.
  - Numbers: 1, 2.5, -3.14. the language does not distinguish between integers and floats, but there are extensions that do.
  - Variables: X, Y, Z. must start with an uppercase letter or an underscore.
  - Compound terms: likes(john, mary), likes(X, mary), likes(john, Y).
- Program:
  - Clauses: likes(john, mary)., likes(john, X) :- likes(X, mary).
  - A program is a collection of clauses that includes facts and rules and other predicates.
- Predicates:
  - Built-in:
    - Equality: X = Y, X \= Y. \= means “not equal”. = means “unify” or logical equality and not arithmetic equality.
    - Guaranteed success/failure: true, fail.
    - Output: write(X), nl. nl means “newline”.
    - Type Checking: var(X), nonvar(X), number(X), atom(X), integer(X), float(X), atomic(X), compound(X).
    - Comparison: X < Y, X =< Y, X > Y, X >= Y.
Clauses are written in Horn form which consists of a head (consequent) and a body (terms) with one semantic: If all the terms in the body are true, then we can deduce that the head is true.
Horn Clause:
- H <- B1, B2, ..., Bn where H is the head and B1, B2, ..., Bn are the body.
- All of B1, B2, ..., Bn must be true for H to be true.
- All of B1, B2, ..., Bn imply H.
- In Prolog: H :- B1, B2, ..., Bn.
The clause is either a fact or a rule.

Recursion in Prolog¶

Recursion is an implementation of divide and conquer by a function that iteratively calls itself with smaller and smaller inputs until it reaches a base case.
Recursive relations:

parent(john, mary).
parent(john, sue).
parent(mary, bill).
parent(mary, tom).
parent(sue, jim).
parent(sue, ann).

% recursive rule with base case
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

?- ancestor(john, ann). % true
?- ancestor(john, sue). % true


% recursive rule with base case
descendant(X, Y) :- parent(Y, X).
descendant(X, Y) :- parent(Y, Z), descendant(X, Z).

?- descendant(jim, john). % true
?- descendant(jim, sue). % true

Computed recursion:

sumOf([], 0).
sumOf([H|T], Sum) :- sumOf(T, Rest), Sum is H + Rest.

?- sumOf([1, 2, 3], Sum). % Sum = 6

¹ ³ Unification and Resolution¶

Read about unification at ³.
Unification tests a goal against a clause(s). e.g. the goal LHS=RHS.
The LHS (or RHS) can be an atom, a variable, or a compound term.
Two atoms unify if they are the same atom.
Two numbers unify if they are the same number.
Two complex (compound) terms unify if:
- They have the same functor and same arity (same number of arguments).
- All their corresponding arguments unify.
A variable unifies with a term by binding to that term; if the variable is already bound, then the unification fails.

² Prolog Dictionary¶

Prolog Dictionary is a collection of Prolog terms and their definitions organized in alphabetical order.
Use this dictionary to look up the meaning of a Prolog term.
Available hereL http://www.cse.unsw.edu.au/~billw/dictionaries/prolog/

⁴ Prolog Tutorial¶

Facts list what is true. E.g. sun_is_shining..
Queries ask questions about what is true based on the facts that are given before asking the question. E.g. ?- sun_is_shining..
Relations:
- Relations are facts with arguments, such as relation(arg1, arg2, ..., argn)..
- Can be queried with variables, such as ?- relation(X, Y, Z)..
- Example: age(john, 23).
Variables:
- Variables are capitalized.
- Variables are unbound until they are bound to a value.
- Variables can be used to query the database.
- Variables can be used to bind values.
- Thus the query ?- relation(X, Y, Z). will bind X, Y, and Z to the values that satisfy the relation.
- And ?- age(john, X). will bind X to 23 which is the value that satisfies the relation.
Rules:
- Rules are used to infer new facts from existing facts.
- Rules are written as head :- body..
- Rules have clauses.
- E.g. mortal(X) :- human(X).
  - Means that X is mortal if X is human.
  - human(X) is the body, it has one clause.
- We can also query rules, such as ?- mortal(john). which will return true if john is human, and false otherwise.
- Or ?- mortal(X). where X will be bound to all the values that satisfy the rule mortal(X)
Backtracking:
- Answers questions that their answer answers to more than one value.
- E.g. ?- mortal(MortalItem). will return true for all the values that satisfy the rule mortal(X), that is, MortalItem=me, MortalItem=socrates, etc.

% facts
sun_is_shining.

% relations: facts with arguments
likes(john, mary).
age(john, 23).
eats(john, apples).
eats(john, oranges).

% rules
mortal(X) :- human(X).
human(socrates).
human(me).

% more complex rules.
fun(X) :- red(X), car(X).
fun(X) :- blue(X), bike(X).
fun(ice_cream).
% fun is true if X is red and a car, or blue and a bike, or ice_cream.

% queries
?- sun_is_shining. % true
?- likes(john, mary). % true
?- age(john, 50). % false
?- agennn(john, 23). % false, as agennn is not defined
?- eats(john, apples). % true
?- eats(john, What). % What = apples, What = oranges.
?- mortal(socrates). % true
?- mortal(X). % X = socrates, X = me.
?- fun(X). % X = ice_cream.
?- fun(bike(red(myBike))). % true

⁵ Logic Programming¶

Logic programming is based on the observation that formulas in mathematical logic can be interpreted as specifications of computations.
The style of programming is declarative rather than imperative.
We do not issue commands telling the computer what to do; instead, we describe the relationship between the input data and the output data, and let the computer figure out how to obtain the output from the input.
To the extent that this is successful, logic programming provides a significantly higher level of abstraction, with the corresponding advantage of extremely concise programs.

References¶

UoPeople. (2023). CS4402: Comparative Programming Languages. Unit 8. Lecture Notes. ↩↩
Prolog Dictionary. http://www.cse.unsw.edu.au/~billw/dictionaries/prolog/ ↩
Prolog Dictionary. Unification. http://www.cse.unsw.edu.au/~billw/dictionaries/prolog/unification.html ↩↩
Prolog Tutorial. http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/index.html#menu ↩
Ben-Ari, M. (2006). Understanding programming languages. Weizman Institute of Science. Chapter 17: Logic Programming. ↩

8. Logic Programming¶

1 Lecture Notes¶

Prolog¶

Recursion in Prolog¶

1 3 Unification and Resolution¶

2 Prolog Dictionary¶

4 Prolog Tutorial¶

5 Logic Programming¶

References¶

¹ Lecture Notes¶

¹ ³ Unification and Resolution¶

² Prolog Dictionary¶

⁴ Prolog Tutorial¶

⁵ Logic Programming¶