Development Roadmap

The first versions will focus on developing a core framework for extensible functions that is itself implemented using extensible functions. This self-bootstrapping core will implement a type-tuple-caching engine using relatively primitive operations, and will then have a method combination system built on that. The core will thus be capable of implementing generic functions with multiple dispatch based on positional argument types, and the decorator APIs will be built around that.

The next phase of development will add alternative engines that are oriented towards predicate dispatch and more sophisticated ways of specifying regular class dispatch (e.g. being able to say things like isinstance(x,Foo) or isinstance(y,Foo)). To some extent this will be porting the expression machinery from RuleDispatch to work on the new core, but in a lot of ways it'll just be redone from scratch. Having type-based multiple dispatch available to implement the framework should enable a significant reduction in the complexity of the resulting library.

An additional phase will focus on adding new features not possible with the RuleDispatch engine, such as "predicate functions" (a kind of dynamic macro or rule expansion feature), "classifiers" (a way of priority-sequencing a set of alternative criteria) and others.

Finally, specialty features such as index customization, thread-safety, event-oriented rulesets, and such will be introduced.

Design Concepts

(Note: Criteria, signatures, and predicates are described and tested in detail by the Criteria.txt document.)

Criterion

A criterion is a symbolic representation of a test that returns a boolean for a given value, for example by testing its type. The simplest criterion is just a class or type object, meaning that the value should be of that type.

Signature

A condition expressed purely in terms of simple tests "and"ed together, using no "or" operations of any kind. A signature specifies what argument expressions are tested, and which criteria should be applied to them. The simplest possible signature is a tuple of criteria, with each criterion applied to the corresponding argument in an argument tuple. (An empty tuple matches any possible input.) Signatures are also described

Predicate

One or more signatures "or"ed together. (Note that this means that signatures are predicates, but predicates are not necessarily signatures.)

Rule

A combination of a predicate, an action type, and a body (usually a function.) The existence of a rule implies the existence of one or more actions of the given action type and body, one for each possible signature that could match the predicate.

Action Type

A factory that can produce an Action when supplied with a signature, body, and sequence. (Examples in peak.rules will include the MethodList, MethodChain, Around, Before, and After types.)

Action

An object representing the behavior of a single invocation of a generic function. Action objects may be combined (using a generic function of the form combine_actions(a1,a2)) to create combined methods ala RuleDispatch. Each action comprises at least a signature and a body, but actions of more complex types may include other information.

Rule Set

A collection of rules, combined with some policy information (such as the default action type) and optional optimization hints. A rule set does not directly implement dispatching. Instead, rule engines subscribe to rule sets, and the rule set informs them when actions are added and removed due to changes in the rule set's rules.

This would almost be better named an "action set" than a "rule set", in that it's (virtually speaking) a collection of actions rather than rules. However, you do add and remove entries from it by specifying rules; the actions are merely implied by the rules.

Generic functions will have a __rules__ attribute that points to their rule set, so that the various decorators can add rules to them. You will probably be able to subclass the base RuleSet class or create alternate implementations, as might be useful for supporting persistent or database-stored rules. (Although you'd probably also need a custom rule engine for that.)

Rule Engine

An object that manages the dispatching of a given rule set to implement a specific generic function. Generic functions will have an __engine__ attribute that points to their current engine. Engines will be responsible for doing any indexing, caching, or code generation that may be required to implement the resulting generic function.

The default engine will implement simple type-based multiple dispatch with type-tuple caching. For simple generic functions this is likely to be faster than almost anything else, even C-assisted RuleDispatch. It also should have far less definition-time overhead than a RuleDispatch-style engine would.

Engines will be pluggable, and in fact there will be a mechanism to allow engines to be switched at runtime when certain conditions are met. For example, the default engine could switch automatically to a RuleDispatch-like engine if a rule is added whose conditions can't be translated to simple type dispatching. There will also be some type of hint system to allow users to suggest what kind of engine implementation or special indexing might be appropriate for a particular function.

Signature Implication

The implies() function is used to determine the logical implication relationship between two signatures. A signature s1 implies a signature s2 if s2 will always match an invocation matched by s1. (Action implication is based on signature implication; see the Action Types section below for more details.)

For the simplest signatures (tuples of types), this corresponds to a subclass relationship between the elements of the tuples:

>>> from peak.rules import implies

>>> implies(int, object)
True
>>> implies(object, int)
False

>>> implies(int, str)
False

>>> implies(int, int)
True

>>> implies( (int,str), (object,object) )
True

>>> implies( (object,int), (object,str) )
False

It's possible for a longer tuple to imply a shorter one:

>>> implies( (int,int), (object,) )
True

But not the other way around:

>>> implies( (int,), (object,object) )
False

And as a special case of type implication, any classic class implies both object and InstanceType, but cannot imply any other new-style classes. This special-casing is used to work around the fact that isinstance() will say that a classic class instance is an instance of both object and InstanceType, but issubclass() doesn't agree. PEAK-Rules wants to conform with isinstance() here:

>>> class X: pass
>>> implies(X, object)
True
>>> implies(X, type(X()))   # InstanceType
True

Action Types

>>> from peak.rules import Method, overrides

>>> def dummy(*args, **kw):
...     print "called with", args, kw

>>> meth = Method.make(dummy, (object,), 1)
>>> meth
Method(<...dummy...>, (<type 'object'>,), 1, None)

>>> meth(1,2,x=3)
called with (1, 2) {'x': 3}

>>> overrides(Method.make(dummy,(int,int)), Method.make(dummy,(object,object)))
True

>>> overrides(Method.make(dummy,(object,object)), Method.make(dummy,(int,int)))
False

>>> meth.override(Method.make(dummy))
Method(<...dummy...>, (<type 'object'>,), 1, None)

>>> def overriding_fn(next_method, etc):
...     print "calling", next_method
...     return next_method(etc)

>>> chain = Method.make(overriding_fn).override(Method.make(dummy))
>>> chain
Method(<...overriding_fn...>, (), 0, Method(<...dummy...>, (), 0, None))

>>> chain(42)
calling Method(<...dummy...>, (), 0, None)
called with (42,) {}

>>> combine_actions(Method.make(overriding_fn), Around(dummy))
Around(<...dummy...>, (), 0, None)

>>> naf(1,2,x="y")
Traceback (most recent call last):
  ...
NoApplicableMethods: ((1, 2), {'x': 'y'})

>>> from peak.rules import Before, After

>>> def primary(*args,**kw):
...     print "primary method called"
...     return 99

>>> b = Before.make(dummy).override(Method.make(primary))
>>> a = After.make(dummy).override(Method.make(primary))

>>> b(23)
called with (23,) {}
primary method called
99

>>> a(42)
primary method called
called with (42,) {}
99

>>> b = Before.make(dummy)
>>> a = After.make(dummy)
>>> p = Method.make(primary)
>>> o = Around.make(overriding_fn)
>>> combine_actions(b, combine_actions(a, combine_actions(p, o)))(17)
calling Before(...dummy..., After(...dummy..., Method(...primary...)))
called with (17,) {}
primary method called
called with (17,) {}
99

>>> b1 = Before.make("b1", (), 1)
>>> b2 = Before.make("b2", (), 2)
>>> b3 = Before.make("b3", (int,), 3)

>>> combine_actions(b2, b3).sorted()
[((<type 'int'>,), 'b3'), ((), 'b2')]

>>> combine_actions(b2, b1).sorted()
[((), 'b1'), ((), 'b2')]

>>> combine_actions(b3, combine_actions(b1,b2)).sorted()
[((<type 'int'>,), 'b3'), ((), 'b1'), ((), 'b2')]

>>> a1 = After.make("a1", (), 1)
>>> a2 = After.make("a2", (), 2)
>>> a3 = After.make("a3", (int,), 3)

>>> combine_actions(a2, a3).sorted()
[((), 'a2'), ((<type 'int'>,), 'a3')]

>>> combine_actions(a2, a1).sorted()
[((), 'a2'), ((), 'a1')]

>>> combine_actions(a3, combine_actions(a1,a2)).sorted()
[((), 'a2'), ((), 'a1'), ((<type 'int'>,), 'a3')]

>>> combine_actions(a1,a1).sorted()
[((), 'a1')]

>>> combine_actions(b1,b1).sorted()
[((), 'b1')]

>>> combine_actions(b1, Before.make("b1", (int,), 1)).sorted()
[((<type 'int'>,), 'b1')]

>>> am = combine_actions(meth, meth)
>>> am
AmbiguousMethods([Method(...), Method(...)])

>>> m1 = Method.make(dummy, (int,))
>>> combine_actions(am, m1) is m1
True
>>> combine_actions(m1, am) is m1
True

>>> m2 = Method.make(overriding_fn, (str,))
>>> combine_actions(am, m2)
Method(<...overriding_fn...>, (<type 'str'>,), 0, AmbiguousMethods(...))

>>> combine_actions(m2, am)
Method(<...overriding_fn...>, (<type 'str'>,), 0, AmbiguousMethods(...))

>>> am = combine_actions(m1, m1)
>>> combine_actions(am, meth) is am
True
>>> combine_actions(meth, am) is am
True

>>> combine_actions(m2,am)
AmbiguousMethods([Method(...), Method(...), Method(...)])

>>> combine_actions(am,m2)
AmbiguousMethods([Method(...), Method(...), Method(...)])

>>> am(1,2,x="y")
Traceback (most recent call last):
  ...
AmbiguousMethods: ([Method(...), Method(...)], (1, 2), {'x': 'y'})

>>> class MyMethod(Method):
...     def __call__(self, *args, **kw):
...         print "calling!"
...         return self.body(*args, **kw)

>>> from peak.rules import when, rules_for, abstract

>>> tmp = lambda foo: 42

>>> def func_with(mtype):
...     abstract()
...     def f(foo): """dummy"""
...     rules_for(f).default_actiontype = mtype
...     when(f, (object,))(tmp)
...     return f

>>> f = func_with(MyMethod)

>>> f(1)
calling!
42

>>> from peak.rules import compile_method, Dispatching
>>> engine = Dispatching(f).engine

>>> compile_method(Method(tmp, ()), engine) is tmp
True

>>> m = MyMethod(tmp, ())
>>> compile_method(m, engine) is tmp
False

>>> compile_method(m, engine) is m
True

>>> class MyMethod2(MyMethod):
...     def optimized(self, engine):
...         print "optimizing"
...         return compile_method(self.body, engine)

>>> m = MyMethod2(tmp)
>>> compile_method(m, engine) is tmp
optimizing
True

>>> f = func_with(MyMethod2)

>>> f(1)
optimizing
42

>>> f(1)
42

>>> class MyMethod3(MyMethod2):
...     def __call__(self, *args, **kw):
...         print "calling!"
...         return self.body(*args, **kw)

>>> f = func_with(MyMethod3)

>>> f(1)
calling!
42

>>> f(1)
calling!
42

Decorators

XXX decorators and how to create them: when, around, before, after:

>>> from peak.rules import before, after
>>> def p(x): print x
>>> def f(): p("yo!")

Rule decorators return the function they are decorating, unless the function's name is also the name of the generic function they're adding to:

>>> before(f)(lambda: p("before"))
<function <lambda> at ...>

>>> after(f)(lambda: p("after"))
<function <lambda> at ...>

>>> f()
before
yo!
after

Creating Custom Combinations

XXX custom combination demo from RuleDispatch (compute upcharges+tax)

Rules

Rules are currently implemented as 3-item tuples comprising a predicate, a body, and an action type that will be used as a factory to create the actions for the rule. At minimum, all a rule needs is a body, so there's a convenience constructor (Rule) that allows you to create a rule with defaults. The predicate and action type default to () and None if not specified:

>>> from peak.rules import Rule
>>> def dummy(): pass
>>> r = Rule(dummy, sequence=0)
>>> r
Rule(<function dummy ...>, (), None, 0)

An action type of None (or any false value) means that the ruleset should decide what action type to use. Actually, it can decide anyway, since the rule set is always responsible for creating action objects; the rule's action type is really just advisory to begin with.

RuleSet

RuleSet objects hold the rules and policy information for a generic function, including the default action type and optional optimziation hints.

Iterating over a ruleset yields its actions:

>>> from peak.rules import RuleSet
>>> rs = RuleSet()
>>> list(rs)
[]

And rules can be added and removed with the add() and remove() methods:

>>> r = Rule(dummy, sequence=42)
>>> rs.add(r)
>>> list(rs)
[Rule(<function dummy ...>, (), <...Method...>, 42)]

>>> rs.remove(r)
>>> list(rs)
[]

Observers can be added with the subscribe() and unsubscribe() methods. Observers have their actions_changed method called with an "added" set and a "removed" set of action definitions. (An action definition is a tuple of the form (actiontype, body, signature, precedence), and can thus be used to create action objects.)

>>> class DummyObserver:
...     def actions_changed(self, added, removed):
...         for a in added: print "Add:", a
...         for a in removed: print "Remove:", a
>>> do = DummyObserver()

>>> rs.subscribe(do)

>>> rs.add(r)
Add: Rule(<function dummy ...>, (), <...Method...>, 42)

>>> rs.remove(r)
Remove: Rule(<function dummy ...>, (), <...Method...>, 42)

>>> rs.unsubscribe(do)

When an observer is first added, it's notified of the current contents of the RuleSet, if any. As a result, observers don't need to do any special case handling for their initial setup. Everything can be handled via the normal operation of the actions_changed() method:

>>> rs.add(r)
>>> rs.subscribe(do)
Add: Rule(<function dummy ...>, (), <...Method...>, 42)

Unsubscribing, however, does not send any removal messages:

>>> rs.unsubscribe(do)

DNF Logic

# These 2 funcs must skip dupes and return the item alone if only 1 found
disj(*items) = Or( [i for item in items for i in disjuncts(item)] )
conj(items)  = And([i for item in items for i in conjuncts(item)] )


def combinatorial(seq, *tail):
    if tail:
        return ((item,)+t for item in seq for t in combinatorial(*tail))
    else:
        return ((item,) for item in seq)

# this func would be more efficient if 'conj' were moved inside 'combinatorial'
# especially if conj were a binary operation, and the results of each nested
# loop were reduced to a unique set...
#
intersect(*items) = Or(
    map(conj, combinatorial(*map(disjuncts,items)))
)

# simplified, but still needs dupe skipping/flattening of the Or
intersect(i1, i2) = Or(
    *[conj((a,b)) for a in set(disjuncts(i1)) for b in set(disjuncts(i2))]
)


disjuncts(Or) = Or.items
disjuncts(Not) = map(negate, conjuncts(Not.expr))
disjuncts(*) = [*]

conjuncts(And) = And.items
conjuncts(Not) = map(negate, disjuncts(Not.expr))
conjuncts(*) = [*]

negate(And) = Or(map(negate,And.items))
negate(Or)  = And(map(negate,Or.items))
negate(Not) = Not.expr
negate(Compare) = reverse comparison sense ?
negate(*) = Not(*)

Not-methods and negate() function could be eliminated by CriteriaBuilder
tracking negation during build.



implies(Or, *)  iff all Or.items imply *
implies(And, *) iff any And.items imply *
implies(*, *)   iff equal items  [need to define for struct/struct, too!]

implies(Range, Range) by range overlap
implies(IsInstance, IsInstance) by subclass relationships/truth map

to_logic(Call)    -> via function mapping for Call(Const(),...)
to_logic(Compare) -> Identity, IsInstance, Range, etc.?
to_logic(*)       -> Truth(expr, mode)

Criteria/Indexing

dispatch_table(*, Identity, cases) -> {seed: bitmap}
  where bitmap = inclusions[seed] | (inclusions[None] - exclusions[seed])
     | (cases - known_cases)