هي البرامج في اللغات الوظيفية أكثر عرضة للتفيضات المكدس؟

Question

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

إذا كانت OCAML تستخدم المكدس لمكالمات الوظيفة، فلن تضعف في النهاية المكدس؟ على سبيل المثال، إذا كان لدي الوظيفة التالية:

let rec sum x =
  if x > 1 then f(x - 1) + x
  else x;;

يجب أن يسبب في نهاية المطاف فائض المكدس. إذا كنت أقوم بفعل شيء ما يعادله في C ++ (باستخدام العودية)، فأنا أعلم أنه سيتفوق.

لذلك سؤالي هو، هل هناك بنيت في ضمانات لمنع اللغات الوظيفية من تفيض المكدس؟ إذا لم يكن الأمر كذلك، فلن تكون أقل فائدة مثل هذا، نظرا لأن خوارزمية التمويل أعلاه، مكتوبة بأسلوب إجرائي مع حلقة من أجل حلقة، يمكن أن تتعامل مع أي عدد (DIS فيما يتعلق بضغط عدد صحيح)؟

Answer 1

جميع (تطبيقات لائقة من ؛-) اللغات الوظيفية تحسين العودية الذيل، ولكن هذا ليس ما تفعله هنا، لأن المكالمة العودية ليست هي العملية الأخيرة (يجب أن يتبعها الإضافة).

لذلك، يتعلم أحدهم قريبا استخدام وظيفة مساعدة من الذيل العودية (وتأخذ مجموعها الحالي كوسخة) لذلك يمكن للمحسن القيام بعمله، أي صافي بناء جملة O'Caml المحتمل الذي أنا صدئ:

let sum x =
  aux(x)(0);;

let rec aux x accum =
  if x > 1 then aux(x - 1)(accum + x)
  else (accum + x);;

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

Answer 2

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

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

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

let rec sum x =
  let sum_aux accum x =
    if x > 1 then sum_aux (accum + x) (x - 1)
    else x
  in sum_aux 0 x;;

Answer 3

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

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

Answer 4

من السهل بالتأكيد أن تكون المبتدئين لكتابة recursions العميقة التي تفجر المكدس. الهدف الهدف غير عادي في ذلك المكتبة List الوظائف ليست آمنة مكدس للقوائم الطويلة. وبعد تطبيقات مثل انسجام لقد استبدلت فعلا قياسي CAML List مكتبة مع نسخة آمنة مكدس. معظم التطبيقات الأخرى تفعل وظيفة أفضل مع المكدس. (إخلاء المسئولية: توضح معلوماتي الهدف CAML 3.08؛ الإصدار الحالي، 3.11، قد يكون أفضل.)

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

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

Answer 5

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