Rule Macro Quotes Function Names

[willow-ahrens]

The rule macro was changed to quote the names of functions in function call expressions. This is a change from the old rule macro. I used to return function objects from the operation function, and now all my code is broken.

This was not a backward-compatible change. I believe the following code should return true:

using SymbolicUtils
using SymbolicUtils:@capture
using TermInterface
struct qux
       args
       qux(args...) = new(args)
end
TermInterface.operation(::qux) = qux
TermInterface.istree(::qux) = true
TermInterface.istree(::Type{qux}) = true
TermInterface.arguments(x::qux) = [x.args...]

@capture qux(1, 2) qux(1, 2)

[0x0f0f0f]

This should return true even with this change. This is a bug of the capture macro i guess. The pattern matcher should support both function names and objects. Code in SymbolicUtils.jl didn't change and aymbolicutils still uses function objects in terms. Will look into it ASAP

[shashi]

The pattern matcher should support both function names and objects

What do you mean??? How is this even possible?

[shashi]

Let's please add all those cases into the tests.

[0x0f0f0f]

Let's please add all those cases into the tests.

Yes. Test cases should be extended. Im currently not at my laptop but will look into fixes asap.

Metatheory.jl/test/test_reductions.jl

Line 154 in 3b6b115

@testset "Pattern matcher can match on both function object references and name symbols" begin

[0x0f0f0f]

I don't see why this code should return true with this change, and I don't think this is because of the capture macro. The matcher is asking whether the term matches the pattern, it looks at the result of operation for both, compares :qux::Symbol and qux::typeof(qux) and returns false, right?

I extended this im order to check for both symbols and function objects as operations.
I tried to achieve something close to lexical scoping when defining rules. PatTerms store a reference to a module (usually where the rule was defined) and then the matcher compiler tries to resolve that symbol in the module to optionally store a function object in the closure. when a pattern stores a symbol as operation and the matched expression has a function object as the operation, then the matcher can check for both. See patterns.jl and check_head in matchers.jl. Will be at my laptop in 10

[willow-ahrens]

I would like to clarify that I have simply switched to an old version of SymbolicUtils which I'll probably work with for a while, so please do not feel rushed on my behalf.

I don't understand why we need to convert functions to symbols and then re-engineer lexical scoping rules.

In my case, qux is not a function object, it's a callable type, which isn't too different, but might be the cause of some of these issues. Even if your new matching infrastructure works as you say, it would not work in the following case:

function peters_awesome_local_scope()
    x = qux
    (@rule x(1, 2) => "hello")(x(1, 2))
end

[0x0f0f0f]

@peterahrens

TermInterface.istree(::typeof(qux)) = true

typeof(qux) is DataType. Doing this breaks a lot of stuff since istree(x) = istree(typeof(x)) by default. You set everything to be a tree! Try doing istree(1) now!!
See how we defined the methods for TermInterface in SymbolicUtils types. https://github.com/JuliaSymbolics/SymbolicUtils.jl/blob/701ce7feab9527aaf6b04b07afd45ebe51dc03e5/src/types.jl#L635

Do instead.

TermInterface.istree(::Type{qux}) = true

See also

Metatheory.jl/src/utils.jl

Lines 141 to 159 in 3b6b115

	macro matchable(expr)
	@assert expr.head == :struct
	name = expr.args[2]
	if name isa Expr && name.head === :curly
	name = name.args[1]
	end
	fields = filter(x -> !(x isa LineNumberNode), expr.args[3].args)
	get_name(s::Symbol) = s
	get_name(e::Expr) = (@assert(e.head == :(::)); e.args[1])
	fields = map(get_name, fields)
	quote
	$expr
	TermInterface.istree(::$name) = true
	TermInterface.operation(::$name) = $name
	TermInterface.arguments(x::$name) = getfield.((x,), ($(QuoteNode.(fields)...),))
	TermInterface.arity(x::$name) = $(length(fields))
	Base.length(x::$name) = $(length(fields) + 1)
	end |> esc
	end

maybe it should be changed to respect this

By the way,

(@rule qux(1, 2)=>"hello")(qux(1, 2))
(@rule qux(1, 2)=>"hello")(1)
(@rule 1=>"hello")(1)
(@rule 1=>"hello")(qux(1, 2))

These tests all pass with this definition

[willow-ahrens]

Ah yes, that was a typo. When the typo is corrected, the expression still returns false. Here's the improved steps to reproduce issues

using SymbolicUtils
using SymbolicUtils:@capture
using TermInterface
struct qux
       args
       qux(args...) = new(args)
end
TermInterface.operation(::qux) = qux
TermInterface.istree(::qux) = true
TermInterface.istree(::Type{qux}) = true
TermInterface.arguments(x::qux) = [x.args...]

println(@capture qux(1, 2) qux(1, 2))
println((@rule qux(1, 2) => "hello")(qux(1, 2)))
function peters_awesome_local_scope()
    x = qux
    (@rule x(1, 2) => "hello")(x(1, 2))
end
println(peters_awesome_local_scope())

[willow-ahrens]

My apologies for the confusion surrounding that typo. I made that mistake when copying my test code from the REPL to github.

[0x0f0f0f]

I don't understand why we need to convert functions to symbols and then re-engineer lexical scoping rules.

I agree that that mechanism is somehow intricate. There's a big TODO REVIEWME comment at the top but it never was reviewed.

Metatheory.jl/src/matchers.jl

Line 96 in 3b6b115

function head_matcher(f::Symbol, mod)

It is not re-engineer lexical scoping rules. It's just saying that other than by its object, a symbolic term operation can and should be identified inside a module by its name most of the times. As a counterexample, I don't think that people will ever write pattern match rules with lambdas as pattern operations in f-application terms, such as @rule (x -> x^2)(a) --> 1, because then

julia> f = (x -> x^2)
#1 (generic function with 1 method)

julia> g = (x -> x^2)
#3 (generic function with 1 method)

julia> f == g
false

But if you give operations a name

julia> foo = sin
sin (generic function with 13 methods)

julia> foo == sin
true

Instead of storing the module and the symbol inside of PatTerm i propose storing both the symbol and the function object in PatTerms when both are available, otherwise just store the name. What if one wants to make a set of rules where the operations in patterns correspond only to meaningless, function-object-less, undefined symbols to work as string-like objects? This makes total sense when rewriting Expr in intermediate steps, such as fand and apply here: https://github.com/JuliaSymbolics/Metatheory.jl/blob/master/test/test_stream_fusion.jl
I do not need neither want to actually define fand and apply. I could, but i just need them as temporary symbolic placeholders and they are just replaced to lambda exprs later. In that example fand and apply are used as placeholders to commute with stuff but there is no function object for them. Is this the wrong approach and should I define fand(f::Expr, g::Expr)? Maybe.

Metatheory's goal is to get to do both things right. To do both match-on-sym-and-substitute and match-on-fun-and-eval.
If you take away one, you either lose SymbolicUtils.jl support or pure Expr support, and making rewriting features as generic as possible for both symbolics and metaprogramming has been one of the focus points of my thesis and a lot of months of work.

In my case, qux is not a function object, it's a callable type, which isn't too different, but might be the cause of some of these issues. Even if your new matching infrastructure works as you say, it would not work in the following case:

function peters_awesome_local_scope()
    x = qux
    (@rule x(1, 2) => "hello")(x(1, 2))
end

Yes. This makes sense now.

By now. PatTerm has only the operation::Any field, that is usually set to the function symbol name.

Solution 1: allow for using $ in the LHS of rules like in BenchmarkTools.jl. Thus, in (@rule ($x)(1, 2) => "hello"), the operation of the PatTerm will be the qux callable object.
This will break the rule's support for Expr-like expressions where there's just symbols as operations and no references to function objects.

Solution 2: Extend PatTerm to have operation_name::Any and operation::Any fields.
When creating rules then store both the quoted and unquoted function names. Then try to match for either one of them.

But then what should be operation_name? should it be :x or nameof(term.operation) = :qux?
What if you are applying the rule to an Expr? such as :(qux(1,2)) and :(x(1,2)). Which one should match? Both? The name in the macro that resolved to the object, or the name of the object?

I would go for using nameof. Let me know what you think

[0x0f0f0f]

Ah yes, that was a typo. When the typo is corrected, the expression still returns false. Here's the improved steps to reproduce issues

This does not work. The capture macro is broken. #86

println(@capture qux(1, 2) qux(1, 2))
function peters_awesome_local_scope()
    x = qux
    (@rule x(1, 2) => "hello")(x(1, 2))
end
println(peters_awesome_local_scope())

These tests work on master.

@testset "Matchable struct" begin
    struct qux
        args
        qux(args...) = new(args)
    end
    TermInterface.operation(::qux) = qux
    TermInterface.istree(::Type{qux}) = true
    TermInterface.arguments(x::qux) = [x.args...]
    
    @capture qux(1, 2) qux(1, 2)
    
    @test (@rule qux(1, 2)=>"hello")(qux(1, 2)) == "hello"
    @test (@rule qux(1, 2)=>"hello")(1) === nothing
    @test (@rule 1=>"hello")(1) == "hello"
    @test (@rule 1=>"hello")(qux(1, 2)) === nothing
end

[0x0f0f0f]

cc @shashi

[shashi]

What if one wants to make a set of rules where the operations in patterns correspond only to meaningless, function-object-less, undefined symbols to work as string-like objects? This makes total sense when rewriting Expr

All that is well and good but I'm not convinced that the syntax to write rules for them should be the exact same!! In my opinion they should definitely be different, in at least accepting a flag or something. They do different things.

[shashi]

Anyway can we release the fix soon?

[willow-ahrens]

I'd like to propose a solution 3.

Define a type for name-only functions, e.g.

struct NameOnlyFunction
    name::Symbol
end

(f::NameOnlyFunction)(args...) = PatTerm(:call, f, args)

or perhaps something like

struct NameOnlyFunction{Name}
    args
    NameOnlyFunction{Name}(args...) where {Name} = new{Name}(collect(args))
end

TermInterface.istree(::Type{NameOnlyFunction{Name}}) where {Name} = true
TermInterface.arguments(ex::NameOnlyFunction{Name}) where {Name} = ex.args
TermInterface.operation(ex::NameOnlyFunction{Name}) where {Name} = NameOnlyFunction{Name}

or if you didn't want the name in the type domain

struct NameOnlyFunction
    name
    args
end
NameOnlyFunction(name) = NameOnlyFunction(name, nothing)

(f::NameOnlyFunction)(args...) = NameOnlyFunction(f.name, collect(args))

TermInterface.istree(::Type{NameOnlyFunction}) = true
TermInterface.arguments(ex::NameOnlyFunction) = ex.args
TermInterface.operation(ex::NameOnlyFunction) = NameOnlyFunction(ex.name)

And of course a corresponding sugary macro

@symfun f g h
@rule x f(x) + g(x) => h(x)

With one of these abstract function types/objects, we wouldn't ever need to parse function names as symbols, since the operation field in PatTerm would just be a type or object provided by a variable resolved at the appropriate scope, the same as it would be if f, g, and h were real functions.

[0x0f0f0f]

@peterahrens fixed println(@capture qux(1, 2) qux(1, 2)) on latest commit on master

[willow-ahrens]

@shashi @0x0f0f0f Any thoughts on my proposed Nov 11 solution to the still-failing test?

println(@capture qux(1, 2) qux(1, 2))
function peters_awesome_local_scope()
    x = qux
    (@rule x(1, 2) => "hello")(x(1, 2))
end
println(peters_awesome_local_scope())

[willow-ahrens]

Looking back on this, I think that all the bugs here have been fixed, and the last example I posted reflects a reasonable change to the interface of the rule macro. I understand that there are many different use cases that need to be supported by Metatheory, and the new interface reflects this broader scope. Thanks to everyone involved for all of your quick responses to this issue!

[willow-ahrens]

I am reopening this issue to ask: If I file a PR to change the macro not to quote AST head nodes (as they may be enums, strings, custom structs, out of scope, etc.), would there be room for this change in any future release of Metatheory?

[0x0f0f0f]

Yes absolutely

I am reopening this issue to ask: If I file a PR to change the macro not to quote AST head nodes (as they may be enums, strings, custom structs, out of scope, etc.), would there be room for this change in any future release of Metatheory?

[0x0f0f0f]

This should finally be solved in #169

julia> @macroexpand(@rule(foo(~bar) => 1)) |> Base.remove_linenums!
quote
    Metatheory.Syntax.DynamicRule((PatTerm)(:call, if isdefined(Main, :foo)
                foo
            else
                :foo
            end, [~bar]), ((_lhs_expr, _egraph, bar)->begin
                1
            end), $(QuoteNode(1)))
end

Now when constructing PatTerm in the @rule macro, the operation of a pattern expands to expression isdefined(mod, op) ? op : :op. This didn't break any test, removes the necessity of defining the operations as functions.

@willow-ahrens please see JuliaSymbolics/TermInterface.jl#21 for "quoting AST head nodes", as it should be done first.

[willow-ahrens]

That's a clever fix! Awesome! I wonder if this would mean we can also remove this:

Metatheory.jl/src/matchers.jl

Lines 92 to 97 in 7828344

	# Try to match both against a function symbol or a function object at the same time.
	# Slows compile time down a bit but lets this matcher work at the same time on both purely symbolic Expr-like object.
	# Execution time should not be affected.
	# and SymbolicUtils-like objects that store function references as operations.
	function head_matcher(f::Union{Function,DataType,UnionAll})
	checkhead(x) = isequal(x, f) || isequal(x, nameof(f))

By the way, I'm not sure where I'm supposed to look in JuliaSymbolics/TermInterface.jl#21 for "quoting AST head nodes"