الخلاصة

  • نقلت Frances E. Allen تحسين البرامج من حيل متفرقة لزيادة السرعة إلى تحليل منضبط لمسارات التحكم والتعريفات والاستخدامات.
  • تعطي الفواصل وتعريفات الوصول وتحليلات الحيوية حقائق ساكنة مشروطة؛ فهي ليست سجلاً لتنفيذ فعلي ولا ضماناً ضد السلوك غير المعرّف أو سباق البيانات أو عدم الاستقرار العددي.
  • ينبغي حفظ إسهام Allen إلى جانب أعمال John Cocke وReese T. Prosser وE. S. Lowry وC. W. Medlock وKenneth Kennedy وفرق Stretch وHarvest وACS.

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

ساعدت Frances E. Allen في تحويل هذا الإذن إلى نتيجة يمكن حسابها ومراجعتها. يسجل تاريخ IBM أنها انضمت إلى الشركة عام 1957 لتدريس FORTRAN للعلماء الجدد، ثم عملت في Stretch–Harvest ومشروع Advanced Computing Systems التجريبي. وفي 2006 كرّمتها ACM بجائزة Turing لمساهماتها الرائدة في نظرية وتقنيات المترجمات المحسّنة، وكانت أول امرأة تحصل عليها.

لكن عبارة «اخترعت Allen التحسين» أوسع من الحقيقة المفيدة. منحت أعمالها المترجم طريقة ليصرح بما يعرفه، وتحت أي افتراضات، وإلى أي حد.

رسم للمسارات الممكنة

يمثل بحث Control Flow Analysis لعام 1970 الكتل الأساسية كعقد، وانتقالات التحكم الممكنة كحواف موجهة. الكتلة الأساسية في النموذج سلسلة خطية لها مدخل واحد ومخرج واحد.

الحافة ليست سجل تشغيل. إنها تقول إن التحكم يمكن أن ينتقل، لا أن تنفيذاً بعينه انتقل فعلاً. هنا يبدأ حد الدليل.

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

يوزع البحث الفضل بدقة. تنسب Allen إلى Reese T. Prosser العمل المبكر على مصفوفات الاتصال وإدخال مفهوم الهيمنة، وإلى E. S. Lowry وC. W. Medlock توسيع دراسة الهيمنة، وإلى John Cocke بناء الفاصل. لم تكن مساهمتها في محو هذه الجذور، بل في وصلها بمنهج هندسي قابل للتطبيق.

إمكان الوصول لا يعني حدوثه

شرح Allen وCocke في 1976 بحث A Program Data Flow Analysis Procedure. يحسب الإجراء التعريفات التي قد تصل إلى كل عقدة، والتعريفات الحية على كل حافة.

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

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

يجمع الإجراء ترتيب الحواف حسب الفواصل مع متجهات البتات، ويتعامل مع الرسوم القابلة وغير القابلة للاختزال في إطار واحد. وينسب النص خوارزمية تحليل الحيوية إلى Kenneth Kennedy، وأفكار بنى البيانات إلى Richard Stasko، ويذكر مساهمات Ullman وHecht وKildall وSchaefer وSchwartz وغيرهم.

الكتالوج ليس حَكَماً على أفضل نتيجة مطلقة

نظم A Catalogue of Optimizing Transformations لـAllen وCocke إزالة العبارات الفرعية المشتركة ونقل الشيفرة وخفض كلفة العمليات وحذف التكرار. أكد المؤلفان أن الكتالوج غير شامل، وأن كلمة «تحسين» قد تكون مضللة حين لا يوجد حد أمثل عام. كان التركيز أساساً على زمن التنفيذ ثم المساحة، لا على كل كلفة تشغيلية أو قابلية الصيانة.

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

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

حفظ الدلالة لا يثبت صحة البرنامج كله

حتى لو وفّى المحسّن بالتزامه كاملاً، قد يستدعي المصدر سلوكاً غير معرّف لإدخال ما، أو يحتوي سباقاً بين خيطين، أو يضخم خطأ التقريب، أو يطبق مطلباً خاطئاً. لا يرتفع برهان المترجم تلقائياً ليصدق هذه الطبقات.

هذا الحد قوة لا عيب. يمكن للتحليل الجيد أن يقول: مع هذا الرسم وهذه التعريفات والاستخدامات وهذه الشروط الدلالية، تصح هذه العلاقة. يبدأ الخطر حين تختصر المؤسسة الجملة إلى ضوء أخضر اسمه «صحيح».

تحتاج سيرة Allen إلى الدقة نفسها. تصفها IBM كمصممة ووسيط لغة في Stretch–Harvest وشخصية مركزية في عمل مترجم ACS. يربط ملف IEEE Computer Society بين تقرير Program Optimization لعام 1966 وعمل الفواصل والكتالوج. ويحفظ ملف ACM الخاص بـJohn Cocke مساهماته المستقلة. حولت فرق العتاد واللغات والمترجمات التجريدات إلى أنظمة عاملة.

لم يكن إرث Allen مترجماً يدعي معرفة كل شيء، بل مترجماً يستطيع أن يقول بدقة ما أثبته.

المصادر