Rewriter

Patterns

FPy provides a pattern-based rewriter for transforming FPy programs. Patterns are specified using the @fpy2.pattern decorator

fpy2.pattern(func: Callable[[P], R])

Decorator to parse a Python function into an FPy pattern. Constructs an FPy Pattern from a Python function. FPy is a stricter subset of Python, so this decorator will reject any function that is not valid in FPy.

class fpy2.rewrite.Pattern

Bases: ABC

Abstract base class for FPy IR patterns.

abstractmethod format() → str

Returns a string representation of the pattern.

abstractmethod vars() → set[NamedId]

Returns the set of pattern variables.

class fpy2.rewrite.ExprPattern(func: FuncDef)

Bases: Pattern

Expression pattern

expr: Expr

expression of the underlying pattern

format() → str

Returns a string representation of the pattern.

vars() → set[NamedId]

Returns the set of pattern variables.

class fpy2.rewrite.StmtPattern(func: FuncDef)

Bases: Pattern

Statement pattern

block: StmtBlock

syntax of the underlying pattern

format() → str

Returns a string representation of the pattern.

vars() → set[NamedId]

Returns the set of pattern variables.

Matcher

Given a fpy2.Pattern instance, the fpy2.rewrite.Matcher class the locations within an FPy program where the pattern matches.

class fpy2.rewrite.Matcher(pattern: Pattern)

Bases: object

FPy pattern matcher.

Matches each instance of self.pattern for a program and returns the list of subsitutions for each match.

match(func: Function) → list[ExprMatch] | list[StmtMatch]

Pattern matches recursively over the function. For each match, returns the substitution (and its location).

match_exact(e: StmtBlock | Expr) → ExprMatch | StmtMatch | None

Pattern matches exactly over the function. Returns the substitution or None if no match is found.

class fpy2.rewrite.LocatedMatch(pattern: Pattern, subst: Subst)

Bases: object

Result of a pattern match.

class fpy2.rewrite.ExprMatch(pattern: Pattern, subst: Subst, expr: Expr)

Bases: LocatedMatch

Result of pattern matching on an expression.

class fpy2.rewrite.StmtMatch(pattern: Pattern, subst: Subst, block: StmtBlock, idx: int)

Bases: LocatedMatch

Result of a pattern match: a location and a substitution.

class fpy2.rewrite.Subst

Bases: object

Mapping between pattern variable and IR instances.

env: dict[NamedId, Expr]

mapping from pattern variable to expressions

vars()

Returns the domain of the substitution.

Applier

Given a fpy2.Pattern instance, the fpy2.rewrite.Applier class applies a substitution, a mapping from pattern variable to syntax, to produce a new FPy program.

class fpy2.rewrite.Applier(pattern: Pattern)

Bases: object

FPy subsitution applier.

Takes a pattern and a substitution and applies the substitution to produce a program (or program fragment).

apply(pmatch: LocatedMatch)

Applies the substitution to the pattern. The result is always a valid IR fragment (including locally SSA).

Rewrite

The fpy2.rewrite.Rewrite class combines the matcher and applier to perform a rewrite replacing l with r where the substitution produced by matches of l are applied to r.

class fpy2.rewrite.Rewrite(lhs: Pattern, rhs: Pattern, *, name: str | None = None)

Bases: object

A rewrite rule from L to R.

apply(func: Function, *, occurence: int = 0, repeat: int = 1)

Applies the rewrite rule to the given pattern.

Optionally specify: - occurence: which match occurence, in traversal order, to rewrite - repeat: how many times to apply the rewrite rule once a match occurs

Raises ValueError if the rewrite rule does not apply.

apply_all(func: Function)

Applies the rewrite rule to all matching patterns in the given function.

Raises ValueError if the rewrite rule does not apply.

lhs: Pattern

the matching side of the rewrite rules

name: str | None

the name of the rewrite rule

rhs: Pattern

the substitution side of the rewrite rule