Introduction to Logic Programming

tags

Epilog Michael Genesereth

Notes

Chapter 1 - Introduction

NOTER_PAGE: (1 . 0.22585924713584288)

Logic Programming is a style of programming in which programs take the form of sets of sentences in the language of Symbolic Logic. Programs written in this style are called logic programs. The language in which these programs are written is called logic programming language. And a computer system that manages the creation and execution of logic programs is called a logic programming system.

NOTER_PAGE: (1 . 0.32651391162029464)

Logic Programming is practical because there are well-known mechanical techniques for executing logic programs and/or producing traditional programs that achieve the same results.

NOTER_PAGE: (2 . 0.28477905073649756)

describes a type of system that he called an advice taker

NOTER_PAGE: (5 . 0.7561374795417349)

Ed Feigenbaum, the inventor of Knowledge Engineering.

NOTER_PAGE: (6 . 0.10474631751227496)

At the other end of the spectrum is the user with his real problem. … He aspires to communicate what he wants done … without having to lay out in detail all necessary subgoals

NOTER_PAGE: (6 . 0.27086743044189854)

Advocates of declarative representations were centered at Stanford

NOTER_PAGE: (6 . 0.6407528641571195)

The first Prolog program, also written in 1972 and implemented in Marseille, was a French question-answering system.

NOTER_PAGE: (6 . 0.8592471358428806)

Chapter 2 - Datasets

NOTER_PAGE: (8 . 0.2291325695581015)

we usually think in terms of objects and relationships among these objects.

NOTER_PAGE: (8 . 0.5981996726677578)

A dataset is a collection of simple facts that characterize the state of an application area. Facts in a dataset are assumed to be true; facts that are not included in the dataset are assumed to be false.

NOTER_PAGE: (9 . 0.8649754500818331)

A vocabulary is a collection of constants.

NOTER_PAGE: (10 . 0.24959083469721768)

Symbols are intended to represent objects in the world.

NOTER_PAGE: (10 . 0.31014729950900166)

Constructors are used to create compound names for objects.

NOTER_PAGE: (10 . 0.3297872340425532)

Predicates represent relationships on objects.

NOTER_PAGE: (10 . 0.353518821603928)

Each constructor and predicate has an associated arity

NOTER_PAGE: (10 . 0.3878887070376432)

A ground term is either a symbol or a compound name

NOTER_PAGE: (10 . 0.5343698854337152)

ground here means that the term does not contain any variables

NOTER_PAGE: (10 . 0.6014729950900164)

The Herbrand universe for a vocabulary is the set of all ground terms that can be formed from the symbols and constructors in the vocabulary.

NOTER_PAGE: (10 . 0.6824877250409166)

For a finite vocabulary with constructors, the Herbrand universe is infinite

NOTER_PAGE: (10 . 0.7217675941080197)

A datum / factoid / fact is an expression formed from an n-ary predicate and n ground terms

NOTER_PAGE: (10 . 0.8625204582651391)

The Herbrand base for a vocabulary is the set of all factoids that can be formed from the constants in the vocabulary.

NOTER_PAGE: (11 . 0.1391162029459902)

Finally, we define a dataset to be any subset of the Herbrand base, i.e. an arbitrary set of facts that can be formed from the vocabulary of a database.

NOTER_PAGE: (11 . 0.25450081833060556)

Even for a small world like this one, there are quite a few possible ways the world could be.

NOTER_PAGE: (12 . 0.337152209492635)

216 possible datasets.

NOTER_PAGE: (12 . 0.45662847790507366)

We can express gender with two unary predicates male and female.

NOTER_PAGE: (13 . 0.18085106382978725)

By contrast, in Kinship there are constraints that limit the number of possible states. For example, it is not possible for a person to be his own parent

NOTER_PAGE: (13 . 0.8461538461538461)

This raises the question of what makes one conceptualization more appropriate than another. Currently, there is no comprehensive answer to this question.

NOTER_PAGE: (17 . 0.43126022913256956)

grain size

NOTER_PAGE: (17 . 0.5114566284779051)

Indistinguishability abstraction is a form of object reformulation that deals with grain size. If several objects mentioned in a dataset satisfy all of the same conditions, under appropriate circumstances, it is possible to abstract the objects to a single object that does not distinguish the identities of the individuals.

NOTER_PAGE: (17 . 0.7757774140752864)

reification of relations as objects

NOTER_PAGE: (18 . 0.11865793780687399)

There is also the reverse of reification, viz. relationalization.

NOTER_PAGE: (18 . 0.40589198036006546)

essential ontological promiscuity of Logic Programming: Any conceptualization of the world is accommodated, and we seek those that are useful for our purposes.

NOTER_PAGE: (18 . 0.5752864157119476)

Chapter 3 - Queries

NOTER_PAGE: (21 . 0.23158756137479544)

Query rules allow us to express compound queries, notably negations (to say that a condition is false), conjunctions (to say that several conditions are all true), and disjunctions (to say that at least one of several conditions is true).

NOTER_PAGE: (22 . 0.20540098199672668)

An atomic sentence, or atom, is analogous to a factoid in a dataset except that the arguments may include variables as well as symbols

NOTER_PAGE: (22 . 0.36415711947626844)

A literal is either an atom or a negation of an atom.

NOTER_PAGE: (22 . 0.4459901800327332)

A query rule is an expression consisting of a distinguished atom, called the head and a collection of zero or more literals, called the body.

NOTER_PAGE: (22 . 0.5482815057283142)

a query rule is something like a reverse implication

NOTER_PAGE: (22 . 0.7667757774140753)

A query is a non-empty, finite set of query rules. Typically, a query consists of just one rule.

NOTER_PAGE: (23 . 0.21685761047463176)

An instance of an expression (atom, literal, or rule) is one in which all variables have been consistently replaced by ground terms

NOTER_PAGE: (23 . 0.3829787234042553)

Given a rule r and a dataset Δ, we define v(r,Δ) to be the set of all ψ such that (1) ψ is the head of an arbitrary instance of r, (2) every positive subgoal in the instance is a member of Δ, and (3) no negative subgoal in the instance is a member of Δ.

NOTER_PAGE: (23 . 0.6022913256955811)

The extension of a query is the set of all facts that can be "deduced" on the basis of the rules in the program, i.e. it is the union of v(ri,Δ) for each ri in our query.

NOTER_PAGE: (23 . 0.6800327332242226)

The definition of semantics in terms of rule instances is simple and clear. However, Logic Programming systems typically do not implement query processing in this way. There are more efficient ways of computing such extensions.

NOTER_PAGE: (24 . 0.6153846153846154)

A query rule is safe if and only if every variable that appears in the head or in any negative literal in the body also appears in at least one positive literal in the body.

NOTER_PAGE: (24 . 0.7659574468085106)

The main problem with this is that many people incorrectly interpret that negation as meaning there is no Z for which q(Y,Z) is true, whereas the correct reading is that q(Y,Z) needs to be false for just one value of Z.

NOTER_PAGE: (25 . 0.49836333878887074)

In Epilog, equality and inequality are expressed using the relations same and distinct.

NOTER_PAGE: (25 . 0.7495908346972177)

The evaluate relation is used to represent equations involving predefined functions.

NOTER_PAGE: (25 . 0.8273322422258593)

Chapter 4 - Examples

NOTER_PAGE: (28 . 0.22995090016366612)

queries that define solutions to a few classic constraint satisfaction problems.

NOTER_PAGE: (28 . 0.369885433715221)

Y here is a thread variable that connects the first subgoal to the second but does not itself appear in the head

NOTER_PAGE: (28 . 0.6620294599018004)

Exercise 4.2

NOTER_PAGE: (32 . 0.2446808510638298)

Chapter 5 - Query Evaluation

NOTER_PAGE: (33 . 0.2291325695581015)

enumerating instances is not a practical method for computing answers to queries.

NOTER_PAGE: (33 . 0.3502454991816694)

If the body of a query rule is a single atom, we check whether that atom is contained in our dataset.

NOTER_PAGE: (33 . 0.676759410801964)

If the body is a negated atom

NOTER_PAGE: (33 . 0.7430441898527005)

If the atom is not contained in our dataset, then the body is true.

NOTER_PAGE: (33 . 0.7643207855973814)

Matching is the process of determining whether a pattern (an expression with or without variables) matches an instance (an expression without variables)

NOTER_PAGE: (34 . 0.6890343698854338)

A substitution is a matcher for a pattern and an instance if and only if applying the substitution to the pattern results in the given instance.

NOTER_PAGE: (35 . 0.26268412438625205)

We start the procedure with two expressions and a substitution (which is initially empty). We then recursively process the two expressions, comparing the subexpressions at each point. Along the way, we expand the substitution with variable assignments as described

NOTER_PAGE: (35 . 0.4451718494271686)

Evaluating queries with variables is complicated by the fact that there can be multiple variable bindings that make the body of a rule true

NOTER_PAGE: (37 . 0.5842880523731587)

relative benefits are greater when we consider sparse datasets

NOTER_PAGE: (40 . 0.28477905073649756)

Chapter 6 - Query Optimization

NOTER_PAGE: (42 . 0.2291325695581015)

Two queries are semantically equivalent if and only if they produce identical results for every dataset.

NOTER_PAGE: (42 . 0.32733224222585927)

6.2 Subgoal Ordering

NOTER_PAGE: (42 . 0.574468085106383)

There would be n for each value of X.

NOTER_PAGE: (43 . 0.30114566284779054)

the method examines the remaining subgoals in left-to-right order. If it encounters a subgoal all of whose variables are bound by subgoals already chosen, then that subgoal is added

NOTER_PAGE: (43 . 0.8314238952536825)

6.3 Subgoal Removal

NOTER_PAGE: (44 . 0.3322422258592472)

redundant subgoals

NOTER_PAGE: (44 . 0.3944353518821604)

Unfortunately, the method is not complete. There are redundant subgoals that it is does not detect. The problem arises when multiple redundant subgoals share variables

NOTER_PAGE: (45 . 0.4590834697217676)

6.4 Rule Removal

NOTER_PAGE: (45 . 0.8011456628477905)

recognize that the second rule subsumes the first, i.e. all of the answers produced by the second rule are produced by the first rule.

NOTER_PAGE: (46 . 0.31014729950900166)

Chapter 7 - View Definitions

NOTER_PAGE: (50 . 0.23404255319148937)

In what follows, we distinguish two different types of relations - base relations and view relations. We define base relations by writing facts in a dataset, and we define view relations by writing rules in a ruleset

NOTER_PAGE: (51 . 0.19639934533551556)

In writing query rules, we use a single generic predicate

NOTER_PAGE: (52 . 0.15875613747954173)

In writing query rules, the subgoals of our rules can mention only predicates for relations described in the dataset

NOTER_PAGE: (52 . 0.20621931260229134)

good practice to comply with some syntactic restrictions

NOTER_PAGE: (52 . 0.6963993453355156)

The semantics of view definitions is more complicated than the semantics of queries due to the possible occurrence of view predicates in subgoals

NOTER_PAGE: (53 . 0.11456628477905074)

combine the facts in a dataset with the rules defining our views into a joint set of facts and rules, hereafter called a closed logic program

NOTER_PAGE: (53 . 0.19885433715220951)

Herbrand universe for a closed logic program is the set of all ground terms that can be formed from the symbols and constructors in the program.

NOTER_PAGE: (53 . 0.3036006546644845)

Herbrand base for a closed logic program is the set of all atoms that can be formed from the constants in the program.

NOTER_PAGE: (53 . 0.425531914893617)

An interpretation for a closed logic program is an arbitrary subset of the Herbrand base

NOTER_PAGE: (53 . 0.5073649754500819)

A model of a closed logic program is an interpretation that satisfies the program.

NOTER_PAGE: (53 . 0.5900163666121113)

An instance of a rule in a closed logic program is a rule in which all variables have been consistently replaced by terms from the Herbrand universe

NOTER_PAGE: (53 . 0.7520458265139116)

In general, a closed logic program can have more than one model

NOTER_PAGE: (54 . 0.839607201309329)

A factoid is logically entailed by a closed logic program if and only if it is true in every model of the program

NOTER_PAGE: (55 . 0.4967266775777414)

intersection of all interpretations that satisfy

NOTER_PAGE: (55 . 0.5793780687397709)

A model Γ of a logic program Ω is minimal if and only if there is no proper subset of Γ that is a model for Ω. If there is just one minimal model of a closed logic program, then minimality guarantees logical entailment.

NOTER_PAGE: (55 . 0.6833060556464812)

closed logic programs with negation can have more than one minimal model.

NOTER_PAGE: (55 . 0.8494271685761048)

concentrate on programs that are semipositive or programs that are stratified with respect to negation

NOTER_PAGE: (56 . 0.12029459901800328)

A semipositive program is one in which negations apply only to base relations

NOTER_PAGE: (56 . 0.2446808510638298)

applying the view definitions in the program to the facts in the program's dataset.

NOTER_PAGE: (56 . 0.32569558101472995)

An instance of an expression (atom, literal, or rule) is one in which all variables have been consistently replaced by ground terms.

NOTER_PAGE: (56 . 0.3821603927986907)

We say that a set of view definitions is stratified if and only if its rules can be partitioned into strata

NOTER_PAGE: (58 . 0.6432078559738135)

The problem with unstratified rulesets is that there is a potential ambiguity.

NOTER_PAGE: (59 . 0.5433715220949263)

there is just one extension for any safe, stratified logic program.

NOTER_PAGE: (61 . 0.22831423895253683)

Chapter 8 - View Evaluation

NOTER_PAGE: (63 . 0.23240589198036007)

start with a query to be answered and work downward, using rules to reduce the goals to subgoals until they reach subgoals written entirely in terms of base relations.

NOTER_PAGE: (63 . 0.4967266775777414)

in cases where there are infinitely many possible conclusions, they can often find answers to specific questions without doing infinitely much work.

NOTER_PAGE: (63 . 0.6211129296235679)

danger of unnecessary infinite loops

NOTER_PAGE: (63 . 0.6947626841243862)

Top-down evaluation is a recursive procedure.

NOTER_PAGE: (64 . 0.2888707037643208)

Unifcation is the process of determining whether two expressions can be unified, i.e. made identical by appropriate substitutions for their variables.

NOTER_PAGE: (65 . 0.6873977086743045)

Using unification, we can convert our procedure for top-down evaluation for ground queries and rules to a procedure for evaluating arbitrary queries and rules.

NOTER_PAGE: (70 . 0.16366612111292964)

Chapter 9 - Examples

NOTER_PAGE: (73 . 0.23322422258592473)

It is tempting to write the childless rule as childless(X) :- person(X) & ~parent(X,Y). However, this would be wrong. This would define X to be childless if X is a person and there is some Y such that X is ~parent(X,Y) is true. But we really want to say that ~parent(X,Y) holds for all Y. Defining isparent and using its negation in the definition of childless allows us to express this universal quantification.

NOTER_PAGE: (74 . 0.47463175122749596)

Another advantage is that these general sentences apply to Blocks World scenes other than the one pictured here.

NOTER_PAGE: (76 . 0.46072013093289693)

Chapter 10 - Lists, Sets, Trees

NOTER_PAGE: (80 . 0.23240589198036007)

binary constructor cons

NOTER_PAGE: (80 . 0.5507364975450082)

There are three ways to write lists - using square brackets, using cons, and using the ! operator.

NOTER_PAGE: (81 . 0.4926350245499182)

Chapter 11 - Operation Definitions

NOTER_PAGE: (86 . 0.23076923076923078)

rules that define operations in terms of changes to base relations

NOTER_PAGE: (86 . 0.3707037643207856)

views are used in talking about facts that are true in states whereas operations are used in talking about changes to states.

NOTER_PAGE: (86 . 0.43944353518821605)

The syntax of operation definitions is analogous to the syntax for view definitions.

NOTER_PAGE: (86 . 0.6833060556464812)

designate some constants as operation constants

NOTER_PAGE: (86 . 0.7626841243862521)

An action is an application of an operation to specific objects

NOTER_PAGE: (86 . 0.8436988543371523)

An operation definition rule (or, more simply, an operation rule) is an expression of the form shown

NOTER_PAGE: (87 . 0.16202945990180034)

If the conditions of a rule are true in any state, then executing the action in the head requites that we execute the effects of the rule.

NOTER_PAGE: (87 . 0.35270049099836337)

As with view rules, safety is a consideration.

NOTER_PAGE: (87 . 0.6653027823240589)

11.5 Example - Colors

NOTER_PAGE: (91 . 0.3625204582651391)

we can sometimes use values we already know to infer additional values and thereby cut down on the number of possibilities we need to consider.

NOTER_PAGE: (91 . 0.6153846153846154)

Chapter 12 - Dynamic Systems

NOTER_PAGE: (97 . 0.22995090016366612)

12.2 Reactive Systems

NOTER_PAGE: (97 . 0.5793780687397709)

simplest form of reactive system is one whose behavior is driven entirely by external inputs.

NOTER_PAGE: (97 . 0.6194762684124386)

12.3 Closed Systems

NOTER_PAGE: (98 . 0.6693944353518821)

A closed dynamic system is one that operates without external input.

NOTER_PAGE: (98 . 0.7144026186579379)

12.4 Mixed Initiative

NOTER_PAGE: (100 . 0.2733224222585925)

A mixed initiative system is one whose behavior is determined by either external or internal inputs.

NOTER_PAGE: (100 . 0.3199672667757774)

single external input can lead to a single state change or a sequence of changes.

NOTER_PAGE: (100 . 0.3453355155482815)

12.5 Simultaneous Actions

NOTER_PAGE: (101 . 0.2823240589198036)

treating simultaneous inputs independently does not always work.

NOTER_PAGE: (101 . 0.6538461538461539)

terminology for talking about compound actions

NOTER_PAGE: (102 . 0.14402618657937807)

If the number of possible actions is small, it is common practice to use chords to specify different combinations of inputs.

NOTER_PAGE: (102 . 0.2004909983633388)

If the number of possible actions is large, representing compound actions as chords is impractical. In such cases, it is common practice to represent compound actions as action lists.

NOTER_PAGE: (102 . 0.367430441898527)

if all actions in an application are independent of each other, specifying the behavior of compound actions is very simple.

NOTER_PAGE: (102 . 0.8117839607201309)

Formalizing the behavior of simultaneous inputs can be tedious. However, using operation definitions for compound actions, it is at least possible to formalize this behavior correctly

NOTER_PAGE: (103 . 0.19803600654664485)

Chapter 13 - Database Management

NOTER_PAGE: (104 . 0.2274959083469722)

there is no method of repair that is satisfactory in all applications.

NOTER_PAGE: (105 . 0.19967266775777415)

not all constraints can be enforced using update rules.

NOTER_PAGE: (105 . 0.5777414075286416)

benefit of materializing views is that a system can simply look up answers to questions about the materialized view rather than having to compute answers from other stored relations. The downside is that we need to keep such relations up-to-date

NOTER_PAGE: (106 . 0.10474631751227496)

it is possible to build a program that differentiates view definitions and produces such operation definitions automatically.

NOTER_PAGE: (106 . 0.49427168576104746)

may be many extensions of the base relations that give rise to the same view extension.

NOTER_PAGE: (106 . 0.8297872340425533)

update can be ambiguous.

NOTER_PAGE: (106 . 0.8723404255319149)

Chapter 14 - Interactive Worksheets

NOTER_PAGE: (109 . 0.22667757774140754)

Chapter 15 - Variations

NOTER_PAGE: (119 . 0.23240589198036007)

Logic Production Systems

NOTER_PAGE: (119 . 0.43535188216039283)

Rules in a production system have the form: conditions → actions . The rules are executed in a cycle

NOTER_PAGE: (119 . 0.5196399345335516)

The repeated execution of the rules generates the successive states of the working memory

NOTER_PAGE: (119 . 0.6669394435351882)

Constraint Logic Programming

NOTER_PAGE: (120 . 0.6162029459901801)

In a constraint logic program (CLP), the set of all constraints are tested for satisfiability at each step

NOTER_PAGE: (120 . 0.7831423895253683)

Disjunctive Logic Programming

NOTER_PAGE: (121 . 0.8764320785597381)

Existential Logic Programming

NOTER_PAGE: (122 . 0.82569558101473)

An existential rule is a rule that has an atom with a functional term in its head

NOTER_PAGE: (122 . 0.8649754500818331)

negation as failure, because we assume a negated atom to be satisfied because of its absence in D.

NOTER_PAGE: (123 . 0.8224222585924714)

negation as failure semantics ensures that there is a unique model.

NOTER_PAGE: (123 . 0.8453355155482816)

Answer Set Programming (ASP) is an approach for defining the semantics of logic programs that may not be stratified.

NOTER_PAGE: (124 . 0.12029459901800328)

A typical answer set solver does not require an input query.

NOTER_PAGE: (124 . 0.4402618657937807)

For a program that does not contain any negated atoms, or if it contains negated atoms but is safe and stratified, it will have exactly one answer set.

NOTER_PAGE: (124 . 0.6702127659574468)

Answer set semantics provides an elegant way to define the meaning of unstratified logic programs.

NOTER_PAGE: (125 . 0.5261865793780688)

In Inductive Logic Programming, given a dataset, a set of starting view definitions, and a target predicate, we can infer a view definition for the target predicate.

NOTER_PAGE: (126 . 0.15548281505728315)

Review from Éric Martin

do not specify internal processing details

NOTER_PAGE: (1 . 0.33782771535580525)

require programmers to know how the proof engine works to properly order rules and atoms

NOTER_PAGE: (1 . 0.3962546816479401)

So much for focusing on what is true

NOTER_PAGE: (1 . 0.4779026217228465)

absolutely nothing in the book will encourage anyone whose opinion on the matter has not crystallised to dedicate time to study logic programming

NOTER_PAGE: (1 . 0.5093632958801498)

tiny, tiny toy examples

NOTER_PAGE: (1 . 0.5363295880149813)

Everything is covered extremely briefly, extremely superficially

NOTER_PAGE: (2 . 0.07340823970037454)

the allegedly new notions or perspectives, update for instance, are given way too little scope

NOTER_PAGE: (2 . 0.07415730337078652)

The approach is actually no more model-theoretic than proof-theoretic; it is neither, as neither semantics nor proof theory are properly defined

NOTER_PAGE: (2 . 0.19325842696629214)