vc2_bit_widths.pyexp: Construct Python programs implementing arithmetic expressions

This module provides the PyExp class which tracks arithmetic operations performed on its instances. These objects may later be used to generate a Python function which implements these steps.

Motivation

When constructing test patterns it is often necessary to compute the output of a single filter output. Typically filters are described in terms of lifting steps which compute the filter output for an entire picture at once, even when only a single pixel or intermediate value is required. Using PyExp, it is possible to automatically extract a function which implements just the computations required to produce a single filter output. In this way, individual filter outputs may be efficiently computed in isolation.

Getting started

The pyexp module provides a series of subclasses of the abstract PyExp base class. Together these subclasses may be used to define Python expressions which may be compiled into a function.

For example, using Constant we can define a pair of constants and add them together:

>>> from vc2_bit_widths.pyexp import Constant

>>> five = Constant(5)
>>> nine = Constant(9)
>>> five_add_nine = five + nine

>>> print(five_add_nine)
BinaryOperator(Constant(5), Constant(9), '+')

Rather than immediately computing a result, adding the Constants together produced a new PyExp (of type BinaryOperator) representing the computation to be carried out. Using the make_function() method, we can create a Python function which actually evaluates the expression:

>>> compute_five_add_nine = five_add_nine.make_function()
>>> compute_five_add_nine()
14

The generate_code() method may be used to inspect the generated code. Here we can see that the generated function does actually perform the computation on demand:

>>> print(five_add_nine.generate_code())
def f():
    return (5 + 9)

To build more interesting functions we can define Arguments. The names passed to the Argument constructor become the argument names in the generated function:

>>> from vc2_bit_widths.pyexp import Argument

>>> a = Argument("a")
>>> b = Argument("b")
>>> average_expr = (a + b) / Constant(2.0)
>>> average = average_expr.make_function()

>>> average(a=10, b=15)
12.5

PyExp instances support many Python operators and will automatically wrap non-PyExp values in Constant. For example:

>>> array = Argument("array")
>>> average_of_first_and_last_expr = (array[0] + array[-1]) / 2.0
>>> average_of_first_and_last = average_of_first_and_last_expr.make_function()

>>> average_of_first_and_last([3, 4, 5, 6])
4.5

Carving functions out of existing code

Because PyExp objects support the usual Python operators they can be passed as arguments to existing code. For example, consider the following function designed to operate on arrays of numbers:

>>> def multiply_by_place(array):
...     return [value * i for i, value in enumerate(array)]

>>> # Demo
>>> multiply_by_place([4, 3, 5, 11])
[0, 3, 10, 33]

Now, instead of passing in an array of numbers, lets pass in an array of PyExp values:

>>> values = Argument("values")
>>> out = multiply_by_place([values[i] for i in range(4)])

>>> from pprint import pprint
>>> pprint(out)
[Constant(0),
 Subscript(Argument('values'), Constant(1)),
 BinaryOperator(Subscript(Argument('values'), Constant(2)), Constant(2), '*'),
 BinaryOperator(Subscript(Argument('values'), Constant(3)), Constant(3), '*')]

Our function now returns a list of PyExp values. Using these we can generate functions which just compute one of the output values of multiply_by_place in isolation:

>>> compute_third_output = out[2].make_function()
>>> compute_third_output([4, 3, 5, 11])
10

We can verify that the generated function is genuinely computing only the required value (and not just computing everything and throwing most of it away) by inspecting its source code:

>>> print(out[2].generate_code())
def f(values):
    return (values[2] * 2)

Manipulating expressions

PyExp supports simple manipulation of expressions in the form of the subs() method which substitutes subexpressions within an expression. For example:

>>> a = Argument("a")
>>> b = Argument("b")
>>> c = Argument("c")

>>> exp = a["deeply"]["nested"]["subscript"] + b
BinaryOperator(Subscript(Subscript(Subscript(Argument('a'), Constant('deeply')), Constant('nested')), Constant('subscript')), Argument('b'), '+')

>>> exp2 = exp.subs({a["deeply"]["nested"]["subscript"]: c})
>>> print(exp2)
BinaryOperator(Argument('c'), Argument("b"), "+")

This functionality is intended to allow simple optimisations such as constant folding (substituting constants in place of variables) and replacing subscripted values with Arguments to reduce overheads.

API

class PyExp

Abstract Base class for Python Expression objects.

class Constant(value)

A constant value.

Parameters
valueany

Must be serialised to a valid Python expression by repr()

property value

The value of this constant.

class Argument(name)

An named argument which will be expected by the Python function implementing this expression.

Parameters
namestr

A valid Python argument name

property name

The name of this argument.

class Subscript(exp, key)

Subscript an expression, i.e. exp[key].

Parameters
expPyExp

The value to be subscripted.

keyPyExp

The key to access.

property exp

The expression being subscripted.

property key

The subscript key.

class BinaryOperator(lhs, rhs, operator)

A binary operation applied to two PyExps, e.g. addition.

Parameters
lhsPyExp
rhsPyExp

The arguments to the operator.

operatorstr

The python operator symbol to apply (e.g. “+”).

property lhs

The expression on the left-hand side of the operator.

property rhs

The expression on the right-hand side of the operator.

property operator

The operator, as a string.