The Art of Prolog

Notes

Preface

NOTER_PAGE: (32 . 0.11393596986817325)

A future for Prolog among the programming languages of the world seems assured.

NOTER_PAGE: (32 . 0.5480225988700564)

Introduction

NOTER_PAGE: (42 . 0.12052730696798493)

Like logic, computers require a precise and explicit statement of one's goals and assumptions.

NOTER_PAGE: (42 . 0.527306967984934)

language for expressing problems to the computer and instructing it how to solve them was designed from the perspective of the engineering of the computer alone.

NOTER_PAGE: (42 . 0.647834274952919)

the von Neumann machine seems an arbitrary, even bizarre, device. Thinking in terms of its con- strained set of operations is a nontrivial problem,

NOTER_PAGE: (43 . 0.4548022598870056)

separation of work: there were those who thought how to solve the problem, and designed the methods for its solution, and there were the coders, who performed the mundane and tedious task of translating the instructions of the designers

NOTER_PAGE: (43 . 0.5527306967984934)

"coding," the last, mundane, intellectually trivial, time-consuming, and tedious phase of solving a problem using a computer system, is perhaps at the very root of what has been known as the "software crisis."

NOTER_PAGE: (44 . 0.10838831291234684)

The ideas behind these equations can be traced back as far as intuitionistic mathematics and proof theory of the early twentieth century. They are related to Hilbert's program, to base the entire body of mathemati- cal knowledge on logical foundations and to provide mechanical proofs for its theories, starting from the axioms of logic and set theory alone. It is interesting to note that the failure of this program, from which en- sued the incompleteness and undecidability results of Gödel and Turing, marks the beginning of the modern age of computers.

NOTER_PAGE: (45 . 0.4632768361581921)

U.S. artificial intelligence scientists, when hearing about Prolog, thought that the Europeans were over-excited over what they, the Americans, had already suggested, tried, and discovered not to work.

NOTER_PAGE: (46 . 0.5560791705937794)

By 1980 the number of researchers actively engaged in logic programming were only a few dozen in the United States and about one hundred around the world.

NOTER_PAGE: (47 . 0.23468426013195098)

Japanese Fifth Generation Project, which took place in October 1981. Although the research program the Japanese presented was rather baggy, faithful to their tradition of achieving consensus at almost any cost, the important role of logic programming in the next generation of computer systems was made clear.

NOTER_PAGE: (47 . 0.33459000942507067)

I Logic Programs

NOTER_PAGE: (50 . 0.14689265536723164)

1 Basic Constructs

NOTER_PAGE: (52 . 0.15174363807728558)

The simplest kind of statement is called a fact. Facts are a means of stating that a relation holds between objects.

NOTER_PAGE: (52 . 0.49764373232799247)

Another name for a relation is a predicate.

NOTER_PAGE: (52 . 0.6060320452403393)

Names of individuals are known as atoms.

NOTER_PAGE: (52 . 0.6258246936852027)

predicates and atoms in facts begin with a lowercase letter rather than an uppercase letter.

NOTER_PAGE: (53 . 0.34745762711864403)

A finite set of facts constitutes a program.

NOTER_PAGE: (53 . 0.3879472693032015)

A query asks whether a certain relation holds between objects.

NOTER_PAGE: (53 . 0.6148775894538606)

Syntactically, queries and facts look the same, but they can be distin- guished by the context.

NOTER_PAGE: (53 . 0.711864406779661)

The simplest rule of deduction is identity: from P deduce P

NOTER_PAGE: (54 . 0.13100848256361922)

The answer no is given if a fact identical to the query is not found, because the fact is not a logical consequence of the program. This answer does not reflect on the truth of the query; it merely says that we failed to prove the query from the program.

NOTER_PAGE: (54 . 0.27332704995287466)

variables are a means of summarizing many queries

NOTER_PAGE: (54 . 0.5956644674835061)

Variables […] stand for an unspecified but single entity rather than for a store location in memory.

NOTER_PAGE: (54 . 0.6946277097078228)

Constants and variables are terms. Also compound terms, or structures, are terms.

NOTER_PAGE: (54 . 0.7540056550424128)

Queries, goals, and more generally terms where variables do not occur are called ground.

NOTER_PAGE: (55 . 0.19321394910461828)

An example of a substitution consisting of a single pair is {X=isaac}.

NOTER_PAGE: (55 . 0.352497643732328)

A is an instance of B if there is a substitution O such that A = BO.

NOTER_PAGE: (55 . 0.5051837888784165)

variables in queries are existentially quantified

NOTER_PAGE: (55 . 0.6757775683317625)

The next deduction rule we introduce is generalization. An existential query P is a logical consequence of an instance of it, PO, for any substi- tution 6

NOTER_PAGE: (55 . 0.7917059377945335)

Used in this way, variables are a means of summarizing many facts.

NOTER_PAGE: (56 . 0.6729500471253534)

This is the third deduction rule, called instantiation. From a universally quantified statement P, deduce an instance of it, PO, for any substitution 0.

NOTER_PAGE: (57 . 0.11205273069679848)

C is a common instance of A and B if it is an instance of A and an instance of B, in other words, if there are substitutions 0 and 02 such that C=A01 is syntactically identical to BO2.

NOTER_PAGE: (57 . 0.4048964218455744)

In general, to answer a query using a fact, search for a common in- stance of the query and fact. The answer is the common instance, if one exists. Otherwise the answer is no.

NOTER_PAGE: (57 . 0.5621468926553672)

Answering an existential query with a universal fact using a common instance involves two logical deductions. The instance is deduced from the fact by the rule of instantiation, and the query is deduced from the instance by the rule of generalization.

NOTER_PAGE: (57 . 0.6214689265536723)

We use '," throughout to denote logical and.

NOTER_PAGE: (58 . 0.12994350282485875)

Conjunctive queries are interesting when there are one or more shared variables

NOTER_PAGE: (58 . 0.3173258003766478)

Operationally, to solve the conjunctive query A1,A2 ,…,A? using a pro- gram P, find a substitution O such that A10 and.. . and AO are ground instances of facts in P.

NOTER_PAGE: (59 . 0.15160075329566855)

third and most important state- ment in logic programming, a rule

NOTER_PAGE: (59 . 0.4604519774011299)

means of ex- pressing new or complex queries in terms of simple queries

NOTER_PAGE: (60 . 0.17325800376647835)

rules are a means of defining new or complex relationships using other, simpler relationships.

NOTER_PAGE: (60 . 0.43220338983050843)

Modus ponens states that from B and A <- B we can deduce A

NOTER_PAGE: (60 . 0.756120527306968)

Universal modus ponens includes identity and instantiation as special cases.

NOTER_PAGE: (61 . 0.354382657869934)

complete definition of the concept of a logic program

NOTER_PAGE: (61 . 0.39585296889726673)

A logic program is a finite set of rules.

NOTER_PAGE: (61 . 0.4646559849198869)

lt is difficult in general to guess the correct ground instance and to choose the right rule.

NOTER_PAGE: (62 . 0.13465160075329566)

Part of the art of logic programming is deciding on what intermediate predicates to define to achieve a complete, elegant axiomatization of a relationship.

NOTER_PAGE: (62 . 0.5141242937853107)

A reduction of a goal G by a program P is the replacement of G by the body of an instance of a clause in P, whose head is identical to the chosen goal.

NOTER_PAGE: (64 . 0.6569274269557022)

The selection of the goal to be reduced is arbitrary.

NOTER_PAGE: (65 . 0.28907721280602633)

In contrast, the choice of the clause and a suitable instance is criti- cal.

NOTER_PAGE: (65 . 0.3549905838041431)

there are several choices of a clause, and infinitely many ground instances. The choice is made nondeterministically

NOTER_PAGE: (65 . 0.371939736346516)

Of course, no real machine can directly implement this definition. How- ever, it can be approximated in a useful way

NOTER_PAGE: (65 . 0.5696798493408662)

A trace of a query implicitly contains a proof that the query follows from the program. A more convenient representation of the proof is with a proof tree.

NOTER_PAGE: (66 . 0.2853107344632768)

The meaning of a logic program P, M(P), is the set of ground goals deducible from P.

NOTER_PAGE: (66 . 0.7617702448210922)

the meaning of a program contains explicitly whatever the program states implicitly.

NOTER_PAGE: (67 . 0.2128060263653484)

a program P is correct and complete with respect to an intended meaning M if M = M(P).

NOTER_PAGE: (67 . 0.435969868173258)

Summary

NOTER_PAGE: (68 . 0.1224105461393597)

2 Database Programming

NOTER_PAGE: (70 . 0.14689265536723164)

A logic database contains a set of facts and rules.

NOTER_PAGE: (70 . 0.3851224105461393)

relation scheme that specifies the role that each position in the relation (or argument in the goal) is intended to represent

NOTER_PAGE: (70 . 0.6779661016949152)

Variables are given mnemonic names in rules, but usually X or Y when discussing queries

NOTER_PAGE: (70 . 0.7966101694915254)

In general, the same predicate name denotes a different relation when it has a different arity.

NOTER_PAGE: (73 . 0.263653483992467)