Expression-tree and graph pattern-matching?

Ecosystem
1

This is wildly off-topic, but I figure there are enough PL folks in this forum, that somebody might have pointers. I apologize in advance to those who come here only for OCaml-related content.

Does anybody have any pointers for where I might look for interesting algorithms for expression-tree and graph pattern-matching? That is to say pattern-matching over those data-structures with interesting constraints (like equality-constraints over nodes, or variables in expressions).

Surely there’s a rich literature on these things, b/c they’re so relevant to so many problems in program-rewriting, analysis, etc. But I’ve been so long in industry that nothing comes to mind immediately, for wherre to look.

Thanks in advance.

ETA: Ah, I’ve found at least one conference (series), “Combinatorial Pattern Matching” that seems relevant. And for graph pattern-matching, there’s VF2 and its descendants.

2

For the tree stuff you likely want to look into the literature on XML processing (no longer hot but trees are here to stay). Stuff like tree transducers, etc. It seems www.cduce.org is still alive (and that makes us back on topic).

3

I found it interesting to note that database/datalog queries can easily express graph patterns if you represent your graph using an edges table (perhaps with extra attributes). The larger the pattern, the more computatonally expensive this may be, but the patterns I usually think about are pretty small. The Ocaml sqlite bindings for example can get the job done. It often seems to be the case that the database world has a parallel universe of terminology for topics.

4

I may mention

  1. Parser combinators. But in this case your string is a graph, and multiple characters can go after current one. (N.B. lokkahead in this situation is very bad slow idea)
  2. You may look at languages for graph queries, for examle cypher.