ما هي الطريقة القياسية لتحسين التكرار المتبادل في F#/Scala؟

Question

لا تدعم هذه اللغات تحسين الوظائف المتكررة بشكل متبادل "أصلاً" ، لذلك أعتقد أنه يجب أن يكون الترامبولين أو .. هيه .. إعادة الكتابة كحلقة) هل أفتقد شيئًا؟

تحديث: يبدو أنني كنت أكذب بشأن FSHARP ، لكنني لم أر مثالًا على مكالمات التيل المتبادلة أثناء غوغلينغ

Answer 1

بادئ ذي بدء ، يدعم F# الوظائف العودية المتبادلة أصلاً ، لأنه يمكن أن يستفيد من tailcall التعليمات المتوفرة في .NET IL (MSDN). ومع ذلك ، هذا أمر صعب بعض الشيء وقد لا يعمل على بعض التطبيقات البديلة لـ .NET (مثل الأطر المدمجة) ، لذلك قد تحتاج أحيانًا إلى التعامل مع هذا باليد.

بشكل عام ، أنا أن هناك طريقتان للتعامل معها:

• الترامبولين - قم بإلقاء استثناء عندما يكون عمق العودية مرتفعًا جدًا وينفذ حلقة المستوى الأعلى تعالج الاستثناء (الاستثناء سيحمل معلومات لاستئناف المكالمة). بدلاً من الاستثناء ، يمكنك أيضًا إرجاع قيمة تحدد أن الوظيفة يجب استدعاؤها مرة أخرى.

• استرخ باستخدام المؤقت - عندما يكون عمق التكرار مرتفعًا جدًا ، يمكنك إنشاء مؤقت ومنحه رد اتصال سيطلق عليه الموقت بعد فترة قصيرة جدًا (سيواصل المؤقت العودية ، ولكن سيتم إسقاط المكدس المستخدم).

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

لإعطاء مثال محدد على التقنية الأولى ، في F# يمكنك كتابة هذا:

type Result<´T> =
  | Done of ´T
  | Call of (unit -> ´T)

let rec factorial acc n = 
  if n = 0 then Done acc
  else Call(fun () -> factorial (acc * n) (n + 1))

يمكن استخدام هذا للوظائف العودية المتبادلة أيضًا. الحلقة الضرورية ستدعو ببساطة f وظيفة مخزنة في Call(f) حتى تنتج Done مع النتيجة النهائية. أعتقد أن هذا ربما يكون أنظف طريقة لتنفيذ هذا.

أنا متأكد من أن هناك تقنيات متطورة أخرى للتعامل مع هذه المشكلة ، لكن هذان هما هما هما اللتان أعرفهما (وقد استخدمتهما).

Answer 2

على Scala 2.8 ، scala.util.control.TailCalls:

import scala.util.control.TailCalls._ 

def isEven(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) 
    done(true) 
  else 
    tailcall(isOdd(xs.tail)) 

def isOdd(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) 
    done(false) 
  else 
    tailcall(isEven(xs.tail)) 

isEven((1 to 100000).toList).result

Answer 3

فقط للحصول على الكود في متناول يديك عندما تكون bing for f# recursion المتبادل:

let rec isOdd x =
    if x = 1 then true else isEven (x-1)
and isEven x = 
    if x = 0 then true else isOdd (x-1)

printfn "%A" (isEven 10000000)

سيؤدي ذلك إلى StackOverflow إذا قمت بتجميع بدون مكالمات Tail (وضع الافتراضي في وضع "Debug" ، والذي يحافظ على المكدس لأصحاب الأخطاء الأسهل) ، ولكن يتم تشغيله بشكل جيد عند تجميعه مع مكالمات الذيل (الافتراضي في وضع "الإصدار"). يقوم المترجم بالمكالمات الذيل افتراضيًا (انظر -خيار-tailcalls) ، و .NET تطبيقات على معظم المنصات تكريمها.