Introduction

• Programs in logic languages are expressed in a form of symbolic logic
• Use a logical inferencing process to produce results
• Declarative rather that procedural:

Only specification of results are stated (not detailed procedures for producing them)

Overview of Logic Programming

• Declarative semantics

There is a simple way to determine the meaning of each statement

Simpler than the semantics of imperative languages

• Programming is nonprocedural

Programs do not state now a result is to be computed, but rather the form of the result

Example: Sorting a List

• Describe the characteristics of a sorted list, not the process of rearranging a list

sort(old_list, new_list) Ì permute (old_list, new_list) Ç sorted (new_list)

sorted (list) Ì “j such that 1£ j < n, list(j) £ list (j+1)

The Origins of Prolog

• University of Aix-Marseille (Calmerauer & Roussel)

Natural language processing

• University of Edinburgh (Kowalski)

Automated theorem proving

Inferencing Process of Prolog

• Queries are called goals
• If a goal is a compound proposition, each of the facts is a subgoal
• To prove a goal is true, must find a chain of inference rules and/or facts. For goal Q:

P2 :- P1

P3 :- P2

…

Q :- Pn

• Process of proving a subgoal called matching, satisfying, or resolution

Approaches

• Matching is the process of proving a proposition
• Proving a subgoal is called satisfying the subgoal
• Bottom-up resolution, forward chaining
• Top-down resolution, backward chaining
• Prolog implementations use backward chaining

Subgoal Strategies

• When goal has more than one subgoal, can use either

Depth-first search:  find a complete proof for the first subgoal before working on others

Breadth-first search: work on all subgoals in parallel

• Prolog uses depth-first search

Can be done with fewer computer resources

Backtracking

• With a goal with multiple subgoals, if fail to show truth of one of subgoals, reconsider previous subgoal to find an alternative solution: backtracking
• Begin search where previous search left off
• Can take lots of time and space because may find all possible proofs to every subgoal

Simple Arithmetic

• Prolog supports integer variables and integer arithmetic
• is operator: takes an arithmetic expression as right operand and variable as left operand

  A is B / 17 + C

• Not the same as an assignment statement!

The following is illegal:

Sum is Sum + Number.

Deficiencies of Prolog

• Resolution order control

In a pure logic programming environment, the order of attempted matches is nondeterministic and all matches would be attempted concurrently

• The closed-world assumption

The only knowledge is what is in the database

• The negation problem

Anything not stated in the database is assumed to be false

• Intrinsic limitations

It is easy to state a sort process in logic, but difficult to actually do—it doesn’t know how to sort

Applications of Logic Programming

• Relational database management systems
• Expert systems
• Natural language processing