Hacker News Reader

Comment by lake_vincent | Hacker News Reader

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?

View on HN

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.

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.

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-annotatio...

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.

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

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).

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...

It's mostly a curiosity. Occasionally things like this occur: 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.

Reply on news.ycombinator.com