A Logic Programming Perspective on Rules

A Logic Programming Perspective on Rules

Leon Sterling (University of Melbourne, Australia) and Kuldar Taveter (Tallinn University of Technology, Estonia)
DOI: 10.4018/978-1-60566-402-6.ch009
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Logic programming emerged from the realization that expressing knowledge in an appropriate clausal form in logic was akin to programming. The basic construct of a logic program can be viewed as a rule. This chapter will review rules from a logic programming perspective with an eye to developments within modern rule languages. It mentions rule interpreters, hybrid computing, interaction with the Web, and agents. An extended example is given concerning rule-based modelling and simulation of traffic at airports.
Chapter Preview
Top

1. Background

Rules have a long history in mathematics and computing, from inference rules such as modus ponens in logic, rewrite rules in grammar, to rules as norms or guidelines. More recently, rules have been seen as a key part of computing in applications such as expert systems and electronic commerce. There is a natural tendency to reinvent the wheel. To try to minimise reinvention in the case of rules, it is worth being aware of some of the developments that rules have gone through over the past forty years. It is in that spirit that this chapter is being written.

The discussion is focussed on how rules are used in logic programming, a computing paradigm that is arguably the most rule-based. The development of logic programming occurred in the intersection of automated theorem proving, artificial intelligence and programming languages. The most successful logic programming language has been Prolog (Clocksin & Mellish, 1981), (Sterling & Shapiro, 1994). We claim that experience with using Prolog has influenced current thinking about rules.

The roots of logic programming lie in the resolution rule of inference developed by Alan Robinson (Robinson, 1965). Robinson’s research aimed to improve the behaviour of automated theorem provers by developing, in Robinson’s words, a “machine-oriented rule of inference”. A key component of Robinson’s approach was two-way matching of logical terms, which became known as unification.

Resolution was regarded as a promising approach for achieving artificial intelligence. Situations could be expressed with logical formulae, problems expressed as a theorem to be proved from the logic describing the situation, and resolution used as the mechanism for machine reasoning. Unfortunately, resolution did not live up to the hype that it could be a universal mechanism for intelligence. Many artificial intelligence researchers abandoned logic-based rule approaches.

Several researchers, instead of abandoning resolution, tried to understand when resolution worked well and when it did not. One idea to improve the performance of resolution was to restrict the form of logical axioms to be used in theorem proving. The most successful restriction was using Horn clauses. Logic programming emerged in the early 1970s from the confluence of the work by Bob Kowalski working on restrictions to resolution-based theorem provers and the work by Alain Colmerauer on using grammar rules in logic for parsing sentences in natural language. The history is described by each of the main protagonists in (Kowalski, 1988) and (Colmerauer & Roussel, 2000) and separately by Jacques Cohen (Cohen, 1988).

The programming in logic programming came from the observation that the process of restricting how logic was expressed was akin to programming. The relevance for this book is that structuring logic is effectively structuring rules and the way that rules are expressed significantly affects their computational efficacy. The programming aspect of logic programming is not directly pursued in this chapter, but the reader is referred to (Kowalski, 1979) and (Sterling & Shapiro, 1994).

In the 1980s there was an explosion of interest in using artificial intelligence in practical applications. Expert systems were a key technology and were often rule-based. Expert system shells were developed and commercialised. The shells allowed developers to write their own rules. The interpreter contained within the shell was essentially either backward chaining from goals to facts or forward chaining from data to conclusions.

More recently rules have been studied as an entity in their own right. As the Internet has transformed the computing landscape, rules have been integrated at various levels. Three examples are as application development constructs for electronic commerce applications, for describing Web content, and for facilitating search. Taveter & Wagner (2001) identified the three most basic types of rules as integrity constraints (also called constraint rules or integrity rules), derivation rules, and reaction rules (also called stimulus-response rules, action rules, event-condition-action rules, or automation rules).

Key Terms in this Chapter

Triggering Event: An event that triggers the execution of a reaction rule.

Reaction Rule also Known as Event-Condition-Action (ECA) Rule: A rule that determines what actions are performed if a certain triggering event occurs and a certain state condition holds.

Agent: An active entity that can act, perceive, and reason.

State Condition: A condition referring to the state of an agent, object, or environment for performing actions by a reaction rule.

Agent-Oriented Modelling: A modelling paradigm where the world is viewed in terms of agents and objects and the models for the world are created from the viewpoint aspects of the viewpoint framework.

Prolog: A programming language based on logic programming whose primary constructs are derivation rules.

Viewpoint Framework: A matrix with three rows representing different abstraction layers and three columns representing the viewpoint aspects interaction, information, and behaviour.

Object: A passive entity that is not able to act, perceive, or reason.

Derivation Rule also Known as Condition-Action Rule: A rule that derives knowledge from other knowledge by an inference or a mathematical calculation.

Integrity Constraint: an assertion that must be satisfied in all evolving states and state transition histories of the system.

Side Effect: An effect by a derivation rule that modifies some state of an agent, object, or environment in addition to its declarative reading.

Logic Programming: a programming paradigm whose constructs are derived from logic and where the computational mechanism is primarily logical deduction.

Complete Chapter List

Search this Book:
Reset