Fun with decorators and unification dispatch

[talin at acm dot org]

Been playing around a bit more with developing my python inference
engine, and I thought it might be of general interest (plus, I am
finding the criticism useful).

My original goal was to brush up on my math skills. Now, I've long felt
that the best way to learn a language *thoroughly* is to write a
compiler for it. So why not write a compiler for math?

However, algebra and calculus aren't just about evaluating an
expression and getting the answer, they are about *manipulating*
mathematical expressions, applying transformations to them. Systems
that do this (such as Mathematica and Yacas) are called "computer
algebra systems", so I decided to see how hard it would be to implement
one in Python.

A computer algebra system is essentially a specialized kind of expert
system, in other words it is a set of transformation rules, where an
input expression is matched against a database of patterns, and the
result of the database query determines what transformation is to be
made.

Most such systems start by implementing their own, specialized
programming language, but I wanted instead to see if I could add a
inference engine capability to Python itself.

So what I have is a dispatch mechanism that maintains a database of
Python functions, keyed by the input pattern. Unlike multimethod
systems, the input patterns are not merely a list of types, but can be
trees containing both constants and variables.

Here's a trivial example, using the classic recursive algorithm for
computing the factorial of a number:

# Declare that "Factor" is a generic function
Factorial = Function()

# Define Factorial( 0 )
@Arity( 0 )
def Factorial():
    return 1

# Define Factorial( x )
@Arity( MatchInteger.x )
def Factorial( x ):
    return x * Factorial( x - 1 )

print Factorial( 12 )

"Function" produces an instance of a generic function, which is a
callable object. When called, it searches its list of patterns to
determine the function to dispatch.

The "Arity" decorator adds the function as a special case of the
generic function. It adds the specific function to the generic's
internal pattern database, and also returns the generic function as its
return result, so that that (in this case) the name "Factorial" is
bound to the generic function object.

"MatchInteger" is a class that produces a matching object, otherwise
known as a bound variable. In this case, the variable's name is "x".
(It overloads the "__getattr__" method to get the variable name.) When
the pattern matcher encounters a matching object, it attempts to bind
the corresponding portion of the expression to that variable. It does
this by adding the mapping of variable name to value into a dictionary
of variable bindings.

When the function is called, the dictionary of variable bindings is
expanded and passed to the function (i.e. func( *bindings )), so that
the variable that was bound to "x" now gets passed in as the "x"
parameter of the function.

MatchInteger itself is a type of "qualified match" (that is, a variable
that only binds under certain conditions), and could be defined as:

MatchInteger = QualifiedMatch( lambda x: type( x ) is int )

(Although it is not in fact defined this way.) QualifiedMatch takes a
list of matching preducates, which are applied to the expression before
binding can take place.

Here's a more complex example, which is a set of rules for simplifying
an expression:

Simplify = Function()

# x => x
@Arity( MatchAny.x )
def Simplify( x ):
    return x

# x * 0 => 0
@Arity( ( Multiply, MatchAny.x, 0 ) )
def Simplify( x ):
    return 0

# x * 1 => x
@Arity( ( Multiply, MatchAny.x, 1 ) )
def Simplify( x ):
    return Simplify( x )

# x + 0 => x
@Arity( ( Add, MatchAny.x, 0 ) )
def Simplify( x ):
    return Simplify( x )

# x + x => 2x
@Arity( ( Add, MatchAny.x, MatchAny.x ) )
def Simplify( x ):
    return (Multiply, 2, Simplify( x ) )

# General recursion rule
@Arity( ( MatchAny.f, MatchAny.x, MatchAny.y ) )
def Simplify( f, x, y ):
    return ( Simplify( f ), Simplify( x ), Simplify( y ) )

And in fact if I call the function:

print Pretty( Simplify( Parse( "(x + 2) * 1" ) ) )
print Pretty( Simplify( Parse( "x * 1 + 0" ) ) )
print Pretty( Simplify( Parse( "y + y" ) ) )
print Pretty( Simplify( Parse( "(x + y) + (x + y)" ) ) )

It prints:

x + 2
x
2 * y
2 * (x + y)

The argument matcher tries to prioritize matches so that more specific
matches (i.e. containing more constants) are matched before more
general matches. This is perhaps too unsophisticated a scheme, but it
seems to have worked so far.

The pattern matcher also looks to see if the object being matched has
the "commute" or "associate" property. If it finds "commute" it
attempts to match against all posssible permutations of the input
arguments (with special optimized logic for functions of one and two
arguments). If the "associate" property is found, it first tries to
flatten the expression (transforming (+ a (+ b c)) into (+ a b c), and
then generating all possible partitions of the arguments into two sets,
before attempting to match each set with the pattern. The matching
algorithms aren't perfect yet, however, there are still a number of
things to work out. (such as deciding whether or not the arguments need
to be unflattened afterwards.)

The matcher makes heavy use of recursive generators to implement
backtracking.

My next tasks is to figure out how to get it to handle matrices. I'd
like to be able to to match any square matrix with a  syntax something
like this:

@Arity( MatchMatrix( MatchInteger.n, MatchInteger.n ).x )

Which is saying to match any matrix of size n x n, and pass both n and
x in as arguments. Still working out the recursive logic though...