يسعدني جدًا أن أعلن عن إتمام برنامج التحويل البرمجي الأول للغة برمجة! Malcc عبارة عن مترجم Lisp AOT إضافي مكتوب بلغة C.

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

(في النهاية هناك TL ؛ DR ، إذا كنت لا تهتم بالخلفية).

عرض مترجم

tim ~/pp/malcc master 0 → ./malcc Mal [malcc] user> (println "hello world") hello world nil user> (+ 1 2) 3 user> (def! fib2 (fn* (n) (let* (f (fn* (n1 n2 c) (if (= cn) n2 (f n2 (+ n1 n2) (+ c 1))))) (f 0 1 1)))) <lambda> user> (fib2 25) 75025 user> ^D% tim ~/pp/malcc master 0 → ./malcc examples/hello.mal hello world tim ~/pp/malcc master 0 → ./malcc --compile examples/hello.mal hello gcc -g -I ./tinycc -I . -o hello hello.c ./reader.c ./printer.c ./hashmap.c ./types.c ./util.c ./env.c ./core.c ./tinycc/libtcc.a -ledit -lgc -lpcre -ldl tim ~/pp/malcc master 0 → ./hello hello world tim ~/pp/malcc master 0 → 

إخفاقات ناجحة

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

ولكن ما زلت حاولت ودرس على طول الطريق!

أولا ، المترجم

في عام 2011 ، بدأت العمل على مترجم بسيط للغة الخيالية Airball (يمكن ترجمة الكرة الطائرة كـ "muff"). بالاسم ، يمكنك تقييم درجة عدم اليقين من أنها ستنجح. كان برنامج Ruby بسيطًا إلى حد ما قام بتحليل التعليمات البرمجية ومشى عبر شجرة بناء جملة مجردة (AST). عندما لا يزال المترجم يعمل ، قمت بإعادة تسميته ليديا وأعد كتابته إلى C لجعله أسرع.



أتذكر أن بناء جملة ليديا بدا ذكيا للغاية بالنسبة لي! ما زلت أستمتع ببساطته.

على الرغم من أن ليديا كانت بعيدة عن المترجم المثالي ، إلا أنها ألهمتني لمواصلة التجريب. ومع ذلك ، ما زلت معذبة من الأسئلة ، وكيفية جعل المترجم يعمل: ما إلى ترجمة في؟ هل أحتاج إلى تعلم المجمّع؟

ثانيا ، المترجم bytecode والمترجم

كخطوة تالية ، في عام 2014 ، بدأت العمل على نظام vm ، وهو جهاز افتراضي لبرنامج Scheme كتب بالروبي. اعتقدت أن الجهاز الظاهري مع مكدسه ورمزه الجانبي سيكون مرحلة انتقالية من مترجم مع AST يمر ومترجم كامل. ونظرًا لتعريف " المخطط" رسميًا ، فلا حاجة إلى اختراع أي شيء.

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

بحلول نهاية عام 2017 ، قمت بإلغاء مخطط vm بحثًا عن شيء أفضل.

لقاء مع مال

في وقت ما في عام 2018 ، صادفت Mal ، وهو مترجم شفوي على طراز Clojure.

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

اعتقدت أيضًا أنه إذا تمكنت من كتابة مترجم فوري لـ Mal ، يمكنني تكرار نفس الخطوات - وإنشاء مترجم لـ Mal.

مترجم مالي على الصدأ

أولاً ، بدأت في تطوير المترجم الشفوي وفقًا للمطابقة . في ذلك الوقت ، كنت أدرس بنشاط راست (سأتركه لمقال آخر) ، لذلك كتبت تنفيذي الخاص بـ Mal in Rust: mal-rust . انظر هنا لمزيد من المعلومات حول هذه التجربة.

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

قرب نهاية البرنامج التعليمي ، تمكنت من تشغيل تطبيق Mal الخاص بي الخاص بـ Mal ، والذي تم كتابته في Mal ، بالإضافة إلى تنفيذ Rust. (مستويين من العمق ، واو). عندما عملت لأول مرة ، قفزت على الكرسي بإثارة!

مترجم مال جيم

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

رأيت المجمع x86 مكتوب في روبي. لقد أثار اهتمامي ، لكن فكرة العمل مع المجمّع جعلني أتوقف.

عند نقطة ما ، تعثرت على هذا التعليق على Hacker News ، والذي أشار إلى Tiny C Compiler على أنه "واجهة تجميع". بدا الأمر وكأنه فكرة رائعة!

لدى TinyCC ملف اختبار يوضح كيفية استخدام libtcc في ترجمة رمز C. من برنامج C. هذه هي نقطة البداية لـ "hello world".

بالعودة مرة أخرى إلى تجول Mal ، مع التذكير بمعرفتي بـ C ، خلال شهرين من الأمسيات المجانية وعطلات نهاية الأسبوع ، تمكنت من كتابة مترجم Mal. كان من دواعي سروري الحقيقي.



إذا كنت معتادًا على التطوير من خلال الاختبار ، فقم بتقييم مدى توفر مجموعة أولية من الاختبارات. الاختبارات تؤدي إلى تنفيذ العمل.

لا أستطيع أن أقول الكثير عن هذه العملية ، ما لم أكرر: دليل Mal هو كنز حقيقي. في كل خطوة ، كنت أعرف بالضبط ما يجب القيام به!

الصعوبات

إذا نظرنا إلى الوراء ، إليك بعض الصعوبات عند كتابة برنامج التحويل البرمجي Mal ، حيث اضطررت إلى العبث:

1. يجب أن تترجم وحدات الماكرو على الطاير وتكون جاهزة للتنفيذ في وقت الترجمة. هذا محير بعض الشيء.
   
2. من الضروري توفير "بيئة" (شجرة من التجزئة / المصفوفات / القواميس الترابطية مع المتغيرات وقيمها) لكل من رمز المترجم والرمز النهائي للبرنامج المترجم. يسمح لك هذا بتعريف وحدات الماكرو في وقت الترجمة.
   
3. نظرًا لأن البيئة متاحة في وقت التحويل البرمجي ، فقد اكتشف Malcc في البداية أخطاء غير محددة أثناء التحويل البرمجي (الوصول إلى متغير لم يتم تعريفه) ، وهذا في بعض الأماكن انتهك توقعات مجموعة الاختبار. في النهاية ، لاجتياز الاختبارات ، قمت بإيقاف تشغيل هذه الميزة. سيكون من الرائع إضافته مرة أخرى كعلم إضافي للمترجم ، حيث يمكنك بهذه الطريقة اكتشاف الكثير من الأخطاء مقدمًا.
4. قمت بتجميع كود C عن طريق الكتابة في ثلاثة أسطر من البنية:
   • top : رمز المستوى الأعلى - وهنا هي وظائف
   • decl : إعلان وتهيئة المتغيرات المستخدمة في الجسم
   • body : الجسم حيث يتم العمل الرئيسي
5. تساءلت طوال اليوم عما إذا كان بإمكاني كتابة جامع القمامة الخاص بي ، لكنني قررت ترك هذا التمرين لوقت لاحق. مكتبة Boehm-Demers-Weiser لجمع القمامة سهلة الاتصال ومتاحة على العديد من المنصات.
   
6. من المهم أن ننظر إلى التعليمات البرمجية التي يكتبها المترجم الخاص بك. كلما واجه المترجم متغير بيئة DEBUG ، فقد قام بإرجاع رمز C مترجم حيث يمكن عرض الأخطاء.

ماذا أفعل خلاف ذلك

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

الآن النصيحة

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

ولكن هذا لا يعني أنني "انتهيت". لا يزال هناك المئات من الأساليب والأدوات التي تحتاج إلى تعلمها لتشعر بأنها مؤلف مترجم حقيقي. لكنني أستطيع أن أقول بثقة: "لقد فعلت ذلك".

هنا العملية برمتها في شكل موجز ، وكيفية جعل مترجم Lisp الخاص بك:

1. اختر اللغة التي تشعر بالراحة بها. أنت لا تريد أن تتعلم لغة جديدة في وقت واحد وكيفية كتابة لغة جديدة أخرى.
   
2. باتباع دليل Mal ، اكتب مترجمًا فوريًا.
   
3. افرحوا!
   
4. اتبع التعليمات مرة أخرى ، ولكن بدلاً من تنفيذ التعليمات البرمجية ، اكتب التعليمات البرمجية التي تنفذ التعليمات البرمجية. (ليس فقط "إعادة بيع" المترجم الفوري الحالي. أنت بحاجة إلى البدء من نقطة الصفر ، على الرغم من أن نسخ النسخ غير محظور).

أعتقد أنه يمكن استخدام هذه الطريقة مع أي لغة برمجة تجمع إلى ملف قابل للتنفيذ. على سبيل المثال ، يمكنك:

1. اكتب مترجم Mal في Go .
2. تعديل الرمز الخاص بك إلى:
   
   • إنشاء سطر من Go code وكتابته إلى ملف ؛
   • ترجمة هذا الملف الناتج مع go build .

من الناحية المثالية ، من الأفضل التحكم في برنامج التحويل البرمجي Go كمكتبة ، لكن هذه أيضًا طريقة لإنشاء برنامج التحويل البرمجي!

بمساعدة دليل Mal وإبداعك ، يمكنك القيام بكل هذا. حتى لو استطعت ، ثم يمكنك!