Graph Programming
Graph Programming
Graph rewriting is the analog of pattern matching....
Patterns easily represent subtrees in the ordinary case:
f[g[x_,XXXX]]
In the graph case, functions define nodes, and their arguments are other nodes....
{node0->f[node1,node2],node2g[node1,...],XXXX}
In effect, the nodei explicitly name pointers in memory that implement the symbolic expressions....
f is like a hyperedge; orderlessness of f etc. is like having undirected hypergraph
{f[e1,e2,...],g[e11,e12,...],XXXX}
f, g etc. are relations
What is the analog of evaluation? Evaluation normally walks the tree recursively, replacing subtrees.
Loops are the analog of x={x} etc.
Straightforward to do one-pass evaluation: direct analog of e.g. “generation” in WolframModel[ ]....
Is WL pattern matching confluent in all cases? Perhaps not with optionals etc.
Explicitly having heads f, g etc. is like “typed Wolfram models”....
Applications
Applications
Can one represent program execution histories this way?
One can represent loops in a way that pure tree-based pattern matching cannot.
Is it safe to have assignment, or will it usually lead to infinite processes? Could be better if all evaluation were lazy.
Large existing hypergraphs
Large existing hypergraphs
E.g. entity-property knowledgebases
SubsetCases[{f[e1,e2,...],g[e11,e12,...],XXXX},{f[e1,_,XXX],XXXX}]
Functions of (pattern) graphs
Functions of (pattern) graphs
Collection[f[e1,e2,...],g[e1,e2,....],....]
gf[Collection[f[x_,lit1],g[lit1,y_],___]]:=XXXX
Key observation: symbolic names knit together pieces of trees...
Key observation: symbolic names knit together pieces of trees...
Collection[f[x,y],f[y,x]]
Collection[f[x,y],f[y,x],f[x,x]]
Collection[f[x_,y_],f[y_,x_]]
Operation of //. directly depends on parametrization of evaluation/updating orders...