C++11 或 Go 等语言是如何实现类型推断的？

Question

我在这里看到 this 问题，但它没有特别详细地回答我的想法。如果像 Go 或 C++11 这样的语言不使用像 Damas-Milner 这样的推理算法，那么它们到底做了什么？我认为这不像在右侧输入类型那么简单，因为如果你有类似的东西怎么办：

5 + 3.4

编译器将如何破译那是什么类型？有没有算法不像

那么简单

if left is integer and right is float:
    return float;
if left is float and right is integer:
    return float;
etc... for every possible pattern

如果您能用简单的术语解释事情，那就太好了。我没有详细研究编译器构造或任何理论主题，我也不会真正讲函数式语言或复杂的数学符号。

Answer 1

I don't think it's as simple as taking the type on the right hand side

对于 auto var = some_expression; 形式的基本类型推断，就是这么简单。每个类型正确的表达式都只有一种类型，并且该类型将是 var 的类型。不会有从表达式类型到另一种类型的隐式转换（如果您为 var 提供了显式类型，则可能会发生这种情况）。

what if you had something like:
5 + 3.4

问题 "What is the type of 5 + 3.4?" 并非特定于类型推断，C++ 编译器总是必须回答这个问题 - 甚至在引入类型推断之前。

所以让我们退后一步，看看 C++ 编译器如何对语句 some_type var = some_expression;:

进行类型检查

首先它确定some_expression的类型。所以在代码中你可以想象像 Type exp_type = type_of(exp); 这样的东西。现在它检查 exp_type 是否等于 some_type 或是否存在从 exp_type 到 some_type 的隐式转换。如果是这样，则该语句类型正确，并且 var 被引入到具有类型 some_type 的环境中。否则不是。

现在，当我们引入类型推断并写成 auto var = some_expression; 时，等式发生了这样的变化：我们仍然做 Type exp_type = type_of(exp);，但不是将它与另一种类型进行比较或应用任何隐式转换，我们而不是简单地将 exp_type 设置为 var.

的类型

现在让我们回到5 + 3.4。它的类型是什么，编译器如何确定它？在 C++ 中，它的类型是 double。确定算术表达式类型的确切规则列在 C++ 标准中（查找 "usual arithmetic conversions"），但基本上可以归结为：在两种操作数类型中，选择一种可以表示更大范围的操作数类型值。如果类型小于 int，则将两个操作数都转换为 int。否则将两个操作数都转换为您选择的类型。

在代码中，您可以通过为每个数字类型分配一个转换等级然后执行如下操作来实现：

Type type_of_binary_arithmetic_expression(Type lhs_type, Type rhs_type) {
    int lhs_rank = conversion_rank(lhs_type);
    int rhs_rank = conversion_rank(rhs_type);
    if(lhs_rank < INT_RANK && rhs_rank < INT_RANK) return INT_TYPE;
    else if(lhs_rank < rhs_rank) return rhs_type;
    else return lhs_type;
}

大概围棋的规则有些不同，但适用相同的原则。

C++11 或 Go 等语言是如何实现类型推断的？

How is type inference implemented in a language like C++11 or Go?

compiler-construction

algorithm

type-inference