Definitions
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
Languages and Systems
Specific systems for rule-based programming
Collections of rule-based programming systems
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
CategoryParadigm |
CategoryRuleBased? | Contributions by
EelcoVisser,
BerndFischer