خب رفقا، اگه با موضوع برنامه‌سازی خودکار یا همون Program Synthesis آشنایید، حتما می‌دونید که یکی از بزرگترین دردسرهاش اینه که اونقدر فضای جستجو برای برنامه‌هایی که ممکنه تولید بشن زیاد و بزرگه که آدم واقعاً گیج میشه! یعنی عملاً باید توی یه دنیای بزرگ برنامه‌های احتمالی بچرخی تا اون یکی که به دردت می‌خوره رو پیدا کنی. این خودش کلی زمان و انرژی می‌بره.
برنامه‌سازی خودکار یا Program Synthesis یعنی این که یه سیستم بتونه خودش کد بنویسه بر اساس یه سری مثال یا خواسته‌هایی که بهش میدیم. حالا یه مشکلی که پیش میاد، اینه که تعداد برنامه‌های ممکن خیلی وحشتناکه؛ یه داستان کاملاً ترکیبیاتی یا اصطلاحاً Combinatorial Search (که یعنی باید بین کلی حالت مختلف بگردیم). معمولاً بچه‌های این حوزه سراغ یه چیزی میان به اسم Combinatorial Constraint Solvers. اینا یه جور ابزار هوشمندن که کمک می‌کنن همه حالت‌های اضافی و مزاحم رو حذف کنی و متمرکز شی روی راه‌حل‌های درست.
تا امروز از Constraint یا همون محدودیت، فقط برای مشخص کردن معنی برنامه استفاده می‌کردیم، ولی به عنوان یه ابزار برای حذف برنامه‌های بد خیلی جدی نگاه نمی‌شد. جدیداً اما یه رویکرد جدید اومده به اسم Inductive Logic Programming (برنامه‌نویسی منطقی استقرایی)، که میگه بیاید روی «ساختار برنامه» هم محدودیت بذاریم، نه فقط روی معنی یا کارکردش! این محدودیت‌های ساختاری یا Syntactic Constraints یه ویژگی جالب دارن؛ قبل از اینکه برنامه رو اجرا کنیم میشه فهمید فلان خط کد مجازه یا نه، حالا چه از هر اپراتوری بخوای استفاده کنی. یعنی بدون اجرای کد کلی چیز رو میشه رد یا قبول کرد.
تو این مقاله، نویسنده اومده گفته بیاید همین محدودیت‌های ساختاری رو جوری مدل کنیم که نه فقط برنامه‌هایی که جواب میدن رو بسازیم، بلکه اونایی که واقعاً به درد می‌خورن رو هم جدا کنیم. برای نشون دادن این ایده هم یه ابزار جدید ساختن به اسم BART. این BART یه Solver باحاله که خیلی سریع این محدودیت‌ها رو هم بررسی و هم حل می‌کنه.
وقتی این روش رو روی کارهایی مثل “شمردن تعداد برنامه‌های ممکن” یا به اصطلاح Program Space Enumeration امتحان کردن، دیدن که با این محدودیت‌ها تقریباً تا ۹۹٪ (!) از فضای برنامه‌ها حذف میشه. یعنی یه عالمه برنامه عجیب و بی‌ربط حذف میشن و فقط اونایی که به احتمال زیاد جواب میدن می‌مونن. همچنین، مدل کردن صحیح فضای برنامه‌ها باعث شد زمان پیدا کردن جواب خیلی بیاد پایین.
خلاصه اگه دوست دارید سیستم‌های برنامه‌ساز هوشمند و سریع داشته باشید که فقط راه‌حل‌های به درد بخور رو بیارن و وقتتون رو با گزینه‌های عجیب غریب تلف نکنن، این داستان محدودیت‌های ساختاری و مدل‌سازی فضای برنامه‌ها چیزیه که حتماً باید جدی بگیرید.
منبع: +
