Towards a Unifying Logic-Based Framework forProgramming
Databases
AI knowledge representation and problem-solving

Robert Kowalski and Fariba Sadri
Department of Computing
Imperial College London

1Outline•

KELPS - a simplified kernel for reactive logic-based
production-style systems•

Related work (MetateM, Transaction Logic)•

LPS = KELPS + Logic Programs•

MALPS = Multi Agent LPS (The Dining Philosophers)•

Model-theoretic semantics•

Operational semantics•The frame problem•

Conclusions

2

KELPS - a simplified kernel for reactive
logic-based production-style systemsPrograms are reactive rules with explicit timein the logical form:X [antecedent(X) Y consequent(X, Y)]abbreviatedwheneverthenantecedent(X) consequent(X, Y)

the antecedent is true,
the consequent is true in the future.

3Model-theoretic semantics:
facts are time-stamped
Computation:model generation
Si

Operational Semantics:
facts updated destructively
without time stamps
ei

Si+1

old-fact
fact1
fact2
…
factn

new-fact
fact1
fact2
…
factn

ti

ti+1
4

KELPS = Composite events + rules + composite actions
pre-sensor detects possible fire in area A at time T1 ∧smoke detector detects smoke in area A at time T2 ∧|T1 – T2 |  60 sec ∧ max(T1, T2, T) activate local fire suppression in area A at time T3 ∧ T <T3  T + 10 sec ∧send security guard to area A at time T4∧ T3 <T4  T3 + 30 sec∨ call fire department to area A at time T3‘∧ T <T3‘  T + 120 sec

5

Syntax of reactive rules in KELPS
antecedent1 (X) ∧… ∧ antecedentn (X)consequent11 (X, Y) ∧… ∧ consequent1l1 (X, Y)∨ …
∨ consequentm1 (X, Y) ∧… ∧ consequentmlm (X, Y)
Each antecedenti (X) and consequenti j(X, Y) is:•an FOL condition in the vocabulary of state predicates(operationally a query to the extended current state)•

an event atom representing an event (including action)•a temporal constraint time1 < time2 or time1 ≤ time2

Each consequenti1 (X, Y) ∧… ∧ consequentil1 (X, Y) is a plan.
6Outline
•

KELPS

•

Related work (MetateM, Transaction Logic)•LPS = KELPS + Logic Programs•

MALPS = Multi Agent LPS (The Dining Philosophers)•Model-theoretic semantics•

Operational semantics•The frame problem•

Conclusions

7

MetateM (Michael Fisher et al)
Programs = reactive rules in modal temporal logic:‘past and present formula’ implies ‘present or future formula’
Computation = model generation.
Model = possible worlds connected by an accessibility relation.
States updated non-destructively by frame axioms.

8

Transaction Logic (Bonner and Kifer)
Programs = sequences of FOL queries and database updates.
Computation = model generation.

Model = possible worlds.
Truth defined relative to paths between possible worlds.
States (databases) updated destructively.

9Outline•

KELPS•

Related work•

LPS = KELPS + Logic Programs•

MALPS = Multi Agent LPS (The Dining Philosophers)•Model-theoretic semantics•Operational semantics•

The frame problem•

Conclusions

10

LPS = KELPS + Logic Programs
Programs = reactive rules + logic programs with FOL queries.
Computation = model generation.

Model = single, minimal Herbrand model with time stamps.
Truth defined as in classical FOL.
States updated destructively.

11LPS framework <R, L, D> and current state S
The state S is a set of ground atomic sentences, representing:•the extensional part of a deductive database, or•
program variables changed by destructive assignment, or•a Herbrand model of the current state of the world.
Reactive rules R: X [antecedent(X) Y consequent(X, Y)]
Logic program L = Lint  Levents  Ltimeless  Ltemp
Ltimeless defines time independent predicates.
Lintdefines intensional predicates in terms of extensional predicates.
Levents defines composite events in terms of atomic events.
Ltemp defines temporal predicates <, .
Domain theory D is a logic program thatdefines preconditions and postconditions of atomic events
12

Blocks world <R, L, D> and current state S
R:

request(on(Block, Place), T1) make-on(Block, Place, T2, T3)  T1 < T2

S* : Deductive database: extensional predicates on(Block, Place, T).
Lint: clear(table, T)
clear(Block, T)   X on(X, Block, T)
Levents: make-on(Block, Place, T, T)  on(Block, Place, T)
make-on(Block, Place, T1, T3)  make-clear(Block, TB1, TB2)
 make-clear(Place, TP1, TP2)  min(TB1, TP1, T1)  max(TB2, TP2, T2)
 move(Block, Place, T3)  T2 < T3

make-clear(Place, T, T)  clear(Place, T)
make-clear(Place, T1, T3)  on(Block, Place, T1)
 make-clear(Block, T1, T2) move(Block, table, T3)  T2 < T3
D:possible(move(Block, Place), T)  clear(Block, T)  clear(Place, T)  Block  Place
initiates(move(Block, Place), on(Block, Place), T)
terminates(move(Block, Place), on(Block, Support), T)  on(Block, Support,T)13

Dialogue/parsing example <R, L, D> where L = Levents D = {} S = {}Reactive rule R:
sentence(T1, T2)  sentence (T3, T4)  T2 < T3 < T2 + 10
Atomic events:
word(my, 1, 2)

word(name, 2, 3)

word(is, 3, 4)word(bob, 4, 5)

Composite events (and actions) Levents :adjective(T1, T2)  word(my, T1, T2)
adjective(T1, T2)  word(your, T1, T2)
noun(T1, T2)  word(name, T1, T2)
noun(T1, T2)  word(bob, T1, T2)

verb(T1, T2)  word(is, T1, T2)
noun(T1, T2)  word(what, T1, T2)sentence(T1, T3)  noun-phrase(T1, T2)  verb-phrase(T2, T3)
noun-phrase(T1, T3)  adjective(T1, T2)  noun(T2, T3)
noun-phrase(T1, T2)  noun(T1, T2)
verb-phrase(T1, T3)  verb(T1, T2)  noun-phrase(T2, T3)
verb-phrase(T1, T2)  verb(T1, T2)
14

The reactive rule is true in the sequence of atomic andcomposite events{word(my, 1, 2)
word(bob, 4, 5)
word(your, 8, 9)
adjective(1, 2)
noun(4, 5)
adjective(8, 9)
noun-phrase(2, 3)sentence(2, 4)
noun-phrase(6, 7)
verb-phrase(7, 10) Tempword(name, 2, 3)
word(what, 6, 7)
word(name, 9, 10)
noun(2, 3)
noun(6, 7)
noun(9, 10)
noun-phrase(4, 5)sentence(2, 5)
noun-phrase(8, 10)sentence(6, 8)

word(is, 3, 4)word(is, 7, 8)verb(3, 4)verb(7, 8)
noun-phrase(1, 3)
verb-phrase(3, 5)sentence(1, 5)
noun-phrase(9, 10)sentence(6, 10)}where Temp (includes 5 < 6) is the extension of the inequality
relation defined by Ltemp .
15

LPS: alternative external notations
Transaction Logic:
P  Q means P(T1)  Q(T2)  T1 < T2
or P(T1 , T2)  Q(T3, T4)  T2 < T3

Modal temporal logic:P  ◊Q means P(T1)  Q(T2)  T1 < T2.
P  Q means P(T)  Q(T+1)
or P(T1)  Q(T2)  T1 <T2  T1+ ε

Graphical notation:
PQt1 t2
t3 t4

Rmeans P(T1)  Q(T2)  R(T3)  T1 + t1  T3  T1 + t2 
T2 + t3  T3  T2 + t4
16

Outline
•

KELPS

•

Related work•

LPS•

MALPS = Multi Agent LPS (The Dining Philosophers)•

Model-theoretic semantics•

Operational semantics•

The frame problem•

Conclusions

17

The Dining Philosophers

18

The Dining Philosophers
The initial state S0: available(fork0)
available(fork1)
available(fork2)
available(fork3)
available(fork4)
Ltimelessadjacent(fork0, philosopher(0), fork1)
adjacent(fork1, philosopher(1), fork2)
adjacent(fork2, philosopher(2), fork3)
adjacent(fork3, philosopher(3), fork4)
adjacent(fork4, philosopher(4), fork0)
19

The Dining Philosophers – with time-free syntax
time-to-eat(philosopher(I))
 dine(philosopher(I))
dine(philosopher(I))
 think(philosopher(I)),
pickup-forks(philosopher(I)),
eat(philosopher(I)),
putdown-forks(philosopher(I))

20

Atomic actions are defined by thedomain specific event theory D

pickup-forks(philosopher(I))
terminatesavailable(F1) and available(F2)preconditions available(F1), available(F2) ifadjacent(F1, philosopher(I), F2).
putdown-forks(philosopher(I))
initiates
available(F1) and available(F2) if
adjacent(F1, philosopher(I), F2).

21

The reactive rule is true in the sequence of states and actions:S0: {available(fork0), available(fork1), available(fork2), available(fork3), available(fork4)}
A1: {think(philosopher(0)), think(philosopher(1)), think(philosopher(2)), think(philosopher(3)), think(philosopher(4)) }S1: {available(fork0), available(fork1), available(fork2), available(fork3), available(fork4)}
A2: {pickup-forks(philosopher(0)), pickup-forks(philosopher(2))}
S2: {available(fork4)}
A3: {eat(philosopher(0)), eat(philosopher(2))}
S3: {available(fork4)}
A4: {putdown-forks(philosopher(0)), putdown-forks(philosopher(2))}
S4: {available(fork0), available(fork1), available(fork2), available(fork3), available(fork4)}
A5: {pickup-forks(philosopher(1)), pickup-forks(philosopher(3))}
S5: {available(fork0)}
A6: {eat(philosopher(1)), eat(philosopher(3))}
S6: {available(fork0)}
A7: {putdown-forks(philosopher(1)), putdown-forks(philosopher(3))}
S7: {available(fork0), available(fork1), available(fork2), available(fork3), available(fork4)}
A8: {pickup-forks(philosopher(4))}
S8: {available(fork1), available(fork2), available(fork3)}
A9: {eat(philosopher(4))}
S9: {available(fork1), available(fork2), available(fork3)}
A10: {putdown-forks(philosopher(4))}
S10: {available(fork0), available(fork1), available(fork2), available(fork3), available(fork4)}

22

Outline
•

KELPS

•

Related work•

LPS•

MALPS•

Model-theoretic semantics•

Operational semantics•

The frame problem•

Conclusions

23Model-theoretic semantics
Given <R, L, D> and initial state S0* with explicit time,ex1*,…, exi*,…. sequence of sets of external events with explicit time,
the computational task is to generate a sequence of sets of actions
a1*,…, ai*,…. such that R is true in the “intended” minimal model of:

L  S0*  S1*  .... Si* ... e1*  e2*  … ei*  ….
where ei* = exi *  ai *Si = (Si-1 – {p| terminates(ei, p, ti) is true in ei*  Si-1*  Ltimeless  Lint  D} )
 {p | initiates(ei, p, ti) is true in ei*  Si-1*  Ltimeless  Lint  D}
Si* = {holds(p, ti) | p  Si at time ti}
24Outline
•

KELPS

•

Related work•

LPS

•

MALPS

•

Model-theoretic semantics•

Operational semantics•The frame problem•

Conclusions

25

The operational semantics is anobserve–decide–think –act cycle.
The i-th cycle transforms Si-1, Ri-1, Gi-1 and ei
into Si, Ri, Gi, and actions ai+1•

Gi is a conjunction of goals.

•Each goal has the form:
subgoal11 (X, Y) ∧… ∧ subgoal1l1 (X, Y)∨ …
∨ subgoalm1 (X, Y) ∧… ∧ subgoalmlm (X, Y)
Each subgoalij is an event, FOL condition or temporal constraint.
26

Simplified operational semantics (for LPS - Levents )Step 0. Observe. Use ei to transform Si-1 into Si.
Step 1. Think. If earlier-antecedents(X)  later-antecedents(X)  consequent(X, Y)
is in Ri-1 and earlier-antecedents(x) is true in ei*  Si*  Ltimeless  Lint
then simplify any temporal constraints in later-antecedents(x)  consequent(x, Y)
and add the result to Ri-1 to obtain Ri.
If later-antecedents(x) is empty, then add the result to Gi-1 as a new goal.
Step 2.1. Decide. Choose a set P of plans from one or more goals in Gi-1.

Step 2.2. Think. For every plan in P, choose a formearlier-consequents(Y)  later-consequents(Y).
If earlier-consequents(y) is true in ei*  Si*  Ltimeless  Lint
then simplify any temporal constraints in later-consequents(y)and add the result as an new plan to the same goal in P to obtain Gi.
Step 2.3. Act. For every plan in P of a formactions(Z)  other-consequents(Z), choose such a form,
attempt to execute actions(Z)and add any successfully executed instances actions(z) to ei+1.

27

The operational semantics is sound with respect tothe model-theoretic semantics.
Theorem. Given external events ex1,…, exn,….,suppose the operational semantics generates:
S0, R0, G0 , a1, … ,Si, Ri, Gi, ai+1, ….
Let M be the “intended” minimal model of:
L  S0*  S1*  .... Si* ... e1*  e2*  … ei*  ….
Then R0  G0 is true in M if and only if

for every new goal G added to a goal state Gi,
there exists a goal state Gj, j  i such that the empty plan (equivalent to true)is added as a new plan to the same goal as G in Gj.

28

IncompletenessThe operational semantics is incomplete.
It cannot preventively make a rule true by making its
antecedents false:
attacks(X, me, T1)  ¬ prepared-for-attack(me, T1)
 surrender(me, T2)  T1 < T2  T1 + It cannot proactively make a reactive rule true by making itsconsequents true before its antecedents become true:

enter-bus(me, T1)
 have-ticket(me, T2)  T1 < T2  T1 + 29

Outline
•

KELPS

•

Related work•

LPS

•

MALPS

•

Model-theoretic semantics•

Operational semantics•

The frame problem•

Conclusions

30

Model-theoretic semantics – an alternative formulation
with general purpose event theory Etholds
holds(P, T2)  happens(E, T1, T2)  initiates(E, P, T1)
holds(P, T2)  holds(P, T1)  happens(E, T1, T2)  ¬ terminates(E, P, T1)

Given <R, L, D> and initial state S0* with explicit time,ex1*,…, exi*,…. sequence of sets of external events with explicit time,
the computational task is to generate a sequence of sets of actions
a1*,…, ai*,…. such that R is true in the “intended” minimal model of:
ETholds  L  D  S0* e1*  e2*  … ei*  ….

31

Solving the computational aspect of the frame problem

Theorem. The “intended” minimal model of:
ETholds  L  D  S0* e1*  e2*  … ei*  ….

is identical to the “intended” minimal model of:
L  D  S0*  S1*  .... Si* ... e1*  e2*  … ei*  ….

32

Conclusions•Destructive assignment does not need a semantics.
It is the semantics.

•Challenge: Find a framework that unifies

Programming
Databases
AI knowledge representation and problem-solving

33