تحليل التدفق والتحسين للهياكل الشبيهة بلغة LISP

في 12، قدم المؤلفون مفهوم تحسين وقت الربط (binding time optimization) وقدموا سلسلة من أساليب تحليل تدفق البيانات لتحديد بعض خصائص وقت الربط للبرامج. في هذه الورقة البحثية، نقوم بتوسيع هذا العمل من خلال توفير أساليب لتحديد فئة الأشكال التي قد يتخذها كائن بيانات غير محدود أثناء تنفيذ برنامج شبيه بـ LISP، ونصف عدداً من الاستخدامات التي يمكن توظيف هذه المعلومات فيها لتحسين تخصيص التخزين في المترجمات والمفسرات للغات البرمجة المتقدمة. نحن معنيون بشكل رئيسي بإيجاد وصف محدود لمجموعة من المخططات لكل نقطة ومتغير في البرنامج، والتي تتضمن جميع أشكال القيم التي يمكن أن يتخذها المتغير عند تلك النقطة أثناء تنفيذ البرنامج. إذا كانت هذه المجموعة صغيرة أو منتظمة في بنيتها، فيمكن استخدام هذه المعلومات لتحسين تنفيذ البرنامج، بشكل رئيسي عن طريق استخدام مخططات تخصيص تخزين أكثر كفاءة. في الجزء الأول، نوضح كيفية البناء من برنامج دون تحديث انتقائي لقواعد شجرية تولد رموزها غير الطرفية مجموعات المخططات المطلوبة؛ وفي هذه الحالة ستكون جميعها أشجاراً. تكون قواعد الشجرة ذات شكل أكثر عمومية مما يُدرس عادةً في 8، 19، لذلك نوضح إمكانية تحويلها إلى الشكل المعتاد. يمكن اعتبار قواعد الشجرة الناتجة بشكل طبيعي تعريفاً تكرارياً للنوع 11 للقيم التي قد تتخذها المتغيرات. علاوة على ذلك، يمكن استخدام خوارزميات قياسية لاختبار اللانهائية أو الفراغ أو الخطية لبنية الشجرة. في الجزء الثاني، يُسمح بالتحديث الانتقائي، لذلك يتم تقديم دلالات بديلة تشبه إلى حد كبير تطبيقات LISP التقليدية، وتكافئ نموذج الشجرة للبرامج التي لا تحتوي على تحديث انتقائي. في هذا النموذج، تكون كائنات البيانات عبارة عن مخططات موجهة. نحن نبتكر طريقة تقريب محدودة توفر معلومات كافية للكشف عن مشاركة الخلايا والهياكل الدائرية متى أمكن حدوثها. يمكن استخدام هذه المعلومات للتعرف على الحالات التي يمكن فيها تجنب استخدام جمع القمامة (garbage collection) أو عدد المراجع (reference counts). العمل المذكور في الجزء الثاني من هذه الورقة يوسع عمل Schwartz 17 و Cousot and Cousot 7. لقد طوروا طرقاً لتحديد ما إذا كانت قيم متغيرين أو أكثر تشترك في خلايا، بينما نقدم نحن معلومات عن البنية التفصيلية لما تتم مشاركته. وتعد القدرة على اكتشاف الحلقات أمراً جديداً أيضاً. كما أنه يوسع عمل Kaplan 13، الذي يميز فقط العلاقات الثنائية بين متغيرات البرنامج، ولا يتعامل مع الحلقات، ولا يميز المحددات (بحيث ينطبق تحليله على العقد التي تمثل مجموعات بدلاً من الصفوف المرتبة).