Programming Languages

G22.2110 Summer 1998

Class #9

Logic Programming Languages

Homework #6: Sethi Exercises 10.5, 10.13, 11.4, 11.7, 11.10

Read Sethi’s Chapter 11, handouts and references

Contents

C11.0. Current Assignments, PL Project

C11.1. Introduction to Logic Programming Languages

C11.2. Introduction to Predicate Calculus

C11.2.1. Propositions

C11.2.2. Clausal Form

C11.3. Predicate Calculus and Proving Theorems

C11.4. An Overview of Logic Programming

C11.5. The Origins of Prolog

C11.6. The Basic Elements of Prolog

C11.6.1. Terms

C11.6.2. Fact Statements

C11.6.3. Rule Statements

C11.6.4. Goal Statements

C11.6.5. The Inferencing Process of Prolog

C11.6.6. Simple Arithmetic

C11.6.7. List Structures

C11.7. Deficiencies of Prolog

C11.7.1. Resolution Order Control

C11.7.2. The Closest World Assumption

C11.7.3. The Negation Problem

C11.8. Applications of Logic Programming

C11.8.1. Relational Database Management Systems

C11.8.2. Expert Systems

C11.8.3. Natural Language Processing

C11.8.4. Education

C11.9. Conclusions

C11.0. Current Assignments, PL Project

PL project #2 due Monday 7/20

HW #6 due next Thursday 7/23

PL project #3 will be posted on Monday 7/20

C11.1. Introduction to Logic Programming Languages

Express programs in a form of symbolic logic.

Use logical inferencing to produce results.

Logic programs are declarative rather than non procedural (i.e., only the specification of the desired results are stated, and not the detailed procedures for producing them).

Very different syntax in comparison to the languages studied so far.

Semantics different to that of imperative languages.

C11.2. Introduction to Predicate Calculus

Basis of logic programming is formal logic.

Proposition: logical statement that may or may not be true, and includes objects and their relationships.

Symbolic logic: used to express propositions, express relationships between propositions, and describe how new propositions can be inferred from existing ones that are true.

Predicate calculus: form of symbolic logic used for logic programming.

C11.2.1. Propositions

Objects in logic programming propositions are represented by simple terms which are either constants or variables.

Constant: symbol that represents an object.

Variable: symbol that can represent different objects at different times.

Atomic propositions: simplest propositions which consist of single compound terms.

Compound term: one element of a mathematical relation which includes a functor (function symbol that names the relation), and an ordered list of parameters (1-uple, 2-tuple, etc.).

e.g.,

man(jake)

like(bob, redheads)

man(fred)

No intrinsic semantics

Propositions can be stated to be facts of queries.

Compound propositions have two or more atomic propositions which are connected by logical connectors, or operators (i.e, negation, conjunction, disjunction, equivalence, implication in order of precedence).

Variables can appear in propositions but only when introduced by special symbols called quantifiers (universal, existential).

C11.2.2. Clausal Form

General syntax: if all of the As are true then at least one B is true.

(existential quantifiers are not required, universal ones are implicit in the use of variables in the atomic propositions, and no operators other than conjunction and disjunction are required in the order shown above)

All propositions can be restricted to clausal form.

Right side is the antecedent, and left side is the consequent.

C11.3. Predicate Calculus and Proving Theorems

Resolution: inference rule that allows inferred propositions to be computed from given propositions.

Unification: process of determining useful values for variables (used by resolution in order to allow the matching process to succeed).

Instantiation: temporary assigning of values to variables to allow unification.

Horn Clauses: restricted kind of clausal form which must be used to specify propositions that are used for resolution. These propositions either have a single atomic proposition on the left side or an empty left side.

Horn Clauses with empty left sides are often used to state facts (headless Horn clauses).

C11.4. An Overview of Logic Programming

Declarative semantics: simple way to determine the meaning of each statement.

e.g.,

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)

C11.5. The Origins of Prolog

Developped by Alain Colmerauer, Philippe Roussel, and Robert Kowalski.

Prolog’s syntax is a modified version of predicate calculus.

Prolog’s inferencing method is a restricted form of resolution.

C11.6. The Basic Elements of Prolog

C11.6.1. Terms

Term: constant, variable, or structure.

Constant: atom (symbolic value, which is either a string of letters, digits, and underscores that begin with a lowercase letter, or a string of any printable ASCII characters delimited by apostrophes) or integer.

Variable: starts with uppercase letter.

The binding of a value (type) to a variable is called instantiation, it only occurs in the resolution process.

Structures: functor(parameter list), can be relations or predicates.

C11.6.2. Fact Statements

e.g.,

female(shelley).

Father(bill, jake).

C11.6.3. Rule Statements

Consequence_1:-antecedent_expression.

e.g., ancestor(mary, shelley) :- mother(mary,shelley).

Parent(X, Y) :- mother(X, Y).

Parent(X, Y) :- father(X, Y).

Grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Sibling(X, Y) :- mother(M, X) , mother(M, Y), father(F, X) , father(F, Y).

C11.6.4. Goal Statements

Syntactic form equivalent to that of headless Horn clause.

e.g., man(fred), father(X, mike)

Two modes with different interactive prompts in Prolog implementations to identify goal statements and nongoal statements.

C11.6.5. The Inferencing Process of Prolog

Match a given goal to a fact in the database.

Either bottom-up resolution or forward chaining (begin with the facts and rules of the database), or top-down resolution or backward chaining (begin with the goal and find a sequence of matching propositions that lead to some set of original facts in the database).

e.g., man (bob)

db: father(bob)

man(X) :- father(X)

Either depth-first, or breadth-first search to resolve subgoals.

Backtracking: reconsideration of a previously proven subgoal.

Prolog’s implementation uses backward chaining and depthth-first search.

C11.6.6. Simple Arithmetic

Prolog supports integer variables and integer arithmetic (is operator).

e.g.,

likes(jake, chocolate).

Likes(jake, apricots).

Likes(darcie, licorice).

Likes(darcie, apricots).

Trace.

Likes(jake, X), likes(darcie, X).

- 1 Call: likes(jake, _0) ?

- 1 Exit: likes(jake, chocolate)
- 1 Call: likes(darcie, chocolate) ?

- 1 Fail: likes(darcie, chocolate)

- 1 Redo: likes(jake, _0) ?

- 1 Exit: likes(jakes, apricots)

(3) 1 Call: likes(darcie, apricots) ?

(3) 1 Exit: likes(darcie, apricots)

X= apricots

C11.6.7. List Structures

Atomic propositions, also called structures, are a form of records.

The other basic data structure is the list.

e.g.,

[apple, prune, grape, kumquat]

[X | Y]: list with head X and tail Y.

C11.7. Deficiencies of Prolog

C11.7.1. Resolution Order Control

User can control the ordering of pattern matching during resolution.

(Prolog evaluates left to right).

Prolog allows explicit control of backtracking.

C11.7.2. The Closest World Assumption

Limitation due to database incompleteness.

C11.7.3. The Negation Problem

The Prolog not operator is not equivalent to a logical NOT operator.

(NOT means that its operand is provably true).

C11.7.4. Intrinsic Limitations

Generation of efficient algorithms.

C11.8. Applications of Logic Programming

C11.8.1. Relational Database Management Systems

Relational calculus is a form of symbolic logic.

Query languages based on relational calculus are nonprocedural.

Simple tables of information can be described by Prolog structures, and relationships between tables can be described by Prolog rules. The retrieval process is inherent in the resolution operation.

Prolog can replace the DDL, DML, and Query Language which are usually embedded in an imperative language.

Deductive capability is an advantage but logical inferences take longer than ordinary table look-up methods.

C11.8.2. Expert Systems

Expert systems consists of a database of facts, an inferencing process, some heuristics about the domain, and some friendly human interface.

Logic programming can help deal with the problem of incompleteness of the database.

Idea is to use Prolog’s ability to add facts and rules to provide the learning capability, and to use its trace facility to inform the user of the "reasoning" behind a given result.

Prolog is missing the ability to query the user for additional information when it is needed.

e.g., Expert System Construction System APES.

C11.8.3. Natural Language Processing

e.g., Intelligent databases.

Intelligent knowledge-based systems.

Forms of logic programming have been found to be equivalent to context-free grammars.

Proof procedures have been found to be equivalent to certain parsing strategies

(e.g., use of backward chaining resolution to parse sentences whose structures are described by context-free grammars).

Some kinds of semantics of natural languages can be made clear by modeling the languages with logic programming.

(e.g., sets of sentences can be expressed in clausal form).

C11.8.4. Education

e.g., micro-Prolog

Possible to introduce computing using Prolog.

Side effect of teaching logic, which can result in clearer thinking and expression.

Help learning a variety of subjects (e.g., solving equations in mathematics, dealing with grammars in natural languages, and understanding the rules and order of the physical world).

Experiments with young children proves that it is easier to teach logic to a beginner than to a programmer who already knows imperative languages.

C11.9. Conclusions

Prolog better than Imperative Languages ?

Prolog programs more organized and written, and therefore lead to fewer errors and maintenance.

Prolog processing is naturally parallel (interpreters can take advantage of multiple processors).

Conciseness of programs decreases development time (good for prototyping).