If you like reasoning about a program in terms of expression trees/graphs, I recently discovered that Wolfram Language has built-ins for this:
https://reference.wolfram.com/language/ref/ExpressionTree.ht...
This seems, at least upon first read, analogous to global value numbering (GVN). Or, depending on how you look at it, common subexpression elimination (CSE). I am mostly wondering why they are not mentioned in the article.
> This transformation is affectionately known as sharing
No, it is ubiquitously known as CSE: common subexpression elimination.
The original DAG representation of the abstract syntax, on the other hand, exhibits substructure sharing.
> Of course, that invariant eventually changed. We added a way in the source langauge to introduce lets, which meant my algorithm was wrong.
Because you have to identify variables by more than just their symbol, due to shadowing, like De Brujn indexing and other schemes.
CSE is not particularly difficult in a functional language. Variable assignments throw a monkey wrench into it. Any terms with side effects also.
By the way, CSE can be done over intermediate representations, rather than abstract syntax. In an intermediate representation, you look for identical instructions with the same operands, not arbitrarily large expressions, while paying attention to variable liveness.
Another by the way is that not only do we have to worry about side effects, but we also cannot do CSE on expressions that guarantee returning a fresh object. E.g. if we are compiling Lisp we cannot merge two occurrences of (cons 1 2). The expressions must produce fresh cells which are not eq to each other. Ultimately that is linked to side effects; being able to mutate one cell with no effect on the other. Construction per se is not a side effect, even if it guarantees freshness.
A great example of the value of academia and scientific research.
Yivycy
Problem solvers based on graphs are hard to get your head around at first, but then you get extremely elegant and powerful solutions to seemingly unsolvable problems.
The only gotchas are: 1) time to get your head around 2) algorithmic complexity of the resulting solution.
Graph theory is probably the most fulfilling math application in the computer science. In a way, graph-based algorithms do magic similar to AI but in a fully determined manner. If you think about it more broadly, a graph resembles a subset of a neural network but only with {0, 1} weights.