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("'{0}' and '{1}' are equal."
...           .format(writer(lhs), writer(rhs)))
'i + j' and 'j + i' are equal.
static equal(exp1, exp2)[source]

Test if the two PSyIR expressions are symbolically equivalent.

Parameters

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

  • exp2 (Optional[psyclone.psyir.nodes.Node]) – the first 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 (py:class: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 (py:class:psyclone.psyir.nodes.Node) – the first expression to be compared.

  • exp2 (py:class:psyclone.psyir.nodes.Node) – the first 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("'{0}' equals '{1}'".format(writer(loop1.start_expr),
                                      writer(loop2.start_expr)))
if not sym_maths.equal(loop1.stop_expr, loop2.stop_expr):
    print("'{0}' does not equal '{1}'".format(writer(loop1.stop_expr),
                                              writer(loop2.stop_expr)))

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

Handling of PSyIR Structures and Arrays

SymPy has no concept of structure references or array syntax like a(i)%b in Fortran. But this case is not handled especially, the PSyIR is converted to Fortran syntax and is provided unmodified to SymPy. SymPy interprets the % symbol as modulo function, so the expression above is read as Mod(a(i), b). This interpretation achieves the expected outcome when comparing structures and array references. For example, a(i+2*j-1)%b(k-i) and a(j*2-1+i)%b(-i+k) will be considered to be equal:

  1. Converting the two expressions to SymPy internally results in Mod(a(i+2*j-1), b(k-i)) and Mod(a(j*2-1+i, b(-i+k)).

  2. Since nothing is known about the arguments of any of the Mod functions, SymPy will first detect that the same function is called in both expression, and then continue to compare the arguments of this function.

  3. The first arguments are a(i+2*j-1) and a(j*2-1+i). The name a is considered an unknown function. SymPy detects that both expressions appear to call the same function, and it will therefore compare the arguments.

  4. SymPy compares i+2*j-1 and j*2-1+i symbolically, and evaluate these expressions to be identical. Therefore, the two expressions a(...) are identical, so the first arguments of the Mod function are identical.

  5. Similarly, it will then continue to evaluate the second argument of the Mod function (b(...)), and evaluate them to be identical.

  6. Since all arguments of the Mod function are identical, SymPy will report these two functions to be the same, which is the expected outcome.

Converting PSyIR to Sympy - SymPyWriter

The method equal of the SymbolicMaths class expects two PSyIR nodes. It converts these expression first into strings before parsing them as SymPy expressions. The conversion is done with the SymPyWriter class. As described in the previous section, a member of a structure in Fortran becomes a stand alone symbol or function in sympy. The SymPy writer will rename members to better indicate that they are members: an expression like a%b%c will be written as a%a_b%a_b_c, which SymPy then parses as MOD(a, MOD(a_b, a_b_c)). This convention makes it easier to identify what the various expressions in SymPy are.

This handling of member variables can result in name clashes. Consider the expression a%b + a_b + b. The structure access will be using two symbols a and a_b - but now there are two different symbols with the same name. Note that the renaming of the member from b to a_b is not the reason for this - without renaming the same clash would happen with the symbol b.

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. The writer then renames all members and makes sure it uses a unique name. In the case of a%b + a_b + b, it would create a%a_b_1 + a_b + b, using the name a_b_1 for the member to avoid the name clash with the reference a_b - so an existing Symbol Reference will not be renamed, only members.

The SymPy writer mostly uses the Fortran writer, but implements the following, SymPy specific features:

  1. It will declare any array access as a SymPy unknown function, and any scalar access as a SymPy symbol. These declarations are stored in a dictionary, which can be queried. This dictionary is parsed into the SymPy writer to ensure the correct interpretation of any names found in the expression. Declaring arrays as functions results in the correct behaviour of SymPy: in case of an unknown function SymPy will compare all arguments, which are the array indices.

  2. It renames members as described above. So a structure reference like a%b (in Fortran syntax) will create two SymPy symbols: a and a_b (or a similar name if a name clash was detected).

  3. No precision or kind information is added to a constant (e.g. a Fortran value like 2_4 will be written just as 2).

  4. The intrinsic functions Max, Min, Mod are returned with a capitalised first letter. The Fortran writer would write them as MAX etc., which SymPy does not recognise and would then handle as unknown functions.

class psyclone.psyir.backend.sympy_writer.SymPyWriter(type_map=None)[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). 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

Parameters

type_map (dict of str:Sympy-data-type values) – Optional initial mapping that contains the SymPy data type of each reference in the expressions. This is the result of the static function psyclone.core.sympy_writer.create_type_map().

static convert_to_sympy_expressions(list_of_expressions)[source]

This function takes a list of PSyIR expressions, and converts them all into Sympy expressions using the SymPy parser. It takes care of all Fortran specific conversion required (e.g. constants with kind specification, …), including the renaming of member accesses, as described in https://psyclone-dev.readthedocs.io/en/latest/sympy.html#sympy

Parameters

list_of_expressions (list of psyclone.psyir.nodes.Node) – the list of expressions which are to be converted into SymPy-parsable strings.

Returns

the converted PSyIR expressions.

Return type

list of SymPy expressions

static create_type_map(list_of_expressions)[source]

This function creates a dictionary mapping each Reference in any of the expressions to either a Sympy Function (if the reference is an array reference) or a Symbol (if the reference is not an array reference).

Parameters

list_of_expressions (list of psyclone.psyir.nodes.Node) – the list of expressions from which all references are taken and added to the a symbol table to avoid renaming any symbols (so that only member names will be renamed).

Returns

the dictionary mapping each reference name to a Sympy data type (Function of Symbol).

Return type

dictionary of string:Sympy-data-type values

get_operator(operator)[source]

Determine the operator that is equivalent to the provided PSyIR operator. This implementation checks for certain functions that SymPy supports: Max, Min, Mod. These functions must be spelled with a capital first letter, otherwise SymPy will handle them as unknown functions. If none of these special operators are given, the base implementation is called (which will return the Fortran syntax).

Parameters

operator (psyclone.psyir.nodes.Operation.Operator) – a PSyIR operator.

Returns

the operator as string.

Return type

str

Raises

KeyError – if the supplied operator is not known.

static get_sympy_expressions_and_symbol_map(list_of_expressions)[source]

This function takes a list of PSyIR expressions, and converts them all into Sympy expressions using the SymPy parser. It takes care of all Fortran specific conversion required (e.g. constants with kind specification, …), including the renaming of member accesses, as described in https://psyclone-dev.readthedocs.io/en/latest/sympy.html#sympy It also returns the symbol map, i.e. the mapping of Fortran symbol names to SymPy Symbols.

Parameters

list_of_expressions (list of psyclone.psyir.nodes.Node) – the list of expressions which are to be converted into SymPy-parsable strings.

Returns

a 2-tuple consisting of the the converted PSyIR expressions, followed by a dictionary mapping the symbol names to SymPy Symbols.

Return type

Tuple[List[sympy.core.basic.Basic], Dict[str, sympy.core.symbol.Symbol]]

Raises

VisitorError – if an invalid SymPy expression is found.

is_intrinsic(operator)[source]

Determine whether the supplied operator is an intrinsic function (i.e. needs to be used as f(a,b)) or not (i.e. used as a + b). This tests for known SymPy names of these functions (e.g. Max), and otherwise calls the function in the base class.

Parameters

operator (str) – the supplied operator.

Returns

true if the supplied operator is an intrinsic and false otherwise.

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.

member_node(node)[source]

In SymPy an access to a member ‘b’ of a structure ‘a’ (i.e. a%b in Fortran) is handled as the ‘MOD’ function MOD(a, b). We must therefore make sure that a member access is unique (e.g. b could already be a scalar variable). This is done by creating a new name, which replaces the % with an _. So a%b becomes MOD(a, a_b). This makes it easier to see where the function names come from. Additionally, we still need to avoid a name clash, e.g. there could already be a variable a_b. This is done by using a symbol table, which was prefilled with all references (a in the example above) in the constructor. We use the string containing the ‘%’ as a unique tag and get a new, unique symbol from the symbol table based on the new name using _. For example, the access to member b in a(i)%b would result in a new symbol with tag a%b and a name like a_b, a_b_1, …

Parameters

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

Returns

the SymPy representation of this member access.

Return type

str

Note

The SymPyWriter class provides the static function convert_to_sympy_expressions which hides the complexities of the conversion from PSyIR expressions to SymPy expressions. It is strongly recommended to only use this function when this functionality is needed.