وقتی یک زبان خودش را می‌سازد: درون کامپایلر خودمیزبان زبان برنامه‌نویسی سلام

کامپایلر خودمیزبان (Self-Hosting Compiler) کامپایلری است که به همان زبانی نوشته شده که کامپایل می‌کند. کامپایلر زبان برنامه‌نویسی سلام چنین کامپایلری است: کد منبعش حدود ۳۴۰ فایل سلام در پوشه‌ی compiler/ است و هر نسخه‌ی منتشرشده از اوت ۲۰۲۶ به این سو را یک فایل اجرایی salam قدیمی‌تر کامپایل کرده است. رسیدن به این نقطه به بوت‌استرپ کردن کامپایلر (Bootstrapping) نیاز داشت: یک پیاده‌سازی قدیمی‌تر به زبان C نخستین نسخه‌ی سلامیِ کامپایلر را کامپایل کرد و آن پیاده‌سازی C در ۲۰ اوت ۲۰۲۶ از مخزن حذف شد. این مقاله توضیح می‌دهد بوت‌استرپ به‌طور کلی چگونه کار می‌کند، سلام آن را چطور انجام داد، یک نسخه امروز چگونه ساخته می‌شود و چرا یک زبان جوان این دردسر را به جان می‌خرد.

«خودمیزبان» یعنی چه

یک زبان وقتی خودمیزبان است که کامپایلر (یا مفسر) خودش به همان زبان نوشته شده باشد و بتواند خودش را کامپایل کند. کامپایلرهای C مانند GCC و Clang به C و C++ نوشته شده‌اند. کامپایلر Go برای نسخه‌ی ۱٫۵ در ۲۰۱۵ از C به Go بازنویسی شد. نخستین کامپایلر Rust به OCaml نوشته شده بود و در ۲۰۱۱ جایش را به کامپایلری به زبان Rust داد. Zig چند سال صرف کرد تا کامپایلر C++ خود را با کامپایلری به زبان Zig جایگزین کند. خودمیزبانی یک نقطه‌ی عطف است، نه یک الزام: بسیاری از زبان‌های خوب، از جمله پیاده‌سازی مرجع پایتون، به زبان دیگری پیاده‌سازی شده‌اند.

اما برای یک زبان سیستمی کامپایلی، این ادعای محکمی است. یک کامپایلر تقریباً همه‌ی قابلیت‌های زبان را به کار می‌گیرد: ساختار و جداشمار برای درخت نحو، نگاشت درهم برای جدول نمادها، رشته و یونیکد برای متن منبع، فایل و فرایند برای ساخت، مدیریت دقیق حافظه در همه جا، و حجم زیادی کد. اگر زبانی نتواند کامپایلر خودش را از پس بربیاید، احتمالاً برای برنامه‌های بزرگ دیگر هم آماده نیست.

معمای مرغ و تخم‌مرغِ بوت‌استرپ

معمای آشکاری وجود دارد. برای کامپایل کامپایلری که به سلام نوشته شده، به یک کامپایلر سلام نیاز دارید. نخستین کامپایلر از کجا می‌آید؟

پاسخ کلی که بوت‌استرپ نام دارد سه گام دارد:

1. نخستین کامپایلر را به یک زبان موجود بنویسید. کامپایلری که کامپایلر امروز سلام را بوت‌استرپ کرد به C نوشته شده بود.
2. کامپایلر دومی برای همان زبان، به خود زبان تازه، بنویسید و آن را با کامپایلر نخست کامپایل کنید. حالا کامپایلری کارا دارید که از کد منبع سلام ساخته شده است.
3. با همین کامپایلر، کد منبع خودش را دوباره کامپایل کنید. از این‌جا به بعد پیاده‌سازی قدیمی دیگر لازم نیست، چون هر نسخه‌ی تازه را نسخه‌ی پیشین کامپایل می‌کند.

کامپایلری که یک ساخت را آغاز می‌کند بذر (Seed) نامیده می‌شود. پس از گام ۳، بذر هر ساخت به‌سادگی یک نسخه‌ی منتشرشده‌ی قبلی است. هزینه‌اش این است که دیگر نمی‌توانید کامپایلر را فقط از کد منبع بسازید: همیشه اول به یک فایل اجرایی کارا از همان زبان نیاز دارید. اسکریپت ساخت سلام وقتی بذری روی دستگاه نباشد همین را صریح می‌گوید:

error: no seed compiler on PATH.
  The compiler is written in Salam, so building it needs a Salam.
  Install a released one:  sh install.sh

مسیر زبان برنامه‌نویسی سلام از C به سلام

تاریخچه‌ی مخزن به ژوئن ۲۰۱۸ برمی‌گردد و چند پیاده‌سازی قدیمی‌تر را در بر دارد. تا تابستان ۲۰۲۶ کامپایلر یک برنامه‌ی C بود که آخرین شکلش در c/src/ قرار داشت: تحلیلگر واژگانی، تجزیه‌گر، تحلیل معنایی، تولیدکننده‌ی کد C، پشتوانه‌ی LLVM، مفسر، پشتوانه‌ی جاوااسکریپت و ابزارهای پیرامونشان. انتقال به سلام در تابستان ۲۰۲۶ انجام شد و git log تاریخ نقطه‌های عطف را نشان می‌دهد:

در لحظه‌ی جابه‌جایی، نسخه‌ی سلامیِ کامپایلر ۱۶۴ فایل و حدود ۶۴٬۹۰۰ خط بود، تقریباً هم‌اندازه‌ی برنامه‌ی C که جایش را گرفت. از آن زمان سه برابر شده و به نزدیک ۲۰۰٬۰۰۰ خط رسیده است، و بزرگ‌ترین افزوده‌ها (تولیدکننده‌ی کد بومی، پیونددهنده، تحلیل‌های مالکیت و بازه) از همان آغاز به سلام نوشته شدند. این بخش‌ها هیچ‌گاه نسخه‌ی C نداشتند.

کامپایلر سلام ساختار کامپایلر C را بازتاب می‌دهد: همان زنجیره‌ی منبع، تحلیلگر واژگانی، توکن‌ها، تجزیه‌گر، AST، تحلیل معنایی و تولید کد. راهنمای انتقال کد در مخزن روش کار را شرح می‌دهد: بخش به بخش و به ترتیب وابستگی منتقل کنید، ساخت C را قابل اجرا نگه دارید و هر مرحله را با آن مقایسه کنید. کدهای C حذف‌شده هنوز در تاریخچه‌ی Git هستند و همچنان مرجع طراحی مفیدی‌اند.

درستی انتقال چگونه بررسی شد

بازنویسی یک کامپایلر فقط وقتی به درد می‌خورد که کامپایلر تازه برنامه‌ها را همان‌طور کامپایل کند که کامپایلر قدیمی. بررسی‌هایی که اینجا به کار رفت ارزش شناختن دارند، چون برای هر انتقال کدی کاربرد دارند:

• هر مرحله را مقایسه کنید، نه فقط خروجی نهایی را. هر دو کامپایلر می‌توانند توکن‌ها، درخت نحو و جدول نمادهایشان را به شکل XML چاپ کنند (salam inspect --emit-tokens، --emit-ast، --emit-symbol) و راهنمای انتقال در مخزن (SKILL.md) توصیه می‌کند هر مرحله‌ی منتقل‌شده با همین خروجی از کامپایلر مرجع راستی‌آزمایی شود.
• کل مجموعه‌ی آزمون را با هر دو اجرا کنید. فایل docs/LLVM_DEFAULT_BACKEND.md یکی از این اجراها را از آن دوره ثبت کرده است: همان ۸۰۲ فایل آزمون که از پشتوانه‌ی LLVM کامپایلر C و کامپایلر خودمیزبان گذشتند، برای هر دو ۶۷۵ موفقیت، صفر شکست در تولید کد و ۱۲۷ آزمونِ خطای مورد انتظار داشتند، و هیچ فایلی نتیجه‌ی متفاوت نداشت.
• برنامه‌های واقعی را اجرا کنید و خروجی‌شان را بایت به بایت مقایسه کنید. ۷۳ برنامه‌ی tests/en/llvm/ ساخته و اجرا می‌شوند و خروجی‌شان با فایل‌های خروجی مورد انتظار مقایسه می‌شود، و هر دو کامپایلر هر ۷۳ برنامه را گذراندند.
• یک دروازه‌ی برابری نگه دارید. compiler/tools/bash/selfhost-parity.sh همان مجموعه‌ی آزمون‌ها را با یک کامپایلر مرجع و با کامپایلر خودمیزبان اجرا می‌کند و اگر کامپایلر خودمیزبان، فراتر از سهمیه‌ی کوچکی که برای هر مجموعه در مخزن ثبت شده، در آزمون‌های بیشتری از مرجع شکست بخورد، شکست می‌خورد.

امروز پوشه‌ی tests/ حدود ۴٬۳۰۰ فایل سلام انگلیسی و ۲٬۷۰۰ فایل سلام فارسی دارد و هر تغییری در کامپایلر با آن‌ها آزموده می‌شود.

یک نسخه‌ی زبان برنامه‌نویسی سلام امروز چگونه ساخته می‌شود

دو اسکریپت در مخزن این کار را انجام می‌دهند.

tools/bash/build-selfhost.sh ساخت یک‌مرحله‌ای است: یک بذر بردار (salamی که در PATH است، یا در CI تازه‌ترین نسخه‌ی منتشرشده) و compiler/main.salam را با آن کامپایل کن. وقتی نتیجه باید LLVM، lld و سیسروت‌های (Sysroot) کامپایل متقابل را در خود داشته باشد، اسکریپت اول با بذر یک کامپایلر ساده می‌سازد و بعد با همان کامپایلر نسخه‌ی نهایی را می‌سازد، تا فایل اجرایی نهایی را کامپایلری کامپایل کرده باشد که از کد منبع فعلی ساخته شده است.

compiler/tools/bash/bootstrap.sh همان بوت‌استرپ سه‌مرحله‌ای کلاسیک است:

sh compiler/tools/bash/bootstrap.sh "$(command -v salam)" build/selfhost

1. مرحله‌ی ۱: بذر کد منبع فعلی را کامپایل می‌کند. نتیجه کد تازه‌ای است که کامپایلر قدیمی کامپایلش کرده.
2. مرحله‌ی ۲: مرحله‌ی ۱ همان کد منبع را کامپایل می‌کند. حالا کد تازه را کامپایلر تازه کامپایل کرده است.
3. مرحله‌ی ۳: مرحله‌ی ۲ کد منبع را یک بار دیگر کامپایل می‌کند.

سپس نوبت بررسی نقطه‌ی ثابت (Fixpoint) است: مرحله‌ی ۲ و مرحله‌ی ۳ را منطق کامپایلری یکسان از کد منبعی یکسان ساخته، پس باید بایت به بایت یکسان باشند. اگر یکسان باشند، اسکریپت چاپ می‌کند identical - bootstrap has reached a fixpoint.. اگر نباشند، به جای شکست یک هشدار چاپ می‌کند، چون ترتیب پیوند و بهینه‌سازی زمان پیوند لزوماً تکرارپذیر نیستند؛ اما تفاوتی که روی یک دستگاه پابرجا بماند نشانه‌ای است که ارزش بررسی دارد.

پشتوانه‌ی بومی هم خودآزمونی از همین نوع دارد: LLVM IR کامپایلر را با salam llvm compiler/main.salam بیرون بکشید، آن IR را با پشتوانه‌ی بومی بسازید و از کامپایلرِ حاصل بخواهید دوباره IR را تولید کند. دو فایل باید جز در برچسب زمانی ساخت یکسان باشند.

برای چشیدن طعم کار، این نمونه‌ای از جنس کدی است که کامپایلر از آن ساخته شده: یک توکن‌ساز کوچک که یک عبارت حسابی را به توکن‌ها می‌بُرد، همان کاری که مرحله‌ی نخست تحلیلگر واژگانی واقعی می‌کند، به زبان سلام معمولی و این بار به فارسی. مانند تحلیلگر واقعی، رقم فارسی و لاتین را با هم می‌پذیرد:

جداشمار دسته: عدد، عملگر، فاصله، ناشناخته پایان

تابع دسته‌ی نویسه(ن: رشته): دسته:
    اگر "0123456789۰۱۲۳۴۵۶۷۸۹".دربردارد(ن):
        برگشت دسته.عدد
    پایان
    اگر "+-*/".دربردارد(ن):
        برگشت دسته.عملگر
    پایان
    اگر ن == " ":
        برگشت دسته.فاصله
    پایان
    برگشت دسته.ناشناخته
پایان

تابع ریشه:
    منبع := "۱۲ + 3 * ۴۵"
    ناپایا رقم‌ها := ""
    ناپایا توکن‌ها := وکتور {} برگردان وکتور<رشته>
    دیرکن توکن‌ها.آزادکن()
    هر ن در منبع + " ":
        د := دسته‌ی نویسه(ن)
        اگر د == دسته.عدد:
            رقم‌ها += ن
            گذر
        پایان
        اگر رقم‌ها != "":
            توکن‌ها.بیفزا("عدد " + رقم‌ها)
            رقم‌ها = ""
        پایان
        اگر د == دسته.عملگر:
            توکن‌ها.بیفزا("عملگر " + ن)
        پایان
    پایان
    هر ت در توکن‌ها:
        سرچاپ ت
    پایان
پایان

تحلیلگر واژگانی واقعی همین ایده است با موردهای بسیار بیشتر: رقم‌های فارسی، نام‌های چندواژه‌ای، رشته‌های خام، بلوک‌های متنی و واژه‌های کلیدی دو زبان. مقاله‌ی مراحل کامپایلر نشان می‌دهد پس از آن چه بر سر توکن‌ها می‌آید.

چرا خودمیزبانی برای یک زبان جوان مهم است

دلیل‌های خودمیزبانی عملی‌اند، نه نمادین.

کامپایلر بزرگ‌ترین برنامه‌ی آزمون است. کامپایلر با نزدیک به ۲۰۰٬۰۰۰ خط، با فاصله بزرگ‌ترین برنامه‌ی سلامی است که وجود دارد و مدیریت حافظه و بررسی‌های ایستای زبان را بیش از هر چیز دیگری به چالش می‌کشد. هر مسیر کند، هر نشت حافظه و هر قابلیت کم‌وکسر زبان اول آنجا خودش را نشان می‌دهد، و کسانی که می‌توانند درستش کنند همان‌هایی‌اند که به آن برخورده‌اند. چند قابلیت زیر همین فشار شکل گرفته‌اند: عملگرهای بیتی، که کد کامپایلر همه جا به آن‌ها نیاز دارد؛ بلوک‌های متنی، که برای نوشتن C و LLVM IR تولیدشده طراحی شدند؛ و وارسی‌گر مالکیت، که هشدارهای سخت‌گیرانه‌ترش فقط وقتی پیش‌فرض شدند که روی compiler/، std/ و برنامه‌های آزمون هیچ چیزی گزارش نکردند.

بهینه‌سازی‌ها دو بار سود می‌دهند. وقتی تولیدکننده‌ی کد بهتر می‌شود، کامپایلری که همراهش منتشر می‌شود هم سریع‌تر می‌شود. وقتی کار روی مالکیت به آزاد کردن رشته‌های دوباره‌مقداردهی‌شده رسید، اوج مصرف حافظه‌ی کامپایل خودِ کامپایلر به C از ۱٬۰۳۷ مگابایت به ۸۵۴ مگابایت رسید؛ این عدد در docs/design/OWNERSHIP.md ثبت شده است.

مشارکت‌کنندگان یک زبان لازم دارند. یک برنامه‌نویس سلام می‌تواند کامپایلر سلام را بدون دانستن C بخواند و تغییر دهد. برای زبانی که می‌خواهد ابزار آموزشی هم باشد، یک کامپایلر باز که به همان زبانِ در حال آموزش نوشته شده دارایی بزرگی است: دانشجویی که دوره‌ی آموزشی را تمام می‌کند می‌تواند کامپایلری را بخواند که برنامه‌هایش را اجرا می‌کند.

پشتوانه‌ها یکدیگر را می‌آزمایند. کامپایلر را می‌توان از راه پشتوانه‌ی C، پشتوانه‌ی LLVM و پشتوانه‌ی بومی ساخت. یک باگ در یکی از تولیدکننده‌های کد معمولاً به این شکل ظاهر می‌شود که کامپایلرِ ساخته‌شده با آن رفتاری متفاوت از کامپایلرِ ساخته‌شده با دیگری دارد. مقاله‌ی سه راه برای تولید کد این سه را شرح می‌دهد.

اعتماد به اعتماد: آیا می‌توان به کامپایلری که خودش را کامپایل کرده اعتماد کرد؟

کن تامپسون در سخنرانی جایزه‌ی تورینگ خود در ۱۹۸۴ با عنوان «Reflections on Trusting Trust» کامپایلری را توصیف کرد که در برنامه‌هایی که کامپایل می‌کند در پشتی می‌گذارد و همین رفتار را در هر نسخه‌ی تازه از خودش هم دوباره جاسازی می‌کند؛ به این ترتیب کد مخرب از کد منبع ناپدید می‌شود اما در همه‌ی فایل‌های اجرایی باقی می‌ماند. این استدلال کلاسیکی است که نشان می‌دهد خواندن کد منبع یک کامپایلر خودمیزبان، به‌تنهایی، چیزی را درباره‌ی فایل اجرایی ثابت نمی‌کند.

آنچه سلام در این زمینه دارد، بی‌پرده:

• کل زنجیره عمومی است. کامپایلر، اسکریپت‌های ساخت و گردش‌کارهای CI که نسخه‌ها را تولید می‌کنند در مخزن گیت‌هاب هستند، و پیاده‌سازی C که زنجیره از آن آغاز شد در تاریخچه‌ی آن قرار دارد.
• بررسی نقطه‌ی ثابت. بوت‌استرپ سه‌مرحله‌ای که به نقطه‌ی ثابت برسد نشان می‌دهد کامپایلر خودش را به‌طور سازگار کامپایل می‌کند. نشان نمی‌دهد که بذر پاک بوده است.
• تولیدکننده‌های کد مستقل. ساختن کامپایلر از راه C (با gcc یا clang به‌عنوان کامپایلر C)، از راه LLVM و از راه پشتوانه‌ی بومی، فایل‌های اجرایی‌ای می‌دهد که تولیدکننده‌های کد ماشینِ بی‌ارتباط با هم ساخته‌اند. این کار سازگار نگه داشتن یک محموله‌ی پنهان در یکی از آن‌ها را دشوارتر می‌کند، اما همه‌ی آن‌ها پیشانه‌ی سلام یکسان و بذر یکسانی دارند.

آنچه تا جایی که مخزن نشان می‌دهد انجام نشده، بررسی رسمی کامپایل دوگانه‌ی متنوع (Diverse Double-Compiling) است؛ روشی که دیوید ویلر (David A. Wheeler) برای پاسخ به حمله‌ی تامپسون پیشنهاد کرد و در آن کامپایلر با یک کامپایلر مستقلِ مورد اعتماد دوباره ساخته و نتیجه‌ها بیت به بیت مقایسه می‌شوند. پشتوانه‌های چندگانه‌ی سلام چنین آزمایشی را ممکن می‌کنند؛ اما نتیجه‌ای از آن منتشر نشده است.

هزینه‌های خودمیزبانی

خودمیزبانی رایگان نیست و هزینه‌هایش در مخزن سلام پیداست:

• نحو تازه یک نسخه منتظر می‌ماند. کامپایلر و کتابخانه‌ی استاندارد در CI با نسخه‌ی منتشرشده‌ی قبلی کامپایل می‌شوند، پس فقط می‌توانند از نحوی استفاده کنند که آن نسخه از قبل می‌فهمد. یک قابلیت اول به زبان می‌رسد و بعدها به کد منبع خود کامپایلر. یادداشت‌های طراحی پروژه ثبت کرده‌اند که در غیر این صورت چه می‌شود: نخستین مرحله‌ی بوت‌استرپ با یک خطای معنایی گمراه‌کننده شکست می‌خورد.
• بذرهای قدیمی از کار می‌افتند. bootstrap.sh برای بذرهای خیلی قدیمی راهنمایی‌هایی دارد، مانند نسخه‌های پیش از ۰٫۲٫۸ که نمی‌توانند .. را در مسیرهای واردسازی ساده کنند. build-selfhost.sh نسخه‌ی ۰٫۳٫۱ یا تازه‌تر می‌خواهد.
• ساختن کامپایلر حافظه‌ی واقعی لازم دارد. کامپایلری که از درخت فعلی ساخته شده برای تحلیل کد منبع خودش حدود ۱ گیگابایت حافظه لازم دارد. بذرهای مربوط به پیش از یک گذر تحلیل افزایشی حدود ۶ گیگابایت لازم داشتند، بیش از آنچه یک فرایند ۳۲ بیتی می‌تواند نشانی‌دهی کند؛ برای همین روی میزبان‌های ۳۲ بیتی مرحله‌ی بذر اکنون با بررسی‌های مالکیتِ خاموش اجرا می‌شود.
• باگ‌ها می‌توانند در بذر پنهان شوند. باگی در کامپایلر که بر چگونگی کامپایل خود کامپایلر هم اثر بگذارد ممکن است سخت دیده شود، چون کامپایلر معیوب همان فایل اجرایی‌ای را ساخته که با آن آزمون می‌کنید. مقایسه‌ی مرحله‌ها و پشتوانه‌ها راه دفاع است.

برای سلام این هزینه‌ها ارزش پرداختن دارند. زبان هنوز به نسخه‌ی ۱٫۰ نرسیده و میان نسخه‌ها تغییر می‌کند، پس نوشتن پرتوقع‌ترین برنامه‌اش به خود همین زبان طراحی را صادق نگه می‌دارد.

پرسش‌های پرتکرار

کامپایلر خودمیزبان چیست؟

کامپایلری است که به همان زبانی نوشته شده که کامپایل می‌کند و می‌تواند کد منبع خودش را کامپایل کند. GCC، Clang، کامپایلر Go، rustc و کامپایلر زبان سلام نمونه‌هایی از آن‌اند.

چگونه یک کامپایلر را بوت‌استرپ می‌کنند؟

نخستین کامپایلر را به یک زبان موجود بنویسید، با آن کامپایلر دومی را که به زبان تازه نوشته شده کامپایل کنید و بعد بگذارید آن کامپایلر خودش را کامپایل کند. از آن پس هر نسخه را نسخه‌ای قدیمی‌تر، یعنی بذر، می‌سازد. کامپایلری که کامپایلر امروز سلام را بوت‌استرپ کرد به C نوشته شده بود.

آیا می‌توان زبان سلام را بدون فایل اجرایی سلام از کد منبع ساخت؟

از درخت فعلی نه: به یک بذر نیاز دارید. یک کامپایلر منتشرشده را از صفحه‌ی نصب نصب کنید و sh tools/bash/build-selfhost.sh را اجرا کنید. در اصل می‌شود از پیاده‌سازی C در تاریخچه‌ی Git شروع کرد و نسخه به نسخه بالا آمد، اما راه درازی است و مخزن آن را مستند نکرده است.

آیا کامپایلر سلام به سلام فارسی نوشته شده یا انگلیسی؟

انگلیسی. کامپایلر هر دو شکل نوشتاری را پردازش می‌کند و کتابخانه‌ی استاندارد و پیام‌های کامپایلر به هر دو زبان وجود دارند، اما کد منبع خود کامپایلر از واژه‌های کلیدی انگلیسی استفاده می‌کند. مقاله‌ی یک زبان، دو خط رابطه‌ی این دو را توضیح می‌دهد.