شجرة المؤشر الأبوية

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

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

يقوم مُصرّف لغة مثل C بإنشاء مكدس مُعقد (spaghetti stack) عند فتح وإغلاق جداول الرموز التي تُمثل نطاقات الكتل . عند فتح نطاق كتلة جديد، يُضاف جدول رموز إلى المكدس. وعند مُصادفة القوس المُعقّف المُغلق، يُغلق النطاق ويُزال جدول الرموز. ولكن يتم الاحتفاظ بجدول الرموز هذا، بدلاً من حذفه، ويحتفظ بجدول الرموز "الأب" ذي المستوى الأعلى، وهكذا. وبالتالي، عندما يُجري المُصرّف لاحقًا عمليات ترجمة على شجرة بناء الجملة المجردة ، فإنه يستطيع، لأي تعبير مُعطى، جلب جدول الرموز الذي يُمثل بيئة ذلك التعبير، وحلّ المراجع إلى المُعرّفات. إذا كان التعبير يُشير إلى مُتغير X، فإنه يبحث عنه أولاً في جدول الرموز الطرفي الذي يُمثل النطاق المعجمي الأعمق، ثم في جدول الرموز الأب، وهكذا.

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

من أمثلة اللغات التي تستخدم هياكل البيانات المعقدة (spaghetti stacks):

• اللغات التي تتمتع باستمرارات من الدرجة الأولى مثل Scheme و Standard ML of New Jersey
• اللغات التي يمكن فيها فحص وتعديل مكدس التنفيذ أثناء التشغيل مثل
  • أحاديث قصيرة
  • فيليكس
  • سيلك

تستطيع الحواسيب المركزية التي تستخدم بنية مجموعة التعليمات الخاصة بجهاز Burroughs B6500 وما تلاه ، والتي تعمل بنظام التشغيل MCP ، إنشاء مهام متعددة ضمن البرنامج نفسه. ولأن هذه الأنظمة كانت في الأصل مبنية على لغة ALGOL، فإنها تدعم الدوال المتداخلة ، مما ينتج عنه تفرع في مكدس التعليمات، وهو ما وصفه Burroughs بشكل غير رسمي بـ"مكدس الصبار".

• بنية بيانات ثابتة