News for hackers. Stuff that matters.
Re:Abstract Interpretation in the Toy Optimizer by almostgotcaught on Saturday July 27, 2024 @01:45PM (#41088173)
no shade at you (i like you and your work and blog) but

> type, known bits, known range

these are all the same thing.

i was thinking about this question in the shower (before responding) and i'm pretty sure type inference (for whatever purpose, like deducing the type, or refining the type, etc) is the only use-case of abstract interpretation. if you look at couset's webpage (i haven't read the original papers) you see lots of cute pics of program trajectory but no one actually uses abstract interpretation for control-flow tracking - the lattice is only ever updated at a type boundary.

prove me wrong (like i could be wrong) but i'm reflecting on implementations in llvm/mlir/pytype ie mature/real use-cases (i have not poked around in pypy's impl).

Re:Abstract Interpretation in the Toy Optimizer by tekknolagi on Saturday July 27, 2024 @02:03PM (#41088280)
I'm not sure what you mean that they're the same thing. They're different domains with different transfer functions. There's even a recent ish paper exploring how they can be used to inform one another. Can you say more?
Re:Abstract Interpretation in the Toy Optimizer by almostgotcaught on Saturday July 27, 2024 @02:53PM (#41088519)
> type, known bits, known range

>I'm not sure what you mean that they're the same thing

they're all components of the type; i have no idea what pypy does with "known bits" but deducing "range" of a value is firmly/unanimously as "type refinement" (see https://en.wikipedia.org/wiki/Refinement_type) i.e. still a part/aspect/dimension of the type not of the value.

Re:Abstract Interpretation in the Toy Optimizer by x0xrx on Sunday July 28, 2024 @08:25AM (#41092768)
I think with a suitably expansive definition of “type” you can get pretty far in this direction.

I have personally used AI for control flow analysis of a toy OO language.

Re:Abstract Interpretation in the Toy Optimizer by funcDropShadow on Monday July 29, 2024 @07:51AM (#41099692)
I'll leave this link here for you: https://www.absint.com/astree/index.htm

If you are not convinced think about the name of the company during your next shower.

Re:Abstract Interpretation in the Toy Optimizer by archi42 on Monday July 29, 2024 @10:09AM (#41100589)
They're related, but they're not the same thing: E.g. when analysing a JS-like language and you see "x = a + b" with raw memory content a = {0x1,0x2}, b = {0x3} you get x = {0x4,0x5,0x13,0x23} - because you can't tell if that + is a string concatenation or numerical addition.

Of course when analysing program code, you might want to carry type information with you. The math behind AI allows to combine basically any domain to a single domain without losing all the nice properties of the Galois connection. But usually you get away with tracking multiple domains simultaneously, since that's also a lot easier from an engineering perspective (someone has to understand and maintain that code for a few decades).

Edit: I recommend following funcDropShadow's advice.