Rule Based Programming

Program-Transformation.Org: The Program Transformation Wiki
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