Rule Based Programming

Here are some attempts at definitions of rule-based programming. Feel free to comment or add your own.

• The rule-based programming paradigm is characterized by the repeated, usually exhaustive, localized transformations of a shared data object (e.g., term, graph, proof, constraint store, ...). The transformations are described by rules which seperate the description of the (sub-) object to be replaced (the pattern) from the calculation of the replacement; optionally, conditional rules can have further conditions that restrict their applicability. The transformations are controlled by explicit or implicit strategies.

A rule-based program consists of a collection of rules.

A rule consists of a pattern that describes how it can be applied and an action that describes what should be done when the rule is applied.

Optionally, a rule can have further conditions that restrict the applicability of the rule.

An implicit strategy exhaustively applies rules.

Ingredients

Here are some typical ingredients of rule-based systems

• three-level decomposition:
  • strategy control: which rule to test/apply where
  • application control: test for rule applicability is seperated from performed calculation
  • calculation

• variation can occur on all three levels: built-in vs. (meta-)programmed strategies, term rewriting vs. graph rewriting, functional vs. imperative calculation

• computation is performed on a shared datastructure (term to be normalized, program to be transformed, constraint store, theorem,...); however, each rule application is localized / usually affects only a part of the datastructure

• rule-based computation is communication-free, i.e., no message-passing; everything is exchanged via the shared datastructure

• rule-based computation has no explicit control flow (done by the strategy)

• rules are oriented (as opposed to equations) and usually memory-less

• the order of rules does not matter

• rules compose (easily), either as union of consequences, or as union of rule sets

Application Areas

• Document transformation and presentation (XML)

• Software building (Make)
• Agent systems

• ProgramTransformation
• Software configuration (Linux kernel)
• Expert systems
• Parsing (context-free grammars)
• Pretty-printing (GPP)
• Theorem proving
• Tree automata
• E-Mail address normalization
• Semantics
• Transition systems

Formalims

• TermRewriting
• LogicProgramming^?
• RewritingStrategies
• RewritingLogic^?
• ContextFreeGrammars
• PrettyPrintTables^?
• AttributeGrammars

Languages and Systems

Specific systems for rule-based programming

• ELAN: RewritingStrategies
• Prolog: LogicProgramming^?
• Stratego: RewritingStrategies
• Mathematica
• Maude
• OBJ
• Claire
• ASFandSDF
• LRR
• IlogRules
• EclipseLanguage

Collections of rule-based programming systems

• RuleBasedProgrammingSystems
• TermRewritingSystems
• TransformationSystems

Issues in Rule Based Programming

• Control over application of rules
• Strategies
• Context-dependent rules
• Dynamic rules

• Algorithmic complexity
• Optimization of rule-based programs
• Semantics
• Compilation and interpretation

Workshops and conferences

• WorkshopOnRuleBasedProgramming
• WorkshopOnRuleBasedConstraintReasoningAndProgramming

History

Rule-based programming began with Artificial Intelligence rule-based systems in the seventies.

The paradigm is inherent in Prolog and has been used in program-manipulation systems like Refine.

Indeed, the rewriting concept appears throughout computer science, from its theoretical foundations to very practical implementations.

Extreme examples include the mail system in Unix which uses rules in order to rewrite mail addresses to canonical forms and the transition rules describing the behaviour of tree automata.

Rewriting is used in semantics in order to describe the meaning of programming languages, as well as in program transformations like the re-engineering of Cobol programs.

It is used to compute, implicitly or explicitly, as in Mathematica or OBJ, but also to perform deduction when using inference rules to describe a logic, theorem prover or constraint solver.

Last, but not least, this approach is central to systems that raise the notion of rule to an explicit first class object, like expert systems, programming languages based on equational logic, algebraic specifications (e.g. OBJ), functional programming (e.g. ML) and transition systems (e.g. Murphi).

Rule-based programming is currently experiencing a renewed period of growth with the emergence of new concepts and systems that allow one to better understand and better use it.

From the theoretical side, after the in-depth study of rewriting concepts during the eighties, the nineties saw the emergence of the general concepts of rewriting logic and of the rewriting calculus.

On the practical side, new languages such as ASM, ASF+SDF, Claire, ELAN, Maude, and Stratego, new systems such as LRR, and also commercial products, such as Ilog Rules, have shown that the concept of rule could be of major interest as a programming tool.

In particular, because it is now of practical use, fundamental questions arise, such as the theoretical study of the algorithmic complexity of programs written in such languages, as well as their optimisation.

Strategies

Of course, semantics of such languages, compilation techniques and methodological studies of their use should also be explored.

Rule based programming is closely related to both functional programming (where the term rewrite system is confluent and terminating) as well as classical logic programming (where the rewrite system is used for nondeterministic search).

Accordingly, the purpose of this workshop is to bring together researchers from these various domains to foster fertilisation between theory and practice, as well as to favour the growth of this programming paradigm.