Validating combinations based on rule sets (or similar mechanism)

Question

Let's say I've got many functions and each function accepts an unordered list (order does not matter). For each function I want to see if this list is valid based on certain rules (a knowledgebase that has the rules for each function's list).

Each one of this lists is at its core a combination, right? And each combination can be:

1. Acceptable
2. Not valid due to a certain element not being acceptable
3. Not valid due to some combination not being acceptable (let's say I allow [1, 2] and [1, 3] but [2, 3] is not acceptable)

I'm trying to find a way to:

1. Have each set of rules/possibilities in a knowledgebase, that can be updated whenever I want (maybe reading from a file? I would actually prefer a DSL to write the rules, if possible) and can be loaded at startup

2. A way to validate these rules/possibilities in an intelligent and elegant manner and not resorting to nested if else's and the such.

Example

fun_1([a, b, c]) :
  check_knowledgebase([a, b, c]) # => valid

fun_1([a, b, d]):
  check_knowledgebase([a, b, d]) # => element d is invalid

fun_1([a, c, d]):
  check_knowledgebase([a, c, d]) # => combining c with d is invalid

I've been thinking about this but I don't know what kind of theory or algorithms I should look into for this. I thought about Rule Engines, but implementing one would be too time consuming for something so small?

EDIT: I'm not exactly looking for a language specific solution, I want a solution that is mostly language agnostic.

Answer 1

Object oriented languages

It's extremely simple to write a simple rule engine in an object oriented language, using the following design:

The knowledge base is a container (e.g. list) of rules, and the RuleEngine acts as the knowledge base checker, that applies all the rules to its input.

In this construct, you could derive a new class for each new kind of rules. In order to avoid unnecessary explosion of rule classes, you could also consider to use parametrized rules e.g. RuleForbidElement('D') instead of RuleForbidD.

You could save these rules to or load these rules from a file with usual serialization techniques.

By the way, you'll recognize here a simplified version of the interpreter pattern with only terminal nodes.

Functional languages

If the class concept in your language supports polymorphism, you could very well apply the same design as above.

However, you could also think of the (lambda calculus based) variation:

• each rule would be a function taking a list in input and returning a boolean in output.
• a knowledge base kb would be a list of functions
• the rule engine would iterate through the list to apply each function to its input and combine all the outputs. A possible implementation could be a recursive function re(x, kb) that returns true if kb is empty or else (head(kb))(x) AND re(x,tail(kb)) , where head() is the first element of a list and tail() is the list without its first element (e.g. hd/tl in caml or car/cdr in lisp)

Each rule is a distinct function, so it's then very flexible to write them and add new ones.

Note that the parametrized classes in the object oriented design, would be replaced here by functions taking some parameters to return a function that can be applied to a list to return a boolean.