Logic Programming and Prolog

Logic Programming and Prolog

• Logic programming differs from procedural and functional programming, focusing on relations between objects.
• Programmers define facts and relations as true.
• The system determines how to use these facts to solve problems and instantiates variables to make relations true.

Prolog Facts and Queries

• Facts examples include male(charlie)., female(alice)., parent(charlie,bob).
• When queries are made, Prolog either returns true, false, or appropriate values of variables (called a substitution).
• Example query ?- male(charlie). returns true. ?- female(Person). returns Person = alice.

Prolog Rules

• Rules define relationships, such as sibling(X, Y) :- parent(P, X), parent(P, Y).
• This rule infers siblings based on shared parents
• With appropriate facts established queries can be run to determine truth

Logic vs Functional Programming

• Functional Programming programs with functions and asks for a function’s value given arguments. f(x, y, z) = x * y + z - 2
• Logic Programming programs with relations and asks for arguments to make a true statement. r(x, y, z) = {(1, 2, 3), (9, 5, 13), (0, 0, 4)}

Logic Programming Characteristics

• Programs are composed of facts and rules.
• Running a program means querying the system.
• The language itself attempts to prove the query's truth.
• This may freeze variable values.
• The system uses unification, resolution, and backtracking.

Prolog Syntax: Constants and Variables

• Constants: Either atoms, any string of alphanumeric/underscore starting with lowercase or Numbers.
• Variables: Strings that begin with '_' or an uppercase letter.

Prolog Syntax: Terms

• Terms are inductively defined
• Constants and variables are terms
• Compound terms are applications of n-ary functors to n terms.
• Prolog distinguishes numbers and variables.

Prolog Syntax: Atomic Formulae

• Atomic formulae, also called predicates, consist of an n-ary relation applied to n terms
• Formulae are true or false and used as facts or queries and components of statements

Prolog Queries

• A query is a proposed fact to be proven.
• Queries without variables return true/false.
• Queries with variables return variable values (substitution).
• Example: the query ?- female(Person). may return "Person = alice".

Prolog Syntax: Complex Formulae

• Complex formulae combine simpler formulae.
• Conjunction: "in Prolog, looks like ' , ' "
• Can be used as queries, but are not able to be used as facts

Prolog Syntax: Implications

• Implications are written backwards (conclusion first) in Prolog as ':-', named a rule.
• Rules assert implications but not for queries.
• Example: sibling(X, Y) :- parent(P, X), parent(P, Y).

Horn Clauses (Rules)

• Horn Clause: c ← h1 ∧ h2 ∧ h3 ∧... ∧ hn
• Antecedents: conjunction of zero or more atomic formulae.
• Consequent: atomic formula.
• Meaning: the consequent is true if the antecedents are all true.

Horn Clauses: In Prolog

• Horn Clause = Clause
• Consequent = Goal = Head
• Antecedents = Subgoals = Tail
• Horn Clause with No Tail = Fact
• Horn Clause with Tail = Rule
• In Prolog c :- h1, ..., hn.
• The syntax elements are ':-' , ',' , '.'

Prolog: Examples of Horn Clauses

• Fact Example: male(charlie). stating charlie is male without other conditions.
• Rule Example: father(charlie,bob):- male(charlie), parent(charlie, bob). states that charlie is the father of bob if he is male and a parent.

Meaning of Prolog Rules

• Prolog rule form: c :- a1, a2, a3, ..., an.
• Logic Equivalent: a1 ∧ a2 ∧ a3 ∧...∧ an → c
• Restrictions: Zero or more conjoined antecedents and only one consequent.

Non-Horn Clauses

• Many non-Horn formulae can be converted into logically equivalent Horn-formulae.
• ¬¬a ⇔ a (double negation)
• ¬(a ∨ b) ⇔ ¬a ∧¬b (DeMorgan)
• a∨ (b ∧ c) ⇔ (a ∨ b) ∧ (a ∨ c) (distributivity)
• a → b ⇔ ¬a∨b (implication)

Prolog Variables

• Variables in Horn clauses are interpreted universally
• A query ?-q(X1, ..., Xn) is interpreted as ∃X1,..., Xn . q(X1,..., Xn)

Horn Clauses with Variables

• isaMother(X) :- female(X), parent(X, Y).
• In first-order logic: ∀X . isaMother(X) ← ∃Y · parent(X, Y) ∧ female(X).

Execution of Prolog Programs

• Core processes include:
  • Unification: variable bindings.
  • Backward Chaining/ Top-Down Reasoning/ Goal-Directed Reasoning: Reduces a goal to one or more subgoals.
  • Backtracking: Searches all options using unification and backchaining.

Unification

• Atomic formulae unify if identical after variable replacement.
• parent(bob,Y) unifies with parent(bob,sue) by replacing Y with sue.
• Parent(bob, Y) unifies with parent(X, sue) by replacing Y by sue and X by bob
• A substitution maps variables to Prolog terms.
• Instantiation is application of substitution to a formula or term.

Unification: Common Instance

• Common instance of A and B exists substitutions S1 and S2 where C = S1(A) = S2(B).
• A and B are unifiable if they have a common instance.
• A substitution that makes a common instance is a unifier.

Unification: Examples

• p(a,a) unifies with p(a,a)
• p(X,X) unifies with p(b,b) and with p(c,c).
• p(X,b) unifies with p(Y,Y) with unifier X/b, Y/b to become p(b,b).

Unification: More Examples

• P(f(X),X) unifies with p(Y,b) with unifier {X\b, Y\f(b)} to become p(f(b),b).
• p(b,f(X,Y),c) unifies with p(U,f(U,V),V) with unifier {X\b, Y\c, U\b, V\c} to become p(b,f(b,c),c).

Unification: Lack of Unification Example

• p(b,f(X,X),c) does not unify with p(U,f(U,V),V)
• must replace U by b.
• must replace V by c.
• However, no substitution for X will convert p(b,f(X,X),c) into p(b,f(b,c),c).

Unification: Singleton Variables

• A singleton variable is a variable that appears only once and can be replaced with _.
• The anonymous variable '_' matches anything and refers to a different unique variable each instance.

Most General Unifier (MGU)

• p(X, f(Y)) and p(g(U), V) have infinite unifiers.
• General unifier: {X\g(U), V\f(Y)}Unites to p(g(U),f(Y)).
• Uses variables to fill fewest details.

Execution of Prolog Programs

• Core processes include:
  • Unification: variable bindings.
  • Backward Chaining/ Top-Down Reasoning/ Goal-Directed Reasoning: Reduces a goal to one or more subgoals.
  • Backtracking: Searches all options using unification and backchaining.

Prolog Search Trees

• Encapsulate unification, backward chaining, and backtracking.
• Internal nodes are ordered list of subgoals/
• Leaves are success nodes or failures
• Edges have variable bindings from unification.
• They describe all computation paths, with possible success and infinite branches.

Logic Programming vs. Prolog: Determinism

• Logic Programming is nondeterministic:
  • Arbitrarily choose which rule or subgoal to expand first.
  • Results are independent of ordering.
• Prolog is deterministic:
  • Expands the first rule and explores the first subgoal first.
  • Results may depend on the rule and subgoal ordering.

Prolog List Syntax

• "[]" is the empty list
• "[Head | Tail]" is a list with first element Head and a Tail containing a list of the remaining elements
• Abbreviated as "[e1, e2,... en ]"
• Two lists unify if and only if have the same structure and the corresponding elements unify

Lists in Prolog

• % member(?X,?List) iff X is an element of List
• member(X,[X|_]).
• member(X,[_|Rest]):-member(X,Rest).

Lists in Prolog: Append

• % append(?X,?Y,?Z) iff Z is the result of appending list Y to list X
• append([],Y,Y).
• append([H|T],Y,[H|Z]):-append(T,Y,Z).

Lists in Prolog: Mlength

• % mylength(?L,?N) iff N is the length of list L
• mylength([],0).
• mylength([_|T],N):-mylength(T,N-1).

Arithmetic in Prolog

• Arithmetic Expression Evaluation requires:
  • expr1 is expr2 where expr2 is fully grounded.
  • expr1 < expr2 or expr1 > expr2 where both are instantiated

Negation as Failure

• Prolog cannot assert something as false, but says a given facts and rules do not allow something to be proven true
• Assuming something unprovable is false, is called negation as failure under a closed world assumption
• \+(G) (or not G) succeeds whenever the goal G fails

Negation as Failure: Proper Use

• not(G) works properly only if:
  • G is fully instantiated at the time prolog processes the goal not(G).
  • variables in G are unique to G
• "Guard" is a method called to ensure these criteria are met

Execution of Prolog Programs

• Execution relies on:
  • Unification for variable bindings.
  • Backward Chaining, Top-Down Reasoning, and Goal-Directed Reasoning to reduce goals.
  • Backtracking to search all solutions.

Cut

• The goal "!" (cut") succeeds immediately and disallows backtracking over the cut, or applying a different clause of the same predicate
• Cuts the derivation tree of all other choices where the cut was introduced
• Improves efficiency by reducing the search space

Reasoning: Bottom up and Top Down

• Bottom-up (or forward) reasoning: uses given facts and rules to infer everything that is true.
• Top-down (or backward) reasoning: starts from query and applies rules in reverse.
• Prolog uses backtracking reduction to perform top-down search

Nondeterministic Programming

• Powerful way to define and implement algorithms
• Nondeterministic machines chooses next operation correctly with several alternatives
• Simulated with Prolog's sequential search and backtracking

Towers of Hanoi

• Task: moving N disks from the left peg to the right peg using the centre peg, without placing a larger disk upon a smaller disk