لماذا لا تستخدم اللغات الوظيفية بحتة عد المرجع؟

Question

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

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

Answer 1

يستند سؤالك إلى افتراض معيب. من الممكن تماما الحصول على مراجع دائرية وبيانات ثابتة. النظر في مثال C # التالي الذي يستخدم بيانات ثابتة لإنشاء مرجع دائري.

class Node { 
  public readonly Node other;
  public Node() { 
    other = new Node(this);
  }
  public Node(Node node) {
    other = node;
  }
}

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

تحرير من قبل ephemient

ردا على التعليق ... هذا تافهة في Haskell

data Node a = Node { other :: Node a }
recursiveNode = Node { other = recursiveNode }

وبالكاد أكثر جهد في SML.

datatype 'a node = NODE of unit -> 'a node
val recursiveNode : unit node =
    let fun mkRecursiveNode () = NODE mkRecursiveNode
    in mkRecursiveNode () end

لا طفرة مطلوبة.

Answer 2

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

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

تميل العد المرجعي إلى القيام به جيدا في المواقف مثل هذه:

• يتم استخدام جميع الذاكرة الكومة تقريبا لعقد كائنات حية.
• تخصيص ومحالة المؤشر نادرة بالنسبة للعمليات الأخرى.
• يمكن إدارة المراجع على معالج آخر أو جهاز كمبيوتر.

لفهم كيف تعمل أنظمة عد مريح عالية الأداء اليوم، ابحث عن عمل ديفيد لحم الخنزير المقدد و إيرز بترانك.

Answer 3

هناك بعض الأشياء، كما أعتقد.

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

(ذات مرة أعتقد أنني ربما "عرفت" هذا، لكن الآن أحاول أن أتذكر / التكهن، لذلك لا تأخذ هذا كأي سلطة.)

Answer 4

انصح هذا الرمز قال عن ديفيد مون, مخترع من آلة lisp:

في أحد الأيام جاء الطالب إلى القمر وقال: "أنا أفهم كيفية جعل جامع القمامة أفضل. يجب أن نحافظ على عدد مرجعي من المؤشرات إلى كل سلبيات".

أخبر القمر بصبر الطالب القصة التالية:

"يوم واحد جاء الطالب إلى القمر وقال:" أفهم كيفية جعل جامع القمامة أفضل ...

Answer 5

أنا على حق؟

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

let rec xs = 0::ys and ys = 1::xs

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

إذا كان الأمر كذلك، لماذا لا؟

بعض اللغات تحظر دورات واستخدام العد المرجعي. Erlang والرياضياتية هي أمثلة.

على سبيل المثال، في Mathematica عند الرجوع إلى قيمة تقوم بعمل نسخة عميقة منه، لا يتحور التصويت الأصلي النسخة:

In[1] := xs = {1, 2, 3}
Out[1] = {1, 2, 3}

In[2] := ys = xs
Out[2] = {1, 2, 3}

In[3] := xs[[1]] = 5
Out[3] = 5

In[4] := xs
Out[4] = {5, 2, 3}

In[5] := ys
Out[5] = {1, 2, 3}

Answer 6

العد المرجعي أبطأ بكثير من GC لأنه ليس جيدا ل CPU. و GC معظم الوقت يمكن أن تنتظر وقت الخمول وأيضا يمكن أن تكون GC متزامنة (على موضوع آخر). هذه هي المشكلة - GC هو أقل الشر والكثير من المحاولات التي أظهرت ذلك.