[Python-3000] AST access (WAS: Adaptation vs. Generic Functions)

Talin talin at acm.org
Mon Apr 10 11:44:12 CEST 2006


Greg Ewing <greg.ewing <at> canterbury.ac.nz> writes:

> I'm wondering whether there should be some kind of
> "code literal" syntax, where you write a Python
> expression and the compiler transforms it as far
> as the AST stage, then makes it available to the
> program as an AST object.
> 
> Or would that be too close to "programmable
> syntax" for Guido's liking?

I have a rather odd use case for this. A while back, I decided I wanted to
write an algebraic solver, similar to what Mathematica does, except that
I wanted to write it in Python. Not just implement it in Python, but have
Python be the language in which the rules of formula manipulation were
expressed.

The way that I approached this was to create something like the generic
function dispatch being discussed. Although my version wasn't nearly
as clean or well thought out as what other people here have done, it
had one unique feature, was that it did a full unification match on the
input arguments.

As an example, suppose you wanted to express the transformation:

   x * 0 => 0

In other words, when you see the expression "x * 0", replace it with
a constant zero.

That's a fairly trivial transformation, a more interesting one is the rules
for calculating derivatives. The general form of the derivative function
was:

   derivative( x, formula )

...which would produce the derivative of the formula with respect to
x. Some of the transformation rules were:

   derivative( x, x ) => 1
   derivative( x, constant( a ) ) => 0
   derivative( x, -n ) => -derivative( x, n )
   derivative( x, a + b ) => derivative( x, a ) + derivative( x, b )
   derivative( x, constant( a ) * b ) => a * derivative( x, b )
   derivative( x, a * b ) => a * derivative( x, b ) + b * derivative( x, a )
   derivative( x, a ** b ) => b * derivative( x, a ) ** (b - 1)

.. and so on. To express this in Python, I used a decorator function called
Arity which would invoke a general dispatcher that attempted to do a
recursive pattern match on the input arguments. Thus, the above rules
would be written in Python as follows:

   @Arity( MatchAny.x, MatchAny.x )
   def Derivative( x ):
       return 1
    
   @Arity( MatchAny.x, MatchAny.n )
   def Derivative( x, n ):
       return 0

   @Arity( MatchAny.x, (Negate, MatchAny.y) )
   def Derivative( x, y, z ):
       return (Negate, Derivative( x, y ))
    
   @Arity( MatchAny.x, (Add, MatchAny.y, MatchAny.z) )
   def Derivative( x, y, z ):
       return (Add, Derivative( x, y ), Derivative( x, z ) )
    
   @Arity( MatchAny.x, (Multiply, MatchNumber.y, MatchAny.z) )
   def Derivative( x, y, z ):
       return (Multiply, y, Derivative( x, z ))
    
   @Arity( MatchAny.x, (Multiply, MatchAny.y, MatchAny.z) )
   def Derivative( x, y, z ):
       return (Add, (Multiply, Derivative( x, y ), z),
                          (Multiply, y, Derivative( x, z )))
    
   @Arity( MatchAny.x, (Power, MatchAny.y, MatchNumber.z) )
   def Derivative( x, y, z ):
       return (Multiply, (Multiply, z, (Power, y, z - 1)), Derivative( x, y ))

Note that the input arguments to the actual Python functions are all
of the unbound variables in the arity. Essentially, each match would
produce a dictionary of bindings between the actual input arguments
and the unbound variables. The corresponding function body would
then be called by unpacking the dict. There were also special decorators
which would indicate that a function has associative or commutative
properties, which would alter the behavior of the dispatcher
appropriately.

You can immediately see the problem - since I don't have syntactical
support, I have to manually enter in the expression in an AST-like form,
which is clumsy to say the least.

Now, bear in mind that I'm not proposing that we modify the Python
language to support my obscure use case. Rather, I'm providing it as
an example for people to use in their discussion :) I think that the lesson
that I came away with is that if you're doing Algebra, you pretty much
have to bite the bullet and write your own parser.

Another interesting thing about the dispatcher, by the way, is that it
was implemented as a generator -- thus, if there was an ambiguous
match, it returned all of the possible matches in sequence. It attempted
to order the matches so that the most specific matches were returned
first (although my metric of specificity was rather loose.)

-- Talin




More information about the Python-3000 mailing list