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

Books

• Rule-Based Programming by ThaddeusKowalski^? and LeonLevy^?