统一"需要&QUOT的最简单的例子;在类型推断 [英] Simplest example of need for "unification" in type inference

问题描述

我试图让我周围的类型推断是如何实现的头。
尤其是，我不太看到/为什么统一繁重的用武之地。

我会举一个例子伪C＃，以帮助澄清：

天真的方式做这将是这样的：

假设你解析你的程序到一个表达式树，使得它可以与执行：

 接口IEnvironment 
 {$ b $对象b查找（字符串名称）; 
} 
 
接口IExpression 
 {
 //评估这个方案在这种环境下
对象评估（IEnvironment E）; 
 $：
} 
  

因此，像乘法可能与实现b
$ b

 类乘：IExpression 
 {
 IExpression LHS; 
 IExpression RHS; 
 //等
公共对象评估（IEnvironment E）
 {
 //假定此时C＃有多态性乘法
返回lhs.Evaluate（五）* rhs.Evaluate（E）; 
} 
} 
  

再到实行类型推断，你可以只做这样的事情：

 接口ITypeEnvironment 
 {
型的getType（字符串名称）; 
} 
 
接口IExpression 
 {
 //为
对象评估（IEnvironment E）之前; 
 //推断类型
型inferType（ITypeEnvironment typeEnvironment）; 
} 
  

那么，乘法的类型推断可能仅仅是这样的：

 类乘：IExpression 
 {
 IExpression LHS; 
 IExpression RHS; 
 
 // ... 
公共类型inferType（ITypeEnvironment typeEnvironment）
 {
型lhsType = lhs.inferType（typeEnvironment）; 
型rhsType = rhs.inferType（typeEnvironment）; 
如果（lhsType = rhsType！）
抛出新的异常（LHS和RHS类型不匹配）; 
 
 //你也可以查看这里LHS / RHS是双一/ INT /浮动等
返回lhsType; 
} 
} 
  

LHS和RHS可能是简单的常量，或变量这是在环境抬头：

 类常量：IExpression 
 {
对象的值; 
公共类型inferType（ITypeEnvironment typeEnvironment）
 {
返回value.GetType（）; //类型的价值; 
} 
公共对象评估（IEnvironment环境）
 {
返回值; 
} 
} 
 
类变量：IExpression 
 {
字符串名称; 
公共类型inferType（ITypeEnvironment typeEnvironment）
 {
返回typeEnvironment.getType（名）; 
} 
公共对象评估（IEnvironment环境）
 {
返回environment.lookup（名）; 
} 
} 
  

但无处在这做我们最终需要一个统一的算法。

所以，很明显，我的例子不是很复杂。是否需要更高阶的功能呢？我们需要参数多态性？

什么是一个最简单的例子，统一实际上是需要正确地推断出表达式的类型。

在方案的一个例子是理想的（即，你需要统一正确推断s表达式的类型非常小的计划程序的一个例子）。

解决方案

  public类型inferType（ITypeEnvironment typeEnvironment）
 {
返回typeEnvironment.getType（名）; 
} 
  

如果你只是不知道叫什么的变量的类型？这是类型推断的整点，对不对？像这样的事情很简单（在某些伪语言）：

 函数foo（X）{返回X + 5; } 
  

您不知道 X ，直到你推断此外，并意识到它必须是一个整数，因为它添加到一个整数，或者类似的东西。

如果你有另一个功能像这样的：

 函数bar（X）{返回美孚（X）; } 
  

您无法弄清楚 X 直到你已经想通了富，等等。

所以，当你第一次看到一个变量，你必须只分配一些占位类型的变量，再后来，当变量传递给某种功能或什么的，你要统一它与参数类型的函数。

I'm trying to get my head around how type inference is implemented. In particularly, I don't quite see where/why the heavy lifting of "unification" comes into play.

I'll give an example in "pseudo C#" to help clarify:

The naive way to do it would be something like this:

Suppose you "parse" your program into an expression tree such that it can be executed with:

interface IEnvironment
{
    object lookup(string name);
}

interface IExpression
{
    // Evaluate this program in this environment
    object Evaluate(IEnvironment e);
}

So something like "Multiplication" might be implemented with:

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);
    }
}

Then to "implement" type inference, you could just do something like:

interface ITypeEnvironment
{
    Type getType(string name);
}

interface IExpression
{
    //as before
    object Evaluate(IEnvironment e);
    // infer type
    Type inferType(ITypeEnvironment typeEnvironment);
}

Then "Multiplication"'s type inference might just be something like:

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 and rhs might be simple constants, or "variables" which are looked up in the environment:

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);
    }
}

But nowhere in this do we end up with the need for a "unification" algorithm.

So, clearly, my example is not complex enough. Does it need higher order functions? Do we need "parametric polymorphism"?

What is the simplest possible example where "unification" is actually needed to correctly infer the type of an expression.

An example in Scheme would be ideal (i.e. an example of a very small Scheme program where you require unification to correctly infer the type of the s-expression).

解决方案

public Type inferType(ITypeEnvironment typeEnvironment)
{
    return typeEnvironment.getType(name);
}

What if you just don't know the type of the variable? That's the whole point of type inference, right? Something very simple like this (in some pseudocode language):

function foo(x) { return x + 5; }

You don't know the type of x, until you infer the addition, and realize that it must be an integer because it's added to an integer, or something like that.

What if you have another function like this:

function bar(x) { return foo(x); }

You can't figure out the type of x until you have figured out the type of foo, and so on.

So when you first see a variable, you have to just assign some placeholder type for a variable, and then later, when that variable is passed to some kind of function or something, you have to "unify" it with the argument type of the function.

这篇关于统一"需要&QUOT的最简单的例子;在类型推断的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！