유형 추론에서 "통일"에 대한 가장 간단한 예

Question

나는 유형 추론이 어떻게 구현되는지에 대한 머리를 잡으려고 노력하고 있습니다. 특히, 나는 "통일"의 무거운 리프팅이 어디에서 발생하는지를 알지 못합니다.

명확히하기 위해 "의사 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);
    }
}

그러나 이것의 어느 곳에서도 우리는 "통일"알고리즘의 필요성으로 끝나지 않습니다.

따라서 분명히 내 예는 충분히 복잡하지 않습니다. 더 높은 차수 기능이 필요합니까? "파라 메트릭 다형성"이 필요합니까?

표현의 유형을 정확하게 추론하기 위해 "통일"이 실제로 필요한 가장 간단한 예는 무엇입니까?

체계의 예는 이상적입니다 (즉, S- 표현의 유형을 올바르게 추론하기 위해 통일이 필요한 매우 작은 체계 프로그램의 예).

Answer 1

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

변수의 유형을 모르는 경우 어떻게해야합니까? 그것이 유형의 추론의 요점입니다. 이와 같은 매우 간단한 것 (일부 의사 코드 언어) :

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

당신은 유형을 모릅니다 x, 당신이 추가를 추론 할 때까지, 정수에 추가되기 때문에 정수가되어야한다는 것을 깨달으십시오.

이와 같은 다른 기능이 있다면 어떨까요?

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

당신은 유형을 알아낼 수 없습니다 x 당신이 유형을 알아 내기 전까지 foo, 등등.

따라서 변수를 먼저 볼 때 변수에 대한 자리 표시 자 유형을 할당 한 다음 나중에 그 변수가 어떤 종류의 함수 나 무언가로 전달되면 인수 유형으로 "통합"해야합니다. 기능.

Answer 2

귀하의 예를 완전히 무시하고 C#에서 메소드 유형을 수행하는 위치의 예를 알려 드리겠습니다. (이 주제가 당신에게 관심이 있다면, 나는 당신이 읽는 것을 권장합니다.입력 유추"내 블로그의 아카이브.)

고려하다:

void M<T>(IDictionary<string, List<T>> x) {}

여기에는 문자열을 T 목록에 매핑하는 사전을 취하는 일반적인 방법 M이 있습니다. 변수가 있다고 가정합니다.

var d = new Dictionary<string, List<int>>() { ...initializers here... };
M(d);

우리는 전화했습니다 M<T> 유형 인수를 제공하지 않고 컴파일러가 추론해야합니다.

컴파일러는 "통합"으로 그렇게합니다. Dictionary<string, List<int>> ~와 함께 IDictionary<string, List<T>>.

먼저 그것을 결정합니다 Dictionary<K, V> 구현 IDictionary<K, V>.

그로부터 우리는 그것을 추론합니다 Dictionary<string, List<int>> 구현 IDictionary<string, List<int>>.

이제 우리는 일치합니다 IDictionary 부분. 우리는 문자열을 문자열로 통일합니다. 이것은 분명히 모두 좋지만 아무것도 배우지 않습니다.

그런 다음 목록과 목록을 통합하고 다시 재발해야한다는 것을 깨달았습니다.

그런 다음 우리는 int를 t로 통일하고 int가 T에 묶인다는 것을 깨달았습니다.

형식 추론 알고리즘은 더 이상 진전을 이룰 수 없을 때까지 치러지고 그 추론에서 추가 공제를 시작합니다. t의 유일한 바운드는 int이므로 발신자가 int가되기를 원한다고 추론합니다. 그래서 우리는 전화합니다 M<int>.

분명합니까?

Answer 3

기능이 있다고 가정합니다

f (x, y)

여기서 x는 예를 들어 FunctionOftWoftionsofInteger 일 수 있거나 functionOfInteger 일 수 있습니다.

우리가 지나가한다고 가정 해 봅시다

F (g (u, 2), g (1, z))

이제 통일을 사용하면 u는 1에 묶여 있고 z는 2에 묶여 있으므로 첫 번째 인수는 functionoftWoftionsofInteger입니다.

따라서 x와 y의 유형이 모두 functionoftwoftionsofinteger임을 추론해야합니다.

나는 C#에 너무 익숙하지 않지만 Lambda Expressions (또는 동등한 대표 등)를 사용하면 이것이 가능할 것입니다.

유형 추론이 정리 증명의 속도를 향상시키는 데 매우 유용한 위치의 예는 "Schubert 's Steamroller"를 살펴보십시오.

http://www.rpi.edu/~brings/pai/schub.steam/node1.html

이 문제에 대한 해결책과 공식에 전념하는 자동화 된 추론 저널의 문제가 있으며, 대부분 정리 증명 시스템에서 유형의 추론을 포함합니다.

http://www.springerlink.com/content/k1425x112w6671g0/