Compiling with Constraints

Huh I haven't thought that I will see minizinc outside of my university. I keep being pleasantly surprised that constraint programming and formal methods are being used somewhere out there.

What I like about these notes is that a complex topic is described in a simple and very practical manner. By the way, a few years ago there was another project on creating a code generator using declarative constraint solving:<p><a href="https:&#x2F;&#x2F;www.researchgate.net&#x2F;profile&#x2F;Peter-Sovietov&#x2F;publication&#x2F;356773876_Development_of_DSL_Compilers_for_Specialized_Processors&#x2F;links&#x2F;64871d7f79a72237652bec79&#x2F;Development-of-DSL-Compilers-for-Specialized-Processors.pdf" rel="nofollow">https:&#x2F;&#x2F;www.researchgate.net&#x2F;profile&#x2F;Peter-Sovietov&#x2F;publicat...</a>

This is reminiscent of an argument I had with the Mercury Prolog guys regarding &quot;typing&quot; in logic programming. My point boils down to this:<p>Any predicate can be considered a constraint. Types are constraints. While it may be reasonable to have syntactic sugars for type declarations that, at compile time, are transformed into predicates, it is unreasonable to lard a completely different kind of semantics on top of an already adequate semantic such as first order logic.<p><a href="https:&#x2F;&#x2F;groups.google.com&#x2F;g&#x2F;comp.lang.prolog&#x2F;c&#x2F;8yJxmY-jbG0&#x2F;m&#x2F;fMxe1Vov09wJ" rel="nofollow">https:&#x2F;&#x2F;groups.google.com&#x2F;g&#x2F;comp.lang.prolog&#x2F;c&#x2F;8yJxmY-jbG0&#x2F;m...</a>

Holy shit, this is an excellent tour. I want to look at constraint-based register allocation for my next project, I think. I also wanted to see if it were possible to synthesize a data format and short x86 opcode sequences that would satisfy certain mathematical laws, but I did not figure out how to do that. Maybe we should chat.<p>In particular, I love the tiny tiny Union-Find!<p><pre><code> uf = {} def find(x): while x in uf: x = uf[x] return x def union(x,y): x = find(x) y = find(y) if x != y: uf[x] = y return y </code></pre> That&#x27;s even smaller than the impl I use in toy projects. Wow.<p>And thanks for linking to my DDCG posts :)

its fascinating how register allocation is not a solved problem. thinking about it, it seems like optimal allocation would depend on input&#x2F;workload, so any ahead of time selection will always be a compromise.