Function identity

[michaelhkay]

To make deep-equal error-free for all arguments (issue #333), and to support the introduction of sets (issue #34), we need to be able to test whether two functions are "the same function". This is a proposed pragmatic solution.

We change the data model for functions so that functions, like nodes, have an identity that is acquired when the function is created; two functions are identical if and only if they have the same identity.

In general any expression that returns a new function allocates it an identity that is different from all other existing functions (as with nodes). However:

• Repeated evaluation of a function reference such as count#1 returns the same function each time, provided that the target function is context-free.
• Optimizers are allowed to rewrite expressions (for example by loop-lifting, etc) so that expressions that would in principle return distinct functions actually return the same function, provided the optimizer can determine that the two functions are equivalent in all respects other than their identity. For example if the expression contains(?, 'xxx') appears in a loop, the expression can be lifted out of the loop so there is no requirement that it returns different functions each time (as there is with nodes)

Benefits of this approach:

• identical($x, $x) is always true (function identity survives binding to variables)
• functions obtained by repeated evaluation of the same expression in the same context are likely to return identical results in cases that are simple enough for an optimizer to analyse
• the results are likely to be reasonably intuitive
• optimisers aren't constrained by rules on identity to restrict the rewrites they can attempt

This does mean that expressions that return functions become a little impure - but only in the same way that expressions that create nodes are a little impure. The impurity is well understood and tolerated.

Maps and arrays do not have identity as a property separate from their content.

[dnovatchev]

We change the data model for functions so that functions, like nodes, have an identity that is acquired when the function is created; two functions are identical if and only if they have the same identity.

Looks quite clean!

Maybe it would be good if globally defined / known functions, such as all standard functions, or functions from a function library can have a permanent identity ?

This will result in less compute-intensive evaluation, and even more importantly will lessen the "impurity effect", as expressions that return functions with known permanent identity will always return the same (and not different) identity value for the same such function.

One way to assign permanent identity to a function is to extend the syntax of function definition, for example:

[68]	InlineFunctionExpr	::=	"function" "(" ParamList? ")" ("as" SequenceType)? ("with-Identity" Guid)? FunctionBody

[michaelhkay]

Resolved by PR #525