Più semplice esempio della necessità di “unificazione” in inferenza

Question

Sto cercando di ottenere la mia testa intorno a come viene implementato inferenza di tipo. In particolare, non ho ben vedere dove / perché il sollevamento di carichi pesanti di "unificazione" entra in gioco.

Ti do un esempio in "pseudo C #" per contribuire a chiarire:

Il modo ingenuo per farlo sarebbe qualcosa di simile:

Supponiamo che "analizza" il programma in un albero di espressione tale da poter essere eseguito con:

interface IEnvironment
{
    object lookup(string name);
}

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

Quindi, qualcosa come "Moltiplicazione" potrebbe essere implementato con:

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

Poi, per "attuare" inferenza dei tipi, si può solo fare qualcosa di simile:

interface ITypeEnvironment
{
    Type getType(string name);
}

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

Poi "Moltiplicazione" 's inferenza di tipo potrebbe essere solo qualcosa di simile:

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

sx e dx potrebbero essere costanti semplici, o "variabili" che sono guardato in su nell'ambiente:

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

Ma da nessuna parte in questo facciamo finiamo con la necessità di un algoritmo di "unificazione".

Quindi, chiaramente, il mio esempio non è abbastanza complessa. Ha bisogno di funzioni di ordine superiore? Abbiamo bisogno di "polimorfismo parametrico"?

Qual è l'esempio più semplice possibile in cui "unificazione" è effettivamente necessario per dedurre correttamente il tipo di un'espressione.

Un esempio nello Schema sarebbe l'ideale (vale a dire un esempio di un programma molto piccolo schema in cui si richiede l'unificazione di dedurre correttamente il tipo di s-espressione).

Answer 1

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

E se proprio non si conosce il tipo di variabile? Questo è il punto centrale di inferenza di tipo, giusto? Qualcosa di molto semplice come questo (in qualche linguaggio pseudocodice):

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

Non si conosce il tipo di x, fino a dedurre l'aggiunta, e rendersi conto che esso deve essere un intero perché è inserito in un intero, o qualcosa del genere.

Che cosa succede se si dispone di un'altra funzione come questa:

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

Non si può capire il tipo di x finché non si è capito il tipo di foo, e così via.

Quindi, la prima volta che vedi una variabile, è necessario assegnare solo un certo tipo segnaposto per una variabile, e poi più tardi, quando la variabile viene passata ad un qualche tipo di funzione o di qualcosa, si deve "unificare" con l'argomento tipo della funzione.

Answer 2

Mi permetta di ignorare completamente il vostro esempio e che vi faccia un esempio di dove facciamo tipo di metodo di inferenza in C #. (Se questo argomento vi interessa, allora vi incoraggio a leggere la " inferenza di tipo " archivio del mio blog.)

Si consideri:

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

Qui abbiamo un metodo M generico che prende un dizionario che mappa le stringhe su liste di T. Supponiamo di avere una variabile:

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

Abbiamo chiamato M<T> senza fornire un argomento di tipo, in modo che il compilatore deve dedurre esso.

Il compilatore fa attraverso Dictionary<string, List<int>> "unificante" con IDictionary<string, List<T>>.

In primo luogo si determina che Dictionary<K, V> implementa IDictionary<K, V>.

Da questo si deduce che Dictionary<string, List<int>> implementa IDictionary<string, List<int>>.

Ora abbiamo una partita da parte IDictionary. Noi unificare stringa con stringa, che è, ovviamente, tutti buoni, ma impariamo nulla da esso.

Poi abbiamo unificare List con List, e rendersi conto che dobbiamo ricorsione di nuovo.

Poi abbiamo unificare int con T, e rendersi conto che int è un limite su T.

L'algoritmo di inferenza di tipo sbuffa via fino a che non può non fare più progressi, e poi inizia a fare ulteriori deduzioni dalle sue inferenze. L'unico limite su T è int, quindi si deduce che il chiamante deve aver voluto T di essere int. Così noi chiamiamo M<int>.

È chiaro?

Answer 3

Supponiamo di avere una funzione

f (x, y)

dove x potrebbe essere ad esempio FunctionOfTwoFunctionsOfInteger o potrebbe essere FunctionOfInteger.

supponiamo passiamo

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

Ora, con l'unificazione, u è tenuto a 1, e z è destinato a 2, in modo che il primo argomento è un FunctionOfTwoFunctionsOfInteger.

Quindi, dobbiamo dedurre che il tipo di x ed y sono entrambi FunctionOfTwoFunctionsOfInteger

Io non sono troppo familiarità con C #, ma con le espressioni lambda (o delegati equivalentemente o altro) questo dovrebbe probabilmente essere possibile.

Per un esempio di dove tipo inferenze è molto utile per migliorare la velocità di teoremi, dare un'occhiata a "Steamroller di Schubert"

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

C'è un problema del Journal of Automated Reasoning dedicato alle soluzioni e formulazioni a questo problema, la maggior parte dei quali coinvolgono digitato inferenze nei sistemi di teoremi:

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