# User-Defined Functions

## User Functions

Finch supports arbitrary Julia Base functions over `isbits`

types. You can also use your own functions and use them in Finch! Just remember to define any special algebraic properties of your functions so that Finch can optimize them better. You must declare the properties of your functions before you call any Finch functions on them.

Finch only supports incrementing assignments to arrays such as `+=`

or `*=`

. If you would like to increment `A[i...]`

by the value of `ex`

with a custom reduction operator `op`

, you may use the following syntax: `A[i...] <<op>>= ex`

.

Consider the greatest common divisor function `gcd`

. This function is associative and commutative, and the greatest common divisor of 1 and anything else is 1, so 1 is an annihilator. We declare these properties by overloading trait functions on Finch's default algebra as follows:

```
Finch.isassociative(::Finch.DefaultAlgebra, ::typeof(gcd)) = true
Finch.iscommutative(::Finch.DefaultAlgebra, ::typeof(gcd)) = true
Finch.isannihilator(::Finch.DefaultAlgebra, ::typeof(gcd), x) = x == 1
```

Then, the following code will only call gcd when neither `u[i]`

nor `v[i]`

are 1 (just once!).

```
u = Tensor(SparseList(Element(1)), [3, 1, 6, 1, 9, 1, 4, 1, 8, 1])
v = Tensor(SparseList(Element(1)), [1, 2, 3, 1, 1, 1, 1, 4, 1, 1])
w = Tensor(SparseList(Element(1)))
@finch MyAlgebra() (w .= 1; for i=_; w[i] = gcd(u[i], v[i]) end)
```

## A Few Convenient Functions

For your convenience, Finch defines a few useful functions that help express common array operations inside Finch:

`Finch.choose`

— Function`choose(z)(a, b)`

`choose(z)`

is a function which returns whichever of `a`

or `b`

is not isequal to `z`

. If neither are `z`

, then return `a`

. Useful for getting the first nonfill value in a sparse array.

```
julia> a = Tensor(SparseList(Element(0.0)), [0, 1.1, 0, 4.4, 0])
5-Tensor
└─ SparseList (0.0) [1:5]
├─ [2]: 1.1
└─ [4]: 4.4
julia> x = Scalar(0.0); @finch for i=_; x[] <<choose(1.1)>>= a[i] end;
julia> x[]
0.0
```

`Finch.minby`

— Function`minby(a, b)`

Return the min of `a`

or `b`

, comparing them by `a[1]`

and `b[1]`

, and breaking ties to the left. Useful for implementing argmin operations:

```
julia> a = [7.7, 3.3, 9.9, 3.3, 9.9]; x = Scalar(Inf => 0);
julia> @finch for i=_; x[] <<minby>>= a[i] => i end;
julia> x[]
3.3 => 2
```

`Finch.maxby`

— Function`maxby(a, b)`

Return the max of `a`

or `b`

, comparing them by `a[1]`

and `b[1]`

, and breaking ties to the left. Useful for implementing argmax operations:

```
julia> a = [7.7, 3.3, 9.9, 3.3, 9.9]; x = Scalar(-Inf => 0);
julia> @finch for i=_; x[] <<maxby>>= a[i] => i end;
julia> x[]
9.9 => 3
```

## Properties

The full list of properties recognized by Finch is as follows (use these to declare the properties of your own functions):

`Finch.isassociative`

— Function`isassociative(algebra, f)`

Return true when `f(a..., f(b...), c...) = f(a..., b..., c...)`

in `algebra`

.

`Finch.iscommutative`

— Function`iscommutative(algebra, f)`

Return true when for all permutations p, `f(a...) = f(a[p]...)`

in `algebra`

.

`Finch.isdistributive`

— Function`isdistributive(algebra, f, g)`

Return true when `f(a, g(b, c)) = g(f(a, b), f(a, c))`

in `algebra`

.

`Finch.isidempotent`

— Function`isidempotent(algebra, f)`

Return true when `f(a, b) = f(f(a, b), b)`

in `algebra`

.

`Finch.isidentity`

— Function`isidentity(algebra, f, x)`

Return true when `f(a..., x, b...) = f(a..., b...)`

in `algebra`

.

`Finch.isannihilator`

— Function`isannihilator(algebra, f, x)`

Return true when `f(a..., x, b...) = x`

in `algebra`

.

`Finch.isinverse`

— Function`isinverse(algebra, f, g)`

Return true when `f(a, g(a))`

is the identity under `f`

in `algebra`

.

`Finch.isinvolution`

— Function`isinvolution(algebra, f)`

Return true when `f(f(a)) = a`

in `algebra`

.

`Finch.return_type`

— Function`return_type(algebra, f, arg_types...)`

Give the return type of `f`

when applied to arguments of types `arg_types...`

in `algebra`

. Used to determine output types of functions in the high-level interface. This function falls back to `Base.promote_op`

.

## Finch Kernel Caching

Finch code is cached when you first run it. Thus, if you run a Finch function once, then make changes to the Finch compiler (like defining new properties), the cached code will be used and the changes will not be reflected.

It's best to design your code so that modifications to the Finch compiler occur before any Finch functions are called. However, if you really need to modify a precompiled Finch kernel, you can call `Finch.refresh()`

to invalidate the code cache.

`Finch.refresh`

— Function`Finch.refresh()`

Finch caches the code for kernels as soon as they are run. If you modify the Finch compiler after running a kernel, you'll need to invalidate the Finch caches to reflect these changes by calling `Finch.refresh()`

. This function should only be called at global scope, and never during precompilation.

### (Advanced) On World-Age and Generated Functions

Julia uses a "world age" to describe the set of defined functions at a point in time. Generated functions run in the same world age in which they were defined, so they can't call functions defined after the generated function. This means that if Finch used normal generated functions, users can't define their own functions without first redefining all of Finch's generated functions.

Finch uses special generators that run in the current world age, but do not update with subsequent compiler function invalidations. If two packages modify the behavior of Finch in different ways, and call those Finch functions during precompilation, the resulting behavior is undefined.

There are several packages that take similar, but different, approaches to allow user participation in staged Julia programming (not to mention Base `eval`

or `@generated`

): StagedFunctions.jl, GeneralizedGenerated.jl, RuntimeGeneratedFunctions.jl, or Zygote.jl.

Our approach is most similar to that of StagedFunctions.jl or Zygote.jl. We chose our approach to be the simple and flexible while keeping the kernel call overhead low.

## (Advanced) Separate Algebras

If you want to define non-standard properties or custom rewrite rules for some functions in a separate context, you can represent these changes with your own algebra type. We express this by subtyping `AbstractAlgebra`

and defining properties as follows:

```
struct MyAlgebra <: AbstractAlgebra end
Finch.isassociative(::MyAlgebra, ::typeof(gcd)) = true
Finch.iscommutative(::MyAlgebra, ::typeof(gcd)) = true
Finch.isannihilator(::MyAlgebra, ::typeof(gcd), x) = x == 1
```

We pass the algebra to Finch as an optional first argument:

`@finch MyAlgebra() (w .= 1; for i=_; w[i] = gcd(u[i], v[i]) end; return w)`

### Rewriting

Define custom rewrite rules by overloading the `get_simplify_rules`

function on your algebra. Unless you want to write the full rule set from scratch, be sure to append your new rules to the old rules, which can be obtained by calling `get_simplify_rules`

with another algebra. Rules can be specified directly on Finch IR using RewriteTools.jl.

`Finch.get_simplify_rules`

— Function`get_simplify_rules(alg, shash)`

Return the program rule set for Finch. One can dispatch on the `alg`

trait to specialize the rule set for different algebras. Defaults to a collection of straightforward rules that use the algebra to check properties of functions like associativity, commutativity, etc. `shash`

is an object that can be called to return a static hash value. This rule set simplifies, normalizes, and propagates constants, and is the basis for how Finch understands sparsity.

`Finch.get_prove_rules`

— Function`get_prove_rules(alg, shash)`

Return the bound rule set for Finch. One can dispatch on the `alg`

trait to specialize the rule set for different algebras. `shash`

is an object that can be called to return a static hash value. This rule set is used to analyze loop bounds in Finch.