Hacker News new | ask | show | jobs
by hamstergene 2935 days ago
That is way too oversimplified case of type inference. A huge lot of languages don't have this:

    let x = (f ? makeDerived1() : makeDerived2()); // no error, x is inferred to be Base

    let x = 1;
    x *= 2;
    x = sin(x) / x; // no error, x is inferred to be Float
The problem is not just that extra computation is needed, it's language design. For example, you probably do not expect a dictionary of Floats and a zero to be a dictionary of Any, but how are you going to implement that in the compiler?
1 comments
viraptor 2935 days ago
The first example is simple. The only extra work is to find common parent class.

And yes, the next example does need backtracking. I agree that it does need extra work in some cases. Most of the time though it's a very straightforward process.

link
comex 2935 days ago
"Does need extra work in some cases" is an understatement. With type 'inference' that's unidirectional, like in C and C++, you only need to look at each expression once. Thus, in most cases, the whole job is O(n) in the number of expressions.

Admittedly, there are exceptions. For example, it's possible in C++ to create humongous types:

    auto p1 = std::make_pair(0, 0); // pair<int, int>
    auto p2 = std::make_pair(p1, p1); // pair<pair<int, int>, pair<int, int>>
    auto p3 = std::make_pair(p2, p2); // pair<pair<pair<int, int>, pair<int, int>>, pair<pair<int, int>, pair<int, int>>>
    auto p4 = std::make_pair(p3, p3); // ...
Also, since templates are Turing complete, it's possible to create situations where type checking a single expression takes arbitrarily long.

But neither of those are situations you're likely to run into by accident. In most real C++ programs, all the types in the program are reasonably simple, and the template system isn't used to do anything especially clever, so the O(n) bound should hold.

On the other hand, full type inference, at least in a language like Swift that allows arbitrary overloads, is inherently a process of exhaustive search over an exponential number of possibilities. Now, as described in this post[1], it ought to be possible in most cases to reduce that exhaustive search to something much simpler – and I actually agree that the Swift compiler could be much, much better at doing so (although it has improved over time). But the post also mentions at least one case where Swift type checking can simulate 3SAT, an NP-complete problem; and I think there are other cases the author didn't think of. So it's really far from straightforward.

[1] https://www.cocoawithlove.com/blog/2016/07/12/type-checker-i...

link