5 ms·

Compiling with Constraints

126 points by philzook 3y ago

mad0 3y ago
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.
- scholaronroad 3y ago
  Out of curiosity, which university is this? IMO the number of universities that actually teach CP is small.
  - adamnemecek 3y ago
    Guessing Monash.
  - mad0 3y ago
    This was on AGH (Akademia Górniczo Hutnicza) in Krakow, Poland. I did my masters there. The course was kind of zero to hero type of thing. Here is the syllabus (unfortunately it is in polish but maybe you will be able to translate it): https://sylabusy.agh.edu.pl/en/document/065a0d32-a947-4234-a289-ce0db953af97.pdf https://sylabusy.agh.edu.pl/en/document/065a0d32-a947-4234-a...
- philzook 3y ago
  There are some nice coursera courses on minizinc - https://www.coursera.org/learn/discrete-optimization https://www.coursera.org/learn/discrete-optimization good hats. very fun. - https://www.coursera.org/learn/basic-modeling https://www.coursera.org/learn/basic-modeling
  - WJW 3y ago
    The hats in the discrete optimization course are indeed good and it's a fun course. Highly recommended! It's extremely rare that I find myself needing to pull out the big boy tools in $DAYJOB but it's good to know they exist and how to use them. Helped out in one of the later days of advent of code, too.
anonymous_union 3y ago
its fascinating how register allocation is not a solved problem. thinking about it, it seems like optimal allocation would depend on input/workload, so any ahead of time selection will always be a compromise.
- convolvatron 3y ago
  certainly optimal would be global, and I'm pretty sure its isomorphic to bin packing..whether you use a fixed call interface or not. so its solved, its just exponential
  - anonymous_union 3y ago
    im not sure. given a hypothetical arch with only 1 free register, which local variable do you allocate to it? 1 int 2 main(int argc, char *argv[]) 3 { 4 int sum = 0; 5 int sum2 = 0; 6 7 if (argc >= 2) 8 for (int i = 0; i < argv[1]; i++) 9 sum += i; 10 11 if (argc >= 3) 12 for (int i = 0; i < argv[2]; i++) 13 sum2 += sum + i; 14 15 return 0; 16 }
    - anonymous_union 3y ago
      oops im dumb, convert argv[1] and argv[2] to integers first.
      - T_MacThrowFace 3y ago
        youngun, this is why line numbers always increase by 10
    - UncleEntity 3y ago
      Oh, I want to play... So, an optimizing compiler would see that pretty much everything is dead code it would assign 0 to the return register and done.
tekknolagi 3y ago
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. In particular, I love the tiny tiny Union-Find! 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 That's even smaller than the impl I use in toy projects. Wow. And thanks for linking to my DDCG posts :)
- philzook 3y ago
  Thanks! Big fan of your posts! Keep it up!
- UncleEntity 3y ago
  Man, that's a very good explanation of DDCG. I've actually tried to understand the original paper at one point and translated all the complicated greek pseudo-code into, umm...pseudo-code to use at some future point. I spent a little time pondering on how to combine it with global value numbering (if that's even something worthwhile to pursue is still an open question) for an added 'cheap' optimization and to manage a java-like local variable heap(?) but haven't done anything with it yet. A little off topic but props where they're due...
  - tekknolagi 3y ago
    Thank you!
richard_shelton 3y ago
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: https://www.researchgate.net/profile/Peter-Sovietov/publication/356773876_Development_of_DSL_Compilers_for_Specialized_Processors/links/64871d7f79a72237652bec79/Development-of-DSL-Compilers-for-Specialized-Processors.pdf https://www.researchgate.net/profile/Peter-Sovietov/publicat...
jabowery 3y ago
This is reminiscent of an argument I had with the Mercury Prolog guys regarding "typing" in logic programming. My point boils down to this: 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. https://groups.google.com/g/comp.lang.prolog/c/8yJxmY-jbG0/m/fMxe1Vov09wJ https://groups.google.com/g/comp.lang.prolog/c/8yJxmY-jbG0/m...

126 points by philzook 3y ago

mad0 3y ago

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.

scholaronroad 3y ago
Out of curiosity, which university is this? IMO the number of universities that actually teach CP is small.
- adamnemecek 3y ago
  Guessing Monash.
- mad0 3y ago
  This was on AGH (Akademia Górniczo Hutnicza) in Krakow, Poland. I did my masters there. The course was kind of zero to hero type of thing. Here is the syllabus (unfortunately it is in polish but maybe you will be able to translate it): https://sylabusy.agh.edu.pl/en/document/065a0d32-a947-4234-a289-ce0db953af97.pdf https://sylabusy.agh.edu.pl/en/document/065a0d32-a947-4234-a...
philzook 3y ago
There are some nice coursera courses on minizinc - https://www.coursera.org/learn/discrete-optimization https://www.coursera.org/learn/discrete-optimization good hats. very fun. - https://www.coursera.org/learn/basic-modeling https://www.coursera.org/learn/basic-modeling
- WJW 3y ago
  The hats in the discrete optimization course are indeed good and it's a fun course. Highly recommended! It's extremely rare that I find myself needing to pull out the big boy tools in $DAYJOB but it's good to know they exist and how to use them. Helped out in one of the later days of advent of code, too.

anonymous_union 3y ago

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

convolvatron 3y ago
certainly optimal would be global, and I'm pretty sure its isomorphic to bin packing..whether you use a fixed call interface or not. so its solved, its just exponential
- anonymous_union 3y ago
  im not sure. given a hypothetical arch with only 1 free register, which local variable do you allocate to it? 1 int 2 main(int argc, char *argv[]) 3 { 4 int sum = 0; 5 int sum2 = 0; 6 7 if (argc >= 2) 8 for (int i = 0; i < argv[1]; i++) 9 sum += i; 10 11 if (argc >= 3) 12 for (int i = 0; i < argv[2]; i++) 13 sum2 += sum + i; 14 15 return 0; 16 }
  - anonymous_union 3y ago
    oops im dumb, convert argv[1] and argv[2] to integers first.
    - T_MacThrowFace 3y ago
      youngun, this is why line numbers always increase by 10
  - UncleEntity 3y ago
    Oh, I want to play... So, an optimizing compiler would see that pretty much everything is dead code it would assign 0 to the return register and done.

tekknolagi 3y ago

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. In particular, I love the tiny tiny Union-Find! 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 That's even smaller than the impl I use in toy projects. Wow. And thanks for linking to my DDCG posts :)

philzook 3y ago
Thanks! Big fan of your posts! Keep it up!
UncleEntity 3y ago
Man, that's a very good explanation of DDCG. I've actually tried to understand the original paper at one point and translated all the complicated greek pseudo-code into, umm...pseudo-code to use at some future point. I spent a little time pondering on how to combine it with global value numbering (if that's even something worthwhile to pursue is still an open question) for an added 'cheap' optimization and to manage a java-like local variable heap(?) but haven't done anything with it yet. A little off topic but props where they're due...
- tekknolagi 3y ago
  Thank you!

richard_shelton 3y ago

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: https://www.researchgate.net/profile/Peter-Sovietov/publication/356773876_Development_of_DSL_Compilers_for_Specialized_Processors/links/64871d7f79a72237652bec79/Development-of-DSL-Compilers-for-Specialized-Processors.pdf https://www.researchgate.net/profile/Peter-Sovietov/publicat...

jabowery 3y ago

This is reminiscent of an argument I had with the Mercury Prolog guys regarding "typing" in logic programming. My point boils down to this: 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. https://groups.google.com/g/comp.lang.prolog/c/8yJxmY-jbG0/m/fMxe1Vov09wJ https://groups.google.com/g/comp.lang.prolog/c/8yJxmY-jbG0/m...