================== Predicate Dispatch ================== Predicate Expression Types ========================== Predicate expression types wrap expressions to specify what kind of dispatching should be done on the base expression. For example, ``predicates.IsInstance`` indicates that an expression is to be looked up by what it's an instance of. There are five built-in expression types:: >>> from peak.rules.predicates import \ ... Truth, Identity, Comparison, IsSubclass, IsInstance And we will test them using code objects: >>> from peak.util.assembler import Code, Const >>> from dis import dis Truth ----- The ``Truth`` predicate tests whether its subject expression is true or false, and selects the appropriate sub-node from a ``(true_node, false_node)`` tuple:: >>> c = Code() >>> c(Truth(42)) >>> dis(c.code()) 0 0 LOAD_FAST 0 ($Arg) 3 UNPACK_SEQUENCE 2 6 LOAD_CONST 1 (42) 9 JUMP_IF_TRUE 1 (to 13) 12 ROT_THREE >> 13 POP_TOP 14 ROT_TWO 15 POP_TOP The generated code unpacks the 2-tuple, and then does a bit of stack manipulation to select the correct subnode. The ``disjuncts()`` of a Truth Test is the Test itself:: >>> from peak.rules import disjuncts >>> from peak.rules.criteria import Test, Signature, Value >>> disjuncts(Test(Truth(88), Value(True))) [Test(Truth(88), Value(True, True))] >>> disjuncts(Test(Truth(88), Value(True, False))) [Test(Truth(88), Value(True, False))] Identity -------- The ``Identity`` predicate looks up the ``id()`` of its subject expression in a dictionary of sub-nodes. If the id isn't found, the ``None`` entry is used:: >>> c = Code() >>> c(Identity(99)) >>> dis(c.code()) 0 0 LOAD_CONST 1 () 3 LOAD_CONST 2 (99) 6 CALL_FUNCTION 1 9 DUP_TOP 10 LOAD_FAST 0 ($Arg) 13 COMPARE_OP 6 (in) 16 JUMP_IF_FALSE 9 (to 28) 19 POP_TOP 20 LOAD_FAST 0 ($Arg) 23 ROT_TWO 24 BINARY_SUBSCR 25 JUMP_FORWARD 9 (to 37) >> 28 POP_TOP 29 POP_TOP 30 LOAD_FAST 0 ($Arg) 33 LOAD_CONST 0 (None) 36 BINARY_SUBSCR Comparison ---------- The ``Comparison`` predicate expects its "arg" to be an ``(exact, ranges)`` pair, such as might be generated by the ``peak.rules.indexing.split_ranges`` function:: >>> c = Code() >>> c(Comparison(555)) >>> dis(c.code()) 0 0 LOAD_CONST 1 () 3 LOAD_CONST 2 (555) 6 LOAD_FAST 0 ($Arg) 9 CALL_FUNCTION 2 The generated code simply calls a helper function, ``value_check``, with its expression and argument. The helper function looks up and returns the appropriate subnode, first by trying for an exact match, and then looking for a range match if no exact match is found:: >>> from peak.rules.predicates import value_check >>> from peak.util.extremes import Min, Max >>> exact = {'x':1, 'y':2} >>> ranges = [((Min,'x'),42), (('x','y'),99), (('y',Max),88)] >>> for letter in 'wxyz': ... print value_check(letter, (exact, ranges)) 42 1 2 88 >>> value_check('xx', (exact, ranges)) 99 IsSubclass ---------- The ``IsSubclass`` predicate uses a ``(cache, lookup)`` node pair, where `cache` is a dictionary from classes to nodes, and `lookup` is a function to call with the class, in the event that the target class isn't found in the cache:: >>> c = Code() >>> c(IsSubclass(Const(int))) >>> dis(c.code()) 0 0 LOAD_CONST 1 () 3 SETUP_EXCEPT 16 (to 22) 6 DUP_TOP 7 LOAD_FAST 0 ($Arg) 10 UNPACK_SEQUENCE 2 13 ROT_THREE 14 POP_TOP 15 BINARY_SUBSCR 16 ROT_TWO 17 POP_TOP 18 POP_BLOCK 19 JUMP_FORWARD 30 (to 52) >> 22 DUP_TOP 23 LOAD_CONST 2 (<...KeyError...>) 26 COMPARE_OP 10 (exception match) 29 JUMP_IF_FALSE 18 (to 50) 32 POP_TOP 33 POP_TOP 34 POP_TOP 35 POP_TOP 36 LOAD_FAST 0 ($Arg) 39 UNPACK_SEQUENCE 2 42 POP_TOP 43 ROT_TWO 44 CALL_FUNCTION 1 47 JUMP_FORWARD 2 (to 52) >> 50 POP_TOP 51 END_FINALLY IsInstance ---------- The ``IsInstance`` predicate is virtually identical to ``IsSubclass``, except that it first obtains the ``__class__`` or ``type()`` of its target:: >>> c = Code() >>> c(IsInstance(Const(999))) >>> dis(c.code()) 0 0 LOAD_CONST 1 (999) 3 SETUP_EXCEPT 10 (to 16) 6 DUP_TOP 7 LOAD_ATTR 0 (__class__) 10 ROT_TWO 11 POP_TOP 12 POP_BLOCK 13 JUMP_FORWARD 26 (to 42) >> 16 DUP_TOP 17 LOAD_CONST 2 (<...AttributeError...>) 20 COMPARE_OP 10 (exception match) 23 JUMP_IF_FALSE 14 (to 40) 26 POP_TOP 27 POP_TOP 28 POP_TOP 29 POP_TOP 30 LOAD_CONST 3 () 33 ROT_TWO 34 CALL_FUNCTION 1 37 JUMP_FORWARD 2 (to 42) >> 40 POP_TOP 41 END_FINALLY >> 42 SETUP_EXCEPT 16 (to 61) 45 DUP_TOP 46 LOAD_FAST 0 ($Arg) 49 UNPACK_SEQUENCE 2 52 ROT_THREE 53 POP_TOP 54 BINARY_SUBSCR 55 ROT_TWO 56 POP_TOP 57 POP_BLOCK 58 JUMP_FORWARD 30 (to 91) >> 61 DUP_TOP 62 LOAD_CONST 4 (<...KeyError...>) 65 COMPARE_OP 10 (exception match) 68 JUMP_IF_FALSE 18 (to 89) 71 POP_TOP 72 POP_TOP 73 POP_TOP 74 POP_TOP 75 LOAD_FAST 0 ($Arg) 78 UNPACK_SEQUENCE 2 81 POP_TOP 82 ROT_TWO 83 CALL_FUNCTION 1 86 JUMP_FORWARD 2 (to 91) >> 89 POP_TOP 90 END_FINALLY Defining New Predicate Types ----------------------------- A predicate type must be a ``peak.util.assembler.nodetype``, capable of generating its own lookup code. The code will be used in a ``SMIGenerator`` context (see the `Code Generation`_ manual), so ``SMIGenerator.ARG`` will contain a lookup node. Each predicate type must be usable with the ``predicates.predicate_node_for`` function, and the ``predicates.always_testable`` function: predicate_node_for(builder, expr, cases, remaining_exprs, memo) Return a dispatch tree node argument appropriate for the expr. The return value(s) of this function will be in the ``SMIGenerator.ARG`` local variable when the predicate type's bytecode is executed. always_testable(expr) Return true if the expression can always be tested, regardless of its position among the signature condition(s). Most predicate types should just implement this by calling ``always_testable()`` recursively on their target expression, and in fact all of the built-in predicate types do this. For more details, see the section on `Order Independence`_ below. Predicate Parsing ================= The ``CriteriaBuilder`` class can be used to parse Python expressions into tests and signatures. It's initialized using the same arguments as the ``codegen.ExprBuilder`` class:: >>> from peak.rules.predicates import CriteriaBuilder, Comparison, istype >>> from peak.rules.criteria import Disjunction, Value, Test, Range, Class, OrElse >>> from peak.util.assembler import Local >>> builder = CriteriaBuilder( ... dict(x=Local('x'), y=Local('y')), locals(), globals(), __builtins__ ... ) >>> pe = builder.parse >>> pe('x+42 > 23*2') Test(Comparison(Add(Local('x'), Const(42))), Range((46, 1), (Max, 1))) The ``in`` operator converts constant classes and ``istype()`` expressions into ``IsInstance`` tests:: >>> pe('x in int') Test(IsInstance(Local('x')), Class(, True)) >>> pe('x not in int') Test(IsInstance(Local('x')), Class(, False)) >>> pe('x in istype(int)') Test(IsInstance(Local('x')), istype(, True)) >>> pe('x not in istype(int)') Test(IsInstance(Local('x')), istype(, False)) >>> pe('x in istype(int, False)') Test(IsInstance(Local('x')), istype(, False)) >>> pe('x not in istype(int, False)') Test(IsInstance(Local('x')), istype(, True)) Iterable constants into or-ed equality tests:: >>> pe('x in (1,2,3)') == Disjunction([ ... Test(Comparison(Local('x')), Value(2, True)), ... Test(Comparison(Local('x')), Value(3, True)), ... Test(Comparison(Local('x')), Value(1, True)) ... ]) True >>> pe('x not in (1,2,3)') == Test( ... Comparison(Local('x')), ... Disjunction([ ... Range((Min, -1), (1, -1)), Range((1, 1), (2, -1)), ... Range((2, 1), (3, -1)), Range((3, 1), (Max, 1)) ... ]) ... ) True And non-iterable constants into plain expressions:: >>> pe('x in 27') Test(Truth(Compare(Local('x'), (('in', Const(27)),))), Value(True, True)) >>> pe('x not in 27') Test(Truth(Compare(Local('x'), (('not in', Const(27)),))), Value(True, True)) The ``is`` operator produces identity tests, if either side is a constant:: >>> pe('x is 42') Test(Identity(Local('x')), IsObject(42, True)) >>> pe('42 is not x') Test(Identity(Local('x')), IsObject(42, False)) And plain expressions when neither side is constant:: >>> pe('x is y') Test(Truth(Compare(Local('x'), (('is', Local('y')),))), Value(True, True)) >>> pe('x is not y') Test(Truth(Compare(Local('x'), (('is not', Local('y')),))), Value(True, True)) >>> pe('not (x is y)') Test(Truth(Compare(Local('x'), (('is', Local('y')),))), Value(True, False)) >>> pe('not (x is not y)') Test(Truth(Compare(Local('x'), (('is not', Local('y')),))), Value(True, False)) Complex logical expressions are always rendered in disjunctive normal form, with negations simplified away or reduced to match flags on criteria objects:: >>> pe('x in int and y in str') Signature([Test(IsInstance(Local('x')), Class(, True)), Test(IsInstance(Local('y')), Class(, True))]) >>> pe('not(x not in int or y not in str)') Signature([Test(IsInstance(Local('x')), Class(, True)), Test(IsInstance(Local('y')), Class(, True))]) >>> pe('x in int and (y in str or y in unicode)') OrElse([Signature([Test(IsInstance(Local('x')), Class(, True)), Test(IsInstance(Local('y')), Class(, True))]), Signature([Test(IsInstance(Local('x')), Class(, True)), Test(IsInstance(Local('y')), Class(, True))])]) >>> pe('not (x in int or y in str)') Signature([Test(IsInstance(Local('x')), Class(, False)), Test(IsInstance(Local('y')), Class(, False))]) >>> pe('not( x not in int and y not in str)') == OrElse([ ... Test(IsInstance(Local('x')), Class(int)), ... Test(IsInstance(Local('y')), Class(str)) ... ]) True >>> pe('not( x in int and y in str)') OrElse([Test(IsInstance(Local('x')), Class(, False)), Test(IsInstance(Local('y')), Class(, False))]) And arbitrary expressions are handled as truth tests:: >>> pe('x') Test(Truth(Local('x')), Value(True, True)) >>> pe('not x') Test(Truth(Local('x')), Value(True, False)) Note, by the way, that backquotes are not allowed in predicate expressions, as they are reserved for use by macros or "meta functions" to create specialized syntax:: >>> pe('`x`') Traceback (most recent call last): ... SyntaxError: backquotes are not allowed in predicates Pattern Matching ---------------- Arbitrary expressions can be pattern matched for conversion into signatures. At the moment, the only patterns matched are ``isinstance`` and ``issubclass`` calls where the second argument is a constant, and ``type(x) is y`` expressions where `y` is a constant:: >>> from peak.rules.criteria import Test, Signature, Classes >>> pe('isinstance(x,int)') Test(IsInstance(Local('x')), Class(, True)) >>> pe('isinstance(x,(str,unicode))') == Disjunction([ ... Test(IsInstance(Local('x')), Class(str)), ... Test(IsInstance(Local('x')), Class(unicode)) ... ]) True >>> pe('type(x) is int') Test(IsInstance(Local('x')), istype(, True)) >>> pe('str is not type(x)') Test(IsInstance(Local('x')), istype(, False)) >>> pe('not isinstance(x,(int,(str,unicode)))') == Test( ... IsInstance(Local('x')), Classes([ ... Class(unicode, False), Class(int, False), Class(str, False)]) ... ) True >>> pe('isinstance(x,(int,(str,unicode)))') == Disjunction([ ... Test(IsInstance(Local('x')), Class(str)), ... Test(IsInstance(Local('x')), Class(int)), ... Test(IsInstance(Local('x')), Class(unicode)) ... ]) True >>> pe('issubclass(x,int)') Test(IsSubclass(Local('x')), Class(, True)) >>> pe('issubclass(x,(str,unicode))') == Disjunction([ ... Test(IsSubclass(Local('x')), Class(str)), ... Test(IsSubclass(Local('x')), Class(unicode)) ... ]) True >>> pe('issubclass(x,(int,(str,unicode)))') == Disjunction([ ... Test(IsSubclass(Local('x')), Class(str)), ... Test(IsSubclass(Local('x')), Class(int)), ... Test(IsSubclass(Local('x')), Class(unicode)) ... ]) True >>> pe('not issubclass(x,(int,(str,unicode)))') == Test( ... IsSubclass(Local('x')), Classes([ ... Class(unicode, False), Class(int, False), Class(str, False)]) ... ) True >>> pe('issubclass(int, object)') True "Meta Function" Expansion ------------------------- To create special functions with the ability to manipulate the compile-time representation of a rule, you can register "meta functions" with the ``meta_function`` decorator. You begin by defining a stub function which will be imported and used by the caller in their rules:: >>> def let(**kw): ... """This is a function that will have special behavior in rules""" ... raise NotImplementedError("`let` can only be used in rules") Then, you define a "meta function" for this function, that will be called at compile time. The signature of this function must match the signature with which it will be called, except that it can have zero or more extra parameters at the beginning named ``__builder__``, ``__star__`` and/or ``__dstar__``. ``__builder__``, for example, will be the active ``ExpressionBuilder``:: >>> def compile_let(__builder__, **kw): ... __builder__.bind(kw) ... return True To register your "meta function", you use ``@meta_function(stub_function)``:: >>> from peak.rules.predicates import meta_function >>> compile_let = meta_function(let)(compile_let) Then, when the stub function is used in a rule, the meta function is called with the PEAK-Rules AST objects resulting from compiling the invocation of the stub function in the rule:: >>> builder = CriteriaBuilder( ... dict(x=Local('x'), y=Local('y')), locals(), globals(), __builtins__ ... ) >>> pe = builder.parse >>> pe('let(q=x*y) and q>42') Test(Comparison(Mul(Local('x'), Local('y'))), Range((42, 1), (Max, 1))) As you can see, our ``compile_let`` meta-function bound ``q`` to ``Mul(Local('x'), Local('y'))``, which was the compiled form of the keyword argument it received. Notice, by the way, that our meta-function does NOT accept ``**`` arguments:: >>> pe('let(**{"z":x*y}) and z>42') Traceback (most recent call last): ... TypeError: does not support parsing **kw Or ``*`` arguments::: >>> pe('let(*[1,2]) and z>42') Traceback (most recent call last): ... TypeError: does not support parsing *args This is because we didn't include ``__star__`` or ``__dstar__`` parameters at the beginning of the ``compile_let()`` parameter list; if we had, the function would have received either the compiled AST for the corresponding part of the call, or ``None`` if no star or double-star arguments were provided. Dynamic Arguments ~~~~~~~~~~~~~~~~~ Notice, by the way, that ``__star__`` and ``__dstar__`` refer to the *caller's* use of ``*`` and ``**`` to make dynamic calls. The meta function can have ``*`` and ``**`` parameters, but these are passed any *static* positional or keyword arguments used by the caller. For example:: >>> def dummy(*args, **kw): ... """Just a dummy""" >>> def compile_dummy(__star__, __dstar__, p1, p2=None, *args, **kw): ... print "p1 =", p1 ... print "p2 =", p2 ... print "args =", args ... print "kw =", kw ... print "__star__ =", __star__ ... print "__dstar__ =", __dstar__ ... return True >>> compile_dummy = meta_function(dummy)(compile_dummy) >>> builder = CriteriaBuilder( ... dict(x=Local('x'), y=Local('y')), locals(), globals(), __builtins__ ... ) >>> pe = builder.parse >>> pe('dummy(x, y, x*x, y*y, k1=x, k2=y, *x+1, **y*2)') p1 = Local('x') p2 = Local('y') args = (Mul(Local('x'), Local('x')), Mul(Local('y'), Local('y'))) kw = {'k2': Local('y'), 'k1': Local('x')} __star__ = Add(Local('x'), Const(1)) __dstar__ = Mul(Local('y'), Const(2)) True >>> pe('dummy(x)') p1 = Local('x') p2 = None args = () kw = {} __star__ = None __dstar__ = None True Argument Errors ~~~~~~~~~~~~~~~ Static argument errors, such as failure to pass the right number of positional arguments, and duplicate keyword arguments that occur in the source (as opposed to runtime ``*`` or ``**`` problems), are detected at compile time:: >>> pe('dummy(x, p1=y)') Traceback (most recent call last): ... TypeError: Duplicate keyword p1 for <... compile_dummy at ...> >>> pe('dummy(p2=x, p2=y)') Traceback (most recent call last): ... TypeError: Duplicate keyword p2 for <... compile_dummy at ...> >>> pe('dummy()') Traceback (most recent call last): ... TypeError: Missing positional argument p1 for <... compile_dummy at ...> >>> pe('let(x)') Traceback (most recent call last): ... TypeError: Too many arguments for <... compile_let at ...> Also, note that meta functions cannot have packed-tuple arguments:: >>> meta_function(lambda x,y:None)(lambda x,(y,z): True) Traceback (most recent call last): ... TypeError: Meta-functions cannot have packed-tuple arguments Custom Argument Compiling ~~~~~~~~~~~~~~~~~~~~~~~~~ On occasion, a meta function may wish to interpret one or more of its arguments using a custom expression builder in place of the standard one, so that instead of a PEAK-Rules AST, it gets some other data structure. You can do this by passing keyword arguments to ``@meta_function()`` that supply a builder function for each argument that needs custom building. A builder function is a 2-argument callable that will be passed the active ``ExpressionBuilder`` instance and the raw Python AST tuples of the argument it is supposed to parse. The function must then return whatever value should be used as the parsed form of the argument supplied to the meta function. For example:: >>> def make_builder(text): ... def builder_function(old_builder, arg_node): ... return text ... return builder_function >>> def dummy2(*args, **kw): ... """Just another dummy""" >>> compile_dummy = meta_function(dummy2, ... p1=make_builder('p1'), p2=make_builder('p2'), ... args=make_builder('args'), kw=make_builder('kw'), ... k2=make_builder('k2'), ... __star__ = make_builder('*'), __dstar__=make_builder('**') ... )(compile_dummy) >>> builder = CriteriaBuilder( ... dict(x=Local('x'), y=Local('y')), locals(), globals(), __builtins__ ... ) >>> pe = builder.parse >>> pe('dummy2(x, y, x*x, y*y, k1=x, k2=y, *x+1, **y*2)') p1 = p1 p2 = p2 args = ('args', 'args') kw = {'k2': 'k2', 'k1': 'kw'} __star__ = * __dstar__ = ** True As you can see, build functions are selected on the basis of the argument name they target. If the meta function has a ``*`` parameter, each of the overflow positional arguments is parsed with the builder function of the corresponding name. If a named keyword argument has a build function, that one is used, otherwise any build function for the ``**`` parameter is used. Binding Scope ~~~~~~~~~~~~~ Note that bindings defined by meta-functions (e.g. our ``let`` example) cannot escape "or" or "not" clauses in an expression:: >>> pe('let(q=1) or x>q') Traceback (most recent call last): ... NameError: q >>> pe('not let(q=1) and x>> pe('not (let(q=1) and x>> pe('let(q=2) and (not let(q=3) or x>> from peak.rules.core import Dispatching, implies >>> from peak.rules.criteria import tests_for >>> engine = Dispatching(implies).engine >>> list(tests_for((int,str), engine)) [Test(IsInstance(Local('s1')), Class(, True)), Test(IsInstance(Local('s2')), Class(, True))] >>> list(tests_for((istype(tuple),), engine)) [Test(IsInstance(Local('s1')), istype(, True))] Each element of the type tuple is converted using a second generic function, ``type_to_test``:: >>> from peak.rules.predicates import type_to_test >>> type_to_test(int, Local('x'), engine) Test(IsInstance(Local('x')), Class(, True)) >>> type_to_test(istype(str), Local('x'), engine) Test(IsInstance(Local('x')), istype(, True)) >>> class x: pass >>> type_to_test(x, Local('x'), engine) Test(IsInstance(Local('x')), Class(, True)) If you implement a new kind of class test for use in type tuples, you'll need to add the appropriate method(s) to ``type_to_test`` if you want it to also work with the predicate engine. Criterion Ordering ================== Criterion ordering for a predicate dispatch engine is defined by the ordering of the tests in its signatures. Any test expression that is not defined as ``always_testable``, must not be computed until after any test expressions to its left have been tested. But tests whose expression is just a local variable (i.e., a plain function argument), do not have such restrictions:: >>> from peak.rules.predicates import IndexedEngine >>> from peak.rules import abstract, when >>> from peak.rules.indexing import Ordering >>> from peak.rules.codegen import Add >>> def f(a,b): pass >>> f = abstract(f) >>> m = when(f, "isinstance(a, int) and a+b==42")(lambda a,b: None) >>> engine = Dispatching(f).engine >>> list(Ordering(engine, IsInstance(Local('a'))).constraints) [frozenset([])] >>> list(Ordering(engine, Comparison(Add(Local('a'),Local('b')))).constraints) [frozenset([IsInstance(Local('a'))])] >>> def f(a,b): pass >>> f = abstract(f) >>> m = when(f, "isinstance(b, str) and a+b==42 and isinstance(a, int)")( ... lambda a,b: None ... ) >>> engine = Dispatching(f).engine >>> list(Ordering(engine, IsInstance(Local('a'))).constraints) [frozenset([])] >>> list(Ordering(engine, IsInstance(Local('b'))).constraints) [frozenset([])] >>> list(Ordering(engine, Comparison(Add(Local('a'),Local('b')))).constraints) [frozenset([IsInstance(Local('b'))])] >>> def f(a,b): pass >>> f = abstract(f) >>> m = when(f, "isinstance(a, int) and isinstance(b, str) and a+b==42")( ... lambda a,b: None ... ) >>> engine = Dispatching(f).engine >>> list(Ordering(engine, IsInstance(Local('a'))).constraints) [frozenset([])] >>> list(Ordering(engine, IsInstance(Local('b'))).constraints) [frozenset([])] >>> list(Ordering(engine, Comparison(Add(Local('a'),Local('b')))).constraints) [frozenset([IsInstance(Local('a')), IsInstance(Local('b'))])] Order Independence ------------------ The determination of whether a test expression can be used in an order- independent way, is via the ``always_testable()`` function:: >>> from peak.rules.predicates import always_testable In general, only locals and constants can have their tests applied independent of signature ordering:: >>> always_testable(Local('x')) True >>> always_testable(Const(99)) True >>> always_testable(Add(Local('a'),Local('b'))) False And predicate test expressions are evaluated according to their tested expression:: >>> always_testable(IsInstance(Local('x'))) True >>> always_testable(IsInstance(Add(Local('a'),Local('b')))) False >>> always_testable(Comparison(Local('x'))) True >>> always_testable(Comparison(Add(Local('a'),Local('b')))) False >>> always_testable(Identity(Local('x'))) True >>> always_testable(Identity(Add(Local('a'),Local('b')))) False >>> always_testable(Truth(Local('x'))) True >>> always_testable(Truth(Add(Local('a'),Local('b')))) False Except for ``IsSubclass()``, which may need to have other tests applied before it:: >>> always_testable(IsSubclass(Local('x'))) False If you create a new predicate type, be sure to define a method for ``always_testable`` that will recursively invoke ``always_testable`` on the predicate's target expression. If you don't do this, then your predicate type will always be treated as order-dependent, even if its target expression is a local or constant.