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... -- http://mail.python.org/mailman/listinfo/python-list