match-refute diagrams

Match-refute diagrams are a low-level hybrid between imperative and logic paradigms, related to both first order logic and binary decision diagrams.

Match-refute diagrams operate on first order predicates over discrete symbols. However, predicates are only used for input and output. Nodes in the diagram are named, and pass information to each other through numbered registers. This design, in comparison to most ways of representing first order logic programs, has a clearly understood runtime: O(ns^r) where n is the number of nodes, s is the number of symbols, and r is the number of registers. By limiting the number of registers and symbols, match-refute diagrams can be efficiently evaluated, even if they are randomly generated. Their design is also intended to be effective as an Implicitly Neutral allelic representation for Evolutionary Strategies. I have not yet run experiments exploring the limits of using them for this purpose.

Essentially, the algorithm for evaluating match-refute diagrams is as follows:

• Create a register set where each register contains :nil, and place it in the root of the diagram.
• While there are register sets that haven't been propagated down the diagram, propagate them by evaluating the match for each tuple of current node's predicate.
  • If the match succeeds, run the register update, and propagate the resulting register set to all of the nodes in the match arm of the node.
  • If the match fails (is refuted), run the register update anyways, and propagate the resulting register set to all of the nodes in the refute arm of the node (if there is one).
  • When a register set reaches an output node, output the specified predicate using the tuple generated by the register set.

Example (rules of tic-tac-toe):

root: player(_ -> %0) { check_move }
check_move: move(_ -> %1, _ -> %2) { check_space }
check_space: board(%1, %2, :blank) { do_move }
do_move: board(%1 -> %1, %2 -> %2, _ -> %3) {
  output next_board(%1, %2, %0)
} {
  output next_board(%1, %2, %3)
}