آلة SECD

آلة SECD هي آلة افتراضية وآلة مجردة مؤثرة، مصممة لتكون هدفًا لمترجمات لغات البرمجة الوظيفية . تشير الأحرف إلى السجلات الداخلية للآلة، وهي على التوالي: و ، و ، و . تشير السجلات و و إلى (بعض تطبيقات) المكدسات ، بينما يشير السجل إلى (بعض تطبيقات) المصفوفة الترابطية .stackenvironmentcontroldumpstackcontroldumpenvironment

كانت هذه الآلة أول آلة مصممة خصيصًا لتقييم تعابير حساب التفاضل والتكامل لامدا . وقد وصفها بيتر لاندين في الأصل في كتابه "التقييم الميكانيكي للتعابير" عام 1964. ^{[ 1 ]} كان الوصف الذي نشره لاندين مجردًا إلى حد ما، وترك العديد من خيارات التنفيذ مفتوحة (مثل الدلالات التشغيلية ).

كانت لغة Lispkit عبارة عن مترجم برمجي يعتمد على جهاز SECD، ^{[ 2 ]} وقد استُخدم جهاز SECD كهدف لأنظمة أخرى مثل Lisp / 370 . ^{[ 3 ]} في عام 1989، عمل باحثون في جامعة كالجاري على تطبيق مادي للجهاز، بنفس المنطق الذي استندت إليه بنية حاسوبية للغة عالية المستوى مرتبطة بجهاز Lisp . ^{[ 4 ]}

يشير دي. إيه. تيرنر (2012) ^{[ 5 ]} إلى أن لغة البرمجة ALGOL 60 لم تكن قادرة على إرجاع دوال من دوال أخرى (مما يجعل الدوال غير من الدرجة الأولى). إذ يمكن لدالة متداخلة داخل دالة أخرى أن تشير إلى متغير موجود على مكدس الدالة الخارجية. وإذا تم إرجاع الدالة المتداخلة من الدالة الخارجية، فإنها ستشير إلى متغير في إطار مكدس لم يعد موجودًا. ويلاحظ تيرنر أن آلة SECD الخاصة بلاندين تحل هذه المشكلة (مما يسمح للدوال بإرجاع دوال أخرى)، حيث يتم الآن تمثيل قيمة الدالة بإغلاق على الكومة يمكنه تخزين بيئة المتغيرات التي يجب استخدامها بغض النظر عما يحدث على المكدس. ^{[ 5 ]}

عند بدء تقييم تعبير ما، يتم تحميل هذا التعبير كعنصر التحكم الوحيد . وتبدأ Cالبيئة Eوالمكدس Sوالتفريغ فارغة.D

أثناء التقييم، Cيتم تحويلها إلى تدوين بولندي معكوس (RPN) حيث يكون ap(للتطبيق ) هو العامل الوحيد. على سبيل المثال، يتم تغيير التعبير F (G X)(عنصر قائمة واحد) إلى القائمة X:G:ap:F:ap.

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

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

إذا كان التطبيق عبارة عن تجريد لقيمة، فسينتج عنه تعبير حسابي لامدا قد يكون تطبيقًا بحد ذاته (بدلاً من قيمة)، وبالتالي لا يمكن إضافته إلى المكدس. في هذه الحالة، تُضاف المحتويات الحالية لـ و و إلى المخزن المؤقت S( Eوهو عبارة عن مكدس من هذه الثلاثيات)، ويُعاد تهيئة إلى فارغة، ويُعاد تهيئة إلى نتيجة التطبيق مع التي تحتوي على بيئة المتغيرات الحرة لهذا التعبير، مُضافًا إليها الربط الناتج عن التطبيق. ثم يستمر التقييم كما هو موضح أعلاه.CDSCE

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

إذا Cكانت Dكلتاهما فارغتين، فإن التقييم الإجمالي قد اكتمل مع وجود النتيجة على المكدس S.

تعتمد آلة SECD على نظام المكدس . تأخذ الدوال وسائطها من المكدس. يتم ترميز وسائط التعليمات المضمنة مباشرة بعدها في سلسلة التعليمات.

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

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

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

يُستخدم سجل التفريغ، الذي يشير إليه رأس Dالسجل، كمخزن مؤقت لقيم السجلات الأخرى، على سبيل المثال أثناء استدعاء الدوال. ويمكن تشبيهه بمكدس الإرجاع في الآلات الأخرى.

يُشابه تنظيم الذاكرة في جهاز SECD النموذج المُستخدم في معظم مُفسّرات لغات البرمجة الوظيفية : عدد من خلايا الذاكرة، يُمكن لكل منها أن تحتوي إما على قيمة عددية (قيمة بسيطة، مثل 13 )، أو على قائمة فارغة أو غير فارغة. في الحالة الأخيرة، تحتوي الخلية على مؤشرين إلى خلايا أخرى، أحدهما يُمثل العنصر الأول، والآخر يُمثل القائمة باستثناء العنصر الأول. يُطلق على هذين المؤشرين تقليديًا اسمي car و cdr على التوالي، ولكن غالبًا ما يُستخدم المصطلحان الحديثان head و tail . يتم تمييز أنواع القيم المختلفة التي يُمكن أن تحتويها الخلية بواسطة وسم . كما يتم غالبًا تمييز أنواع القيم المختلفة (الأعداد الصحيحة، والسلاسل النصية، وما إلى ذلك).

لذا، يمكن تمثيل قائمة تحتوي على الأرقام 1 و 2 و 3 ، والتي تُكتب عادةً على النحو التالي:(1 2 3)

محتوى علامة العنوان (القيمة للأعداد الصحيحة، و car و cdr للقوائم) 9 [ عدد صحيح | 2 ] 8 [ عدد صحيح | 3 ] 7 [ قائمة | 8 | 0 ] 6 [ قائمة | 9 | 7 ] ... 2 [ قائمة | 1 | 6 ] 1 [ عدد صحيح | 1 ] 0 [ لا شيء ]

لا تنتمي خلايا الذاكرة من 3 إلى 5 إلى قائمتنا، التي يمكن توزيع خلاياها عشوائيًا في الذاكرة. الخلية 2 هي رأس القائمة، وتشير إلى الخلية 1 التي تحتوي على قيمة العنصر الأول، وإلى القائمة التي تحتوي على العنصرين 2 و 3 فقط (بدءًا من الخلية 6). تشير الخلية 6 إلى خلية تحتوي على القيمة 2، وإلى الخلية 7 التي تمثل القائمة التي تحتوي على العنصر 3 فقط . ويتم ذلك بالإشارة إلى الخلية 8 التي تحتوي على القيمة 3 ، وإلى قائمة فارغة ( nil ) كـ cdr. في جهاز SECD، تمثل الخلية 0 دائمًا القائمة الفارغة ضمنيًا، لذا لا حاجة إلى قيمة علامة خاصة للإشارة إلى قائمة فارغة (يمكن لأي شيء يحتاج إلى ذلك ببساطة الإشارة إلى الخلية 0).

إن مبدأ أن يشير cdr في خلية القائمة إلى قائمة أخرى هو مجرد اصطلاح. إذا كان كل من car و cdr يشيران إلى ذرات، فسينتج عن ذلك زوج، يُكتب عادةً على النحو التالي:(1 . 2)

• nilيدفع مؤشرًا فارغًا إلى المكدس
• ldcيدفع وسيطًا ثابتًا إلى المكدس
• ldيدفع قيمة متغير إلى المكدس. يُشار إلى المتغير بواسطة الوسيط، وهو زوج. يحدد الجزء car من الزوج المستوى، بينما يحدد الجزء cdr الموضع. لذا، (1 . 3)يُعطي هذا الوسيط الثالث للدالة الحالية (المستوى 1).
• selتتوقع هذه الدالة وسيطين من نوع قائمة، وتقوم بسحب قيمة من المكدس. يتم تنفيذ القائمة الأولى إذا كانت القيمة المسحوبة غير فارغة، وإلا يتم تنفيذ القائمة الثانية. قبل إنشاء أحد مؤشري القائمة C، يتم إنشاء مؤشر جديد إلى التعليمات التالية.${\displaystyle sel}$يتم حفظها في ملف التفريغ.
• joinيستخرج مرجع القائمة من الذاكرة ويجعله القيمة الجديدة لـ C. يتم تنفيذ هذه التعليمات في نهاية كلا البديلين لـ sel.
• ldfتأخذ هذه الدالة وسيطًا واحدًا على شكل قائمة يمثل دالة. تقوم بإنشاء إغلاق (زوج يحتوي على الدالة والبيئة الحالية) وتدفعه إلى المكدس.
• apيسحب هذا الأمر دالة مغلقة وقائمة بقيم المعاملات من مكدس الاستدعاءات. تُطبَّق الدالة المغلقة على المعاملات عن طريق تثبيت بيئتها كبيئة حالية، ودفع قائمة المعاملات أمامها، ومسح مكدس الاستدعاءات، وتعيين مؤشر الدالةC للدالة المغلقة . تُحفظ القيم السابقة لـ ، والقيمة التالية لـ في ذاكرة التخزين المؤقت.SEC
• retيقوم بسحب قيمة إرجاع واحدة من المكدس، واستعادة S، Eو Cمن التفريغ، ودفع قيمة الإرجاع إلى المكدس الحالي.
• dumيدفع "وهميًا"، أي قائمة فارغة، أمام قائمة البيئة.
• rapيعمل مثل${\displaystyle ap}$، فقط أنها تستبدل حالة بيئة وهمية بالحالة الحالية، مما يجعل الدوال المتكررة ممكنة

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

• آلة CEK
• آلة كريفين

• دانفي، أوليفييه . تفكيك منطقي لآلة لاندين SECD . تقرير بحثي لمجموعة البريكس RS-04-30، 2004. ISSN 0909-0878
• فيلد، أنتوني ج. فيلد وبيتر ج. هاريسون. 1988 البرمجة الوظيفية . أديسون-ويسلي. ISBN 0-201-19249-7
• غراهام، برايان ت. 1992. "معالج SECD الدقيق: دراسة حالة للتحقق". سبرينغر. ISBN 0-7923-9245-0
• كوجي، بيتر م. هندسة الحواسيب الرمزية . ISBN 0-07-035596-7
• لاندين، بي جيه (مارس 1966). "لغات البرمجة الـ 700 التالية" (ملف PDF) . مجلة اتصالات رابطة مكائن ​​الحوسبة . 9 (3): 157-166 . doi : 10.1145/365230.365257 . S2CID 13409665. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 20 يونيو 2010. تاريخ الاسترجاع : 28 أغسطس 2015 . 

• هوس SECD ، المجموعة الكاملة