Redesign proposal

[shashi]

Interfaces for traversing terms is easy, but similarterm is the main magic of this package. The awkwardness of the current implementation is the use of exprhead as a keyword argument in similarterm. SymbolicUtils only has (mostly) terms that represent function calls, but we couldn't just ignore exprhead because Julia tries to dispatch on it. Also, exprhead is set to :call by default -- a clear sign of abstraction leak. I think it's time to take concept of a "head" seriously...

The proposal is to just make head the first argument to similarterm instead of the reference object in whose image we are trying to build the new term. It then also makes sense to rename similarterm to maketerm. This also allows one to compute the head in other ways than using a reference term.

So the new interface could be:

maketerm(h::H, t; type=Any, metadata=nothing) # -> to be implemented by provider of H
head(t) = h
tail(t) = t

I'm using the word tail because arguments is already in use to mean basically tail[2:end] in the case that the head is a function call. It would presumably have this check programmatically, going forward.

In SymbolicUtils, we would define

struct SUApply end
maketerm(::SUApply, tail; kw...) = term(tail...; kw...)
istree(x::Symbolic) = true # replace Symbolic with concrete types that are tree
head(x::Symbolic) = SUTerm()
tail(x::Symbolic) = (operation(x), arguments(x)...) # or some efficient alternative

So this would stay within the closure of types that represent function calls.

In Metatheory you'd just need to add a MTHead type.

struct MTHead; head::Symbol; end
maketerm(h::MTHead, tail) = Expr(h.head, tail...)
head(::Expr) = MTTerm() # This will be considered piracy, however, so you might want to add a wrapper around Expr in MT eventually

I have thought about this a lot, and I think it's easiest to leave type and metadata as keyword arguments, and not try to cram them into head or something like that, but other arguments are welcome. These are like the stuff after : in a typed language definition.

This should address #10 and answer #15.

@0x0f0f0f @willow-ahrens @YingboMa

[0x0f0f0f]

Checking in MT if this is OK with the e-graphs implementation. I like the proposal, and it sounds like a good abstraction that fixes the leak.

[willow-ahrens]

I agree with the introduction of maketerm. For efficient code, different terms in an AST should probably just be enums or similar rather than separate structs, and this looks compatible with that.

On naming: head and tail are typically used for lists. Because this package is targeted towards abstract syntax trees, consider renaming head and tail to node and children or construct and subterms or tokens.

[willow-ahrens]

I've been using operation and arguments to play the role of head and tail already in Finch and it works well. If possible, it would be nice to keep them named that way.

[shashi]

@willow-ahrens operation in SU currently returns the function or the "symbolic" function, and sometimes even structs that are callable. I am not sure how to reconcile that with the maketerm proposal--if operation is the first argument to maketerm then it means it needs to be special cased to return a specific kind of term in that case.

head and tail are typically used for lists.

That's true. I was thinking of S-expressions here, car, cdr but not all lists are terms and we are indeed dealing with typed ASTs. But head and children could work!? I find that "node" is often overloaded a lot, it is often used to mean a whole subtree rather than a value at the root of the subtree.

[willow-ahrens]

Okay! To confirm my understanding, this proposal renames operation (in TermInterface) to head and arguments (in TermInterface) to children, removes exprhead, and adds maketerm, is that right?

[willow-ahrens]

We used to have

similarterm(t::MyType, f, args, symtype=T; metadata=nothing, exprhead=exprhead(t))

but now we have

similarterm(t::MyType, children, symtype=T; metadata=nothing) =
    maketerm(head(t), children, symtype = symtype, metadata = metadata)

where perhaps children = [f, args...], or maybe children = [array, indicies...] or perhaps even children = statements_in_a_block

[shashi]

Yes, all that is correct! :)

[0x0f0f0f]

I can start integrating this on a Metatheory branch when there's a test branch here

[0x0f0f0f]

@shashi

struct SUApply end
maketerm(::SUApply, tail; kw...) = term(tail...; kw...)
istree(x::Symbolic) = true # replace Symbolic with concrete types that are tree
head(x::Symbolic) = SUTerm()
tail(x::Symbolic) = (operation(x), arguments(x)...) # or some efficient alternative

Did you mean something like

head(x::Symbolic) = SUApply()

?

Same for MT,

struct MTHead; head::Symbol; end
maketerm(h::MTHead, tail) = Expr(h.head, tail...)
head(::Expr) = MTTerm() 

Did you mean

head(x::Expr) = MTHead(x.head)

?