كيف تعمل اللغة stackless؟

Question

ولقد سمعت من اللغات stackless. ولكن ليس لدي أي فكرة كيف يمكن تنفيذ مثل هذه اللغة. يمكن للشخص أن يفسر؟

Answer 1

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

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

واحد مشكلة شائعة جميع هذه الطلبات لها هي، <م> "كيف كبيرة وينبغي أن يكون كومة بلدي؟" . مع ذاكرة يجري برخص التراب، ومعظمهم ما يحدث هو أن يتم تعيين جزء كبير جانبا لكومة (التخلف MS إلى 1MB)، وتطبيق نموذجي هيكل الدعوة لم يحصل في أي مكان بالقرب من استخدام عنه. ولكن إذا كان تطبيق لا استخدام كل شيء، فإنه يموت مع اشارة ذاكرة غير قانونية ( "أنا آسف ديف، لا أستطيع أن أفعل ذلك")، بحكم التوصل قبالة نهاية المكدس.

ومعظم ما يسمى دعا اللغات "stackless" ليست حقا stackless. انهم فقط لا تستخدم كومة متجاورة التي تقدمها هذه الأنظمة. ما يفعلونه بدلا من ذلك هو تخصيص إطار مكدس من كومة على كل استدعاء وظيفة. التكلفة لكل استدعاء دالة ترتفع إلى حد ما. إذا وظائف وعادة ما تكون معقدة، أو اللغة هو التفسير، وهذا تكلفة إضافية غير ذات أهمية. (واحد ويمكن أيضا تحديد DAGs الدعوة في الرسم البياني دعوة البرنامج وتخصيص جزء كومة لتغطية DAG بأكمله، وبهذه الطريقة يمكنك الحصول على كل تخصيص كومة وسرعة الكلاسيكية الوظائف كومة كبيرة تدعو لجميع المكالمات داخل الدعوة DAG) <. / P>

وهناك عدة أسباب لاستخدام تخصيص كومة كومة للإطارات:

1) إذا كان البرنامج لا العودية عميقة تعتمد على مشكلة معينة هو حل، فمن الصعب جدا أن preallocate منطقة "كومة كبيرة" مقدما لأنه لم يعرف حجم الحاجة. يمكن للمرء أن ترتيب برعونة تدعو ظيفة لتحقق لمعرفة ما إذا كان هناك ما يكفي من كومة اليسار، وإذا لم يكن كذلك، إعادة تخصيص جزء أكبر، نسخ كومة القديم وتعديل جميع المؤشرات في كومة. هذا صعب لدرجة أنني لا أعرف من أي تطبيقات. تخصيص إطارات كومة يعني تطبيق أبدا أن أقول لها آسف حتى هناك حرفيا لا تترك ذاكرة allocatable.

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

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

PARLANSE الناطقة البرمجة I نفذت يفعل 1) و 2). أنا أعمل على 3).

Answer 2

Stackless بيثون لا يزال لديه كومة بيثون (على الرغم من أنه قد يكون الأمثل دعوة الذيل وغيرها من إطار الدعوة دمج الحيل )، لكنه مطلقة تماما من المكدس C المترجم.

وهاسكل (كما هو مطبق عادة) لايوجد مكدس الاستدعاءات. ويستند التقييم على تخفيض الرسم البياني .

Answer 3

وهناك مادة لطيفة حول الإطار الببغاء لغة في HTTP: // شبكة الاتصالات العالمية .linux-mag.com / مخبأ / 7373 / 1.html . ببغاء لا يستخدم كومة للدعوة ويشرح هذا المقال تقنية قليلا.

Answer 4

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

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

وتحرير: أنا أعرف بعض أبنية لها مداخن مخصصة، لكنها ليست ضرورية

.

Answer 5

وهناك وسيلة سهلة لفهم وصف استمرارا على هذا المقال: HTTP: // شبكة الاتصالات العالمية. defmacro.org/ramblings/fp.html

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

Answer 6

ويقول كنت تريد تنفيذ stackless C. أول شيء يجب أن ندرك أن هذا لا يحتاج الى كومة:

a == b

ولكن، هل هذا؟

isequal(a, b) { return a == b; }

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

وماذا عن العودية؟ ليس هناك أى مشكلة. وظيفة الذيل العودية مثل:

bang(x) { return x == 1 ? 1 : x * bang(x-1); }

لا يزال من الممكن inlined، لأن حقا انها مجرد لحلقة في تمويه:

bang(x) {
    for(int i = x; i >=1; i--) x *= x-1;
    return x;
}

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

ax = x;
NOTDONE:
if(ax > 1) {
    x = x*(--ax);
    goto NOTDONE;
}

وهناك حالة واحدة حيث لديك لجعل التجارة صغيرة قبالة. لا يمكن inlined هذا:

fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }

وStackless C ببساطة لا تستطيع أن تفعل هذا. هل التخلي عن الكثير؟ ليس صحيحا. هذا شيء طبيعي C لا تستطيع أن تفعل جيدا إما جدا. إذا كنت لا تصدقني مجرد دعوة fib(1000) وانظر ماذا يحدث للكمبيوتر الخاص بك الثمينة.

Answer 7

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

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

ومن الواضح أن لا يعمل مع المكالمات عودي. (وذاكرتي هو أن المترجم CDC FORTRAN IV من شأنه أن يولد كود كسر إذا فعلتم محاولة العودية ...)

Answer 8

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