SymPy

PSyclone uses the symbolic maths package “SymPy” for comparing expressions symbolically, e.g. a comparison like i+j > i+j-1 will be evaluated to be true.

The SymPy package is wrapped in the PSyclone class SymbolicMaths:

class psyclone.core.SymbolicMaths[source]

A wrapper around the symbolic maths package ‘sympy’. It provides convenience functions for PSyclone. It has a Singleton access, e.g.:

>>> from psyclone.psyir.backend.fortran import FortranWriter
>>> from psyclone.core import SymbolicMaths
>>> sympy = SymbolicMaths.get()
>>> # Assume lhs is the PSyIR of 'i+j', and rhs is 'j+i'
>>> if sympy.equal(lhs, rhs):
...     writer = FortranWriter()
...     print(f"'{writer(lhs)}' and '{writer(rhs)}' are equal.")
'i + j' and 'j + i' are equal.
static equal(exp1, exp2)[source]

Test if the two PSyIR expressions are symbolically equivalent.

Parameters:

  • exp1 (psyclone.psyir.nodes.Node) – the first expression to be compared.

  • exp2 (psyclone.psyir.nodes.Node) – the second expression to be compared.

Returns:

whether the two expressions are mathematically identical.

Return type:

bool

static expand(expr)[source]

Expand a PSyIR expression. This is done by converting the PSyIR expression to a sympy expression, applying the expansion operation and then converting the resultant output back into PSyIR.

Currently does not work if the PSyIR expression contains Range nodes, see issue #1655.

Parameters:

expr (psyclone.psyir.nodes.Node) – the expression to be expanded.

static get()[source]

Static function that creates (if necessary) and returns the singleton SymbolicMaths instance.

Returns:

the instance of the symbolic maths class.

Return type:

psyclone.core.SymbolicMaths

static never_equal(exp1, exp2)[source]

Returns if the given SymPy expressions are guaranteed to be different regardless of the values of symbolic variables. E.g. n-1 and n are always different, but 5 and n are not always different.

Parameters:

  • exp1 (psyclone.psyir.nodes.Node) – the first expression to be compared.

  • exp2 (psyclone.psyir.nodes.Node) – the second expression to be compared.

Returns:

whether or not the expressions are never equal.

Return type:

bool

static solve_equal_for(exp1, exp2, symbol)[source]

Returns all solutions of exp1==exp2, solved for the specified symbol. It restricts the solution domain to integer values. If there is an infinite number of solutions, it returns the string ‘independent’, indicating that the solution of exp1==exp2 does not depend on the specified symbol. This is done to avoid that the SymPy instance representing an infinite set is used elsewhere in PSyclone (i.e. creating a dependency in other modules to SymPy). Otherwise a standard Python set is returned that stores the solutions.

Parameters:

  • exp1 (sympy.core.basic.Basic) – the first expression.

  • exp2 (sympy.core.basic.Basic) – the second expression.

  • symbol (sympy.core.symbol.Symbol) – the symbol for which to solve.

Returns:

a set of solutions, or the string “independent”.

Return type:

Union[set, str]

This can be used for tests of nodes in the PSyIR. For example, the NEMO loop fuse transformation checks that the loops to be fused have the same loop boundaries using code like this:

from psyclone.core import SymbolicMaths
from psyclone.psyir.backend.fortran import FortranWriter

# Assume loop1 is ``do i=1, k`` and loop2 ``do i=5+k-4-k, 2*k-k-1``.

writer = FortranWriter()
sym_maths = SymbolicMaths.get()
if sym_maths.equal(loop1.start_expr, loop2.start_expr):
    print(f"'{writer(loop1.start_expr)}' equals "
          f"'{writer(loop2.start_expr)}'")
if not sym_maths.equal(loop1.stop_expr, loop2.stop_expr):
    print(f"'{writer(loop1.stop_expr)}' does not equal "
          f"'{ writer(loop2.stop_expr)}'")

'1' equals '5 + k - 4 - k'
'k' does not equal '2 * k - k - 1'

SymPyWriter - Converting PSyIR to SymPy

The methods of the SymbolicMaths class expect to be passed PSyIR nodes. They convert these expressions first into strings before parsing them as SymPy expressions. The conversion is done with the SymPyWriter class, and it is the task of the SymPyWriter to convert the PSyIR into a form that can be understood by SymPy. Several Fortran constructs need to be converted in order to work with SymPy. The SymPy writer mostly uses the Fortran writer for creating a string for the PSyIR, but implements the following features to allow the parsing of the expressions by SymPy:

Array Accesses

Any array access is declared as a SymPy unknown function and any scalar access as a SymPy symbol. These declarations are stored in a dictionary, which is used by the parser of SymPy to ensure the correct interpretation of any names found in the expression. Note that while SymPy has the concept of Indexed expressions, they do not work well when solving equations that requires the comparison of indices (which is frequently needed for the dependency analysis). For example, M[x] - M[1] == 0 does not result in the solution x=1 when M is an indexed SymPy type. Using an unknown function on the other hand handles this as expected.

Array Expressions

Each array index will be converted into three arguments for the corresponding unknown SymPy function that represents the array access. For example, an array expression a(i:j:k) will become a(i, j, k), and to then maintain the same number of arguments for each use of an array/function, a(i) will become a(i,i,1), and b(i,j) becomes b(i,i,1,j,j,1) etc. Array expressions like a(:) will be using specific names for the lower and upper bound, defaulting to sympy_lower and sympy_upper. So the previous expression becomes a(sympy_lower, sympy_upper, 1). Note that in case of a name clash SymPyWriter will change the names of the boundaries to be unique.

Fortran-specific Syntax

No precision or kind information is added to a constant (e.g. a Fortran value like 2_4 will be written just as 2). The intrinsic functions Max, Min, Mod are capitalised to be recognised by SymPy which is case sensitive.

User-defined Types

SymPy has no concept of user-defined types like a(i)%b in Fortran. A structure reference like this is converted to a single new symbol (scalar) or function (if an array index is involved). The default name will be the name of the reference and members concatenated using _, e.g. a%b%c becomes a_b_c, which will be declared as a new SymPy symbol or function (if it is an array access). The SymPy writer uses a symbol table to make sure it creates unique symbols. It first adds all References in the expression to the symbol table, which guarantees that no Reference to an existing symbol is renamed. In the case of a%b + a_b + b, it would create a_b_1 + a_b + b, using the name a_b_1 for the structure reference to avoid the name clash with the reference a_b.

Any array indices are converted into arguments of this new function. So an expression like a(i)%b%c(j,k) becomes a_b_c(i,i,1,j,j,1,k,k,1) (see Array Expressions). The SymPyWriter creates a custom SymPy function, which keeps a list of which reference/member contained how many indices. In the example this would be [1, 0, 2], indicating that the first reference had one index, the second one none (i.e. it is not an array access), and the last reference had two indices. This allows the function to properly re-create the Fortran string.

Documentation for SymPyWriter Functions

The SymPyWriter provides the following functions:

class psyclone.psyir.backend.sympy_writer.SymPyWriter(*expressions)[source]

Implements a PSyIR-to-SymPy writer, which is used to create a representation of the PSyIR tree that can be understood by SymPy. Most Fortran expressions work as expected without modification. This class implements special handling for constants (which can have a precision attached, e.g. 2_4) and some intrinsic functions (e.g. MAX, which SymPy expects to be Max). Array accesses are converted into functions (while SymPy supports indexed expression, they cannot be used as expected when solving, SymPy does not solve component-wise - M[x]-M[1] would not result in x=1, while it does for SymPy unknown functions). Array expressions are supported by the writer: it will convert any array expression like a(i:j:k) by using three arguments: a(i, j, k). Then simple array accesses like b(i,j) are converted to b(i,i,1,j,j,1). Similarly, if a is known to be an array, then the writer will use a(sympy_lower,sympy_upper,1). This makes sure all SymPy unknown functions that represent an array use the same number of arguments.

The simple use case of converting a (list of) PSyIR expressions to SymPy expressions is as follows:

symp_expr_list = SymPyWriter(exp1, exp2, ...)

If additional functionality is required (access to the type map or to convert a potentially modified SymPy expression back to PSyIR), an instance of SymPy writer must be created:

writer = SymPyWriter()
symp_expr_list = writer([exp1, exp2, ...])

It additionally supports accesses to structure types. A full description can be found in the manual: https://psyclone-dev.readthedocs.io/en/latest/sympy.html#sympy

static __new__(cls, *expressions)[source]

This function allows the SymPy writer to be used in two different ways: if only the SymPy expression of the PSyIR expressions are required, it can be called as:

sympy_expressions = SymPyWriter(exp1, exp2, ...)

But if additional information is needed (e.g. the SymPy type map, or to convert a SymPy expression back to PSyIR), an instance of the SymPyWriter must be kept, e.g.:

writer = SymPyWriter()
sympy_expressions = writer([exp1, exp2, ...])
writer.type_map
Parameters:

expressions (Tuple[psyclone.psyir.nodes.Node]) – a (potentially empty) tuple of PSyIR nodes to be converted to SymPy expressions.

Returns:

either an instance of SymPyWriter, if no parameter is specified, or a list of SymPy expressions.

Return type:

Union[psyclone.psyir.backend.SymPyWriter, List[sympy.core.basic.Basic]]

arrayofstructuresreference_node(node)[source]

This handles ArrayOfStructureReferences (and also simple StructureReferences). An access like a(i)%b(j) is converted to the string a_b(i,i,1,j,j,1) (also handling name clashes in case that the user code already contains a symbol a_b). The SymPy function created for this new symbol will store the original signature and the number of indices for each member (so in the example above that would be Signature("a%b") and (1,1). This information is sufficient to convert the SymPy symbol back to the correct Fortran representation

Parameters:

node (psyclone.psyir.nodes.StructureReference) – a StructureReference PSyIR node.

Returns:

the code as string.

Return type:

str

arrayreference_node(node)[source]

The implementation of the method handling a ArrayOfStructureReference is generic enough to also handle non-structure arrays. So just use it.

Parameters:

node (psyclone.psyir.nodes.ArrayReference) – a ArrayReference PSyIR node.

Returns:

the code as string.

Return type:

str

gen_indices(indices, var_name=None)[source]

Given a list of PSyIR nodes representing the dimensions of an array, return a list of strings representing those array dimensions. This is used both for array references and array declarations. Note that ‘indices’ can also be a shape in case of Fortran. The implementation here overwrites the one in the base class to convert each array index into three parameters to support array expressions.

Parameters:

  • indices (List[psyclone.psyir.symbols.Node]) – list of PSyIR nodes.

  • var_name (str) – name of the variable for which the dimensions are created. Not used in this implementation.

Returns:

the Fortran representation of the dimensions.

Return type:

List[str]

Raises:

NotImplementedError – if the format of the dimension is not supported.

intrinsiccall_node(node)[source]

This method is called when an IntrinsicCall instance is found in the PSyIR tree. The Sympy backend will use the exact sympy name for some math intrinsics (listed in _intrinsic_to_str) and will remove named arguments.

Parameters:

node (psyclone.psyir.nodes.IntrinsicCall) – an IntrinsicCall PSyIR node.

Returns:

the SymPy representation for the Intrinsic.

Return type:

str

literal_node(node)[source]

This method is called when a Literal instance is found in the PSyIR tree. For SymPy we need to handle booleans (which are expected to be capitalised: True). Real values work by just ignoring any precision information (e.g. 2_4, 3.1_wp). Character constants are not supported and will raise an exception.

Parameters:

node (psyclone.psyir.nodes.Literal) – a Literal PSyIR node.

Returns:

the SymPy representation for the literal.

Return type:

str

Raises:

TypeError – if a character constant is found, which is not supported with SymPy.

property lower_bound
Returns:

the name to be used for an unspecified lower bound.

Return type:

str

range_node(node)[source]

This method is called when a Range instance is found in the PSyIR tree. This implementation converts a range into three parameters for the corresponding SymPy function.

Parameters:

node (psyclone.psyir.nodes.Range) – a Range PSyIR node.

Returns:

the Fortran code as a string.

Return type:

str

reference_node(node)[source]

This method is called when a Reference instance is found in the PSyIR tree. It handles the case that this normal reference might be an array expression, which in the SymPy writer needs to have indices added explicitly: it basically converts the array expression a to a(sympy_lower, sympy_upper, 1).

Parameters:

node (psyclone.psyir.nodes.Reference) – a Reference PSyIR node.

Returns:

the text representation of this reference.

Return type:

str

structurereference_node(node)[source]

The implementation of the method handling a ArrayOfStructureReference is generic enough to also handle non-arrays. So just use it.

Parameters:

node (psyclone.psyir.nodes.StructureReference) – a StructureReference PSyIR node.

Returns:

the code as string.

Return type:

str

property type_map
Returns:

the mapping of names to SymPy symbols or functions.

Return type:

Dict[str, Union[sympy.core.symbol.Symbol, sympy.core.function.Function]]

property upper_bound
Returns:

the name to be used for an unspecified upper bound.

Return type:

str

SymPyReader - Converting SymPy to PSyIr

The SymPyReader converts a SymPy expression back to PSyIR. Together with the SymPyWriter it allows to take a PSyIR expression, manipulate it with SymPy, and creating a new PSyIR that can be used. The SymPyReader is closely connected to the SymPyWriter: as explained in Array Expressions the SymPyWriter creates special symbols to indicate the lower- and upper-bound of an array expression. In order to convert these arguments back to the corresponding Fortran representation, the SymPyReader needs to know the actual names (which might have been changed from their default because of a name clash with a user variable). The SymPyReader constructor therefore takes a SymPyWriter as argument, and it is the responsibility of the user to make sure the provided SymPyWriter instance is indeed the one used to create the SymPy expressions in the first place.

An example of converting an expression expr from PSyIR to SymPy and back:

from sympy import expand
from psyclone.psyir.backend.fortran import FortranWriter
from psyclone.psyir.backend.sympy_writer import SymPyWriter
from psyclone.psyir.frontend.sympy_reader import SymPyReader

sympy_writer = SymPyWriter()
sympy_expr = sympy_writer(expr)

# Use SymPy to modify the expression ...
new_expr = expand(sympy_expr)

# Find the required symbol table in the original PSyIR
symbol_table = expr.scope.symbol_table

sympy_reader = SymPyReader(sympy_writer)
# Convert the new sympy expression to PSyIR
new_psyir_expr = sympy_reader.psyir_from_expression(new_expr, symbol_table)

writer = FortranWriter()
print(f"{writer(expr)} = {writer(new_psyir_expr)}")

(j + 1) * k = j * k + k

Documentation for SymPyReader Functions

The SymPyReader provides the following functions:

class psyclone.psyir.frontend.sympy_reader.SymPyReader(sympy_writer)[source]

This class converts a SymPy expression, that was created by the SymPyWriter, back to PSyIR. It basically allows to use SymPy to modify PSyIR expressions:

  1. The SymPyWriter converts the Fortran expression to SymPy

  2. SymPy is used to manipulate these mathematical expressions

  3. The SymPyReader is used to convert these SymPy expressions back into PSyIR (from which source code can be recreated)

Most SymPy expressions can be parsed as Fortran expression immediately, but the big exception to this are Fortran Arrays which must be able to support array expressions like a(1:5:2). As outlined in the SymPyWriter, each array is represented as an UndefinedFunction in SymPy, and each each dimension of the Fortran array will provide three arguments to this function: the start, stop, and step value. So the expression above will be converted to a(1,5,2), and a(7) will be represented as a(7:7:1). If the start- or stop-expression is not specified, e.g. a(:), the SymPy writer will use two special symbols sympy_lower and sympy_upper, e.g. the above expression will become a(sympy_lower:sympy_upper:1). The SymPyWriter will change the name if required in case of a name clash (i.e. if the user declared a variable called sympy_lower etc).

The task of the SymPy reader is to convert these expressions back to the original PSyIR representation. For example, the SymPy expressions a(i,j,k) will be written as a(i:j:k). This conversion is done by the function print_fortran_array by combining each 3-tuple of arguments back to the corresponding Fortran representation.

The SymPyWriter sets the _sympystr attribute of the SymPy UndefinedFunction it creates to print_fortran_array. The _sympystr method is automatically called by SymPy when converting an expression into a string.

In order to achieve this, the SymPyReader must know the names used for the lower- and upper-bounds. The constructor takes a SymPyWriter as argument in order to get the name of these bounds. It is important that the SymPyWriter provided here is the one that was used to create the SymPy expressions in the first place.

Parameters:

sympy_writer (psyclone.psyir.backend.SymPyWriter) – the SymPyWriter that was used to create the SymPy expressions.

print_fortran_array(printer)[source]

A custom print function to convert a modified Fortran array access back to standard Fortran. This function is set as _sympystr_ method of the SymPy functions created in the SymPyWriter (see _create_type_map method of the SymPyWriter), so it will be called by SymPy to convert this function to a string, with the function to convert being the first argument! This function converts the three values that each index is converted to back into the Fortran array notation. It uses the class variables SymPyReader._lower_bound and SymPyReader._upper_bound as the names that were used when the SymPy expressions were created in order to convert array expressions correctly back.

Parameters:

  • function (sympy.core.function.Function) – this function is called from a SymPy Function class, therefore the first argument is a SymPy Function instance (and NOT a SymPyReader) instance.

  • printer (sympy.printing.str.StrPrinter) – the SymPy writer base class.

Returns:

the string representation of this array access.

Return type:

str

psyir_from_expression(sympy_expr, symbol_table)[source]

This function converts a SymPy expression back into PSyIR. It converts the SymPy expression into a string, which is then parsed by the FortranReader. It relies on the print_fortran_array function to convert the function arguments back to Fortran array expressions. This function will be called by SymPy when converting the functions that represent array indices into a string, see psyclone.psyir.backend.SymPyWriter._create_type_map, where this function is defined to be called for string conversion.

Parameters:

  • sympy_expr (sympy.core.basic.Basic) – the original SymPy expression.

  • symbol_table (psyclone.psyir.symbols.SymbolTable) – the symbol table required for parsing, it should be the table from which the original SymPy expression was created from (i.e. contain all the required symbols in the SymPy expression).

Returns:

the PSyIR representation of the SymPy expression.

Return type:

psyclone.psyir.nodes.Node