كيفية تنفيذ الاستمرارية؟

Question

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

ما هي أبسط طريقة لتنفيذ استمرارية المخطط في C؟

Answer 1

أذكر أنني قرأت مقالاً قد يفيدك: تشيني على M.T.A. :-)

بعض تطبيقات المخطط التي أعرفها، مثل SISC, ، قم بتخصيص إطارات الاستدعاء الخاصة بهم على الكومة.

@ollie:لا تحتاج إلى القيام بالرفع إذا كانت جميع إطارات الاتصال الخاصة بك موجودة في الكومة.هناك مقايضة في الأداء بالطبع:وقت الرفع، مقابل الحمل المطلوب لتخصيص كافة الإطارات في الكومة.ربما ينبغي أن تكون معلمة وقت تشغيل قابلة للضبط في المترجم.:-ص

Answer 2

ملخص جيد متاح في استراتيجيات التنفيذ لاستمرارية من الدرجة الأولى, ، مقال بقلم كلينجر وهارثيمر وأوست.أوصي بالنظر في تنفيذ Chez Scheme على وجه الخصوص.

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

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

Answer 3

إذا كنت تبدأ من الصفر، فيجب عليك حقًا النظر في تحويل أسلوب التمرير المستمر (CPS).

تشمل المصادر الجيدة "LISP في قطع صغيرة" و مخطط مارك فيلي في عرض مدته 90 دقيقة.

Answer 4

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

ر.كينت ديبفيج.“ثلاثة نماذج تنفيذية للمخطط”.http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

تحقق أيضًا من أوراق التنفيذ على ReadScheme.org.http://library.readscheme.org/page8.html

الملخص هو كما يلي:

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

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

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

يخصص النموذج القائم على السلسلة إصدارات من هذه الهياكل مباشرة في نص البرنامج ، والذي يتم تمثيله كسلسلة من الرموز.في النموذج القائم على السلسلة ، يتم ترجمة برامج المخطط إلى لغة FFP مصممة خصيصًا لدعم المخطط.يتم تنفيذ البرامج في هذه اللغة مباشرة بواسطة آلة FFP ، وهو جهاز كمبيوتر متعدد المعالجات.

النموذج القائم على المكدس ذو فائدة عملية فورية؛إنه النموذج الذي يستخدمه نظام مخطط Chez الخاص بالمؤلف ، وهو تطبيق عالي الأداء للمخطط.سيكون النموذج المستند إلى السلسلة مفيدًا لتوفير المخطط كبديل عالي المستوى لـ FFP على جهاز FFP بمجرد تحقيق الجهاز.

Answer 5

إلى جانب الإجابات اللطيفة التي حصلت عليها حتى الآن، أوصي بإجابات Andrew Appel التجميع مع الاستمرارات.إنها مكتوبة بشكل جيد للغاية وعلى الرغم من أنها لا تتعامل مباشرة مع لغة C، إلا أنها مصدر لأفكار رائعة حقًا لكتاب المترجمات.

يحتوي موقع Chicken Wiki أيضًا على صفحات ستجدها مثيرة جدًا للاهتمام، مثل الهيكل الداخلي و عملية التجميع (حيث يتم شرح CPS بمثال فعلي للتجميع).

Answer 6

الأمثلة التي يمكنك الاطلاع عليها هي: فرخة (تنفيذ مخطط مكتوب بلغة C يدعم الاستمرارية)؛بول جراهام على ليسب - حيث يقوم بإنشاء محول CPS لتنفيذ مجموعة فرعية من الاستمرارات في Common Lisp؛و كتل الويب - إطار ويب قائم على الاستمرارية، والذي ينفذ أيضًا شكلاً محدودًا من الاستمرارات في Common Lisp.

Answer 7

الاستمرارية ليست هي المشكلة:يمكنك تنفيذ تلك ذات الوظائف العادية ذات الترتيب الأعلى باستخدام CPS.المشكلة في تخصيص المكدس الساذج هي أن الاستدعاءات الخلفية لا يتم تحسينها أبدًا، مما يعني أنه لا يمكن أن تكون مخططًا.

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

هناك بعض التعليمات البرمجية توضيح هاتين الفكرتين.

Answer 8

الطريقة التقليدية هي الاستخدام setjmp و longjmp, ، على الرغم من وجود محاذير.

وهنا أ تفسير جيد إلى حد معقول

Answer 9

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

يتم تنفيذ الاستمرارات بشكل تافه باستخدام الألياف. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29.الأشياء الوحيدة التي تحتاج إلى تغليف دقيق هي تمرير المعلمات وقيم الإرجاع.

في نظام التشغيل Windows، يتم تنفيذ الألياف باستخدام عائلة المكالمات CreateFiber/SwitchToFiber.في الأنظمة المتوافقة مع Posix، يمكن القيام بذلك باستخدام makecontext/swapcontext.

يحتوي Boost::coroutine على تطبيق عملي لـ coroutines لـ C++ والذي يمكن أن يكون بمثابة نقطة مرجعية للتنفيذ.

Answer 10

استخدم مكدسًا صريحًا بدلاً من ذلك.

Answer 11

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

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

Answer 12

مثل soegaard وأشار، ويبقى المرجع الرئيسي هذا

الفكرة هي أن الاستمرار هو إغلاق يحافظ على مجموعة التحكم في التقييم الخاصة به.إن مكدس التحكم مطلوب لمواصلة التقييم من لحظة إنشاء الاستمرارية باستخدام call/cc.

يؤدي استدعاء الاستمرارية في كثير من الأحيان إلى إطالة وقت التنفيذ ويملأ الذاكرة بمكدسات مكررة.لقد كتبت هذا الكود الغبي لإثبات أنه في mit-scheme يؤدي إلى تعطل المخطط،

يقوم الكود بجمع أول 1000 رقم 1+2+3+...+1000.

(call-with-current-continuation 
 (lambda (break)
   ((lambda (s) (s s 1000 break))
    (lambda (s n cc)
      (if (= 0 n)
          (cc 0)
          (+ n
             ;; non-tail-recursive,
             ;; the stack grows at each recursive call
             (call-with-current-continuation
              (lambda (__)
                (s s (- n 1) __)))))))))

إذا قمت بالتبديل من 1000 إلى 100000، فسوف يستغرق الرمز ثانيتين، وإذا قمت بزيادة رقم الإدخال فسوف يتعطل.