اختبار الرجل أو الصبي

اقترح عالم الحاسوب دونالد كنوث اختبار "الرجل أو الصبي" كوسيلة لتقييم تطبيقات لغة البرمجة ALGOL 60. وكان الهدف من الاختبار هو التمييز بين المترجمات التي تُنفذ " الاستدعاء الذاتي والمراجع غير المحلية " بشكل صحيح وتلك التي لا تُنفذها. ^{[ 1 ]}

توجد العديد من مترجمات لغة ALGOL60 المصممة للتعامل مع الاستدعاء الذاتي والمراجع غير المحلية بشكل صحيح، وقد فكرتُ أن برنامج اختبار بسيط قد يكون مفيدًا. لذا، كتبتُ الروتين البسيط التالي، الذي قد يُساعد في التمييز بين المترجمين المحترفين والمترجمين المبتدئين.

في ALGOL 60 :

ابدأ الإجراء الحقيقي A ( k , x1 , x2 , x3 , x4 , x5 ) ؛ القيمة k ؛ عدد صحيح k ؛ أعداد حقيقية x1 , x2 , x3 , x4 , x5 ؛ ابدأ الإجراء الحقيقي B ؛ ابدأ k := k - 1 ؛ B := A := A ( k , B , x1 , x2 , x3 , x4 ) نهاية ؛ إذا كان k ≤ 0 فإن A : = x4 + x5 وإلا B نهاية ؛ outreal ( 1 , A ( 10 , 1 , -1 , -1 , 1 , 0 ) ) نهاية

ينتج عن ذلك شجرة من إطارات استدعاء B تشير إلى بعضها البعض وإلى إطارات استدعاء A الحاوية لها ، ولكل منها نسخة خاصة بها من k تتغير في كل مرة يتم فيها استدعاء B المرتبط بها . قد يكون من غير المجدي محاولة حلها على الورق، ولكن بالنسبة لـ k  =  10، فإن الإجابة الصحيحة هي -67، على الرغم من أن كنوت قد افترض في المقالة الأصلية أنها -121. حتى الأجهزة الحديثة تنفد مساحة الذاكرة المخصصة لها بسرعة عند القيم الأكبر لـ k ، والموضحة في الجدول أدناه ( OEIS : A132343  ).

ك	⁠${\displaystyle A(k,1,-1,-1,1,0)}$⁠
0	1
1	0
2	-2
3	0
4	1
5	0
6	1
7	-1
8	-10
9	-30
10	-67
11	-138
12	-291
13	-642
14	-1446
15	-3250
16	-7244
17	-16 065
18	-35601​
19	-78 985
20	-175 416
21	-389 695
22	−865 609
23	-1 922 362
24	-4 268 854
25	-9 479 595
26	-21 051 458

هناك ثلاث ميزات في لغة Algol مستخدمة في هذا البرنامج، والتي قد يصعب تنفيذها بشكل صحيح في المترجم:

1. تعريفات الدوال المتداخلة : بما أن الدالة B تُعرَّف في السياق المحلي للدالة A ، فإن جسم B لديه إمكانية الوصول إلى الرموز المحلية للدالة A ، وأبرزها k التي تُعدِّلها، بالإضافة إلى x1 و x2 و x3 و x4 و x5 . هذا الأمر بسيط في لغة باسكال ، وهي لغة مشتقة من لغة ألغول، ولكنه غير ممكن في لغة C ، وهي لغة مشتقة رئيسية أخرى من ألغول(دون محاكاة الآلية يدويًا باستخدام عامل عنوان C، وتمرير مؤشرات إلى المتغيرات المحلية بين الدوال).
2. مراجع الدوال : لا يُمثل B في الاستدعاء التكراريA(k, B, x1, x2, x3, x4)استدعاءً للدالة B ، بل مرجعًا إليها ، والتي سيتم استدعاؤها فقط عندما تكون قيمة k أكبر من الصفر. هذا واضح في لغة باسكال القياسية ( ISO 7185 )، وكذلك في لغة C. بعض إصدارات باسكال (مثل الإصدارات القديمة من Turbo Pascal ) لا تدعم مراجع الإجراءات، ولكن عندما تكون مجموعة الدوال التي يمكن الرجوع إليها معروفة مسبقًا (في هذا البرنامج، هي B فقط )، يمكن تجاوز هذه المشكلة.
3. ازدواجية الثوابت/الدوال : قد تكون المعاملات x1 إلى x5 للدالة A ثوابت عددية أو مراجع للدالة B ، x4 + x5ويجب تهيئة التعبير للتعامل مع كلتا الحالتين كما لو تم استبدال المعاملين x4 و x5 بالمعامل الفعلي المقابل ( استدعاء بالاسم ). ^{[ 3 ]} ربما تكون هذه مشكلة أكبر في اللغات ذات الكتابة الثابتة مقارنةً باللغات ذات الكتابة الديناميكية، ولكن الحل القياسي هو إعادة تفسير الثوابت 1 و 0 و -1 في الاستدعاء الرئيسي للدالة A كدوال بدون وسائط تُرجع هذه القيم.

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

• مشكلة فونارج
• جهاز جنسن

• أمثلة اختبار الرجل أو الصبي في العديد من لغات البرمجة