متتبع أشعة بلغة Brainfuck: برنامج بحجم 23MB وبيكسل واحد في الدقيقة

اعتبر كاتب مدونة epestr.com سطرًا في دليل CMake بمثابة تحدٍّ: فقد كُتبت متتبعات الأشعة حتى بلغة CMake Language، وإن لم يكن ذلك ممارسة موصى بها. وكان قد كتب متتبع أشعة وأعاد كتابته لوحدة GPU، فاختار Brainfuck التي يصفها بأنها أبسط لغة يعرفها، وعزم على إعادة إنتاج الصورة من قسم Metal في سلسلة Ray Tracing in One Weekend. ونُشر الكود على GitHub باسم mTvare6/rayfuck.

ثماني تعليمات وشريط واحد

توفر Brainfuck ثماني عمليات وبنية بيانات واحدة: شريط لا نهائي من الخلايا، تحتفظ كل خلية ببايت واحد غير مُوقَّع. لا يوجد سجل أوسع من خلية واحدة، ولا تعليمة تمس خليتين معًا، والجمع والضرب ليسا تعليمتين. لذلك كُدِّرت الأعداد الحقيقية يدويًا: تشغل كل قيمة أربع خلايا بصيغة النقطة الثابتة Q16.16 المُوقَّعة، 16 بتًا للجزء الصحيح و16 للكسر، أي دقة 1/2^16 ونطاق يقارب [-2^15, 2^15). واستُبعدت صيغة Q8.8 كضيّقة جدًا، لأن الكرة التي تؤدي دور الأرض تحتاج نصف قطر 1000 لتبدو مسطحة.

بناء الحساب من الصفر

لم تُكتب 23 ميغابايت من Brainfuck يدويًا: يُحوَّل البرنامج إلى صيغة شبيهة بـ SSA ثم يُفكَّك إلى DSL وسيط صغير يضم نحو ثلاثين عملية مثل copy و mul و sqrt و if و while. وتؤدي عمليتان أساسيتان معظم العمل: move ([->+<]) تنقل قيمة خلية إلى جارتها، و copy ([->+>+<<]). الضرب جمع متكرر على الخلايا الأربع، والقسمة تتبع طريقة القسمة المطولة بالأساس 256: يُطرح المقسوم عليه 255 مرة على الأكثر لكل خلية.

كما أُعيد بناء مكتبة الرياضيات من المكوّنات نفسها. تأتي الأعداد العشوائية من مولّد صغير: A = (5*A + 1) % 256، ودورته الكاملة البالغة 256 قيمة تكفي لأخذ العينات الفائقة في المشهد. وللجذر التربيعي استُبعدت طريقة هيرون بسبب القسمة، ولم تكن متسلسلة تايلور ملائمة تحت 0.305، فاستخدم الكاتب جذرًا بالقسمة المطولة.

بيكسل واحد في الدقيقة

يبلغ البرنامج النهائي 23MB، أي أكبر من الصورة التي يرسمها (نحو 0.9MB)، ويلاحظ الكاتب أن Brainfuck وسيلة ضغط سيئة. وتبلغ السرعة نحو 100 حساب شعاع في الدقيقة، أي بيكسل واحد في الدقيقة، لذا تستغرق صورة بحجم 400×225 نحو 62.5 يومًا على حاسوبه المحمول. وفي وقت الكتابة أُنجز 1229 بيكسلًا من نحو 90 ألفًا، ولم يختلف منها سوى 10 عن المرجع بلغة C، ومعظم الفروق بمقدار واحد.

وبعد تعليق في نقاش على Reddit يقترح أوليات fork/join، حسّن الكاتب بدلًا من ذلك مفسّر JIT وأبلغ عن تسريع كبير؛ أما العرض الفعلي فهو، بحسب قوله، يشبه لوحة لفان غوخ، على الأرجح بسبب أخطاء الدقة.