我试图弄清楚类型推断是如何实现的。特别是，我不太明白“统一”的繁重工作在哪里/为什么发挥作用。
我将在“伪 C#”中举一个例子来帮助澄清：
天真的方法是这样的：
假设您将程序“解析”成一个表达式树，以便可以使用以下命令执行它：
interface IEnvironment
{
object lookup(string name);
}
interface IExpression
{
// Evaluate this program in this environment
object Evaluate(IEnvironment e);
}
所以像“乘法”这样的东西可以用：
class Multiply : IExpression
{
IExpression lhs;
IExpression rhs;
// etc.
public object Evaluate(IEnvironment e)
{
// assume for the moment C# has polymorphic multiplication
return lhs.Evaluate(e) * rhs.Evaluate(e);
}
}
然后要“实现”类型推断，您可以执行以下操作：
interface ITypeEnvironment
{
Type getType(string name);
}
interface IExpression
{
//as before
object Evaluate(IEnvironment e);
// infer type
Type inferType(ITypeEnvironment typeEnvironment);
}
那么“乘法”的类型推断可能就是这样的：
class Multiply : IExpression
{
IExpression lhs;
IExpression rhs;
// ...
public Type inferType(ITypeEnvironment typeEnvironment)
{
Type lhsType = lhs.inferType(typeEnvironment);
Type rhsType = rhs.inferType(typeEnvironment);
if(lhsType != rhsType)
throw new Exception("lhs and rhs types do not match");
// you could also check here that lhs/rhs are one of double/int/float etc.
return lhsType;
}
}
lhs 和 rhs 可能是简单的常量，或者是在环境中查找的“变量”：
class Constant : IExpression
{
object value;
public Type inferType(ITypeEnvironment typeEnvironment)
{
return value.GetType(); // The type of the value;
}
public object Evaluate(IEnvironment environment)
{
return value;
}
}
class Variable : IExpression
{
string name;
public Type inferType(ITypeEnvironment typeEnvironment)
{
return typeEnvironment.getType(name);
}
public object Evaluate(IEnvironment environment)
{
return environment.lookup(name);
}
}
但在这方面，我们最终不需要“统一”算法。
所以，很明显，我的例子不够复杂。它需要高阶函数吗？我们需要“参数多态性”吗？
什么是最简单的示例，其中实际上需要“统一”来正确推断表达式的类型。
Scheme 中的一个例子是理想的（即一个非常小的Scheme 程序的例子，你需要统一来正确推断s 表达式的类型）。