The Sad State Concerning the Relationships between Logic, Rules and Logic Programming


January 13, 2015 3:48 PM

Confusions about the relationships between logic, rules and logic programming are endemic in the world of computing. Here are some quotes from Paul Thagard’s popular textbook [15], Mind, Introduction to Cognitive Science, which show how bad things are:

Rules are if-then structures such as: IF you pass forty Arts courses, THEN you graduate with a B.A. These structures are very similar to the conditionals discussed in chapter 2, but they have different representational and computational properties. (Page 43)

Unlike logic, rule-based systems can also easily represent strategic information about what to do. Rules often contain actions that represent goals, such as IF you want to go home for the weekend, and you have the bus fare, THEN you can catch a bus. (Page 45)

In logic-based systems the fundamental operation of thinking is logical deduction, but from the perspective of rule-based systems the fundamental operation of thinking is search.  (Page 45)

Rule-based problem solving sounds a lot like logical deduction, but it differs in that much more attention is paid to strategies for applying the right rules at the right time. (Page 47)

I am particularly sensitive to the claim about the difference between deduction and search, because two of my earliest papers [3, 4] investigated the relationship between deduction and search. In my 2011 book [5], I discuss Thagard’s various claims about logic and rules, and I argue that there are three varieties of production rules:

  1. Rules like IF you pass forty Arts courses, THEN you graduate with a B.A. These are logic programming clauses, used to reason forwards from conditions to conclusions.
  2. Rules like IF you want to go home for the weekend, and you have the bus fare, THEN you can catch a bus. These are “forward chaining” rules, used to simulate backward reasoning with logic programming clauses, such as, you go home for the weekend, if you have the bus fare, and you catch a bus.
  3. Rules like IF you are hungry THEN eat something. These are reactive rules, used to make the conclusion of the rule true whenever the condition of the rule becomes true.

In the book, I argue that reactive rules have a more general syntax than logic programming clauses, and they are also more fundamental. But, curiously, almost all of the examples of rules in Thagard’s book are of the first and second variety. So, contrary to Thagard’s intentions, most of his arguments against logic and in favour of rules are actually arguments for logic programming.

In the book (Chapter 8), I argue that reactive rules (or maintenance goals) are the “driving force of life”. Consider, for example, the following AgentSpeak [14] reactive rule (or “plan”), which specifies a waste-collecting robot’s mission in life:

+location(waste, X):location(robot, X) & location(bin, Y) <- pick(waste); !location(robot, Y); drop(waste).

The rule is triggered whenever waste appears at a location and the robot is at the same location.  The robot then picks up the waste, moves to the bin location and drops the waste. The direction of the arrow <- is motivated by the seeming similarity of such plans to logic programming clauses. But it is opposite to the direction that is needed to give the plan a logical meaning. For example:

If there is waste at location X at time T1, and the robot is at location X at T1 and the bin is at location Y at T1, then the robot picks up the waste at time T1+1, the robot goes to location Y at some time T2 (after T1) and the robot drops the waste into the bin at time T2+1.

 

There are two problems with such rule-based systems: How to specify the logic of reactive rules, and how to relate the logic of reactive rules to the logic of logic programs.

Abductive logic programming (ALP) [2, 6] provides a candidate solution: Given a Horn clause logic program P, a set of integrity constraints I (representing reactive rules) and candidate assumptions A (representing all possible state-transforming actions), the computational task is to find a collection of actions Δ ⊆ A, such that I is true in the minimal model of P ⋃ Δ. For more general logic programs, the minimal model needs to be replaced by a more general canonical model, such as the perfect model.

The ALP solution also needs a way to generate state transitions. It is common to use the event calculus [13] for this purpose. But this involves using a frame axiom, to reason explicitly that a fact (or fluent) that is true in a state continues to be true in subsequent states until it is terminated by an action or external event. This kind of reasoning is not computationally feasible in the general case. However, Fariba Sadri and I have shown [7, 8, 9, 10, 11, 12] that state transitions can also be generated in the usual, more efficient way that uses destructive updates, without affecting the model theoretic semantics. We call the resulting framework LPS, for Logic-based Production System, because it was motivated by the goal of giving a logical semantics to production systems.

In some of our recent papers, for the sake of simplicity, we have focussed on a Kernel sublanguage, KELPS [10, 11], which consists of reactive rules alone. It was only recently that we realised that the model-theoretic semantics of KELPS is similar to that of MetaTem, which was being developed by other researchers in our logic programming group at Imperial College in the late 1980s.

MetaTem is a modal temporal logic language in which all program statements have the form past and present formula implies present or future formula. For example,

    hungry ==> (buy_food ∧ О cook_food ∧ О О eat)

At a sufficiently abstract level, the semantics of MetaTem is identical to that of LPS and KELPS: Computation is the process of attempting to generate a model that makes the program true. But in MetaTem, models are possible world structures, generated using frame axioms. In KELPS/LPS, programs are represented in a non-modal language with explicit time, and models are classical models in which all facts are time stamped and contained in a single structure.  For example, in KELPS, the MetaTem program above would be approximated by a reactive rule of the form:

    hungry(T) --> buy_food(T+1) ∧ cook_food(T+2) ∧ eat(T+3)

where buying food occurs after (instead of at the same time as) becoming hungry.

I believe that KELPS and LPS are more powerful and more efficient than MetaTem. But the  MetaTem  approach was on the right track. Back in the 1980s, because it was so different from logic programming and because it was formulated in modal logic, I couldn’t see the bigger picture.

Having finally understood MetaTem after more than 25 years, although it was developed under my own nose, I am not surprised that other researchers also have problems in seeing connections that are staring them in the face. Nonetheless, it is still a sad state of affairs.

 

References

  1. Barringer, H., Fisher, M., Gabbay, D., Gough, G., & Owens, R. (1990, January). METATEM: A framework for programming in temporal logic. In Stepwise Refinement of Distributed Systems Models, Formalisms, Correctness (pp. 94-129). Springer Berlin Heidelberg, Available at http://www.dcs.kcl.ac.uk/staff/dg/068-metatem.pdf.
  2. Kakas, A. C., Kowalski, R., Toni, F. (1998). The Role of Logic Programming in Abduction, Handbook of Logic in Artificial Intelligence and Programming 5, Oxford University Press, 235-324.
  3. Kowalski, R. (1970), "Search Strategies for Theorem-proving", in Machine Intelligence 5,  (eds. B. Meltzer and D. Michie), Edinburgh University Press, 1970, pp. 181-201, Available at http://aitopics.org/sites/default/files/classic/Machine%20Intelligence%205/MI5-Ch10-Kowalski.pdf.
  4. Kowalski, R. (1972), "And-or Graphs, Theorem-proving Graphs and Bi-directional Search", in Machine Intelligence 7,  (eds. B. Meltzer and D. Michie), Edinburgh University Press, 1972, pp. 167-94. Available at http://aitopics.org/sites/default/files/classic/Machine_Intelligence_7/MI-7-Ch10-Kowalski.pdf.
  5. Kowalski, R. (2011) Computational Logic and Human Thinking: How to be Artificially Intelligent, Cambridge University Press. Available at http://www.doc.ic.ac.uk/~rak/papers/newbook.pdf.
  6. Kowalski, R. and Sadri, F. (1999) From Logic Programming Towards Multi-agent Systems, Annals of Mathematics and Artificial Intelligence, Vol. 25, 391-419.
  7. Kowalski, R. and Sadri, F. (2009) Integrating Logic Programming and Production Systems in Abductive Logic Programming Agents. In Proceedings of the Third International Conference on Web Reasoning and Rule Systems, Chantilly, Virginia, USA.
  8. Kowalski, R. and Sadri, F. (2010) An Agent Language with Destructive Assignment and Model-Theoretic Semantics, In: Dix J., Leite J., Governatori G., Jamroga W. (eds.), Proc. of the 11th International Workshop on Computational Logic in Multi-Agent Systems (CLIMA), 200-218.
  9. Kowalski, R. and Sadri, F. (2011) Abductive Logic Programming Agents with Destructive Databases, Annals of Mathematics and Artificial Intelligence, Vol. 62, No. 1, 129-158.
  10. Kowalski, R. and Sadri, F. (2012) A Logic-Based Framework for Reactive Systems, Rules on the Web: Research and Applications, In: A. Bikakis and A. Giurca (Eds.) Proceedings of the 6th International Symposium on Rules: Research Based and Industry Focused (RuleML 2012),  Springer-Verlag, LNCS 7438, pp. 1–15. See also http://www.doc.ic.ac.uk/~rak/papers/RuleML.pdf.
  11. Kowalski, R. and Sadri, F. (2014)  A Logical Characterization of a Reactive System Language, In: A. Bikakis et al. (Eds.) Proceedings of the 8th International Web Rule Symposium (RuleML 2014), LNCS 8620, Springer International Publishing Switzerland, pp. 22-36. See also http://www.doc.ic.ac.uk/~rak/papers/KELPS%20Completeness.pdf.
  12. Kowalski, R. and Sadri, F. (2014) Model-theoretic and operational semantics for Reactive Computing. To appear in New Generation Computing.
  13. Kowalski, R., Sergot, M. (1986) A Logic-based Calculus of Events. New Generation Computing, Vol. 4, No.1, 67—95. Available at http://www.doc.ic.ac.uk/~rak/papers/event%20calculus.pdf.
  14. Rao, A. (1996) AgentSpeak (L): BDI agents speak out in a logical computable language. Agents Breaking Away, 42-55. Available at http://www.upv.es/sma/teoria/teoria_ag/agentspeakl/agentspeakl-rao.pdf.
  15. Thagard, P. (2005) Mind: Introduction to cognitive science. MIT press.