لماذا هو تحديد ما إذا كانت وظيفة نقي صعبة ؟

Question

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

هذا النوع من الخلط لي, لأنه لا يبدو أن من الصعب على المترجم/المترجم إلى حل بشكل متكرر.في شبة الكود:

function isPure(functionMetadata): boolean;
begin
   result = true;
   for each variable in functionMetadata.variablesModified
      result = result and variable.isLocalToThisFunction;
   for each dependency in functionMetadata.functionsCalled
      result = result and isPure(dependency);
end;

هذه هي الفكرة الأساسية.من الواضح أنك تحتاج إلى بعض النوع من الاختيار لمنع لانهائية العودية على متبادل تعتمد على الوظائف ، ولكن هذا ليس من الصعب جدا لاقامة.

الوظائف العليا التي تأخذ مؤشرات الدالة قد تكون إشكالية ، حيث لا يمكن التحقق منها بشكل ثابت ، ولكن سؤالي يفترض أن المترجم له نوعا من اللغة القيد تعين أن نقي مؤشر وظيفة يمكن أن تنتقل إلى معلمة معينة.إذا كان أحد موجودا ، التي يمكن استخدامها لتلبية الشرط.

من الواضح أن هذا سيكون أسهل في لغة مترجمة من تفسير واحد ، لأن كل هذا العدد الطحن سوف يتم قبل أن يتم تنفيذ البرنامج و حتى لا يتباطأ أي شيء, ولكن أنا حقا لا أرى أي مشاكل جوهرية من شأنها أن تجعل من المستحيل تقييم.

لا أحد مع أكثر قليلا من المعرفة في هذا المجال أعرف ما أنا في عداد المفقودين ؟

Answer 1

ومن الصعب بشكل خاص في بيثون. منذ anObject.aFunc يمكن تغيير تعسفا في وقت التشغيل، لا يمكنك تحديد في وقت الترجمة التي وظيفة سوف anObject.aFunc() مكالمة أو حتى لو أنها ستكون وظيفة على الإطلاق.

Answer 2

وتحتاج أيضا إلى تعليم كل مكالمة النظام، كل FFI، ...

وعلاوة على ذلك، أصغر 'تسرب' يميل إلى تسرب إلى رمز قاعدة بأكملها.

وانها ليست مشكلة مستعصية على الحل من الناحية النظرية، ولكن في واقع الامر انه جدا الصعب جدا القيام به بطريقة أن النظام كله لا يشعر هش.

وبوصفها جانبا، وأنا لا أعتقد أن هذا يجعل أطروحة الدكتوراه جيدة. هاسكل فعال بالفعل (نسخة من) هذا، مع الكائن الدقيق الاحادي الخلية IO.

وأنا متأكد من الكثير من الناس لا تزال تنظر في هذا 'عمليا'. (تكهنات) في 20 سنوات ونحن قد يكون هذا.

Answer 3

وبالإضافة إلى أجوبة أخرى ممتازة هنا: شبة الكود الخاص بك يبدو فقط في ما إذا كانت وظيفة بتعديل المتغيرات. ولكن هذا ليس حقا ما يعنيه "نقية". "بيور" يعني عادة شيء أقرب إلى "شفافة مرجعيا." وبعبارة أخرى، فإن الناتج هو تعتمد اعتمادا كليا على المدخلات. حتى شيء بسيط مثل القراءة في الوقت الحالي وجعل ذلك عاملا في نتيجة (أو يقرأ من المدخلات، أو قراءة حالة الجهاز، أو ...) يجعل وظيفة غير نقية دون تعديل أي المتغيرات.

وأيضا، هل يمكن كتابة دالة "النقية" التي لم تعديل متغيرات.

Answer 4

وهنا فإن أول ما برزت في ذهني عندما قرأت سؤالك.

<اقتباس فقرة>   

والدرجة التسلسلات الهرمية

وتحديد إذا تضمن متغير يتم تعديل هذا القانون من خلال حفر كل أسلوب واحد وهو ما يسمى في المتغير لتحديد ما اذا كان يتحور. هذا هو ... إلى حد ما على التوالي إلى الأمام لنوع مختوم مع طريقة غير ظاهري.

ولكن النظر في أساليب الظاهري. يجب أن تجد كل نوع مشتق واحد، والتحقق من أن كل تجاوز واحد من تلك الطريقة لا تتحول الدولة. تحديد هذا ببساطة غير ممكن في أي لغة / الإطار الذي يسمح لتوليد دينامية رمز أو ببساطة ديناميكية (إذا كان من الممكن، فإنه من الصعب للغاية). السبب هو أن مجموعة من أنواع مشتقة ليست ثابتة لأن واحدة جديدة يمكن أن تتولد في وقت التشغيل.

وخذ C # كمثال على ذلك. لا يوجد شيء يمنعني من إنشاء فئة مشتقة في وقت التشغيل الذي يتجاوز هذا الأسلوب الظاهري ويعدل الدولة. ومن شأن ثابت التحقق لا تكون قادرة على الكشف عن هذا النوع من التعديل، وبالتالي لا يمكن التحقق من صحة وطريقة نقية أم لا.

Answer 5

وأعتقد أن المشكلة الرئيسية أن تفعل ذلك بكفاءة.

وD-لغة لها وظائف نقية ولكن عليك أن تحدد بنفسك، وبالتالي فإن المترجم من شأنه أن نعرف للتحقق منها. اعتقد انه اذا كنت تحديدها يدويا ثم أنه سيكون من الأسهل القيام به.

Answer 6

وتقرير ما إذا كان وظيفة معينة نقية، بشكل عام، هي اختزال لتحديد ما إذا كان أي برنامج معين ستوقف - وكما هو معروف جيدا أن مشكلة وقف هو نوع من مشكلة لا يمكن حلها بكفاءة

Answer 7

علما بأن التعقيد يعتمد على اللغة أيضا.أكثر ديناميكية لغات, فمن الممكن تحديد أي شيء في أي وقت.على سبيل المثال ، في Tcl

proc myproc {a b} {
    if { $a > $b } {
        return $a
    } else {
        return $b
    }
}

كل قطعة واحدة من التي يمكن تعديلها في أي وقت.على سبيل المثال:

• "إذا" القيادة يمكن إعادة كتابة استخدام وتحديث المتغيرات العالمية
• "العودة" الأمر على نفس المنوال ، يمكن أن تفعل الشيء نفسه
• على أن يكون تنفيذ الحكم أثر على إن الأمر أنه عندما "إذا" ، يعود الأمر أعاد بناء على مدخلات إذا كان الأمر

باعتراف الجميع, Tcl هو حالة متطرفة;واحدة من أكثر اللغات الديناميكية هناك.أن يقال, وهو يسلط الضوء على المشكلة التي يمكن أن يكون من الصعب تحديد نقاء وظيفة حتى مرة واحدة كنت قد دخلت عليه.