alt Hacker NewsThank you. I remember reading “Gödel, Escher, Bach” and getting into the rabbit hole of term-rewriting. Then figured out it would be a fantastic way to build a compiler, simply by iteratively rewriting expressions into what is basically assembly code. Would also be a great framework for a modular bring-your-own-parser compiler construction kit. Going from theory to practice on how to achieve that, i.e. the best way to declaratively encode such transformations in Lisp-like language, how to deal with conflicts, ambiguity and the exponentially exploding search space eventually led me to e-graphs and some of the stuff you mention in this comment…
At which point it felt like having jumped into the deep sea, at night, and sharks are all around. I have no formal education in CS, and a lot of this stuff is way above my pay grade. Though it made me wonder why none of this stuff has hit mainstream; modern compilers are still very crude, it seems like such an obvious idea to model compilation as transformation of one graph into another. Is this just fringe academic research that hasn’t yet trickled down to the masses of us code monkeys?
I still have a soft-spot for this niche of computer science, but I need to find 5 years and 20 IQ points to understand how it all fits together.
I personally have a great respect and love of the intuitive and consider formalism or abstract mathematics only interesting in the service of elaboration or exploration of the intuitive.
Basically all optimizing compilers have a simplifier or rewriter in them. I don't see it as a requirement or even necessarily a priori desirable to frame their discussion or formulation in terms of high barrier mathematical language. Do so if it is fun or useful. Sometimes it is. It is to my subjective taste to do so. Compiler writers are a pretty clever group by and large and are aware of a decent amount of useful math.
There is also a tendency to underestimate where 10 years of study and effort applied to a subject can bring you and attribute it totally to some intrinsic intelligence.
Term rewriting _is_ really neat. Realizing and remembering what you find neat and exciting is important. I like equations.