أبسط مثال على الحاجة إلى "التوحيد" في النوع الاستدلال

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

هنا لدينا طريقة عامة 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 مع ر، وأدرك أن int هو ملزمة في T.

تشجع خوارزمية استنتاج النوع بعيدا حتى لا يمكن تحقيق مزيد من التقدم، ثم يبدأ في إجراء المزيد من الاستقطاعات من استنتاجاتها. الملزمة الوحيدة على T INT INT، لذلك نحن نستنتج أن المتصل يجب أن يكون مطلوبا أن تكون كثيرة. لذلك نحن ندعو M<int>.

هل هذا واضح؟

Answer 3

لنفترض أن لدينا وظيفة

f (x، y)

حيث x قد يكون على سبيل المثال watchoftwofunctionsofinnger أو قد يكون العمل وظيفة.

لنفترض أننا تمر

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

الآن مع التوحيد، أنت مرتبط ب 1، و z مرتبط ب 2، وبالتالي فإن الحجة الأولى هي وظيفة الوظائف.

لذلك، علينا أن نستنتج أن نوع x و y كلاهما الوظائف

أنا لست على دراية للغاية ب C #، ولكن مع تعبيرات لامدا (أو المندوبين المعادلين أو أيا كان) ربما يكون ذلك ممكنا.

للحصول على مثال على انخفاض النوع مفيد للغاية في تحسين سرعة نظرية النظرية، نلقي نظرة على "Schubert's Steamroller"

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

هناك مشكلة في مجلة المنطق الآلي المخصص للحلول والتركيبات لهذه المشكلة، معظمها تنطوي على الاستمرار المكتبكي في أنظمة إثبات نظرية:

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