3 ms·

Can you please explain why this is useful? I'm an intermediate python programmer with some undergrad level knowledge of complexity theory, so this is mostly ove

Can you please explain why this is useful? I'm an intermediate python programmer with some undergrad level knowledge of complexity theory, so this is mostly over my head, but it's interesting. I have no idea what one would actually use the results of this paper for - is it just a curiosity?

hither_shores 4y ago
In principle, this means you can ask mypy to check arbitrary properties of your code at compile-time. (It won't necessarily succeed, because not all properties can be checked, but you can make it try). In practice, python is very poorly suited to this kind of work.
deltasevennine 4y ago
It means that the type checker is Turing complete and can in theory run forever or get stuck in an infinite loop. It also means that it's expressive enough such that it can be more powerful then a traditional type system
- hbrn 4y ago
  I'm surprised how many people are pointing to the halting problem. It might be the most well known thing about Turing Machines, but doesn't seem like the most relevant here. Turing equivalence seems more interesting. Intuitively I'd think that type systems are supposed to be more constrained than programs they are being applied to. The fact that they are equivalent makes me think that those type systems are flawed (though I can't explain why).
  - deltasevennine 4y ago
    Nothing is suppose to be one way or the other. It's just a feature with a trade off that exists or doesn't exist. There are plenty of languages with turing complete type systems. agda, idris, coq, haskell, scala, etc...
w1nk 4y ago
It's mostly a curiosity. Occasionally things like this occur: https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-into-nso-zero-click.html https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i... . TL;DR exploited an accidentally turing complete file format to execute instructions inside a virtual machine.
an1sotropy 4y ago
Like others have said, this isn't really about being useful, so much as interesting or revealing. It answers the question "can we be certain that a Python program with type hints can actually be type-checked?" by saying "sorry, no: it's possible that the type checking will never finish". The paper does that by hooking into some basic results of theoretical computer science: Turing Machines (TMs) can model any program, there is no program that can look at another program and say that it finishes execution (the halting problem is undecidable), and, oops, you can compile TMs into Python type hints, therefore type checking Python is undecidable.
- lake_vincent 4y ago
  Ah, I see! That makes a lot of sense, thank you for explaining. If I understand correctly, that means type-checking python as you described was an open problem before, and this paper effectively proves it will never happen (ideally). They do this by establishing Turing completeness of type-hints, which are the main mechanisms for type-checking.
  - an1sotropy 4y ago
    Well, I'm sure mypy and things like it will continue to grow, and the discipline of Python type hinting will probably become more popular, not less, because it offers new opportunities for catching bugs (but maybe not for optimizations, which I think is interesting*). So maybe it was an open question whether type checking would always terminate (now answered in the negative), but that shouldn't stop anyone from using type hints, considering their practical benefits. * https://doc.pypy.org/en/latest/faq.html#would-type-annotations-help-pypy-s-performance https://doc.pypy.org/en/latest/faq.html#would-type-annotatio...

hither_shores 4y ago

In principle, this means you can ask mypy to check arbitrary properties of your code at compile-time. (It won't necessarily succeed, because not all properties can be checked, but you can make it try). In practice, python is very poorly suited to this kind of work.

deltasevennine 4y ago

It means that the type checker is Turing complete and can in theory run forever or get stuck in an infinite loop. It also means that it's expressive enough such that it can be more powerful then a traditional type system

hbrn 4y ago
I'm surprised how many people are pointing to the halting problem. It might be the most well known thing about Turing Machines, but doesn't seem like the most relevant here. Turing equivalence seems more interesting. Intuitively I'd think that type systems are supposed to be more constrained than programs they are being applied to. The fact that they are equivalent makes me think that those type systems are flawed (though I can't explain why).
- deltasevennine 4y ago
  Nothing is suppose to be one way or the other. It's just a feature with a trade off that exists or doesn't exist. There are plenty of languages with turing complete type systems. agda, idris, coq, haskell, scala, etc...

w1nk 4y ago

It's mostly a curiosity. Occasionally things like this occur: https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-into-nso-zero-click.html https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i... . TL;DR exploited an accidentally turing complete file format to execute instructions inside a virtual machine.

an1sotropy 4y ago

Like others have said, this isn't really about being useful, so much as interesting or revealing. It answers the question "can we be certain that a Python program with type hints can actually be type-checked?" by saying "sorry, no: it's possible that the type checking will never finish". The paper does that by hooking into some basic results of theoretical computer science: Turing Machines (TMs) can model any program, there is no program that can look at another program and say that it finishes execution (the halting problem is undecidable), and, oops, you can compile TMs into Python type hints, therefore type checking Python is undecidable.

lake_vincent 4y ago
Ah, I see! That makes a lot of sense, thank you for explaining. If I understand correctly, that means type-checking python as you described was an open problem before, and this paper effectively proves it will never happen (ideally). They do this by establishing Turing completeness of type-hints, which are the main mechanisms for type-checking.
- an1sotropy 4y ago
  Well, I'm sure mypy and things like it will continue to grow, and the discipline of Python type hinting will probably become more popular, not less, because it offers new opportunities for catching bugs (but maybe not for optimizations, which I think is interesting*). So maybe it was an open question whether type checking would always terminate (now answered in the negative), but that shouldn't stop anyone from using type hints, considering their practical benefits. * https://doc.pypy.org/en/latest/faq.html#would-type-annotations-help-pypy-s-performance https://doc.pypy.org/en/latest/faq.html#would-type-annotatio...