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...

 

[Paul Rubin]

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

Was the comment a typo for Factorial?

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

Overriding old definition of Factorial

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

Overriding it again

print Factorial( 12 )

I'm confused, how did it know what to do? Are you using some reflection
hack in the MatchInteger decorator to figure out the function name?

 

[talin at acm dot org]

Yes, it was a typo.

Even thought the function has not yet been bound to the name
"Factorial" when it calls the decorator, the function's __name__
attribute is set to it, so I use that to look up the name of the
generic.

Here''s the source for Arity:

def Arity( *pattern ):
"""A function decorator that defines a specific arity of a generic
function. This registers the
specific implementation with the generic function (which must be in
the global scope.)"""

def inner( f ):
if isinstance( f, Function ):
generic = f
f = generic.last_defined
else:
name = f.__name__
if not name in f.func_globals:
raise Exception( "Generic function " + name + " has not
been defined." )
generic = f.func_globals[ name ]
generic.name = name
generic.last_defined = f
generic.add_arity( pattern, f )
return generic
return inner

There's a couple of kludges here:

1) The Generic doesn't know its own name until you define at least one
specialization for it. Otherwise, you would have to say:

Factorial = Function( "Factorial" )

which I consider verbose and redundant.

2) The whole last_defined thing is to allow multiple arities for a
single specialized function. Since the arity normally returns the
generic, and not the specialized func, as the return value, that means
that any additional decorators will be applied to the generic rather
than the specialized func. last_defined is a kludge for getting around
that, but only for decorators that understand the situation.

 

[Talin]

Well, the Matrix matching function now works as described above:

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

Now I am trying to see if I can write the rules for Derviative()...