Das einfachste Beispiel für die Notwendigkeit einer „Vereinigung“ in Typinferenz

Question

Ich versuche meinen Kopf darüber zu machen, wie die Inferenz von Typs implementiert wird. Insbesondere sehe ich nicht ganz, wo/warum das schwere Heben der "Vereinigung" ins Spiel kommt.

Ich werde ein Beispiel in "Pseudo C#" geben, um zu klären:

Die naive Art, es zu tun, wäre ungefähr so:

Angenommen, Sie "analysieren" Ihr Programm in einen Ausdrucksbaum so analysieren, so dass es ausgeführt werden kann:

interface IEnvironment
{
    object lookup(string name);
}

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

So kann so etwas wie "Multiplikation" implementiert werden mit:

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

Um dann den Typ -Inferenz zu "implementieren", könnten Sie einfach so etwas tun wie:

interface ITypeEnvironment
{
    Type getType(string name);
}

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

Dann könnte "Multiplication" -Typ -Inferenz nur so etwas sein wie:

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 und RHS können einfache Konstanten oder "Variablen" sein, die in der Umgebung nachgeschlagen werden:

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

Aber nirgendwo in diesem Grund haben wir den Bedarf an einem "Vereinigung" -Algorithmus.

Mein Beispiel ist also eindeutig nicht komplex genug. Benötigt es Funktionen höherer Ordnung? Benötigen wir "parametrische Polymorphismus"?

Was ist das einfachste Beispiel, bei dem tatsächlich "Vereinigung" erforderlich ist, um den Typ eines Ausdrucks korrekt zu schließen.

Ein Beispiel im Schema wäre ideal (dh ein Beispiel für ein sehr kleines Programmprogramm, bei dem Sie eine Vereinigung benötigen, um den Typ der S-Expression korrekt zu schließen).

Answer 1

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

Was ist, wenn Sie die Art der Variablen nur nicht kennen? Das ist der springende Punkt vom Typ Folgerung, oder? Etwas sehr Einfaches wie dieses (in einer Pseudocode -Sprache):

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

Sie wissen nicht die Art von x, bis Sie die Ergänzung schließen und erkennen, dass es eine Ganzzahl sein muss, weil es einer Ganzzahl oder ähnlichem hinzugefügt wird.

Was ist, wenn Sie eine andere Funktion wie diese haben:

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

Sie können die Art von nicht herausfinden x bis Sie die Art von herausgefunden haben foo, usw.

Wenn Sie also zum ersten Mal eine Variable sehen, müssen Sie nur einen Platzhaltertyp für eine Variable zuweisen, und später müssen Sie sie mit dem Argumentyp der Argumentation "vereinen", wenn diese Variable an eine Art von Funktion oder etwas übergeben wird Funktion.

Answer 2

Lassen Sie mich Ihr Beispiel vollständig ignorieren und geben Sie Ihnen ein Beispiel dafür, wo wir Methodentyp -Inferenz in C#durchführen. (Wenn dieses Thema Sie interessiert, ermutige ich Sie, das zu lesen "Geben Sie Inferenz ein"Archiv meines Blogs.)

In Betracht ziehen:

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

Hier haben wir eine generische Methode m, die ein Wörterbuch annimmt, das Zeichenfolgen auf Listen von T ordnet. Angenommen, Sie haben eine Variable:

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

Wir haben angerufen M<T> Ohne ein Typ -Argument vorzulegen, muss der Compiler es schließen.

Der Compiler tut dies, indem er "vereinigt" Dictionary<string, List<int>> mit IDictionary<string, List<T>>.

Zuerst bestimmt es das Dictionary<K, V> Geräte IDictionary<K, V>.

Daraus schließen wir das Dictionary<string, List<int>> Geräte IDictionary<string, List<int>>.

Jetzt haben wir ein Match gegen die IDictionary Teil. Wir vereinen Zeichenfolge mit String, was offensichtlich alles gut ist, aber wir lernen nichts daraus.

Dann vereinen wir die Liste mit der Liste und erkennen, dass wir uns wieder wiederholen müssen.

Dann vereinen wir Int mit T und erkennen, dass int eine gebundene für T. ist.

Der Typ -Inferenzalgorithmus tuckert weg, bis er nicht mehr Fortschritte machen kann, und dann beginnt er weitere Abzüge von seinen Schlussfolgerungen vorzunehmen. Das einzige gebundene T int ist int, daher schließen wir, dass der Anrufer gewollt haben muss, dass T int ist. Also rufen wir an M<int>.

Ist das klar?

Answer 3

Angenommen, wir haben eine Funktion

f (x, y)

wobei X EG FunctionOftwofunctionsOfInteger sein könnte oder es kann sich um Funktionsofteiger handeln.

Angenommen, wir gehen ein

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

Mit der Vereinigung ist U an 1 gebunden und Z an 2 gebunden, sodass das erste Argument ein FunktionsoftwooTionsOfInteger ist.

Wir müssen also schließen, dass die Art von x und y beide functionoftWofunctionsOfTeger sind

Ich bin mit C#nicht allzu vertraut, aber mit Lambda -Ausdrücken (oder gleichzeitig delegiert oder was auch immer) dies wahrscheinlich möglich sein.

Ein Beispiel dafür, wo die Typausführung sehr nützlich ist, um die Geschwindigkeit des Satzes zu verbessern, sehen Sie sich den "Schuberts Steamroller" an.

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

Es gibt eine Frage des Journal of Authoricated Argumenting, das Lösungen und Formulierungen für dieses Problem gewidmet ist.

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