Самый простой пример необходимости «объединения» в выводе типа

Question

Я пытаюсь понять, как реализуется типовый вывод. В частности, я не совсем вижу, где/почему тяжелая подъем «объединения» вступает в игру.

Я приведу пример в «Pseudo 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 и RH могут быть простыми константами или «переменными», которые смотрят в окружающей среде:

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

Здесь у нас есть общий метод M, который принимает словарь, который отображает строки в списки T. Предположим, у вас есть переменная:

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, поэтому мы выдвигаем, что вызывающий абонент хотел, чтобы T был int. Итак, мы называем M<int>.

Это ясно?

Answer 3

Предположим, у нас есть функция

f (x, y)

где x может быть eg functionOftWOfunctionsOfInteger или это может быть функционально.

Предположим, мы проходим

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

Теперь с объединением U связано с 1, а Z связан с 2, поэтому первый аргумент - это функциональная функция.

Итак, мы должны сделать вывод, что тип x и y оба функционируют

Я не слишком знаком с C#, но с выражениями Lambda (или эквивалентно делегатами или чем -то еще) это, вероятно, должно быть возможно.

Для примера того, где тип подключения очень полезно для улучшения скорости доказывания теоремы, взгляните на «Steamroller Шуберта»

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

Существует проблема журнала автоматизированных рассуждений, посвященных решениям и составам этой проблеме, большинство из которых включают в себя напечатанные выводы в теоремах, подтверждающих системы:

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