Defining new semantics for expressions in Python

Question

I want to define constraint specification language based on Python. For example:

x = IntVar()
c = Constraint(x < 19)
c.solve()

Here IntVar is a class describing a variable that can assume any integer value, and Constraint is a class to represent constraints. To implement this I can just overload operator < by defining method __lt__ for class IntVar.

Suppose now that I want to state that 10 < x < 19. I would like to write something like:

c = Constraint(x > 10 and x < 19)

Unfortunately, I cannot do this because and cannot be overloaded in Python. Using & instead of and is not an option because of its precedence and because a bit-wise & has its proper meaning in the constraint language, e.g., (x & 0x4) == 1.

What solution could you suggest?

As a workaround I am using quoted expressions for constraints:

c = Constraint("x < 19")

But this requires implementing constraint language parsing that I would prefer to avoid, and, more importantly, the syntactical correctness may be checked only when the parsing is actually done. Thus the user may spend several hours to discover that there is a syntax error in a constraint definition.

Another option I considered is using kind of a lambda expression for constraint definition:

c = Constraint(lambda: x < 19)

but I cannot get access to the parse tree of the lambda-object.

Answer 1

Using &, | and ~ is actually a pretty good option. You simply need to document that parentheses are required because of the different operator precedence.

SQLAlchemy does it like this for example. For people who do not like this kind of abuse of the bitwise operators, it also provides and_(*args), or_(*args), and not_(arg) functions doing the same thing as their operator counterparts. However, you are forced to prefix notation (and_(foo, bar)) which is not as readable as infix notation (foo & bar).

---

The lambda approach is a good idea, too (besides the ugliness introduced by the lambda itself). Unfortunately the AST is indeed not available without source code - but wait, you do have the source code, just not attached to the function object!

Imagine this code:

import ast
import inspect

def evaluate(constraint):
    print ast.dump(ast.parse(inspect.getsource(constraint)))

evaluate(lambda x: x < 5 and x > -5)

That will give you this AST:

Module(
    body=[
        Expr(
            value=Call(
                func=Name(id='evaluate', ctx=Load()), args=[
                    Lambda(
                        args=arguments(
                            args=[
                                Name(id='x', ctx=Param())
                            ],
                            vararg=None,
                            kwarg=None,
                            defaults=[]
                        ),
                        body=BoolOp(
                            op=And(),
                            values=[
                                Compare(
                                    left=Name(id='x', ctx=Load()),
                                    ops=[Lt()],
                                    comparators=[Num(n=5)]
                                ),
                                Compare(
                                    left=Name(id='x', ctx=Load()),
                                    ops=[Gt()],
                                    comparators=[Num(n=-5)]
                                )
                            ]
                        )
                    )
                ],
                keywords=[],
                starargs=None,
                kwargs=None
            )
        )
    ]
)

The disadvantage is that you get the whole source line - but you can easily walk the AST until you reach your lambda expression (the first one inside the call to your evaluation function) and then you can work on just the relevant part.

To avoid having to evaluate it on your own, you can now simply rewrite the AST to use the bitwise operators instead and then compile the new AST to a function which will then make use of the overloadable operators.

Let's have a look at the AST of ((x < 5) & (x > -5)):

body=BinOp(
    left=Compare(
        left=Name(id='x', ctx=Load()),
        ops=[Lt()],
        comparators=[Num(n=5)]
    ),
    op=BitAnd(),
    right=Compare(
        left=Name(id='x', ctx=Load()),
        ops=[Gt()],
        comparators=[Num(n=-5)]
    )
)

As you can see, the difference is pretty minor. You just need to rewrite your AST's BoolOp to use a BinOp!

The AST of and_(x < 5, x > -5) would look like this:

body=Call(
    func=Name(id='and_', ctx=Load()),
    args=[
        Compare(
            left=Name(id='x', ctx=Load()),
            ops=[Lt()],
            comparators=[Num(n=5)]
        ),
        Compare(
            left=Name(id='x', ctx=Load()),
            ops=[Gt()],
            comparators=[Num(n=-5)]
        )
    ],
    keywords=[],
    starargs=None,
    kwargs=None
)

Also not too hard to rewrite to.