[viraptor]

Type inference, at least for variables doesn't really take that much time. In practice almost every language does it, they just don't expose it to the developer. For example you can do this in C:

    foo->bar()->baz()

And the compiler has to get the type for the bar() result. That's one a small step from:

    let x = foo->bar()

Also that dictionary is most likely parsed and assigned a type in the expression whether you specify the variable type or not.

[hamstergene]

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?

[viraptor]

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.

[comex]

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

[dep_b]

You don't understand the problem. It's the possibility of types versus the types declared. Swift will always try to go with the most exact type it can find. C doesn't have types. C is just a bunch of numbers. Swift always has types, even if you don't type them. In case of a large dictionary with multiple types for keys and values it has a ton of possibilities to test for before the real type is determined.

Could be 2 seconds to compile a very large (like 20 items) untyped dictionary declaration in the days of yore. If you would put:

    let dict: [String: Any] = [ /* bunch of confusing key-values */ ]

The compile time would go down to 100ms or less. Because it would only check if all of the keys were Strings and all of the values conformed to Any.

[viraptor]

> C doesn't have types.

I'll just stop you there to consider why foo->bar()->baz() works and how does compiler know "baz" can be referenced. It may not have type hierarchy, but it sure has types.

I wrote type inference like that and yeah, in pathological cases it take some time. But if you spend dev-visible time on a mixed type dictionary, that's just bad implementation.