Session 13 : Logic Programming Languages
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